УЗАГАЛЬНЕНА СТАТИСТИЧНА АТАКА НА СИНХРОННІ ПОТОКОВІ ШИФРИ

Автор(и)

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

DOI:

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

Ключові слова:

потоковий шифр, нелінійний криптоаналіз, атака на основі підібраних векторів ініціалізації, алгебраїчно вироджена функція, знаходження наближень булевих функцій.

Анотація

На сьогодні найбільш потужними атаками на синхронні потокові шифри є атаки на основі підібраних векторів ініціалізації. До них відносяться кубічна атака Дінура-Шаміра, статистична атака Фішера-Хазаї-Майєра (FKM), а також їх різні модифікації та вдоско-налення. Атака FKM будується на основі статистичних наближень булевих функцій, пов’язаних з алгоритмами шифрування, функціями, які залежать лишевід деяких розрядів ключа. Розробниками атаки запропоновано спосіб знаходження зазначених наближень, але не надано теоретичного обґрунтування ефективності цього способу. Крім того, залишається відкритим питання про те, чи можливо підвищити ефективність атаки FKM, вибираючи наближення збільш широкого класу булевих функцій. В даній статті пропонується атака на синхронні потокові шифри, яка узагальнює як кубічну атаку, так і атаку FKM. Ця атака базується на алгебраїчно вироджених наближеннях булевих функцій, що надає більше можливостей для реалізації основної ідеї атаки FKM. Запропоновано поліноміальний ймовірнісний алгоритм побудови зазначених наближень за відомими підпросторами, що є допустимими для заданої булевої функції. Показано, що вибираючи певним чином параметрицього алгоритму, можна будувати атаки на синхронні потокові шифри, значно більш ефективні в порівнянні з повним перебором ключів.

Біографії авторів

Антон Николаевич Алексейчук, НТУУ «КПІ»

доктор технічних наук, професор Інституту спеціального зв’язку та захисту інформації НТУУ «КПІ».

Сергей Николаевич Конюшок, НТУУ «КПІ»

кандидат технічних наук, доцент, заступник начальника Інституту спеціального зв’язку та захисту інформації НТУУ «КПІ».

Артем Юрьевич Сторожук, НТУУ «КПІ»

аспірант Інституту спеціального зв’язку та захисту інформації НТУУ «КПІ»

Посилання

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

ный анализ. 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.

##submission.downloads##

Опубліковано

2015-11-03

Номер

Том 17 № 3 (2015)

Розділ

Статті

Ліцензія

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.

  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.

  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).