Cтатистична атака на комбінувальні генератори гами з нерівномірним рухом

Скорочена інформація про документ
dc.contributor.authorМатійко, Александра Андріївна
dc.contributor.authorОлексійчук, Антон Миколайович
dc.date.accessioned2025-12-15T13:38:35Z
dc.date.available2025-12-15T13:38:35Z
dc.date.issued2025
dc.description.abstractКомбінувальнігенератори гами з нерівномірним рухом є основою для побудови низки потокових шифрів, найвідомішими з яких є шифри сім’ї 5Aта Alpha1. Кожен такий генератор складається з декількох двійкових лінійних регістрів зсуву, булевої комбінувальної функції та блоку управління рухом регістрів, який визначає правила, за якими останні зсуваються в процесі вироблення шифрувальної гами. Незважаючи на певні слабкості відомих потокових шифрів, побудованих на базі комбінувальних генераторів гами з нерівномірним рухом, такі генератори досі викликають теоретичний та прикладний інтерес внаслідок простоти їхньої будови та потенційної здатності забезпечувати стійкість до широкого класу атак за умови належного вибору їхніх компонент. У статті досліджуються комбінувальні генератори гами, кожен регістр яких або зсувається на один крок, або простоює в кожному такті, причому один з регістрів рухається рівномірно. Раніше авторами статті показано, що зазначеним генераторам притаманна слабкість, яка полягає у статистичній залежності між кожними сусідніми знаками їхніх вихідних послідовностей. Основним результатом цієї статті є статистична атака, яка базується на зазначеній слабкості. Запропонована атака спрямована на відновлення початкового стану регістру, що рухається рівномірно, за відомою вихідною послідовністю генератора або декількома такими послідовностями, які виробляються генератором в режимі реініціалізації початкового стану. Показано, що в останньому випадку складність атаки залежитьлінійно від довжини зазначеного регістру. Отримано аналітичну оцінку обсягу матеріалу, потрібного для реалізації запропонованої атаки з потрібною достовірністю. Зокрема, показано, що для шифру Alpha1 відповідний обсяг матеріалу становить приблизно 300 відрізків гами поряд з відповідними їм векторами ініціалізації. Сформульовано умови, які послаблюють стійкість генераторів з нерівномірним рухом відносно запропонованої атаки. Вони полягають в тому, що коефіцієнти Уолша-Адамара комбінувальної функції приймають нульові значення на всіх векторах ваги 0 і 1 та ненульові значення на певних векторах ваги 2. Показано, що ці умови виконуються для генератора гами шифру Alpha1. При цьому середній обсяг матеріалу, потрібного для відновлення початкового стану довільного генератора гами, який задовольняє наведені умови, є за порядком таким самим, що і для шифру Alpha1.
dc.description.abstractotherCombination keystream generators with irregular clocking are the basis for constructing of stream ciphers, the most famous of which are A5 and Alpha1. Each such generator consists of several binary linear feedback shift registers, a Boolean combination function, and a register clocking control unit that defines the rules by which registers are shifted in the process of keystream generating. Despite certain weaknesses of known stream ciphers based on combination keystream generators with irregular clocking, such generators still arouse theoretical and applied interest due to the simplicity of their structure and the potential ability to provide security to a wide class of attacks, provided that their components are properly selected. Combination keystream generators, each register of which is either shifted by one step or is idle in each clock cycle, with one of the registers clocking regularly, are investigated in the article. Previously, the authors of the article showed that the mentioned generators have an inherent weakness, which consists in statistical dependence between each neighboring signs of their output sequences. The main result of this article is a statistical attack based on the mentioned weakness. The proposed attack is aimed at restoring the initial state of the register clocking uniformly by a known output sequence of the generator or several such sequences produced by the generator in the chosen IV mode. It is shown that in the latter case the complexity of the attack depends linearly on the length of the mentioned register. An analytical bound of the amount of keystream required to implement the proposed attack with the required success probability is obtained. In particular, it is shown that for Alpha1 the corresponding amount is approximately 300 keystream frames along with their corresponding initialization vectors. Conditions that weaken the security of generators with irregular clocking against the proposed attack are formulated. They consist in the fact that the Walsh-Hadamard coefficients of the combination function take zero values on all vectors of weight 0 or 1 and non-zero values on certain vectors of weight 2. It is shown that these conditions are fulfilled for the keystream generator of Alpha1. In this case, the average amount of keystream required to recover the initial state of an arbitrary keystream generator that satisfies the above conditions is of the same order as for Alpha1.
dc.format.pagerangePp. 32-42
dc.identifier.citationМатійко, А. Cтатистична атака на комбінувальні генератори гами з нерівномірним рухом / Александра Матійко, Антон Олексійчук // Information Technology and Security. – 2025. – Vol. 13, Iss. 1 (24). – Pp. 32-42. – Bibliogr.: 17 ref.
dc.identifier.doihttps://doi.org/10.20535/2411-1031.2025.13.1.328762
dc.identifier.orcid0000-0002-6947-5958
dc.identifier.orcid0000-0003-4385-4631
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/77702
dc.language.isouk
dc.publisherInstitute of Special Communication and Information Protection of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”
dc.publisher.placeKyiv
dc.relation.ispartofInformation Technology and Security, Vol. 13, Iss. 1 (24)
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectкриптографічний захист інформації
dc.subjectкомбінувальний генератор гами з нерівномірним рухом
dc.subjectстатистична атака
dc.subjectперетворення Уолша-Адамара
dc.subject51/A
dc.subjectAlpha1
dc.subjectcryptographic information protection
dc.subjectcombination keystream generators with irregular clocking
dc.subjectstatistical attack
dc.subjectWalsh-Hadamard transform
dc.subjectA5/1
dc.subject.udc004.056
dc.titleCтатистична атака на комбінувальні генератори гами з нерівномірним рухом
dc.title.alternativeA statistical attack on combination keystream generators with irregular clocking
dc.typeArticle

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
32-42.pdf
Розмір:
438.36 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Information Technology and Security, Vol. 13, Iss. 1 (24)