Selected Slides and Resources About Cryptanalysis.
Recommended for UCL students taking GA18/COMPM068 course.
Number Theory resources:
- Intro slides to Number Theory by Christophe Petit taught within GA18 Cryptanalysis course in 2015 and 2016.
- Intro slides about, algebra finite fields and elliptic curves: groups and ECCs,
- [optional] algebra for cryptographers old basic intro slides.
- Our Tutorial1 Number Theory and Basic Attacks from 2015/16.
- Excellent slides about factoring and discrete log cryptanalysis by Christophe Petit taught at UCL GA18 in 2015 and 2016.
- Our Tutorial 3 on Factorization by Jonathan Bootle.
- Our Tutorial on Index Calculus, by Mary Maller questions/ answer.
- Number theory labs we did at UCL in 2016:
Classical cryptanalysis resources:
- Enigma and Block Ciphers – 100 years of cryptanalysis with non-commutative combinations of permutations slides.
- Executive summary, all about how Enigma was broken during WW2 on 1 page, for UCL students.
- Slides about Data Encryption Standard (DES), its design and security, Linear and Differential Cryptanalysis (LC/DC), BLC, GLC and lots more.
- Some slides about Rijndael/AES and some more about finite fields and AES.
- All about AC = Algebraic Cryptanalysis, block and stream ciphers alike.
- New Frontier in Symmetric Cryptanalysis, slides from an invited talk by N. Courtois at Indocrypt 2008, 14-17 December 2008, slides are available here.
- Low Degree and Cube Attacks slides.
- A lab session for students about the ElimLin algorithm.
- 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.
- 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 extracti 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.
- Software, bitcoin and side channel 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):
- 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 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].
Larger Selection of papers about cryptanalysis (mix of old and recent).
- Nicolas T. Courtois: High Saturation Complete Graph Approach for EC Point Decomposition and ECDL Problem, preprint, 18 Jul 2016, cf. here.
Two software tools are needed to check the results of this paper: our ax64.exe program and our ec2decomp.exe program.
- 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.
- 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).
- 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.
- 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.
- Here is a long all-about-GOST presentation.
- 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.
- 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.
- 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.
- 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.
- Gregory Bard, Nicolas Courtois, Jorge Nakahara Jr, Pouyan Sepehrdad and
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.
- 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,
- Sophia Antipolis, French Riviera, with web proceedings (slides presented available here ).
- 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).
- Nicolas Courtois: The 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.
- 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 was 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/.
- 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.
- See also my(older) web page page about algebraic attacks on stream ciphers.