Recent years have shown that more than ever governments and intelligence agencies strive to control and bypass the cryptographic means used for the protection of data and communications. Backdooring encryption algorithms is considered as the best way to enforce cryptographic control. Until now, only implementation backdoors (at the protocol/implementation/management level) are generally considered. In this paper we propose to address the most critical issue of backdoors: mathematical backdoors or by-design backdoors, which are put directly at the mathematical design of the encryption algorithm. While the algorithm may be totally public, proving that there is a backdoor, identifying it and exploiting it, may be an intractable problem.
We intend to explain that it is possible to design and put such backdoors. Considering a particular family (among all the possible ones), we present BEA-1, a block cipher algorithm which is similar to the AES and which contains a mathematical backdoor enabling an operational and effective cryptanalysis. Without the knowledge of our backdoor, BEA-1 has successfully passed all the statistical tests and cryptographic analyses that NIST and NSA officially consider for cryptographic validation. In particular, the BEA-1 algorithm (80-bit block size, 120-bit key, 11 rounds) is designed to resist to linear and differential ctyptanalyses. Our algorithm has been made public in February 2017 and no one has proved that the backdoor is easily detectable and have shown how to exploit it.
In the second part of this talk, we reveal which backdoor has been built, how to exploit it thus allowing to recover the 120-bit key in around 10 secondes with only 600 kb of data (300 Kb of plaintexts + 300 Kb of corresponding ciphertexts). In the final part, we addressed other ideas which are worth considering to built more complex backdoors and we will outline the possible trends in this domain.