GENERALIZED STATISTICAL ATTACK ON SYNCRONOUS STREAM CIPHERS

Authors

  • Антон Николаевич Алексейчук NTUU «KPI»
  • Сергей Николаевич Конюшок NTUU «KPI»
  • Артем Юрьевич Сторожук NTUU «KPI»

DOI:

https://doi.org/10.18372/2410-7840.17.9532

Keywords:

stream cipher, non-linear cryptanalysis, chosen IV attack, algebraic degenerate function, finding approximations of Boolean functions.

Abstract

Nowadays chosen IV attacks on synchronous streamciphers are the most powerful. These include Dinur-Shamir cube attack, statistical Fisher-Khazaei-Meier(FKM) attack, and their different modifications and improvements.The FKM attack is based on statistical approximations(depended only on some key bits) of Booleanfunctions associated with encryption algorithms. Attack’developers suggested a method for finding theseapproximations but didn’t provide a theoretical justificationof such method’ efficiency. Also there is an openquestion: is it possible to increase attack’ efficiency bychoosing approximations from a wider class of Booleanfunctions. We propose a generalization of cube attack andstatistical attack FKM on synchronous stream ciphers.This attack is based on algebraic degenerate approximationsof Boolean functions that provides more opportunitiesfor implementation of FKM attack’ basic idea. Wealso propose a polynomial probabilistic algorithm forconstruction of such approximations from known subspacesacceptable for defined Boolean function. We showthat the proposed algorithm allows us to construct muchmore efficient attacks on synchronous stream cipherscompared with exhaustive search.

Author Biographies

Антон Николаевич Алексейчук, NTUU «KPI»

Doctor of Technical Science, Professorof Institute of Special Communication and InformationSecurity of NTUU «KPI».

Сергей Николаевич Конюшок, NTUU «KPI»

Candidate of Technical Science,docent, vice-head of Institute of Special Communication and Information Security of NTUU «KPI»

Артем Юрьевич Сторожук, NTUU «KPI»

post-graduate student of Institute of Special Communication and Information Security of NTUU «KPI».

References

Алексейчук А.Н. Алгебраически вырожденные приближения булевых функций / А. Н. Алексейчук, С. Н. Конюшок // Кибернетика и систем-

ный анализ. 2014. Т. 50. № 6. С. 3-14.

Алексейчук А.Н. Статистическая атака на генератор гаммы с линейным законом реинициализации начального состояния и функцией усложнения, близкой к алгебраически вырожденной /А.Н. Алексейчук, С.Н. Конюшок, А.Ю. Сторожук // Радиотехника. 2014. Вып. 176. С. 13-21.

Олексійчук А.М. Швидкі алгоритми побудови k-вимірних наближень наближень булевих функцій// А.М. Олексійчук, С.М. Конюшок, А.Ю. Сторожук // Захист інформації. 2015. Т. 17. № 1.С. 43-52.

Логачев О.А. Булевы функции в теории кодирования и криптологии / О.А. Логачев, А.А. Сальников, В.В. Ященко. М. : МЦНМО, 2004. 470 с.

Эндрюс Г. Теория разбиений / Г. Эндрюс. Пер. с англ. М.: Наука, 1982, 255 с.

Aumasson J.-Ph. Efficient FPGA implementations of high-dimensional cube testers on the streamcipher Grain-128 / J.-Ph. Aumasson, I. Dinur, L. Hensen, W. Meier, A. Shamir // http://eprint.iacr.org/2009/218.

Aumasson J.-Ph. Cube testers and key recovery attacks on reduced-raund MD6 and Trivium / J.-Ph.Aumasson, I. Dinur, W. Meier, A. Shamir // Fast Software Encryption – FSE’09. Proceedings. Springer-Verlag. 2009. P. 1-22.

Aumasson J.-Ph. New features of latin dances:analysis of Salsa, ChaCha, and Rumba / J.-Ph.Aumasson, S. Fischer, S. Khazaei, W. Meier, C.

Rechberger // Fast Softvare Encryption – FSE 2008,Proceedings. Springer-Verlag. 2008, P. 470-488.

Dinur I. An experimentally verified attack on full Grain-128 using dedicated reconfigurable hardware / I. Dinur, T. Gueysu, C. Paar, A. Shamir, R. Zimmermann // http://eprint.iacr.org/2011/282.

Dinur I. Cube attacks on tweakable black box polynomials / I. Dinur, A. Shamir // Advances in Cryptology – EUROCRYPT’09. Proceedings.

Springer-Verlag. 2009. P. 278-299.

Dinur I. Breaking Grain-128 with dynamic cube attacks / I. Dinur, A. Shamir // Fast Software Encryption – FSE’11. Proceedings. Springer-Verlag. 2011. P. 167-187.

Faisal Sh. Extended cubes: enhancing cube attacks by low-degree non-linear equations / Sh. Faisal, M. Resa, W. Susilo, J. Seberry // Proc. of the 6-th ACM Symp. on Information, Comput. and Communication Security (AIACCS’11). 2011. P. 296-305.

Fischer S. Chosen IV statistical analysis for key recovery attacks on stream ciphers / S. Fischer, S. Khazaei, W. Meier // AFRICACRYPT 2008.

Proceedings. Springer-Verlag. 2008. P. 236-245.

Hoeffding W. Probability inequalities for sums of bounded random variables / W. Hoeffding // J. Amer. Statist. Assoc. 1963. Vol. 58. № 301. P. 13-30.

Downloads

Published

2015-11-03

How to Cite

Алексейчук, А. Н., Конюшок, С. Н., & Сторожук, А. Ю. (2015). GENERALIZED STATISTICAL ATTACK ON SYNCRONOUS STREAM CIPHERS. Ukrainian Information Security Research Journal, 17(3), 246–255. https://doi.org/10.18372/2410-7840.17.9532

Issue

Vol. 17 No. 3 (2015)

Section

Articles

License

The scientific journal adheres to the principles of Open Access and provides free, immediate, and permanent access to all published materials without financial, technical, or legal barriers for readers.

All articles are published in Open Access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.

Copyright

Authors who publish their works in the journal:

  • retain the copyright to their publications;

  • grant the journal the right of first publication of the article;

  • agree to the distribution of their materials under the CC BY 4.0 license;

  • have the right to reuse, archive, and distribute their works (including in institutional and subject repositories), provided that proper reference is made to the original publication in the journal.