Application of parallel SAT solving algorithms for cryptanalysis of the shrinking and self-shrinking keystream generators

Oleg Zaikin

Abstract


In this study, shrinking and self-shrinking keystream generators are analyzed. These generators can be used in stream ciphering. For each generator the following cryptanalysis problem was considered: given a known keystream fragment, find the corresponding 64-bit secret key. Both problems were reduced to Boolean satisfiability problem (SAT), and then parallel CDCL solvers were used to solve them. Solvers of two types were employed. In solvers of the first type the base CDCL algorithm itself is parallelized. Solvers of the second type decompose an original SAT instance into a family of simpler independent subproblems. Computational experiments were held on a computing cluster. As a result, several cryptanalysis instances of the mentioned type were solved. It turned out, that the parallel solvers of the first type suit better for the considered cryptanalysis problems.

Full Text:

PDF (Russian)

References


Menezes A. J., van Oorschot P. C., Vanstone S.A. Handbook of applied cryptography. CRC Press. 1996. 810 p.

Biere A., Heule M., van Maaren H., Walsh T. Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications. Vol. 185. IOS Press. 2009.

Semenov A.A., Bespalov. D.V. Tehnologii reshenija mnogomernyh zadach logicheskogo poiska // Vestnik Tomskogo gosudarstvennogo universiteta. 2005. # 14. S. 61–73.

Belej E.G., Semenov A.A., O vychislitel'nom poiske kvaziortogonal'nyh sistem latinskih kvadratov, blizkih k ortogonal'nym sistemam // International Journal of Open Information Technologies. 2018. Vol. 6. No. 2. S. 22-30.

Zaikin O.S., Otpuschennikov I.V., Semenov A.A. Solving weakened cryptanalysis problems for the Bivium cipher in the volunteer computing project SAT@home // International Journal of Open Information Technologies. 2015. Vol. 3. No. 12, pp. 1-3.

Zaikin O.S., Semenov A.A. Primenenie metoda Monte-Karlo k prognozirovaniju vremeni parallel'nogo reshenija problemy bulevoj vypolnimosti // Vychislitel'nye metody i programmirovanie: novye vychislitel'nye tehnologii. 2014. T. 15. # 1. S. 22-35.

Posypkin M.A., Zaikin O.S., Bespalov D.V., Semenov A.A. Reshenie zadach kriptoanaliza potochnyh shifrov v raspredelennyh vychislitel'nyh sredah // Trudy Instituta sistemnogo analiza Rossijskoj akademii nauk. 2009. T. 46. S. 119-137.

Zaikin, O.S., Semenov A.A., Posypkin M.A. Procedury postroenija dekompozicionnyh mnozhestv dlja raspredelennogo reshenija SAT-zadach v proekte dobrovol'nyh vychislenij SAT@home // Upravlenie bol'shimi sistemami. M.: IPU RAN. 2013. Vyp. 43. S. 138–156.

Afanasiev A.P., Bychkov I.V., Zaikin O.S., Manzyuk M.O., Posypkin M.A., Semenov A.A. Concept of a multitask grid system with a flexible allocation of idle computational resources of supercomputers // Computer and Systems Sciences International. 2017. Vol. 56. Issue 4. pp. 701–707.

Semenov A.A. Dekompozicionnye predstavlenija logicheskih uravnenij v zadachah obrashhenija diskretnyh funkcij // Izvestija Rossijskoj akademii nauk. Teorija i sistemy upravlenija. 2009. # 5. S. 47-61.

Coppersmith D., Krawczyk H., Mansour Y. The shrinking generator // Proceedings of CRYPTO’93. Lecture Notes in Computer Science. Springer-Verlag. 1993. Vol. 773. pp. 23–39.

Staffelbach O., Meier W. The Self-shrinking generator // Proceedings of EUROCRYPT’94. Lecture Notes in Computer Science. Springer-Verlag. 1994. Vol. 950. pp. 205–214.

Otpuschennikov I.V., Semenov A.A., Gribanova I.A., Zaikin O.S., Kochemazov S.E. Encoding cryptographic functions to SAT using Transalg system // In Proceedings of ECAI’2016. Frontiers in Artificial Intelligence and Applications. 2016. Vol 285. pp. 1594-1595.

Kochemazov S., Zaikin O. ALAIS: a Modular Tool for Finding Backdoors for SAT // Proceedings of SAT’2018. Lecture Notes in Computer Science. Springer-Verlag. 2018. Vol. 10929. pp. 419–427.

Balyo T., Biere A., Iser M., Sinz C. SAT Race 2015. // Artificial Intelligence. 2016. Vol. 241. pp. 45-65.

Irkutskij superkomp'juternyj centr SO RAN. URL: http://hpc.icc.ru.

Jeli A.N. Issledovanie stojkosti generatorov kljuchevogo potoka k logicheskomu kriptoanalizu // Novye informacionnye tehnologii v avtomatizirovannyh sistemah. 2015 # 18. S. 108-117.

Debraize B., Goubin L. Guess-and-determine Algebraic Attack on the Self-Shrinking Generator // Proceedings of Fast Software Encryption 2008. Lecture Notes in Computer Science. Springer-Verlag. 2008. Vol. 5086. pp. 235–252.

Zaikin O. Kochemazov S. An Improved SAT-Based Guess-and-Determine Attack on the Alternating Step Generator // Proceedings of International Conference on Information Security 2017. Lecture Notes in Computer Science. Springer-Verlag. 2017. Vol. 10599. pp. 21–38.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162