Estimations of cryptographic resistance of ciphers in the Trivium family to SAT-based cryptanalysis

O. S. Zaikin ; I. V. Otpuschennikov ; A. A. Semenov

Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 46-48.

Résumé

Here we present the cryptanalysis results for three stream ciphers in the Trivium family: Bivium, Trivium toy, and Bivium toy. The cryptanalysis was performed via reducing the inversion problems for corresponding discrete functions to Boolean satisfiability problem (SAT). This approach made it possible to perform the cryptanalysis of Bivium toy cipher using common sequential SAT solvers. On average, to solve one cryptanalysis instance for Bivium toy on one core of AMD Opteron 6276 processor, it took about two minutes. For cryptanalysis of Bivium, we designed a variant of “guess-and-determine” attack, in which it is assumed that the values of the last 9 cells at the end of the second Bivium register are known. Thus, the problem is to find values of 168 remaining cells of Bivium registers (the total length of two registers used in Bivium is 177 bits). For this purpose, we analyze 200 bits of keystream. To solve one corresponding cryptanalysis instance, it took about two weeks of work of volunteer computing project SAT@home. The Trivium toy cipher, in its non-weakened form, turned out to be highly resistant to SAT-based cryptanalysis. It proves once more that the general design of the Trivium cipher is very good. We considered the recovery problem for values of registers in Trivium toy based on 100 bits of keystream. At the current stage, we only managed to perform in a reasonable time the variant of “guess-and-determine” attack, in which we know the initial values of the first 16 cells of the second register. Thus, in the corresponding cryptanalysis instances, we need to find values of remaining 80 out of 96 cells. Using the computing cluster of Irkutsk Supercomputer center SB RAS, we managed to solve several instances of Trivium toy cryptanalysis. For this purpose, we used the PD-SAT parallel solver developed in ISDCT SB RAS. On average, to solve one instance using 320 cores of AMD Opteron 6276, it took about one day.

Détail

Keywords: stream cipher, Bivium, Boolean satisfiability problem.
Mots-clés : Trivium, cryptanalysis

Bibliographie

[1] Canniere C. D., “Trivium: A stream cipher construction inspired by block cipher design principles”, LNCS, 4176, 2006, 171–186 | Zbl

[2] Maximov A., Biryukov A., “Two trivial attacks on Trivium”, SAC'07, LNCS, 4876, 2007, 36–55 | Zbl

[3] Mcdonald C., Charnes C., Pieprzyk J., Attacking Bivium with MiniSat, Technical Report 2007/040, ECRYPT Stream Cipher Project, 2007

[4] Eibach T., Pilz E., Volkel G., “Attacking Bivium using SAT solvers”, LNCS, 4996, 2008, 63–76 | Zbl

[5] Soos M., Nohl K., Castelluccia C., “Extending SAT solvers to cryptographic problems”, LNCS, 5584, 2009, 244–257 | MR

[6] Zaikin O. S., Semenov A. A., “Primenenie metoda Monte-Karlo k prognozirovaniyu vremeni parallelnogo resheniya problemy bulevoi vypolnimosti”, Vychislitelnye metody i programmirovanie: novye vychislitelnye tekhnologii, 15:1 (2014), 22–35

[7] Semenov A. A., Zaikin O. S., “Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem”, LNCS, 9251, 2015, 222–230

[8] Lechtaler A. C., Cipriano M., Garcia E., et al., “Model design for a reduced variant of a Trivium type stream cipher”, J. Computer Science Technology, 14:1 (2014), 55–58

[9] Otpuschennikov I. V., Semenov A. A., “Tekhnologiya translyatsii kombinatornykh problem v bulevy uravneniya”, Prikladnaya diskretnaya matematika, 2011, no. 1, 96–115

[10] Otpuschennikov I. V., Semenov A. A., Kochemazov S. E., “Transalg: a tool for translating procedural descriptions of discrete functions to SAT”, Proc. 5th Intern. Workshop on Computer Science and Engineering: Information Processing and Control Engineering (WCSE 2015-IPCE), 2015, 289–294

[11] Bard G. V., Algebraic Cryptanalysis, Springer, 2009 | MR | Zbl