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

Issue

Vol. 17 No. 3 (2015)

Section

Articles

License

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).