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

Автор(и)

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

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

Як цитувати

Алексейчук, А. Н., Конюшок, С. Н., & Сторожук, А. Ю. (2015). УЗАГАЛЬНЕНА СТАТИСТИЧНА АТАКА НА СИНХРОННІ ПОТОКОВІ ШИФРИ. Захист інформації, 17(3), 246–255. https://doi.org/10.18372/2410-7840.17.9532

Номер

Том 17 № 3 (2015)

Розділ

Статті

Ліцензія

Науковий журнал дотримується принципів відкритого доступу (Open Access) та забезпечує вільний, негайний і постійний доступ до всіх опублікованих матеріалів без фінансових, технічних або юридичних обмежень для читачів.

Усі статті публікуються у відкритому доступі відповідно до ліцензії Creative Commons Attribution 4.0 International (CC BY 4.0).

Авторські права

Автори, які публікують свої роботи в журналі:

  • зберігають за собою авторські права на свої публікації;

  • надають журналу право на перше опублікування статті;

  • погоджуються на поширення матеріалів за ліцензією CC BY 4.0;

  • мають право повторно використовувати, архівувати та поширювати свої роботи (у тому числі в інституційних та тематичних репозитаріях) за умови посилання на первинну публікацію в журналі.