Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2
Мета даної роботи — обґрунтування стійкості шифру «Струмок» відносно широкого класу кореляційних атак, який охоплює, зокрема, відомі атаки на SNOW 2.0. Основним результатом є теорема, яка встановлює аналітичну оцінку параметра, що характеризує ефективність кореляційних атак на SNOW 2.0-подібні шифри...
Збережено в:
| Опубліковано в: : | Математичне та комп'ютерне моделювання. Серія: Технічні науки |
|---|---|
| Дата: | 2019 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/168580 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 / А.М. Олексійчук, С.М. Конюшок, М.В. Поремський // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 114-119. — Бібліогр.: 9 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859464828065677312 |
|---|---|
| author | Олексійчук, А.М. Конюшок, С.М. Поремський, М.В. |
| author_facet | Олексійчук, А.М. Конюшок, С.М. Поремський, М.В. |
| citation_txt | Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 / А.М. Олексійчук, С.М. Конюшок, М.В. Поремський // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 114-119. — Бібліогр.: 9 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичне та комп'ютерне моделювання. Серія: Технічні науки |
| description | Мета даної роботи — обґрунтування стійкості шифру «Струмок» відносно широкого класу кореляційних атак, який охоплює, зокрема, відомі атаки на SNOW 2.0. Основним результатом є теорема, яка встановлює аналітичну оцінку параметра, що характеризує ефективність кореляційних атак на SNOW 2.0-подібні шифри у термінах їх компонент. Це дозволяє на практиці оцінювати та обґрунтовувати стійкість таких шифрів відносно кореляційних атак над полями характеристики 2.
The purpose of this article is to justify the security of Strumok against a wide class of correlation attacks, including known attacks on SNOW 2.0. The main result is a theorem that establishes an analytical bound for parameter characterizing the effectiveness of correlation attacks on SNOW 2.0-like ciphers in terms of their components. This allows in practice to evaluate and justify the security of such ciphers against correlation attacks over finite fields of characteristic 2.
|
| first_indexed | 2025-11-24T04:55:25Z |
| format | Article |
| fulltext |
Математичне та комп’ютерне моделювання
114
УДК 621.391:519.2
DOI: 10.32626/2308-5916.2019-19.114-119
А. М. Олексійчук, д-р техн. наук,
С. М. Конюшок, канд. техн. наук,
М. В. Поремський, аспірант
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського», м. Київ
ОБҐРУНТУВАННЯ СТІЙКОСТІ ПОТОКОВОГО ШИФРУ
«СТРУМОК» ВІДНОСНО КОРЕЛЯЦІЙНИХ АТАК
НАД СКІНЧЕННИМИ ПОЛЯМИ ХАРАКТЕРИСТИКИ 2
Потоковий шифр SNOW 2.0 запропонований у 2002 р. як
альтернатива попередньої (більш слабкої) версії — SNOW.
На сьогодні цей шифр є стандартизованим та являє собою
один з найбільш швидких програмно орієнтованих потоко-
вих шифрів.
Найбільш потужними з відомих атак на SNOW 2.0 є коре-
ляційні атаки, сутність яких полягає у складанні та розв’язанні
систем лінійних рівнянь із спотвореними правими частинами,
зокрема, систем рівнянь над полями порядку більшого ніж 2.
Не дивлячись на певний прогрес у цьому напрямі, залишають-
ся не вирішеними задачі, пов’язані з розробкою методів оці-
нювання та обґрунтування стійкості SNOW 2.0-подібних по-
токових шифрів відносно кореляційних атак. На сьогодні від-
сутні методи, які дозволяють обґрунтовувати стійкість зазна-
чених шифрів відносно відомих кореляційних атак безпосере-
дньо за параметрами їх компонент. Крім того, спроба застосу-
вати відомі методи оцінювання стійкості SNOW 2.0 відносно
кореляційних атак до інших потокових шифрів (наприклад,
шифру «Струмок», який запропоновано в ролі кандидата на
національний стандарт шифрування України) наштовхується
на труднощі, пов’язані з розміром задач, які треба розв’язувати
для отримання оцінок. На відміну від SNOW 2.0, побудовано-
го над полем порядку
32
2 , шифр «Струмок» задається над по-
лем порядку
64
2 , що призводить до неможливості практично-
го застосування відомих певних алгоритмів, часова складність
яких збільшується від
32 37
2 2 до
64
2 двійкових операцій.
Мета даної роботи — обґрунтування стійкості шифру
«Струмок» відносно широкого класу кореляційних атак, який
охоплює, зокрема, відомі атаки на SNOW 2.0. Основним резуль-
татом є теорема, яка встановлює аналітичну оцінку параметра,
що характеризує ефективність кореляційних атак на SNOW 2.0-
подібні шифри у термінах їх компонент. Це дозволяє на практи-
© А. М. Олексійчук, С. М. Конюшок, М. В. Поремський, 2019
Серія: Технічні науки. Випуск 19
115
ці оцінювати та обґрунтовувати стійкість таких шифрів віднос-
но кореляційних атак над полями характеристики 2.
Ключові слова: потоковий шифр, кореляційний крипто-
аналіз, система лінійних рівнянь зі спотвореними правими ча-
стинами, обґрунтування стійкості, «Струмок».
Вступ. Нагадаємо означення класу SNOW 2.0-подібних потоко-
вих шифрів [1, 2], до яких відноситься шифр «Струмок» [3].
Позначимо rV множину двійкових векторів довжини 2r . За-
дамо на цій множині структуру поля порядку 2 ,
r узгоджену з опера-
цією покоординатного булевого додавання двійкових векторів.
Ототожнимо також звичайним чином елементи множини rV з r -роз-
рядними цілими числами та позначимо символом операцію дода-
вання цих чисел за модулем 2
r
.
За означенням [2] вхідними даними для побудови генератора
гами r -розрядного SNOW 2.0-подібного потокового шифру є примі-
тивний многочлен
1
1 0( ) ...
n n
ng z z c z c
над полем
2
rF , підс-
тановка : r rV V та натуральне число 1, 2n . Генератор гами
являє собою скінченний автономний автомат з множиною станів
2n
r rV V , функцією переходів
1 2 0(( , , ... , ), , )n nh x x x u v 1 1(( , , ... , ), , ( ))n nx x x x v u ,
та функцією виходів
1 2 0(( , , ... , ), , )n nf x x x u v 0 1( )nx x u v ,
де 0 1, ..., , ,n rx x u v V , 1 1 0 0...n n nx c x c x . Отже, знак гами в i -
му такті визначається за початковим станом
1 2 0 0 0(( , , ... , ), , )n nx x x u v генератора за допомогою рекурентних
співвідношень 1( )i i i n i ix x u v , 1i i iu x v , 1iv
( ),iu справедливих для усіх 0, 1, ...i .
Надалі вважатимемо, що r pt , де ,p t N , , 2p t , і підстано-
вка має такий вигляд:
1( , ..., )pz z 1 1( ( ), ..., ( ))p ps z s z D , 1 2
( ,..., ) t
p
pz z F , (1)
де is — підстановка (вузол заміни) на множині tV , яка ототожнюєть-
ся з адитивною групою поля
2
tF , 1,i p , D — оборотна матриця
порядку p над полем
2
tF .
Зауважимо, що у шифрі «Струмок» використовуються такі па-
раметри [3]: 8t , 8p ( 64r ), 16n , 13 . Підстановка
Математичне та комп’ютерне моделювання
116
має вигляд (1), де вузли заміни та матриця D задаються так само, як
у блоковому шифрі «Калина» [4].
Постановка задачі й отримані результати. Найбільш потуж-
ними з відомих сьогодні атак на SNOW 2.0 є кореляційні атаки [5–8],
спрямовані на відновлення початкового стану лінійного регістру зсу-
ву (ЛРЗ), що входить до складу генератора, за шифрувальною гамою.
В роботі [9] описано загальну схему побудови таких атак на довільні
SNOW 2.0-подібні шифри і показано, що усі вони базуються на скла-
данні та розв’язанні певних наслідків системи лінійних рівнянь із
спотвореними правими частинами
1 1i i i i ix x x 1i n i n ix x , 0, 1,...i , (2)
де
1 1(( ) ( )) (( )
( )), 0, 1,...,
i i n i i n i i n i i
i n i i
x u x u x x v
x x v i
(3)
причому знаки 1 1, , , ,i i i i n i nx x x x x лінійної рекуренти у форму-
лі (2) є відомими лінійними функціями початкового стану ЛРЗ, а
змінні 1, , , ,i i n i n i ix x x u v у формулі (3) є незалежними випадко-
вими величинами з рівномірним розподілом на множині rV .
Відповідно до [9] будь-яка кореляційна атака на шифр визнача-
ється додатним дільником r числа r та ненульовим елементом c
поля
2
rF і полягає у складанні та розв’язанні певної системи рівнянь
від l nr невідомих, де r r r , із спотвореними правими частина-
ми над полем
2
rF , причому закон розподілу спотворень i у правих
частинах рівнянь має такий вигляд:
2
2 2
: Tr ( )
{ } { }
r
r r
i i
x F cx z
z x
P P ,
2
rz F , (4)
0, 1,...i , де
2
2
Tr ( )
r
r позначає функцію сліду поля
2
rF в полі
2
.rF
Для оцінювання середньої трудомісткості атаки і обсягу матері-
алу (кількості знаків гами), потрібного для її успішної реалізації, мо-
жна використовувати наступний алгоритм [8].
Алгоритм 1.
Вхідні дані:
натуральні числа , ,n p t ;
число 2k , що є степенем двійки;
верхня оцінка ( )r k параметра
2
2
, 1( ) 2 (2 { } 1)
r
r r
c r k
z F
k z
P , (5)
Серія: Технічні науки. Випуск 19
117
де 1,..., k є незалежними випадковими величинами, розподіленими
за законом (4).
1. Покласти
1
( )r pt r
, l nr , 1 log k .
2. Для кожного 1, 1l l обчислити
1
( ) 2( ( )) ln 2r rm k k l r
,
1 ( )
( , ) ( ( )) 2
r l l
r rT k l m k k
( 1)
( ( ) 2 ) 2
r l r l
rr m k r l
.
3. Обрати * 1, 1l l таке, що ( , *) min{ ( , ) : 1, 1}r rT k l T k l l l .
Результат:
число *l фрагментів (довжини r бітів кожний) початкового ста-
ну ЛРЗ, які відновлюються за допомогою атаки;
нижня оцінка середньої часової складності атаки ( , *)rT k l ;
нижня оцінка обсягу матеріалу
( *) 1 1
( , *) 2 (2 * ln 2) ( ( ))
r l l
r rN k l k l r k
,
потрібного для успішної реалізації атаки.
Для того, щоб алгоритм 1 можна було використовувати на прак-
тиці, треба вміти оцінювати значення параметра (5) за числом r , еле-
ментом
2
\ {0}rc F та компонентами шифру (матрицею D і вузлами
заміни is , 1,i p ; див. формулу (1)). Отже, постає задача отримання
аналітичних верхніх оцінок параметра (5) безпосередньо за компонен-
тами алгоритму шифрування та параметрами кореляційної атаки.
Розв’язок цієї задачі містить наступна теорема (доведення якої
виходить за межі статті).
Теорема. За умов, зазначених вище, справедлива нерівність
, ( )c r k
( )
2
2
max(2 1)
T
B D
k
r
n
, (6)
де
max ,max{ ( ) : ( , ) \{(0, 0)}, 0, 1}a b i t tn n s a b V V i p , (7)
2
( ) min{ ( ) ( ) : \{0}}t
T T p
B D wt z wt zD z F , (8)
і для будь-яких , ta b V , 0, 1i p :
, ( )a b in s
( ) ( ) ( ) ( )
, , , ,
max{| (0, 0) | | (0, 1) |, | (1, 0) | | (1, 1) |}
i i i i
a b a b a b a b
A A A A ,
( ) ( )( ) 2
,
, :
msb( )
( , ) 2 ( 1)
t t
i i i i i
i i t
i i
x y u a x a s y bi t
a b
x y V
x y u u
A u u
, , {0, 1}u u ,
Математичне та комп’ютерне моделювання
118
де ( )i imsb x y u є найстарший розряд суми цілих чисел, що відпо-
відають зазначеним двійковим векторам довжини t ,
t t
i ix y u поз-
начає суму цих чисел за модулем 2
t
.
Використовуючи теорему і алгоритм 1, отримаємо оцінки ефек-
тивності кореляційних атак над полем 256F на шифр «Струмок» (таб-
лиця). Відзначимо, що в цьому випадку 8t , 8p , 16n ,
( ) 1 9
T
B D p , і як показує пряме обчислення, значення параметра
(7) дорівнює
4
max 3 2n
.
Таблиця
Результати виконання алгоритму 1 для шифру «Струмок» ( 8r )
k *l 2
log ( , *)
r
T k l
2
log ( , *)
r
N k l
2 44 363,91 361,62
4 34 285,42 285,06
8 29 249,40 249,38
16 1 384,88 283,58
Висновки. Результати обчислень, наведені в таблиці свідчать про
те, що будь-яка із зазначених кореляційних атак на «Струмок» має се-
редню часову складність не менше ніж
249,40
2 та потребує не менше
ніж
249,38
2 знаків гами. Це свідчить про практичну стійкість зазначе-
ного шифру за умови, що довжина відрізку гами, яка виробляється при
будь-якому фіксованому ключі, не перевищує (наприклад)
80
2 .
Список використаних джерел:
1. Ekdahl P., Johansson T. A new version of the stream cipher SNOW. Selected
Areas in Cryptography — SAC. 2002. LNCS 2295. Springer-Verlag. P. 47–61.
2. Олексійчук А. М. Достатня умова стійкості SNOW 2.0-подібних потоко-
вих шифрів відносно певних атак зі зв’язаними ключами. Захист інфор-
мації. 2016. Т. 18. № 3. С. 261–268.
3. Gorbenko I., Kuznetsov A., Gorbenko Yu., Alekseychuk A., Timchenko V.
Strumok Keystream Generator. The 9th IEEE International Conference on De-
pendable Systems, Services and Technologies, DESSERT’2018, 24–27 May,
2018. Kyiv, Ukraine. P. 292–299.
4. Oliynykov R. V., Gorbenko I. D., Kazymyrov O. V. [et. al]. A New Encryption
Standard of Ukraine: The Kalyna Block Cipher. Cryptology ePrint Archive.
URL: http://eprint.iacr.org/ 2015/650.
5. Nyberg K., Wallen J. Improved linear distinguishers for SNOW 2.0. Fast
Software Encryption — FSE 2006. LNCS 4047. Springer-Verlag. P. 144–162.
6. Maximov A., Johansson Th. Fast computation for large distribution and and its
cryptographic application. Advanced in Cryptology. ASIACRYPT 2005. —
LNCS 3788. Springer-Verlag. P. 313–332.
Серія: Технічні науки. Випуск 19
119
7. Lee J.-K., Lee D. H., Park S. Cryptanalysis of SOSEMANUC and SNOW 2.0
using linear masks. Advanced in Cryptology. ASIACRYPT 2008. LNCS 5350.
Springer-Verlag. P. 524–538.
8. Zhang B., Xu C., Meier W. Fast correlation attacks over extension fields,
large-unit linear approximation and cryptanalysis of SNOW 2.0. Cryptology
ePrint Archive. URL: http://eprint.iacr.org/2016/311.
9. Олексійчук А. М., Поремський М. В. Загальна схема побудови кореля-
ційних атак на SNOW 2.0-подібні потокові шифри. Правове, нормативне
та метрологічне забезпечення системи захисту інформацїї в Україні.
Вип. 1 (35). 2018. С. 70–79.
SECURITY JUSTIFICATION FOR STRUMOK
STREAM CIPHER AGAINST CORRELATION ATTACKS
OVER FINITE FIELDS OF CHARACTERISTIC 2
The stream cipher SNOW 2.0 was proposed in 2002 as an alternative
to the previous (weaker) version — SNOW. This cipher is standardized to-
day and is one of the fastest program-oriented stream ciphers.
The most powerful known attacks on SNOW 2.0 are correlation at-
tacks, the essence of which is to form and solve systems of noised linear
equations, in particular, over finite fields of order greater than 2. Despite
some progress in this direction, remain unresolved problems related to the
development of methods for evaluation and justification the security of
SNOW 2.0-like stream ciphers against correlation attacks. To date, there
are no methods that can justify the security of these ciphers against known
correlation attacks directly from the parameters of their components. In
addition, an attempt to apply known methods for evaluating the security of
SNOW 2.0 against correlation attacks to some other stream ciphers (for
example, Strumok, which is a candidate for National encryption standard
of Ukraine) faces the difficulties associated with the size of tasks that have
been solved. Unlike SNOW 2.0, constructed above the field of order
32
2 ,
the Strumok cipher is set over a field of order
64
2 , which leads to the im-
possibility of practical implementation of some known algorithms, the time
complexity of which increases from
32 37
2 2 to
64
2 bit operations.
The purpose of this article is to justify the security of Strumok against
a wide class of correlation attacks, including known attacks on SNOW 2.0.
The main result is a theorem that establishes an analytical bound for pa-
rameter characterizing the effectiveness of correlation attacks on SNOW
2.0-like ciphers in terms of their components. This allows in practice to
evaluate and justify the security of such ciphers against correlation attacks
over finite fields of characteristic 2.
Key words: stream cipher, correlation cryptanalysis, system of noised
linear equations, security justification, Strumok.
Одержано 15.01.2019
|
| id | nasplib_isofts_kiev_ua-123456789-168580 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2308-5916 |
| language | Ukrainian |
| last_indexed | 2025-11-24T04:55:25Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Олексійчук, А.М. Конюшок, С.М. Поремський, М.В. 2020-05-04T17:10:02Z 2020-05-04T17:10:02Z 2019 Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 / А.М. Олексійчук, С.М. Конюшок, М.В. Поремський // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 114-119. — Бібліогр.: 9 назв. — укр. 2308-5916 DOI: 10.32626/2308-5916.2019-19.114-119 https://nasplib.isofts.kiev.ua/handle/123456789/168580 621.391:519.2 Мета даної роботи — обґрунтування стійкості шифру «Струмок» відносно широкого класу кореляційних атак, який охоплює, зокрема, відомі атаки на SNOW 2.0. Основним результатом є теорема, яка встановлює аналітичну оцінку параметра, що характеризує ефективність кореляційних атак на SNOW 2.0-подібні шифри у термінах їх компонент. Це дозволяє на практиці оцінювати та обґрунтовувати стійкість таких шифрів відносно кореляційних атак над полями характеристики 2. The purpose of this article is to justify the security of Strumok against a wide class of correlation attacks, including known attacks on SNOW 2.0. The main result is a theorem that establishes an analytical bound for parameter characterizing the effectiveness of correlation attacks on SNOW 2.0-like ciphers in terms of their components. This allows in practice to evaluate and justify the security of such ciphers against correlation attacks over finite fields of characteristic 2. uk Інститут кібернетики ім. В.М. Глушкова НАН України Математичне та комп'ютерне моделювання. Серія: Технічні науки Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 Security justification for Strumok stream cipher against correlation attacks over finite fields of characteristic 2 Article published earlier |
| spellingShingle | Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 Олексійчук, А.М. Конюшок, С.М. Поремський, М.В. |
| title | Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 |
| title_alt | Security justification for Strumok stream cipher against correlation attacks over finite fields of characteristic 2 |
| title_full | Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 |
| title_fullStr | Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 |
| title_full_unstemmed | Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 |
| title_short | Обґрунтування стійкості потокового шифру "Струмок" відносно кореляційних атак над скінченними полями характеристики 2 |
| title_sort | обґрунтування стійкості потокового шифру "струмок" відносно кореляційних атак над скінченними полями характеристики 2 |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/168580 |
| work_keys_str_mv | AT oleksíičukam obgruntuvannâstíikostípotokovogošifrustrumokvídnosnokorelâcíinihataknadskínčennimipolâmiharakteristiki2 AT konûšoksm obgruntuvannâstíikostípotokovogošifrustrumokvídnosnokorelâcíinihataknadskínčennimipolâmiharakteristiki2 AT poremsʹkiimv obgruntuvannâstíikostípotokovogošifrustrumokvídnosnokorelâcíinihataknadskínčennimipolâmiharakteristiki2 AT oleksíičukam securityjustificationforstrumokstreamcipheragainstcorrelationattacksoverfinitefieldsofcharacteristic2 AT konûšoksm securityjustificationforstrumokstreamcipheragainstcorrelationattacksoverfinitefieldsofcharacteristic2 AT poremsʹkiimv securityjustificationforstrumokstreamcipheragainstcorrelationattacksoverfinitefieldsofcharacteristic2 |