## Correlation cube attacks: from weak-key distinguisher to key recovery.(English)Zbl 1428.94086

Nielsen, Jesper Buus (ed.) et al., Advances in cryptology – EUROCRYPT 2018. 37th annual international conference on the theory and applications of cryptographic techniques, Tel Aviv, Israel, April 29 – May 3, 2018. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10821, 715-744 (2018).
Summary: In this paper, we describe a new variant of cube attacks called correlation cube attack. The new attack recovers the secret key of a cryptosystem by exploiting conditional correlation properties between the superpoly of a cube and a specific set of low-degree polynomials that we call a basis, which satisfies that the superpoly is a zero constant when all the polynomials in the basis are zeros. We present a detailed procedure of correlation cube attack for the general case, including how to find a basis of the superpoly of a given cube. One of the most significant advantages of this new analysis technique over other variants of cube attacks is that it converts from a weak-key distinguisher to a key recovery attack.{
}As an illustration, we apply the attack to round-reduced variants of the stream cipher Trivium. Based on the tool of numeric mapping introduced by M. Liu [Crypto 2017, Lect. Notes Comput. Sci. 10403, 227–249 (2017; Zbl 1406.94073)] , we develop a specific technique to efficiently find a basis of the superpoly of a given cube as well as a large set of potentially good cubes used in the attack on Trivium variants, and further set up deterministic or probabilistic equations on the key bits according to the conditional correlation properties between the superpolys of the cubes and their bases. For a variant when the number of initialization rounds is reduced from 1152 to 805, we can recover about 7-bit key information on average with time complexity $$2^{44}$$, using $$2^{45}$$ keystream bits and preprocessing time $$2^{51}$$. For a variant of Trivium reduced to 835 rounds, we can recover about 5-bit key information on average with the same complexity. All the attacks are practical and fully verified by experiments. To the best of our knowledge, they are thus far the best known key recovery attacks for these variants of Trivium, and this is the first time that a weak-key distinguisher on Trivium stream cipher can be converted to a key recovery attack.
For the entire collection see [Zbl 1387.94007].

### MSC:

 94A60 Cryptography

### Keywords:

cryptanalysis; cube attack; numeric mapping; stream cipher; Trivium

Zbl 1406.94073
Full Text: