Файл: 2015.05.26 - Матеріали ХVІ Міжнародної науково-практичної конференції «Безпека інформації в інформаційно-телекомунікаційних системах».pdf

УДК 681.3.06:519.248.681 
 

ДОСЛІДЖЕННЯ ВПЛИВУ ПАРАМЕТРІВ КУБІЧНОЇ АТАКИ 

НА ЙМОВІРНІСТЬ ЇЇ УСПІХУ 

*В. Б. Сергієнко, аспірант; **Л. О. Завадська, канд. ф.-м. наук, доц. 

Національний технічний університет України 

«Київський політехнічний інститут» 

*e-mail: visergienko@ukr.net 

**e-mail: ludazavadska@gmail.com 

В  умовах  сучасних  масштабів  електронного  документообігу  важливим  питанням  є 

захист  інформаційних  ресурсів.  Для  забезпечення  надійного  захисту  необхідне  поєднання 

організаційних,  технічних  і  криптографічних  методів.  Зокрема,  важливу  роль  у 

криптографічному захисті інформації відіграють симетричні криптосистеми. Оскільки вони є 

широко  розповсюдженими,  то  задача  розробки,  дослідження,  удосконалення  методів 

криптоаналізу  таких  схем  шифрування  задля  забезпечення  їх  стійкості  є  важливою  в 

практичному  і  теоретичному  аспекті.    Інструментом  для  аналізу  в  цьому  випадку  можуть 

виступати різні види криптоатак, одним з яких є новий перспективний вид атаки – кубічні 

атаки,  вперше  описані  у  статті  [1],  опублікованій  Дінуром  та  Шаміром  (Itai  Dinur,  Adi 

Shamir)  у  2008  році  й  застосовані  до  учасника  конкурсу  eStream  потокових  шифрів  під 

назвою Trivium. Пізніше, у 2009 році, світ побачила оновлена і доповнена версія цієї статті 

[2].  І  хоч  цей  вид  атаки  розроблявся  з  прицілом  на  потокові  криптосистеми,  основні  ідеї 

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

Об’єктом  дослідження  даної  статті  є  кубічні  атаки  на  криптосистеми  з  наявними 

відкритими змінними. У роботі розглядається питання застосовності кубічних атак за умови 

використання  лише  макстермів  заданого  степеня.  Вводиться  поняття  сприятливої  функції 

для кубічної атаки. Функція визнається сприятливою, якщо можливе успішне застосування 

до  неї  кубічної  атаки  (з  повним  визначенням  секретного  ключа)  з  макстермами  тільки 

певного визначеного степеня. 

Як  результат  досліджень  отримано  математичний  вираз  для  кількості  сприятливих 

функцій  в  залежності  від  кількості  відкритих  і  секретних  змінних,  при  використанні 

макстермів  лише  першого  (мінімального)  степеня,  а  також  степеня,  на  одиницю  меншого, 

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

Теоретичні  результати  перевірено  за  допомогою  програмних  розрахунків.  Також  у  роботі 

проаналізована  імовірність  успіху  атаки  для  функцій  з  різними  кількостями  змінних,  для 

мінімального  і  максимального  степеня  макстермів.  Звісно,  за  умови  використання 

макстермів  малих  степенів,  імовірність  успішної  атаки  є  дуже  малою  за  реальних  значень 

кількості відкритих та секретних змінних. Проте, знаючи величину цієї імовірності, можна 

оцінити  максимальний  степінь  макстермів,  що  забезпечує  прийнятний  рівень  імовірності 

успіху кубічної атаки. 

Окрім  виведених  математичних  залежностей,  у  роботі  також  наводяться  певні 

міркування  про  загальний  вигляд  формули  для  опису  кількості  сприятливих  функцій,  для 

довільного степеня макстерма, що можуть служити підґрунтям для подальших досліджень за 

даною  тематикою.  У  той  же  час  розглядувана  задача  представляє  самостійний  інтерес  з 

точки зору теорії булевих функцій та комбінаторики. 

Література 

1.  Dinur, I., Shamir, A. Cube attacks on tweakable black box polynomials. Cryptology ePrint 

Archive, 2008/385. [Online] Available at: http://eprint.iacr.org/2008/385.pdf. 

2.  Dinur, I., Shamir, A. Cube attacks on tweakable black box polynomials. EUROCRYPT, 

vol. 5479 of Lecture Notes in Computer Science Springer, 2009, p. 278-299. 

21 

В.Б. Сергієнко, Л.О. Завадська Дослідження впливу параметрів кубічної атаки на 

ймовірність її успіху 

Отримано математичний вираз для кількості сприятливих функцій для кубічної атаки 

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

застосуванні  атаки)  в  залежності  від  кількості  відкритих  і  секретних  змінних,  при 

використанні  макстермів  лише  першого  (мінімального)  степеня,  а  також  степеня,  на 

одиницю  меншого,  ніж  степінь  шифруючої  функції  (тобто,  макстермів  максимально 

можливого степеня), проаналізована ймовірність успіху атаки для обох випадків. Теоретичні 

результати перевірено за допомогою програмних розрахунків. У роботі також наведені певні 

міркування  про  загальний  вигляд  формули  для  довільного  степеня  макстерма,  що  є 

підґрунтям для подальших досліджень за даною тематикою. 

Ключові слова: кубічні атаки, макстерм, імовірність успіху. 
V.B. Sergienko, L.O. Zavadska The research of influence of Cube attack parameters on 

its success rate 

In this paper, we present mathematical expression for number of Boolean functions, to 

which Cube attack with maxterms of minimal (degree 1) and maximal (encryption function degree 
reduced by 1) degree can be successfully applied. It depends on encryption function degree and on 
the number of its secret and public variables. Theoretical results were verified using computer 
calculations. We also provide analysis of cube attack’s success rate for encryption functions with 
different numbers of variables, for both minimal and maximal maxterm degree, as well as some 
general thoughts on mathematical expression for an arbitrary maxterm degree case, which form a 
basis for further research in this field. 

Keywords: cube attacks, maxterm, success rate. 

22 

УДК 003.26:512.57 

УЗАГАЛЬНЕНА МОДЕЛЬ СИМЕТРИЧНОГО ШИФРУ 

А.В. Фесенко, асистент 

Фізико-технічний інститут Національного технічного університета України «КПІ» 

e-mail: 

andrey.fesenko@gmail.com

Останнім  часом  багато  уваги  приділяється  дослідженню  загальних  математичних  моделей 

криптографічних  систем,  що  представляють  собою  алгебраїчні  структури  –  багатоосновні 

універсальні алгебри. Використання таких абстрактних моделей дозволяє виявити основні принципи 

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

було запропоновано в 1949 році К. Шенноном. Оскільки модель була універсальною і досить вдало 

описує практично всі відомі симетричні шифри, вона майже не зазнала змін з того часу. 

Означення 1. [3] Алгебраїчна модель симетричного (детермінованого, скінченного) шифру є 

універсальною алгеброю 

)

,

,

,

(

f

Y

X

K

A

=

з системою носіїв 

)

,

,

(

Y

X

K

, де 

K

, 

X

та 

Y

 – 

непорожні 

скінченні  множини,  і  однією  алгебраїчною  операцією 

Y

X

K

f

→

×

:

,  яка  задовільняє  наступним 

умовам: (а) 

Y

X

K

f

→

×

:

 – 

сюр’єкція; (б) для довільних значень 

K

k

∈

та 

X

x

x

∈

2

1

,

виконується 

співвідношення 

≠

⇒

≠

)

,

(

1

2

1

x

k

f

x

x

)

,

(

2

x

k

f

. 

Скінченні  множини 

K

, 

X

,  та 

Y

називають  відповідно  множиною  ключів,  множиною 

відкритих текстів та множиною шифротекстів, а відображення 

f

 – 

функцією шифрування шифру 

A

.  Шифротекст 

Y

y

∈

називається  результатом  шифрування  відкритого  тексту 

X

x

∈

з 

використанням ключа 

K

k

∈

, якщо виконується співвідношення 

y

x

k

f

=

)

,

(

. Для довільного ключа 

K

k

∈

часткова  функція 

Y

X

f

k

→

:

функції  шифрування 

f

,  де 

)

,

(

)

(

x

k

f

x

f

k

=

,  називається 

шифруючим перетворенням шифру 

)

,

,

,

(

f

Y

X

K

A

=

, яке відповідає ключу 

K

k

∈

. Для довільного 

ключа 

K

k

∈

частково визначена ліва обернена функція 

X

Y

f

k

→

−

:

1

називається розшифровуючим 

перетворенням  шифру 

A

,  причому  для  довільних  значень  ключа 

K

k

∈

й  елемента 

X

x

∈

має 

місце співвідношення 

x

x

f

f

k

k

=

−

))

(

(

1

. 

Алгебраїчна  модель  симетричного  шифру  означення  1  має  певні  недоліки,  які,  наприклад, 

зазначені  в  роботі  [2],  а  саме  –  для  довільного  ключа 

K

k

∈

розшифровуюче  перетворення 

X

Y

f

k

→

−

:

1

шифру 

)

,

,

,

(

f

Y

X

K

задано  не  зовсім  коректно,  оскільки  воно  є  невизначеним  для 

елементів 

Y

y

∈

, які не належать множині 

)

( X

f

k

. 

Більш того, за умов перешкод в каналах зв’язку 

аргументами  шифруючого  та  розшифровуючого  перетворень  можуть  бути  елементи  не  сімейства 

основних  множин.  Як  правило  визначення  ефективного  шифру  не  є  строгим  за  такої  моделі.  Для 

розв’язання наведених проблем пропонується узагальнена модель симетричного шифру. 

Означення 2.  Нехай 

Σ

  – 

непорожній  алфавіт.  Узагальнена  модель  шифру  є  алгебраїчна 

система 

)

,

,

(

*

f

r

l

Σ

з  носієм 

*

Σ

,  унарною  алгебраїчною  операцією 

*

*

:

Σ

→

Σ

l

і  кватернарним 

відношенням 

f

r

,  заданим  на  множині 

( )

4

*

Σ

,  яке  задовольняє  наступним  умовам:  для  довільних 

значень 

*

2

1

,

Σ

∈

t

t

якщо 

2

1

t

t

=

, то 

)

(

)

(

2

1

t

l

t

l

=

; для довільного значення 

N

n

∈

існують значення 

*

,

,

,

Σ

∈

y

x

k

t

такі,  що 

n

t

>

і 

f

r

y

x

k

t

∈

)

,

,

,

(

;  для  довільних  значень 

*

,

,

,

Σ

∈

y

x

k

t

якщо 

f

r

y

x

k

t

∈

)

,

,

,

(

, то 

)

(

,

,

t

l

y

x

k

≤

; не існує значень 

*

2

1

2

1

,

,

,

,

,

Σ

∈

y

x

x

k

t

t

таких, що 

2

1

t

t

=

, 

2

1

x

x

≠

, 

f

r

y

x

k

t

∈

)

,

,

,

(

1

1

та 

f

r

y

x

k

t

∈

)

,

,

,

(

2

2

;  для  довільних  значень 

*

2

1

2

1

2

1

2

1

,

,

,

,

,

,

,

Σ

∈

y

y

x

x

k

k

t

t

таких,  що 

23 

2

1

t

t

=

, 

f

r

y

x

k

t

∈

)

,

,

,

(

1

1

1

1

та 

f

r

y

x

k

t

∈

)

,

,

,

(

2

2

2

2

,  мають  існувати  значення 

*

3

3

,

Σ

∈

y

t

такі,  що 

1

3

t

t

=

і 

f

r

y

x

k

t

∈

)

,

,

,

(

3

2

1

3

. 

Фактично  означення  2  алгебраїчної  системи 

)

,

,

(

*

f

r

l

Σ

визначає  певну  (нескінченну) 

підмножину 

T

всіх  натуральних  чисел:  значення 

N

n

∈

належить  множині 

T

тоді  й  тільки  тоді, 

коли  існують  значення 

*

,

,

,

Σ

∈

y

x

k

t

такі,  що 

n

t

=

і 

f

r

y

x

k

t

∈

)

,

,

,

(

.  Множина 

T

називається 

множиною  параметрів  безпеки.  З  означення  2  випливає,  що  для  задання  параметру  безпеки 

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

T

n

∈

,  де 

*

1

1

1

,

,

,

Σ

∈

y

x

k

t

, 

f

r

y

x

k

t

∈

)

,

,

,

(

1

1

1

і 

n

t

=

.  Алгебраїчна 

операція 

l

для  параметра  безпеки 

T

n

∈

,  фактично  обмежує  відношення 

f

r

для  всіх  значень 

*

1

,

,

,

Σ

∈

y

x

k

t

, де 

n

t

=

1

, підмножиною 

(

)

4

)

)

(

( t

l

Σ

(або 

( )

4

)

(t

l

Σ

, якщо до алфавіту 

Σ

додати один 

новий символ). Позначимо множину 

4

)

)

(

( t

l

Σ

через 

n

W

. Позначимо через 

n

K

, 

n

X

та 

n

Y

проекції 

відношення 

f

r

за другою, третьою та четвертою компонентою відповідно, коли довжина значення в 

першій компоненті дорівнює 

n

, тобто, наприклад, 

}

)

,

,

,

(

:

,

,

|

{

1

1

*

*

f

n

n

r

y

x

k

t

t

y

x

k

K

∈

Σ

∈

Σ

∈

∃

Σ

∈

=

. 

Отже 

n

n

n

n

W

Y

X

K

⊆

,

,

.  З  означення  2  випливає,  що  відношення 

f

r

визначає  відображення 

n

n

n

n

Y

X

K

f

→

×

:

, оскільки для будь-яких значень 

n

K

k

∈

і 

n

X

x

∈

має існувати така пара значень 

n

t

Σ

∈

1

і 

n

Y

y

∈

, що 

f

r

y

x

k

t

∈

)

,

,

,

(

1

причому значення 

n

Y

y

∈

є спільним для всіх таких пар. Більш 

того  для  довільних  значень 

n

K

k

∈

та 

n

X

x

x

∈

2

1

,

виконується  співвідношення 

≠

⇒

≠

)

,

(

1

2

1

x

k

f

x

x

n

)

,

(

2

x

k

f

.  Отже  узагальнена  модель  шифру  є  класом  шифрів 

{

}

)

,

,

,

(

n

n

n

n

n

f

Y

X

K

=

ℑ

, 

T

n

∈

,  параметризованим  певною  (нескінченною)  підмножиною 

натуральних  чисел  –  множиною  параметрів  безпеки.  Така  узагальнена  модель  шифру  у  разі 

нескінченної  множини  параметрів  безпеки  дозволяє  визначити  відповідну  масову  задачу  та 

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

поняття  ефективності,  використовуючи  стандартний  підхід  з  теорії  складності.  Будемо  називати 

узагальнену  модель  шифру  ефективною  (поліноміальною),  якщо  існує  такий  поліном 

p

,  що  для 

достатньо великих значень 

T

n

∈

для процедур обчислення значення 

n

t

Σ

∈

і 

*

,

,

Σ

∈

y

x

k

таких, що 

f

r

y

x

k

t

∈

)

,

,

,

(

;  обчислення  значення 

)

(t

l

; 

перевірки,  що 

n

K

I

k

∈

, 

n

X

I

x

∈

та 

n

Y

I

y

∈

, 

перевірки 

існування  прообразу  для 

n

Y

I

y

∈

,  породжених  функції 

n

n

n

n

Y

X

K

f

→

×

:

та  частково  визначеної 

функції 

n

n

n

n

Y

X

K

f

→

×

−

:

1

існують детерміновані алгоритми, складність яких не перевищує 

)

(n

p

. 

Література 

1. 

Алексейчук А.Н. Регулярные конгруэнции и строение алгебраических моделей симметричных 

криптосистем / А.Н. Алексейчук, А.И. Романов // Радиотехника. – 2002. – Вып. 126. – С. 42-58. 

2. 

Бабаш А.В.  Криптография  /  А.В. Бабаш,  Г.П. Шанкин  –  Под  ред.  В.П. Шерстюка, 

Э.А. Примаренко. – М.:Солон-Р, 2002. – 512 с. 

А.В. Фесенко Узагальнена модель симетричного шифру 

Побудовано нову узагальнену модель симетричного шифру, яка дозволяє уникнути недоліків 

алгебраїчної моделі шифру за К. Шенноном та більш формально визначити клас ефективних шифрів. 

Ключові слова: алгебраїчна модель, симетричний шифр, алгебраїчна система 

А.V. Fesenko A generalized model of symmetric cipher 

A new generalized model of symmetric cipher  was constructed, which allows to avoid the 

defects of cipher’s algebraic model by Shannon and to define formally a class of efficient ciphers. 

Keywords: algebraic model, symmetric cipher, algebraic structure 

24 

УДК 621.391:519.2 

ДОСЛІДЖЕННЯ ТЕОРЕТИЧНОГО ЗНАЧЕННЯ ОБСЯГУ МАТЕРІАЛУ ПРИ 

МОДЕЛЮВАННІ СТАТИСТИЧНОЇ АТАКИ НА ГЕНЕРАТОР ГАМИ З ЛІНІЙНИМ 

ЗАКОНОМ РЕІНІЦІАЛІЗАЦІЇ ТА ФУНКЦІЄЮ УСКЛАДНЕННЯ, ЩО Є БЛИЗЬКОЮ 

ДО АЛГЕБРАЇЧНО ВИРОДЖЕНОЇ 

*

С.М. Конюшок, канд. техн. наук, доц.; *А.Ю. Сторожук 

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

e-mail: storojs72@gmail.com 

Сучасні  синхронні  потокові  шифри,  що  використовуються  для  захисту  інформації  з 

обмеженим доступом, повинні бути стійкими відносно статистичних атак на основі відомих 

(підібраних) векторів ініціалізації. Атака такого типу можливі на практиці через необхідність 

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

генератора гами (ГГ) потокового шифру [1].  

Одна з перших алгебраїчних атак на основі відомих векторів ініціалізації [2] припускає, 

що  закон  реініціалізації  ГГ  є  лінійним,  а  функція  ускладнення  залежить  від  невеликої 

кількості змінних s. Трудомісткість такої атаки складає О(tsl

2

 + t

2

s

) 

операцій, де t 

–

довжина 

відрізку  гами,  яка  виробляється  генератором  при  кожному  запуску  (новому  значенню 

вектора  ініціалізації);  l 

–

довжина  ключа;  при  цьому  необхідна  кількість  перезапусків 

повинна бути не менше ніж 2

s

.  

Атака [2] узагальнювалась та розвивалась в кількох напрямках [3 

–

 6]

. Наприклад в [4] 

показано,  що  атаку  можна  застосувати  до  генератора  гами  з  алгебраїчно  виродженою 

функцією ускладнення порядку n – s; також розглянутий випадок, коли функція може бути 

невідомою для криптоаналітика. Існує модифікація атаки [2] на генератор гами з функцією 

ускладнення, близькою до афінної булевої функції. Також можна відмітити роботу [7], яка 

описує алгоритм відновлення ключа по єдиному відрізку вихідного зашифрованого тексту, 

але з припущенням, що криптоаналітику відомі знаки цієї послідовності у визначених тактах, 

номера  яких  експоненційно  залежать  від  довжини  початкового  стану  ГГ.  Нарешті,  в  [8] 

запропонована найбільш відома на сьогодні атака такого типу, яка основана на апроксимації 

функції  ускладнення  ГГ  k-мірною  булевою  функцією.  При  визначених  припущеннях 

отримані  оцінки  обсягу  матеріалу,  достатнього  для  проведення  атаки,  а  також  її 

трудомісткості.  

В  докладі  приводяться  результати  моделювання  атаки  [8]  на  деякі  генератори  гами. 

Проведені  експериментальні  дослідження  теоретичного  обсягу  матеріалу,  необхідного  для 

однозначного  відновлення  ключа  за  допомогою  цієї  атаки.  Встановлено,  що  на  практиці 

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

Приведені роз’яснення можливих причин подібних ефектів. 

Література 

1.  eStream – the ECRYPT stream cipher project / http://www.ecrypt.eu.org/stream. 
2.  Daemen J. Resynchronization weaknesses in synchronous stream ciphers 
3.  Borissov Y. On a resynchronization weakness in a class of combiners with memmory / Y. 

Borissov, S. Nikova, B. Preneel, J. Vandewalle // The 3

rd

  Conf. on Security in Communication 

Networks, Proceedings. Berlin. Springer-Verlag, 2003. – P. 165–177. 

4. 

Golić  J.  On  the  resynchronization  attack  /  J.  Golić,  G.  Morgari  //  Fast  Software 

Encryption. – FSE’03, Proceedings. Berlin. Springer-Verlag, 2003. – P. 100–110. 

5.  Armknecht  F.  Extending the resynchronization attack / F. Armknecht, J. Lano, B. 

Preneel // Selected Areas in Cryptography – SAC’04, Proceedings. Berlin. Springer-Verlag. 2004. – 
P. 19–38. 

6.  Yang W. A resynchronization attack on stream ciphers filtered by Maiorana-McFarland 

functions / W. yang, Y. Hu // Front. Comput. Sci. China, 2011. – Vol. 5(2). – P. 158 – 162. 

25