Cryptanalysis Ressources

Dr. Nicolas Courtois is a professional cryptanalyst and a founding member of the group Code Breakers at LinkedIn. His team has won the UK University Cipher Challenge in March 2013.

 

Selected Slides and Resources About Cryptanalysis.
Recommended for UCL students taking GA18/COMPM068 course.

Number Theory resources:

  1. Intro slides to Number Theory by Christophe Petit taught within GA18 Cryptanalysis course in 2015 and 2016.
  2. Intro slides about, algebra finite fields and elliptic curves: groups and ECCs,
  3. Most recent versions of GA18 Number Theory tutorials will be found in Section Teaching here, below some versions are older.
  4. Excellent slides about factoring and discrete log cryptanalysis by Christophe Petit taught at UCL GA18 in 2015 and 2016.
  5. Our Tutorial 3 on Factorization by Jonathan Bootle.
  6. Our Tutorial on Index Calculus, by Mary Maller questions/ answer.
  7. Number theory labs we did at UCL in 2016:
    • Lab1 Intro to SAGE
    • Lab3 Algorithmic Number Theory
    • Lab4 on DL Attacks
    • Lab5 on Factoring.

Classical cryptanalysis resources:

  1. Enigma and Block Ciphers – 100 years of cryptanalysis with non-commutative combinations of permutations slides.
  2. Executive summary, all about how Enigma was broken during WW2 on 1 page, for UCL students.
  3. Slides about Data Encryption Standard (DES), its design and security, Linear and Differential Cryptanalysis (LC/DC), BLC, GLC and lots more.
  4. Some slides about Rijndael/AES and some more about finite fields and AES.
  5. All about AC = Algebraic Cryptanalysis, block and stream ciphers alike.
  6. New Frontier in Symmetric Cryptanalysis, slides from an invited talk by N. Courtois at Indocrypt 2008, 14-17 December 2008, slides are available here.
  7. Low Degree and Cube Attacks slides.
  8. A lab session for students about the ElimLin algorithm.
  9. A tool for deep inspection of equations generated in ElimLin algorithm: here. Documentation is here.

Additional resources are available to UCL students in our Moodle GA18 space.

Software Tools for Cryptanalysis Which we Use in Research and Teaching:

  • SAGE software has a lot of code contributed by specialists in cryptanalysis. It is used at UCL GA18 labs.
  • NTL library has LLL implemented and quite a few number theory routines.
  • Tools for algebraic cryptanalysis of ciphers – web page by Courtois.
  • CryptoMiniSAT is an amazing tool by Mate Soos for solving systems of equations obtained in cryptanalysis available here. Here is our archive of older exe versions of it.
  • Three major methods to convert MQ to SAT are available in our software tools page inside our ax64.exe program.
    • One is LI=Local Interpolation or /nobard option in ax64.exe, used for example in this paper or on slide 40 here.
    • Another is BCJ=Bard-Courtois-Jefferson Java, or /bard option. This calls an indepndent stand-alone tool:
    • A ready program to convert systems of equations over GF(2) to SAT by Gregory Bard following this paper win Java under Windows cf. here. This implements BCJ converter tool, as described here. One research paper which is using this method is the following which breaks 79 rounds of KATAN32.
    • Finally when CryptoMiniSat is used, cf.  here, ax64.exe has a special converter routine with native XORs. This is obtained either with /soos option or by default if compatible solvers are used, for example with option /cryptominisat64291.
  • Experimental algebraic cryptanalysis of block ciphers – web page by Courtois.
  • Om Bhallamudi: Tool for Software Algebraic attacks on T-310 block cipher, see our codegen.py program. 
  • A tool for Differential Cryptanalysis (DC) for T-310 block cipher by Matteo Scarlata, here
  • Ax64 also contains some T-310 code.
  • See also this page about hard problems in algebraic cryptanalysis, cf. here.
  • We have constructed “easy start” systems with Visual Studio C/C++ GMP NTL secp256k1 OpenSSL and other libraries [+ready databases if needed] for students which do projects and labs in cryptanalysis.
  • Some integer factoring code: GNFS.
  • Software for extracting keys from contactless cards [building passes, university cards,older Oyster cards etc..] = Courtois Dark Side attack page and direct link to working implementation by Andrei Costin.
  • Bitcoin attacks and exploits:
    • A tool to crack bitcoin passwords at a high speed: brainflayer cracker by Ryan Castellucci with enhancements code contributed by Courtois and Song. Another similar project is adpwc project below.
    • HOW to crack bitcoin and LinkedIn passwords at home (easy starter project for UCL students and GA18 code breaking competition, by  Nicolas Courtois and Guangyan Song, windows PC only):
      • Here is our main Visual Studio 2010 project adpwc.
      • Two large files are needed at runtime for this project to run correctly:
        • Our Bitcoin bedb database file (database of historical bitcoin public keys).
        • Here is our LinkedIn unmasked passwords file.
        • Missing: cache file (0.5 Gb).
    • How to mine bitcoin data at a high speed (50 Mb/second): our UCL tutorial.
    • A tool to find repeated randoms in bitcoin blockchain by F. Valsorda: blockchainr [we also have developed other proprietary tools for this task].

Side Channel Attacks Section: More Tools for Cryptanalysis Which we Use in Research and Teaching:

  • HOW to implement a cache side channel attack (easy starter project for UCL students and GA18 code breaking competition, by Nicolas Courtois and Guangyan Song, windows PC only):
  • HOW to implement a HT/ALU side channel attack on a PC which focuses on public-key cryptography algorithms making intensive use of expensive arithmetic operations (another easy starter project for UCL students and GA18 code breaking competition, by Mateo Inchaurrandieta. See here.
  • Ask our about our Rowhmamer exploits with KALI Linux.

 

Larger Selection of papers about cryptanalysis (mix of old and recent).

  1. Nicolas T. Courtois: High Saturation Complete Graph Approach for EC Point Decomposition and ECDL Problem, preprint, 18 Jul 2016, cf. here.
    Brief review.
    Two software tools are needed to check the results of this paper: our ax64.exe program and our ec2decomp.exe program.
  2. Petr Susil, Pouyan Sepehrdad, Serge Vaudenay, Nicolas Courtois: 
    On selection of samples in algebraic attacks and a new technique to find hidden low degree equations
    ,
    Int. J. Inf. Sec. 15(1): 51-65 (2016).
    Here is the paper and here is an earlier version
  3. Nicolas Courtois: 
    An Improved Differential Attack on Full GOST
    ,
    in “The New Codebreakers — a Festschrift for David Kahn”, LNCS 9100, Springer, 2016, pp.282-303.
    This paper introduces the best single-key attack on GOST ever found (2^179)!
    The Springer version is a short 20-page version of a substantially longer paper: there is an older preprint (15 March 2012) and  a recent extended version of this paper (full version is 54 pages as of 17 December 2015).
  4. Nicolas Courtois: On Multiple Symmetric Fixed Points in GOST,
    In Cryptologia, Volume 39, Issue 4, 2015, pp. 322-334.
    Full version can be found here.
  5. Survey talk on cryptanalysis of GOST given in Edinburgh, part of workshop on Security of symmetric ciphers in network protocols, May 25, 2015 – May 29, 2015, ICMS, Edinburgh, UK. Here are slides presented.
  6. Here is a long all-about-GOST presentation.
  7. Here is an extended monography work on GOST Block cipher by N. Courtois: Algebraic Complexity Reduction and Cryptanalysis of GOST, 224 pages, 2010-2015, available here.
  8. Nicolas Courtois, Daniel Hulme, Kumail Hussain, Jerzy Gawinecki, Marek Grajek:
    On Bad Randomness and Cloning of Contactless Payment and Building Smart Cards, .
    In IWCC 2013, International Workshop on Cyber Crime, co-located with the 34th IEEE Symposium on Security and Privacy (IEEE S+P 2013) San Francisco, USA, 24 May 2013.
    Available at here  and here are the slides.
  9. Nicolas T. Courtois, Daniel Hulme, Theodosis Mourouzis:
    Multiplicative Complexity and Solving Generalized Brent Equations With SAT Solvers.
    In COMPUTATION TOOLS 2012,
    The Third International Conference on Computational Logics, Algebras, Programming, Tools, and Benchmarking,
    July 22-27, 2012 – Nice, France.
    Published in: conference, ISBN: 978-1-61208-222-6,
    Pages: 22 to 27, Copyright: Copyright (c) IARIA, 2012,
    Date: 22 July 2012, full paper vailable here.
    We have received the Best Paper Award.
    Here are extended slides by Courtois et al. about Multiplicative Complexity.
  10. Nicolas T. Courtois, Pouyan Sepherdad, Petr Susil and Serge Vaudenay:
    ElimLin Algorithm Revisited. In FSE 2012, LNCS 7549, pp. 306-325, Springer 2012. Can also be found here or here.
  11. Gregory Bard, Nicolas Courtois, Jorge Nakahara Jr, Pouyan Sepehrdad and
    Bingsheng Zhang:
    Algebraic, AIDA/Cube and Side Channel Analysis of KATAN Family of Block Ciphers. 
    In Indocrypt 2010, LNCS 6498, pp 176-196, Springer.
    See paper and another version and here are the slides.
  12. Nicolas T. Courtois, Keith Jackson and David Ware:  Fault-Algebraic Attacks on Inner Rounds of DES.  In eSmart 2010, European Smart Card Security Conference, 22-24 September 2010,
  13. Sophia Antipolis, French Riviera, with web proceedings (slides presented available here ).
  14. Card-only attacks on MiFare Crypto-1 cipher.Nicolas T. Courtois:
    The Dark Side of Security by Obscurity and Cloning MiFare Classic Rail and Building Passes Anywhere, Anytime , new attack requires only 300 queries to the card, appears in SECRYPT 2009 –
    International Conference on Security and Cryptography: 7-10 July 2009, Milan,
    Italy. Also known as “Courtois dark side” attack on MiFare Classic. Here are
    the slides).A version of this paper is available here.This paper concerns more than 1 billion of smart cards and compromises
    very heavily the security of thousands of buildings and several
    train/bus/parking payment systems in Europe and elsewhere (allowing for
    example unauthorized access to buildings, travel for free, free parking etc.).Other researchers also found other and  different card-only attacks on MiFare Classic but they are more than 10
    times more difficult to handle in terms of online time (more queries to the card, for example when standing or sitting next to the victim).
    The best practical attack currently known on MiFare Classic is actually a combination
    of our attack with 300 queries to find the first key (estimated time: 10
    seconds with Proxmark3), and the Nested Authentication attack from the Oakland paper
    to recover all the other keys (which is extremely fast).
  15. Nicolas CourtoisThe Security of Hidden Field Equations (HFE),
    Cryptographers’ Track Rsa Conference 2001
    ,
    LNCS 2020, pp. 266-281, Springer-Verlag.
    Donwload the paper hfesec.dvi / hfesec.ps / hfesec.pdf.
    The slides on HFE security from RSA2001:
    hfesecsl.dvi
    / hfesecsl.ps / hfesecsl.pdf.Comments: This paper describes a subexponential attack on HFE and is the best
    attack ever found on HFE and HFE Challenge
    At Crypto 2003 Joux and Faugère will explain why this attack works and improve it slightly.
    See also the “official” HFE cryptosystem home page.
  16. Nicolas Courtois, Gregory V. Bard and David Wagner:
    Algebraic and Slide Attacks on KeeLoq
    . This paper
    describes 1) the first successful algebraic attack in history on a full round
    real-life block cipher 2) the fastest attack ever found on KeeLoq. The
    complexity of the latter is about 2^28  KeeLoq encryptions on average, and can be even
    2^23 
    for a fraction of keys (see our next paper in preparation, not in FSE proceedings).
    The paper w
    as presented at Fast Software Encryption 2008, Lausanne, Switzerland, February
    10-13, 2008, and appears in LNCS Springer, 2008. It is the most highly cited paper in this Springer volume.
    Here are the slides.
    See also a VERY OLD version of the paper, NOT up-to-date at all: eprint/2007/062/.
  17. New Frontier in Symmetric Cryptanalysis,
    slides from an invited talk by N. Courtois at Indocrypt 2008,
    14-17 December 2008, slides are available here, and an older 2p version is here.
  18. See also my(older)  web page page about algebraic attacks on stream ciphers.

One Comment

  1. Pingback: UCL Code Breaking Competition Winners Announced | Financial Cryptography, Bitcoin, Crypto Currencies, Cryptanalysis

Leave a Reply

Your email address will not be published. Required fields are marked *