Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак
New Boolean’s function concepts, such as correlation with a known function value and Boolean’s function extension, are introduced. Algebraic attacks on stream ciphers with linear feedback are shown to be reduced to approximation of the nonlinear filter using low-degree polynomials in terms of the co...
Saved in:
| Date: | 2017 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2017
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/109717 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334320961617920 |
|---|---|
| author | Pometun, S. O. |
| author_facet | Pometun, S. O. |
| author_institution_txt_mv | [
{
"author": "S. O. Pometun",
"institution": null
}
] |
| author_sort | Pometun, S. O. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-11T11:06:21Z |
| description | New Boolean’s function concepts, such as correlation with a known function value and Boolean’s function extension, are introduced. Algebraic attacks on stream ciphers with linear feedback are shown to be reduced to approximation of the nonlinear filter using low-degree polynomials in terms of the correlation with the known function value. This kind of correlation can also be used in describing algebraic attacks on other types of ciphers. |
| first_indexed | 2025-07-17T10:23:03Z |
| format | Article |
| fulltext |
© С.О. Пометун, 2008
Системні дослідження та інформаційні технології, 2008, № 2 29
TIДC
ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ,
ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ
СИСТЕМИ
УДК 681.3
АЛГЕБРАЇЧНІ АТАКИ НА ПОТОКОВІ ШИФРАТОРИ ЯК
УЗАГАЛЬНЕННЯ КОРЕЛЯЦІЙНИХ АТАК
С.О. ПОМЕТУН
Запропоновано нові теоретичні поняття для булевих функцій: кореляція при
відомому значенні функції та її розширення. Доведено, що алгебраїчна атака
на потокові шифратори без пам’яті зводиться до апроксимації ускладнюючої
функції шифратора низькостепеневими поліномами в термінах введеної коре-
ляції. Ця кореляція може бути використана і для опису алгебраїчних атак на
інші типи шифраторів.
ВСТУП
Останнім часом почали інтенсивно розвиватися методи криптоаналізу, які
базуються на запропонованих декілька років тому так званих алгебраїчних
атаках [1,2]. Криптоаналіз великого класу шифраторів можна звести до
розв’язання системи нелінійних рівнянь від багатьох змінних над деяким
скінченним полем (найчастіше )2(GF ). Проте обчислювальна складність
розв’язання таких систем «лобовими» методами настільки велика, що не
дозволяє скільки-небудь суттєво знизити стійкість криптосистеми. Складан-
ня і дослідження таких систем та пошуки відносно швидких способів їх
розв’язання для конкретних шифраторів відносять, в першу чергу, до аналі-
тичних методів криптоаналізу. Окремий випадок аналітичних методів крип-
тоаналізу — способи зниження степеня рівнянь таких систем шляхом дом-
ноження їх на спеціально підібрані поліноми — і називають алгебраїчними
атаками (хоча в зарубіжній літературі під алгебраїчними атаками розуміють
вже будь-який спосіб відносно швидкого розв’язання таких систем). Із за-
стосуванням аналітичного криптоаналізу можна ознайомитись, наприклад, в
роботі [3], де криптоаналіз (знаходження ключа) знаменитого алгоритму
DES (стандарт шифрування США до 2001 р. і фактичний світовий стандарт
шифрування комерційної (і не тільки) інформації протягом останньої чверті
20-го століття) зводиться до розв’язання системи рівнянь.
Алгебраїчні атаки на потокові шифратори вперше запропоновані у
2003 р. [2], де була показана їх ефективність для певного класу шифрато-
рів — потокових шифраторів без пам’яті, побудованих на основі регістрів
С.О. Пометун
ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 30
зсуву з лінійним зворотним зв’язком (РЗЛЗЗ). Для деяких шифраторів, на-
приклад, LILI-128 (пропонувався на Європейський конкурс шифраторів
Nessie), Toyocrypt (пропонувався на Японський конкурс шифраторів Cryp-
trec) алгебраїчна атака має відносно невелику обчислювальну складність
( 572 та 492 операцій відповідно). Для шифратора Toyocrypt атака потребує
лише 20 Кбайт гами (або шифрованого тексту за умови атаки при відомому
відкритому тексті) і може бути реалізована на практиці [2]. Зауважимо, що
система рівнянь для Toyocrypt має 128 змінних і складність у 492 операцій,
що набагато менше, ніж складність повного перебору — 1282 операцій. Об-
числювальна складність розв’язання системи рівнянь сильно залежить від її
степеня. У випадку з Toyocrypt за допомогою алгебраїчної атаки степінь си-
стеми вдалося знизити з 63 до 3.
Незабаром з’явилося узагальнення алгебраїчних атак на потокові
шифратори з пам’яттю [4]. Функціонування S -блоків (основних нелінійних
елементів більшості блокових шифраторів) теж описується системою
рівнянь, тому алгебраїчні атаки можуть застосовуватися і до них (див.,
наприклад, [5]). Таким чином, на сьогоднішній день алгебраїчні атаки
потенційно можуть застосовуватися для всіх основних типів сучасних
шифраторів. Для шифраторів, побудованих на основі РЗЛЗЗ, алгебраїчні
атаки вдалося вдосконалити за рахунок додаткових передобчислень. Такі
атаки названо швидкими алгебраїчними атаками [6].
Метою даної роботи є дослідження алгебраїчних атак та розробка від-
повідних формальних понять.
У першому розділі поставлено, власне, задачу криптоаналізу, в друго-
му — коротко наведено вже відомі результати алгебраїчних атак, у третьо-
му — дається їх формалізація. Нарешті, у четвертому розділі наведено при-
клади опису алгебраїчних атак за допомогою введених понять та завершено
їх логічний зв’язок із кореляційними атаками.
1. ПОСТАНОВКА ЗАДАЧІ
Алгебраїчні атаки будемо розглядати на прикладі алгебраїчних атак на
потокові шифратори без пам’яті, побудовані на основі РЗЛЗЗ. Їх функціону-
вання може бути представлено системою рівнянь
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
−−
−
−
−
,)),...,((
.......................................
,)),...,((
,),...,(
110
1
110
010
Nn
N
n
n
bkkLf
bkkLf
bkkf
(1)
де ),...,( 10 −= nkkk — невідомий ключ (початковий стан регістрів шифрато-
ра) довжини n біт; ),...,( 10 −= Nbbb — гама, яка при шифруванні побітово
додається до відкритого тексту (сучасні шифратори будуються стійкими до
Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак
Системні дослідження та інформаційні технології, 2008, № 2 31
атак на основі відкритого тексту, тому гаму вважають відомою); N — кіль-
кість наявних біт гами (вважається, що доступна достатня кількість гами);
L — деякий лінійний оператор (описує зміну станів РЗЛЗЗ); →nGFf )2(:
)2(GF→ — ускладнююча функція. Оператор L та ускладнююча функція
f також відомі, оскільки відомою вважається вся конструкція шифратора.
Цією схемою описуються фільтруючі шифратори, побудовані на одно-
му РЗЛЗЗ, шифратори на декількох РЗЛЗЗ із нелінійно скомбінованими ви-
ходами, а також будь-які шифратори без додаткової пам’яті (чи їх частини)
на лінійних регістрах зсуву з регулярним (відомим) законом руху. Всі змінні
розглядаються над полем )2(GF , хоча ідея атаки, в принципі, може бути
розширена і на довільні скінченні поля. Задача криптоаналізу — знайти не-
відомий ключ k .
2. АЛГЕБРАЇЧНА АТАКА НА ПОТОКОВІ ШИФРАТОРИ
Наведемо основні ідеї та результати, отримані Куртуа та Маєром у робо-
ті [2], де вперше запропоновано та розробляються алгебраїчні атаки на ши-
фратори, які описуються системою (1).
Нехай ),...,(),...,()( 1010
t
n
t
n
ttt sskkLkLs −− === — стан шифратора (за-
повнення РЗЛЗЗ) в момент часу t . Тоді рівняння (1) будуть мати вигляд
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
−
− ,)(
....................
,)(
,)(
1
1
1
1
0
0
N
N bsf
bsf
bsf
(2)
де для будь-якого індексу t , ts — лінійна функція від ключа k (запис
)(kLt позначає t -й степінь лінійного оператора L , тоді як ts — заповнення
РЗЛЗЗ у момент часу t , тут t є індексом). На функцію f накладаються ви-
моги по забезпеченню стійкості шифратора проти різних методів криптоа-
налізу. Зокрема, функцію f вибирають достатньо високого степеня (під
степенем функції розуміється степінь поліному Жегалкіна, яким подаєтсья
функція). Це робиться для того, щоб систему (2) важко було розв’язати ме-
тодом лінеаризації, при якому кожний терм поліному замінюється новою
змінною, і система (2) перетворюється на систему лінійних рівнянь з вели-
кою кількістю змінних. Як правило, функція f використовує лише nk << з
її вхідних аргументів. Таким чином, набір рівнянь (2) — це сильно перевиз-
начена система нелінійних рівнянь від n змінних деякого степеня kr ≤ , де
k — кількість суттєвих аргументів функції f . На практиці n часто лежить
у діапазоні 25680… , k — у діапазоні 1710… , r близьке до k .
С.О. Пометун
ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 32
Метою алгебраїчної атаки є отримання іншої системи (3) степеня
rk <′ , яка випливає з системи (2), але не є еквівалентною їй. Для цього рів-
няння (2) домножаються на деяку функцію )( tsg , і отримуємо
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
−
−
−− ).()()(
.....................................
),()()(
),()()(
1
1
11
1
1
11
0
0
00
N
N
NN sgbsgsf
sgbsgsf
sgbsgsf
(3)
Для простоти позначимо суттєві аргументи функцій f та g через
),...,( 10 −= kxxx і будемо вважати, що f та g — функції від k аргументів.
Виявляється, що в багатьох випадках можна підібрати таку g , що для сте-
пенів ( deg ) буде виконуватись ))((deg))()((deg xfxgxf < . Наприклад, як-
що 16325421)( xxxxxxxxxf ++= , то при 1)( 2 += xxg
=+++= )]1)([(deg))()((deg 216325421 xxxxxxxxxxgxf
=++++= )]1()1()[(deg 212263531 xxxxxxxxx
4))((deg2)1(deg 21 =<=+= xfxx ,
бо 0)1( 22 =+xx , )2(2 GFx ∈ .
Степінь правої частини (3) дорівнює ))((deg xg або нулю в залежності
від того, tb дорівнює одиниці чи нулю.
Випадок, коли до системи (3) включають всі рівняння з (2) ( ≤)(deg xg
)()(deg xgxf≤ ) назвемо сценарієм атаки А1.
Якщо степінь )(xg надто великий, тобто )(deg)()(deg xfxgxf < та
)(deg)()(deg xgxgxf < , то до системи (3) записують лише ті рівняння, для
яких 0=tb (сценарій атаки А2).
Також можливий випадок, коли 0)()( =xgxf тотожньо, і <))((deg xg
))((deg xf< , тоді до (3) записують тільки ті рівняння, для яких 1=tb , і сис-
тема матиме вигляд }1:{,0)( =∈= t
t bttsg (сценарій атаки А3).
Отриману систему меншого степеня (3) часто розв’язувати простіше
(тобто для розв’язання буде потрібно менше обчислювальних операцій), бо
її степінь менший. Зазвичай це робиться методом лінеаризації або його мо-
дифікаціями.
Доведено твердження, що визначає умови, за яких, незалежно від фун-
кції f , степінь системи (2) може бути знижений [2].
Твердження 1. Для будь-якої функції )2()2(: GFGFf k → існує функ-
ція 0)( ≠xg степеня не більше, ніж ⎡ ⎤2/k , така, що степінь )()( xgxf не
Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак
Системні дослідження та інформаційні технології, 2008, № 2 33
більше, ніж ⎣ ⎦2/k (і може дорівнювати нулю), де ⎡ ⎤2/k , ⎣ ⎦2/k — відповід-
но верхнє і нижнє округлення числа 2/k до найближчого цілого.
Наслідок. Можна вибрати таку функцію )(xg , коли незалежно від ви-
браного сценарію атаки степінь системи (3) не перевищує ⎡ ⎤2/k .
Доведення твердження 1 також дає конструктивний шлях знаходження
функції )(xg зі складністю порядку k32 операцій.
В принципі можна розглядати випадки, коли рівняння отриманої сис-
теми (3) не будуть низького степеня, але вони будуть наближатися з висо-
кою точністю рівняннями низького степеня. Це утворює сценарії атак Б1–Б3.
3. ФОРМАЛІЗАЦІЯ АЛГЕБРАЇЧНОЇ АТАКИ
Наведемо запропоновану в даній роботі формалізацію описаної вище алгеб-
раїчної атаки (з узагальненням на сценарії Б1–Б3). Вводемо поняття кореля-
ції за відомого значення функції та розширення булевої функції, що дасть
змогу описати алгебраїчну атаку на потокові шифратори без пам’яті як ко-
реляційну атаку в термінах введеної кореляції.
Фактично вище мова йшла про спрощення розв’язання системи нелі-
нійних рівнянь вигляду (2) шляхом заміни їх на систему (3).
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
⇒
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
−
−
−−
−
− ).()()(
...................................
),()()(
),()()(
,)(
...................
,)(
,)(
1
1
11
1
1
11
0
0
00
1
1
1
1
0
0
N
N
NN
N
N sgbsgsf
sgbsgsf
sgbsgsf
bsf
bsf
bsf
Тут і далі ⇒ позначає логічне слідування (імплікацію), а ⇔ — еквіва-
лентність.
Виграш в тому, що система (3) може розв’язуватися простіше. У дано-
му випадку вона має менший степінь. Програш — можливість появи зайвих
коренів.
В середньому (за умови збалансованості функцій f та g ) кожному рів-
нянню системи (3), які після перейменування аргументів мають вигляд
)()()( xgaxgxf = , задовольняє 4/3 всіх аргументів (окрім тих, що задово-
льняють одночасно рівнянням 1)( =xg та 1)( += axf ). Вважаємо, що рів-
няння системи (3) — незалежні, тоді для відсіювання всіх зайвих коренів
необхідна така кількість рівнянь N , що nN 2/1~)4/3( ( n2 — кількість різ-
них можливих розв’язків). Звідки nnN 4,2)2/1(log 4/3 ≈= . Для незбалансо-
ваних функцій зміниться лише константа перед n . Для розв’язання системи
(3) методом лінеаризації необхідно близько nC
fgk
i
i
n 4,2
)(deg
0
>>∑
=′
=
рівнянь,
тому зайвих коренів практично ніколи немає.
С.О. Пометун
ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 34
Заміна системи (2) на (3) для кожного окремого рівняння запису-
ється так: )()()()( xgaxgxfaxf =⇒= , але +⇔= )(()()()( xfxgaxgxf
aaxga =++ )() . Позначимо axgaxfxha ++≡ )())(()( , тоді маємо
axha =)( , і заміна (2) на (3) запишеться так:
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=
=
=
⇒
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
−
−
−
−
−
.)(
.................
,)(
,)(
,)(
.................
,)(
,)(
1
1
1
1
0
0
1
1
1
1
0
0
1
1
0
N
N
b
b
b
N
N bsh
bsh
bsh
bsf
bsf
bsf
N
(4)
Для більш ґрунтовного опису зручно ввести означення.
Означення 1. Множиною a -значень функції f назвемо множину
})(:)2({)( axfGFxfX k
a =∈= всіх аргументів функції f , на яких вона
приймає конкретне значення )2(GFa∈ .
Так, )(0 fX — множина нулів .f Будь-яка булева функція f взаємно-
однозначно визначається множиною своїх a -значень k
a GFX )2(⊂ .
Мають місце рівності )1()( 1 += + fXfX aa , )()( 0 fXafX a =+ ,
)()()( 000 hXfXhfX ∪= , )()()( 111 hXhXhfX ∩= , kGFfXfX )2()()( 10 =⊕ .
Означення 2. Функцію )(xh назвемо a -розширенням )(xf , якщо
)()( hXfX aa ⊂ .
Тепер імплікацію axhaxf =⇒= )()( можна записати так: )(xh є
a -розширенням )(xf або )()( hXfX aa ⊂ .
Має місце еквівалентність )()()()( 11 fXhXhXfX aaaa ++ ⊂⇔⊂ , тоб-
то, наприклад, якщо h є 0 -розширенням f , то f є 1-розширенням h .
Будь-яка функція завжди має два тривіальних розширення: ⊂)(0 fX
)0(0X⊂ , )1()( 11 XfX ⊂ .
Означення 3. Функцію )(xh назвемо розширенням )(xf (позначимо
)()( hXfX ⊂ ), якщо )()( 00 hXfX ⊂ або )()( 11 hXfX ⊂ ).
За таких означень, якщо )(xh є розширенням )(xf , то й )(xf є роз-
ширенням )(xh .
Доведемо наступне основне твердження про еквівалентність.
Твердження 2. Для будь-якої )(xh , яка є a -розширенням )(xf , існує
)(xg така, що ,)()()()( xgaxgxfaxh =⇔= і навпаки, для будь-якої )(xg
існує єдина )(xh така, що )(xh є a -розширенням )(xf та =)()( xgxf
axhxga =⇔= )()( .
Доведення.
1. Існування )(xg .
Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак
Системні дослідження та інформаційні технології, 2008, № 2 35
За умовою )()( hXfX aa ⊂ . Покладемо AfXhXgX aa ⊕= )(\)()(0 , де
)( fXA a⊂ — довільна підмножина a -значень функції f . Тоді ⇔= agfg
aagaf =++⇔ )( та
=∪=∪+=+=++ )()()()())(())(( 0000 gXfXgXafXgafXagafX aa
=∪∪∪=⊕∪= AfXfXhXfXAfXhXfX aaaaaaa )())(\)(()(])(\)([)(
)())(\)(()( hXfXhXfX aaaa =∪= .
Отже,
hagaf =++ )( , тобто ahgagf =⇔= .
2. Існування )(xh .
aagafgafg =++⇔= )( , отже шукана agafh ++= )( .
Зауваження. Фактично це твердження означає, що домноження рів-
няння axf =)( на деяку функцію )(xg (метод алгебраїчної атаки) еквівале-
нтне його заміні рівнянням axh =)( , де )(xh — a -розширення )(xf (див.
рівняння (4)). Більше того, кожному розширенню )(xh відповідає )(2 fX a
різних )(xg (відповідно до кількості множин A ), і такий опис алгебраїчної
атаки, на відміну від домноження, не є надлишковим.
Метод алгебраїчної атаки також припускає, що )(xh може не бути
низького степеня, але з високою ймовірністю наближається функцією
низького степеня )(xh′ . Тобто axhaxf =⇒= )()( (або, що теж саме,
1)|( === affhP ) та ε−==′ 1)( hhP , де ε — маленьке. Тоді
δ−===′ 1)|( affhP , де δ — теж маленьке. Для опису цього випадку уза-
гальнимо поняття a -розширення функції і введемо кореляцію за відомого
значення функції.
Означення 4. Кореляцією функцій )(xh та )(xf за відомого значення
axf =)( назвемо величину
)|()|(),( affhPaffhPfhCa =≠−=== .
Якщо 0)( == afP , то 1),( =fhCa для будь-якої )(xh .
Нагадаємо означення звичайної кореляції.
Означення 5. Кореляцією булевих функцій )(xh та )(xf називають
величину
)()(),( fhPfhPfhC ≠−== .
Мають місце рівності
==≠−=== )|()|(),( affhPaffhPfhCa
===−−=== ))|(1()|( affhPaffhP
,1)|(21)|(2 −===−=== afahPaffhP
С.О. Пометун
ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 36
0),1(),( =++ fhCfhC aa .
Таким чином, запис ε−= 1),( fhCa означає, що функція )(xh є апрок-
симацією з точністю ε−1 функції )(xf в термінах кореляції за відомого
значення axf =)( . Фактично це звичайна апроксимація, але не на всій мно-
жині аргументів kGF )2( , а на підмножині )( fX a a -значень )(xf .
Твердження 3. Функція )(xh є a -розширенням )(xf тоді і лише тоді,
коли кореляція )(xh та )(xf за відомого значення axf =)( дорівнює 1.
Доведення.
1. Необхідність.
Нехай ahaf =⇒= , тоді
1121)|(2),( =−=−=== afahPfhCa .
2. Достатність.
)(1)|(11)|(2 ahafafahPafahP =⇒=⇒===⇒=−== .
Тепер, в термінах введених означень ідея алгебраїчної атаки має такий
вигляд:
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=
=
=
⇒
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
−
−
−
−
−
.)(
.......................
,)(
,)(
,)(
...................
,)(
,)(
1
1
1
1
0
0
1
1
1
1
0
0
1
1
0
N
N
b
b
b
N
N bsh
bsh
bsh
bsf
bsf
bsf
N
Відповідні кореляції для функцій 0h та 1h дорівнюють: =),( 00 fhC
01 ε−= та 111 1),( ε−=fhC . Ймовірності істинності рівнянь системи (4)
2/1
2
1),(
)0|0( 0
0
0 ε−=
+
===
fhC
fhP
та
2/1
2
1),(
)1|1( 1
1
1 ε−=
+
===
fhC
fhP .
Якщо для якогось )2(GFa∈ 0=aε , то маємо окремий випадок
1),( =fhCa , axhaxf =⇒= )()( , що дає детерміновану систему. Цей випа-
док описує сценарії А1–А3. Випадок 0≠ε дає систему зі спотвореними
правими частинами (ймовірності спотворення для 0h та 1h — 2/0ε та
2/1ε відповідно) і описує сценарії Б1–Б3 (див. розд. 2).
Таким чином, алгебраїчна атака зведена до пошуку хороших апрокси-
мацій ускладнюючої функції в термінах введеної кореляції, тобто представ-
лена як певний вид вже досить давно відомих кореляційниих атак [7, 8].
Твердження 4. За умови збалансованості )(xf має місце співвідно-
шення
)),(),((),( 102
1 fhCfhCfhC += .
Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак
Системні дослідження та інформаційні технології, 2008, № 2 37
Доведення.
=−==+−===+ )1)1|(21)0|(2()),(),(( 2
1
102
1 ffhPffhPfhCfhC
=−==+=== 1)1|()0|( ffhPffhP
=−===+==== 1)1(/)1,()0(/)0,( fPffhPfPffhP
),(1)(21)2/1(/))1,()0,(( fhCfhPffhPffhP =−==−==+=== .
Наслідок. )),(,),((max),( 10 fhCfhCfhC ≤ .
Твердження 5. При фіксованій )(xf та випадковій )(xh випадкові ве-
личини ),(0 fhC та ),(1 fhC є незалежними.
Доведення. ),(0 fhC є функцією від звуження )(xh на множину
)(0 fX , а ),(1 fhC — функцією від звуження )(xh на множину )(1 fX .
Оскільки 0)()( 10 =∩ fXfX , то ці звуження розподілені незалежно, зна-
чить, і ),(0 fhC та ),(1 fhC теж незалежні.
Приклад до тверджень 4, 5.
2121 ),()( xxxxfxf +== , 1),()( 2121 +== xxxxhxh ,
2/1121)(2),( 4
3 =−⋅=−== fhPfhC ,
0121)0|0(2),( 2
1
0 =−⋅=−=== fhPfhC ,
11121)1|1(2),(1 =−⋅=−=== fhPfhC ,
2/1)10()),(),((2/1),( 2
1
102
1 =+=+== fhCfhCfhC .
Твердження 4 та 5 теоретично обґрунтовують можливість існування
хороших (з досить високим абсолютним значенням кореляції) низькостепе-
невих апроксимацій в термінах 0C та 1C , навіть якщо не існує хороших
низькостепеневих апроксимацій в термінах звичайної кореляції C . Наслідок
з твердження 4 означає, що апроксимація хоча б за однією з кореляцій 0C
чи 1C завжди є, принаймні, не гіршою, ніж апроксимація за звичайною
кореляцією C . Тобто, якщо функція не має хороших апроксимацій по
відношенню до кореляцій 0C та 1C , то вона автоматично не має хороших
апроксимацій по відношенню до кореляції C , але не навпаки. Це означає,
що кореляція за відомого значення функції є в певному розумінні
узагальненням звичайної кореляції. Відповідно алгебраїчні атаки можна
розуміти не просто як певний вид кореляційних атак, а як їх узагальнення,
завдяки узагальненню поняття кореляції булевих функцій.
Спираючись на результати, отримані в роботі [5], де уніфікуються ал-
гебраїчні атаки на потокові шифратори без пам’яті, з пам’яттю та S-блоки
(відображення mn GFGF )2()2( → , які часто є основою блокових шифрато-
рів), можна стверджувати, що алгебраїчні атаки на блокові шифратори та
С.О. Пометун
ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 38
потокові шифратори з пам’яттю теж можуть бути зведені до кореляційних в
термінах введеної кореляції.
4. ЗАСТОСУВАННЯ АТАКИ
Таким чином, вразливість того чи іншого шифратора до алгебраїчної атаки
визначається наявністю низькостепеневих функцій ,)(xh сильно скорельо-
ваних (часто з кореляцією, що дорівнює 1) з функцією )(xf , в термінах ко-
реляції за відомого значення axf =)( , тобто наявністю наближень (апрок-
симацій) в термінах такої кореляції для 0=a або 1=a . Більш детально
набір рівнянь (2) розбивається на дві приблизно рівні за потужністю множи-
ни }0:|0)({0 === t
t btsfA та }1:|1)({1 === t
t btsfA (нагадаємо, що гама
відома). І якщо, наприклад, знайдеться така низькостепенева )(0 xh , що
ε−= 1),( 00 fhC , то будується множина рівнянь }0:|0)({ 00 ===′ t
t btshA .
Складність її розв’язання часто набагато менша, ніж складність розв’язання
вихідної системи (при 0=ε 0A′ детермінована, а при 0≠ε має спотворені
праві частини з ймовірністю спотворення 2/ε ). Аналогічні дії виконуються
для множини 1A , якщо )(xf добре наближається деякою низькостепеневою
функцією в термінах кореляції 1C .
Приклади з практики. Для фільтруючої функції )(xf (63-го степеня
від 128 змінних) шифратора Toyocrypt знайшлися такі функції )(0 xh , )(1 xh
3-го степеня, що 1),( 00 =fhC та 1),( 11 =fhC (!) [2]. Складність розв’язання
нової системи порядку 492 операцій. Така атака може бути реалізована на
практиці. Степінь ускладнюючої функції знижений набагато нижче границі,
яка дається твердженням 2, тому можна припустити, що шифратор не роз-
роблявся стійким проти цієї атаки. Для фільтруючої функції )(xg (6-го сте-
пеня від 10 змінних) шифратора LILI-128 знайшлися такі )(),( 10 xhxh 4-го
степеня, що 1),( 00 =fhC та 1),( 11 =fhC [2]. Це теж суттєвий виграш (адже
при оцінці складності криптоаналітичних атак розробники вважали, що сте-
пінь ускладнюючої функції дорівнює все ж таки шести, бо алгебраїчні атаки
ще були невідомі). Окрім того, твердження 2 дає верхню границю для зни-
жуваного степеня. В цьому випадку ⎡ ⎤ 452/10 >= , тобто ускладнююча фу-
нкція вибрана не оптимально.
Варто зауважити, що придатні тільки нетривіальні апроксимації, оскі-
льки завжди мають місце рівності 1),1(,1),0( 10 == fCfC , але рівняння
00 = та 11= не дають ніякої інформації про ключ.
Однією з основних вимог до ускладнюючої функції шифратора (для за-
побігання кореляційним атакам) є неможливість її хорошого наближення за
допомогою афінних функцій. Чому ж перевірялась можливість наближення
в термінах звичайної кореляції C , а кореляції 0C та 1C випали з уваги? Од-
на з можливих відповідей дається таким твердженням.
Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак
Системні дослідження та інформаційні технології, 2008, № 2 39
Твердження 6. Якщо )(),( xfxh — збалансовані функції, то
),(),(),( 10 fhCfhCfhC == .
Доведення. Для збалансованих функцій )(xf та )(xh мають місце рі-
вності
⇒
⎪⎭
⎪
⎬
⎫
===+====
===+====
2/1)1,0()1,1()1(
2/1)1,0()0,0()0(
hfPhfPhP
hfPhfPfP
)1,1()0,0( =====⇒ hfPhfP .
Отже, для будь-якого )2(GFa∈
=−==+===−== 1))1,1()0,0((21)(2),( fhPfhPfhPfhC
=−
==
=−=== 1
2/1
),(21),(4 afahPafahP
),(1)|(21
)(
),(2 fhCafahP
afP
afahP
a=−===−
=
==
= .
Взявши до уваги, що ускладнююча функція )(xf шифратора завжди
вибирається збалансованою і будь-яка невироджена афінна функція )(xl
теж збалансована, бачимо, що, поки )(xf наближалася афінними функція-
ми )(xl , різниці між цими кореляціями не було. Різниця проявляється лише
тоді, коли )(xf наближається незбалансованими (тобто, з необхідністю не
афінними) функціями )(xh , що й має місце в алгебраїчних атаках.
ВИСНОВКИ
У роботі досліджувались алгебраїчні атаки на потокові шифратори без
пам’яті. Було введено новий тип кореляції булевих функцій — кореляцію за
відомого значення функції. Це дало змогу об’єднати шість різних сценаріїв
алгебраїчної атаки в єдине логічне ціле. До цього досліджувалися лише три
простіші сценарії, які приводили до детермінованих систем рівнянь (у за-
пропонованому описі атаки це відповідає пошуку апроксимацій ускладню-
ючої функції з кореляцією, що дорівнює строго одиниці). Показано, що вве-
дена кореляція є в певному сенсі узагальненням звичайної кореляції, і тому
алгебраїчні атаки (на всі типи шифраторів) можуть розглядатися як узагаль-
нення кореляційних атак.
Запропонований опис дозволяє теоретично досліджувати шість сценарі-
їв атаки одночасно, а також може бути теоретичою основою для розробки
алгоритмів перевірки шифратора на вразливість проти всіх шести сценаріїв
атаки.
Захищеність інформації (фізична, організаційна і криптографічна) є
принципово важливою властивістю інформації у сучасному світі. Дана
робота може бути корисною для покращення криптографічного захисту
інформації.
С.О. Пометун
ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 40
ЛІТЕРАТУРА
1. Courtois N., Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of
equations, Advances in Cryptology // Lecture Notes in Computer Science. —
2002. — 2501. — Р. 267–287.
2. Courtois N., Meier W. Algebraic Attacks on Stream Ciphers with Linear Feedback //
Ibd. — 2003. — 2656. — P. 345–359.
3. Schaumuller-Bichl I. Cryptanalysis of the Data Encryption Standard by the Method
of Formal Coding // Ibd. — 1983.— 149. — Р. 235–255.
4. Armknecht F., Krause M. Algebraic attacks on Combiners with Memory // Ibd. —
2003. — 2729. — Р. 162–176.
5. Armknecht F. On the Existence of low-degree Equations for Algebraic Attacks //
http://eprint.iacr.org/2004/185/.
6. Courtois N. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback // Lec-
ture Notes in Computer Science. — 2003. —2729. — Р. 177–194.
7. Siegenthaler T. Cryptanalyst's representation of nonlinearly filtered ml-sequences //
Ibd. — 1986. — 219. — Р. 103–110.
8. Meier W., Staffelbach O. Fast correlation attacks on certain stream ciphers // Journal
of Cryptology. — 1989. — I, № 3. — Р. 159–176.
Надійшла 08.11.2006
|
| id | journaliasakpiua-article-109717 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:23:03Z |
| publishDate | 2017 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/56/cdaa7c31f42b10cba4da82e3f9303c56.pdf |
| spelling | journaliasakpiua-article-1097172018-04-11T11:06:21Z Algebraic attacks on stream ciphers as generalization of correlation attacks Алгебраические атаки на потоковые шифраторы как обобщение корреляционных атак Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак Pometun, S. O. New Boolean’s function concepts, such as correlation with a known function value and Boolean’s function extension, are introduced. Algebraic attacks on stream ciphers with linear feedback are shown to be reduced to approximation of the nonlinear filter using low-degree polynomials in terms of the correlation with the known function value. This kind of correlation can also be used in describing algebraic attacks on other types of ciphers. Предложены новые теоретические понятия для булевых функций: корреляция при известном значении функции и ее расширение. Доказано, что алгебраическая атака на потоковые шифраторы без памяти сводится к аппроксимации усложняющей функции шифратора низкостепенными полиномами в терминах введенной корреляции. Эта корреляция может быть использована также и для описания алгебраических атак на другие типы шифраторов. Запропоновано нові теоретичні поняття для булевих функцій: кореляція при відомому значенні та розширення функції. Доведено, що алгебраїчна атака на потокові шифратори без пам’яті зводиться до апроксимації ускладнюючої функції шифратора низькостепеневими поліномами в термінах введеної кореляції. Ця кореляція може бути використана і для опису алгебраїчних атак на інші типи шифраторів. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2017-09-08 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/109717 System research and information technologies; No. 2 (2008); 29-40 Системные исследования и информационные технологии; № 2 (2008); 29-40 Системні дослідження та інформаційні технології; № 2 (2008); 29-40 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/109717/104770 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Pometun, S. O. Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак |
| title | Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак |
| title_alt | Algebraic attacks on stream ciphers as generalization of correlation attacks Алгебраические атаки на потоковые шифраторы как обобщение корреляционных атак |
| title_full | Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак |
| title_fullStr | Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак |
| title_full_unstemmed | Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак |
| title_short | Алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак |
| title_sort | алгебраїчні атаки на потокові шифратори як узагальнення кореляційних атак |
| url | https://journal.iasa.kpi.ua/article/view/109717 |
| work_keys_str_mv | AT pometunso algebraicattacksonstreamciphersasgeneralizationofcorrelationattacks AT pometunso algebraičeskieatakinapotokovyešifratorykakobobŝeniekorrelâcionnyhatak AT pometunso algebraíčníatakinapotokovíšifratoriâkuzagalʹnennâkorelâcíjnihatak |