“Only those who attempt the absurd will achieve the impossible”.
—M. C. Escher
Cryptanalysis is about making the impossible possible, trying something very hard or which has never been done before. It is about finding rare or exceptionnal events, and being able to connect them together to form a working attack. Sometimes we do it just for fun, it is an academic sport where researchers compete against each other, and compare different methods. Most of the time it is done in order to evalaute the complexity of a potential attack, in order to enlighten crypto engineers about the impact of various technical choices they make.
Dr. Nicolas Courtois has extensive expertise in cryptanalysis and is a founding member of the group Code Breakers at LinkedIn. His team has won the UK University Cipher Challenge in March 2013. Many many years ago New Scientist wrote: “but Courtois isn’t going to apologize for opening this cryptographic can of worms” and put a title “cipher crisis” on the first page… He has introduced numerous innovations in particular regarding the usage and role played by algebraization and multivariate polynomials in cryptanalysis. Where most authors just see seeminlgy loosely connected specific events such as linear and differential properties which combine together, or some obscure Gröbner basis anomalies, or just lucky combinatorial events, Dr Courtois has developed an alternative far-reaching unified formal algebraic view of cryptanalysis, with polynomials, round invariants, the Fundamental Equation (FE), algebraic annihilation, absorption and other events. Most of these can be seen as fundamentally resulting from a small number of core observations: such as lack of unique factorization of polynomials over finite fields, and phase transitions on core fundamental problems which occur in the rich world of solving algebraic relations with multivariate polynomials. Most cryptanalytis attacks result from basic fundamentally natural and abundant events, their probabilities can be studied, and are sometimes surprisingly high.
Selected Slides and Resources About Cryptanalysis.
Recommended for UCL students taking COMP0058 course.
Classical Cryptanalysis resources:
- An elementary tutorial about how to backdoor a block cipher in a quite general setting. The method involves solving a certain system of equations in order to find unusal and strong properties.
- Success is not guaranteed though, see our tutorial paper.
- Here are slides presented at CECC 2019 (invited talk).
- Three more papers below provide additionnal explanations about WHY such attacks are AT ALL possible and explain the philosophy of cryptanalysis with invariant attacks:
- Nicolas T. Courtois:
Structural Nonlinear Invariant Attacks on T-310: Attacking Arbitrary Boolean Functions,
preprint available here, received 28 Dec 2018. - Nicolas T. Courtois, Aidan Patrick:
Lack of Unique Factorization as a Tool in Block Cipher Cryptanalysis,
preprint, submitted 12 May 2019. - Nicolas T. Courtois:
Invariant Hopping Attacks on Block Ciphers, presented at WCC2019, Saint-Jacut-de-la-Mer, France, 31st March – 5 April 2019. Here is the paper after it was accepted for presentation and revised. Here is a new extended version of it. Here are slides presented at WCC 2019.
- This paper is on the same topic but we look at yet more advanced attacks:
Nicolas T. Courtois, Jean-Jacques Quisquater:
Can a Differential Attack Work for an Arbitrarily Large Number of Rounds?
In ICISC 2020, pp. 157-181, LNCS 12593, Springer 2021, see here.
Here are slides presented in normal / extended version and here is the video of my presentation. - 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.
- Student exercises about breaking Enigma, updated March 2020.
- A paper Enigma simulator which helps to solve our exercises.
- A complete Enigma emulation.
- Our presentation at CECC 2020 conference: about weak Enigma rotors latin squares linear approximations and invariant differentials, by Nicolas Courtois and Marek Grajek, slides are avail. here.
- Here are some latest discoveries about Enigma rotors:
- On latin squares, invariant differentials, random permutations and historical Enigma rotors, in Cryptologia vol? 2022, published online 07 dec 2021, see here.
- Nicolas T. Courtois, Marek Grajek and Michal Rams:
On Weak Rotors, Latin Squares, Linear Algebraic Representations, Invariant Differentials and Cryptanalysis of Enigma, in Rad HAZU, Matemati\^{c}ke Znanosti, pp. 51-77,
a.k.a. post-proceedings of CECC 2020, conference took place in Zagreb, Croatia on June 24 – 26, 2020. (the initial title was different).
- 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.
Number Theory resources:
- Some lecture notes for UCL GA18 Cryptanalysis:
- Intro slides about, algebra finite fields and elliptic curves: groups and ECCs with exercises.
- [optional] algebra for cryptographers old basic intro slides.
- Intro slides to Number Theory by Christophe Petit in 2015-2016.
- Excellent slides about factoring and discrete log cryptanalysis by Christophe Petit in 2015-16.
- Most recent labs from 2020:
- LabF0 on installing SAGE, modular arithmetic and groups.
- Older labs on algebra, crypto, number theory, etc etc.
- Datasets produced by UCL students about prime numbers which are used twice on the Internet are available here.
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.
- Our latest instructions on installing SAGE. / older version [off-line only].
- We recommend this free book and online video tutorials about SAGE by Gregory Bard.
- Another simple tutorial on basic algebra and number theory in SAGE.
- 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.
- A paper written by our last year student is now published: Nicolas T. Courtois, Maria-Bristena Oprisanu:
- Ciphertext-only attacks and weak long-term keys in T-310, published in Cryptologia, pages 1-21, published online 08 Jan 2018, onlive version is available here. And here is a special link to access it for free [first-come first-served.]
- 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:
- Documents and software for running RowHammer RAM Fault attacks on commercial PCs [temporary versions will be updated]. Work by Varnavas Papaioannou done at UCL under supervision of Nicolas Courtois.
- Here is our UCL master thesis on RowHammer.
- Varnavas Papaioannou: On Feasibility and Performance of Rowhammmer Attack. M.Sc. Information Security dissertation, University College London. 4 September, 2017. Available here.
- Here is one recent updated version of our paper presented at ASHES on 3 nov 2017:
- Our tutorial:
- Varnavas Papaioannou: Rowhammer Tutorial, September 24, 2017. Available here.
- Our github: It should be cited as: Varnavas Papaioannou. User-Space Rowhammer Testing Tools, October 2017. It contains 0123:
- 0) it contains our patches to improve two third party tools (hammertime by Tatar 2016 and rowhammer-test by Dullien and Seaborn 2015).
- 1) a stand-alone tool hprh based on Transparent Huge Pages (THP) feature in Linux,
- 2) a stand-alone tool tcrh based on a timing channel and trying to identify possible targets that are mapped within the same RAM bank.
- 3) another stand-alone timing attack able to identify regions in memory that are physically contiguous.
- Here is our UCL master thesis on RowHammer.
- 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):
- Here is some basic documentation.
- Here are some pictures which explain how this works (from our lab).
- Here is the victim process project.
- Here is the attacker process project.
- 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.
Larger Selection of papers about cryptanalysis (mix of old and recent).
- Nicolas T. Courtois:
Structural Nonlinear Invariant Attacks on T-310: Attacking Arbitrary Boolean Functions,
preprint available here, received 28 Dec 2018. - Nicolas T. Courtois, Invariant Hopping Attacks on Block Ciphers, accepted at WCC2019, The Eleventh International Workshop on Coding and Cryptography, Saint-Jacut-de-la-Mer, France, from 31st March to 5 April 2019. Here is the paper accepted and revised. Here are slides presented at WCC 2019.
- Nicolas T. Courtois, Maria-Bristena Oprisanu:
Ciphertext-only attacks and weak long-term keys in T-310,
published in Cryptologia, pages 1-21, published online 08 Jan 2018, online version is available here.
And here is a special link to access it for free [first-come first-served.] - 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. - 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
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. - 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.
Pingback: UCL Code Breaking Competition Winners Announced | Financial Cryptography, Bitcoin, Crypto Currencies, Cryptanalysis