Can GOST Be Made Secure Against Differential Cryptanalysis?

Abstract

GOST is a well-known Russian government standard block cipher which was submitted to ISO in 2010 to become an international standard. A number of advanced differential attacks on GOST have been proposed including the best known single-key attack on GOST to date in 2¹⁷⁹ [14]. This attack, however, was designed for the oldest known set of GOST S-boxes hoping that similar attacks should exist for other versions of GOST. This claim was bitterly disputed by Russian researchers as recently as July 2012, who stated that “S-boxes heavily affect security” and “with ‘good’ S-boxes the attack fails” [32].

Nothing can be more mistaken. In this article, the authors review 40 years of development of block ciphers in order to resist differential attacks. They study all ten known sets of GOST S-boxes. It appears that the choice of S-boxes has a limited effect on the actual security of GOST against advanced differential attacks. There is no evidence that the version of GOST submitted to ISO in 2011 is stronger than any previous version of GOST.

Keywords:

• aggregated differentials
• block ciphers
• Boolean functions
• differential cryptanalysis
• GOST
• non-linearity
• optimal S-boxes
• sets of differentials
• truncated differentials

Additional information

Notes on contributors

Nicolas T. Courtois

Nicolas T. Courtois is a cryptologist and a Senior Lecturer at University College London. He has done his PhD thesis in cryptology at Paris 6 University. Previously he was employed by Gemalto, the world's largest manufacturer of smart cards. He is a highly influential cryptologist and code-breaker with more than 100 regular publications more than 6000 citations and h-index of 32. His research focuses on the security analysis of cryptographic schemes with particular focus on realistic attack scenarios. He has filed more than 8 patents on industrial applications of cryptology.

Theodosis Mourouzis

Theodosis Mourouzis is originally from Cyprus, Greece. Subsequently he has studied pure mathematics and number theory at University of Cambridge, UK. Then he has started a PhD at the UCL SECRET doctoral training center in security and crime science. He has recently completed bis PhD at UCL in the area of cryptography under supervision of Dr. Courtois. His PhD thesis is about optimizations in algebraic and differential cryptanalysis and in July 2012 he has obtained the Best Paper Award at the Computation Tools conference in France.

Michał Misztal

Michał Misztal is a lecturer at Institute of Mathematics and Cryptology at Military University of Technology in Warsaw Poland. He teaches specialist modules on introduction to cryptography and block stream cipher cryptanalysis. Together with Dr. Szmidt he has co-authored a cryptography teaching manual for students in Polish. His research focuses mainly on differential cryptanalysis of modern ciphers.

Jean-Jacques Quisquater

Jean-Jacques Quisquater is a well-known cryptographer and a professor at Université catholique de Louvain, Belgium. He is one of the most highly cited cryptographers in Europe with an H-index of 58. He is a recipient with Claus P. Schnorr of the RSA Award for Excellence in Mathematics in 2013 and the ESORICS Outstanding Research Award 2013. He is well known for his extensive research publications in cryptography and for his long standing engagement with the security industry with the first smart cards using strong cryptography (DES, RSA), the GQ authentication protocol used by hundreds of millions on Novell Netware clients, highly influential work on side channel attacks and many other innovations.

Guangyan Song

Guangyan Song is originally from China. He has completed a M.Sc in Machine Learning at University College London in 2010. Then he worked as a data Scientist and Software Engineer in the anti-virus branch of Cisco Systems in London where he worked on Internet analytics, behavior prediction and executable classification problems in malware detection. He currently is a PhD candidate at UCL under supervision of Dr. Courtois. His PhD research focuses on optimization problems in software cryptanalytic attacks on modern block ciphers.