On Multiple Symmetric Fixed Points in GOST

Abstract

In this article the author revisits the oldest attack on GOST known, the Kara Reflection attack, and another totally unrelated truncated differential attack by Courtois and Misztal. It is hard to imagine that there could be any relationship between two so remote attacks which have nothing in common. However, there is one: Very surprisingly, both properties can be combined and lead the fastest attack on GOST ever found, which is nearly feasible to execute in practice.

Keywords:

• black-box reductions
• block ciphers
• differential cryptanalysis
• Feistel schemes
• fixed points
• GOST
• ISO 18033
• key scheduling
• low-data complexity
• multiple-key attacks
• reflection attacks
• self-similarity

Additional information

Notes on contributors

Nicolas Courtois

Nicolas T. Courtois is a cryptologist and a Senior Lecturer at University College London. He was born in Poland, received his PhD from the Paris 6 University, and then he worked as a cryptographic engineer for the French smart card industry. He is a highly influential code-breaker with more than 100 regular publications and more than 6000 citations. He has pioneered and/or achieved significant results in all of the following areas of cryptography: Design and analysis of new public key cryptosystems (Sflash, Quartz, HFE), generalized linear cryptanalysis of block ciphers (Crypto 2004), cryptanalysis of LFSR-based stream ciphers with and without additional memory (Eurocrypt 2003, Crypto 2004, ICISC 2004), efficient algorithms for solving systems of multivariate equations (Eurocrypt 2000), innovative attacks on block ciphers (Asiacrypt 2001, AES'4), alternatives to Grobner bases algorithms (Asiacrypt 2001, FSE 2012), low-data complexity cryptanalysis of block ciphers with SAT Solvers (IMA 2007), self-similarity attacks on block ciphers with black-box reductions (FSE 2008, Cryptologia 2012), advanced differential attacks (SECRYPT 2009), and importantly, in security analysis of major industrial standards and real life cryptographic algorithms used by hundreds of millions of people every day (E0 cipher in Bluetooth, automobile cipher KeeLoq, MiFare Classic Crypto-1 in contactless smart cards).