Multiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs

Alex Biryukov; Dmitry Khovratovich; Léo Perrin

doi:10.13154/tosc.v2016.i2.226-247

Alex Biryukov Interdisciplinary Centre for Security, Reliability and Trust (SnT), Computer Science and Communications Research Unit (CSC), University of Luxembourg, Luxembourg, Luxembourg
Dmitry Khovratovich University of Luxembourg, Luxembourg, Luxembourg
Léo Perrin Interdisciplinary Centre for Security, Reliability and Trust (SnT), University of Luxembourg, Luxembourg, Luxembourg

DOI: https://doi.org/10.13154/tosc.v2016.i2.226-247

Keywords: Generic SPN, Algebraic attack, Multi-set, Integral, Division property, Kuznyechik, Khazad

Abstract

We devise the first closed formula for the number of rounds of a blockcipher with secret components so that these components can be revealed using multiset, algebraic-degree, or division-integral properties, which in this case are equivalent. Using the new result, we attack 7 (out of 9) rounds of Kuznyechik, the recent Russian blockcipher standard, thus halving its security margin. With the same technique we attack 6 (out of 8) rounds of Khazad, the legacy 64-bit blockcipher. Finally, we show how to cryptanalyze and find a decomposition of generic SPN construction for which the inner-components are secret. All the attacks are the best to date.