Lack of Unique Factorisation as a Tool for Block Cipher Cryptanalysis

Speaker: Dr Nicolas T. Courtois, University College London
Date: 2019. 5. 27(Mon) 17:00 ~ 18:00
Location: Location : #206, Woojung Building

Nicolas Courtois is a Senior Lecturer at University College London, where he teaches about applied cryptography, cryptanalysis and computer security.
His research focuses on the security analysis of cryptographic systems with particular focus on realistic attack scenarios and systems used by millions of users every day. His Google Scholar profile lists 140+ papers with 8,400 citations in cryptography. His H-index is 37. A university team lead by Nicolas Courtois was given the UK University Cipher Champion in March 2013. He is a founding member of the group Code-Breakers at LinkedIn and a member of the editorial board of Cryptologia. Previously, he was a crypto research engineer at Gemalto, the world’s largest manufacturer of smart cards and secure hardware. The Courtois DarkSide attack on MiFare classic, which chip has been sold in
2 billion copies, allows to extract secret keys though a practical simultaneous differential card-only attack. He has filed more than ten patents on practical applications of cryptography. He is an expert on security engineering, electronic payment and crypto currency. His blog is blog.bettercrypto.com.


Linear cryptanalysis may seem a boring topic: they are about super simple invariants characterized by say a word on n=64 bits with very few bits at 1, the space of possible attacks is small, and basic principles are trivial. In contract mathematics offers an infinitely rich world of possibilities. If so, why is that cryptographers have ever found so few attacks on block ciphers? In this paper we argue that black-box methods used so far to find attacks in symmetric cryptography are inadequate and we work with a more recent white-box algebraic methodology. Invariant attacks can be constructed explicitly through the study of roots of the so-called Fundamental Equation (FE). We also argue that certain properties of the ring of Boolean polynomials such as lack of unique factorization allow for a certain type of product construction attacks to flourish. As a proof of concept we show how to construct a complex and non-trivial attack where a polynomial of degree 7 is an invariant for any number of rounds for a complex block cipher.