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

УДК 691.321 
 

ПОРІВНЯННЯ ОПЕРАЦІЙ МОДУЛЬНОГО ТА ПОКОМПОНЕНТНОГО 

ДОДАВАННЯ НА МНОЖИНІ N-МІРНИХ ВЕКТОРІВ НАД ПРОСТИМ 

СКІНЧЕННИМ ПОЛЕМ 

*Л.В. Ковальчук, д-р техн. наук, доц., **Н.В. Лисенко, **С.М. Красніков 

*

Фізико-технічний інститут НТУУ «КПІ» 

**ДержНДІ Спецзв’язку 

e-mail: natalka.lsnk@gmail.com 

Дуже  часто  при  оцінюванні  стійкості  блокових  шифрів  (БШ)  до  різних  методів 

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

Наприклад, зменшують кількість раундів БШ, змінюють ключовий розклад, а особливо часто 

замінюють  (явно  або  неявно)  модульне  додавання  на  побітове.  Якихось  обґрунтованих 

аргументів стосовно математичної коректності такої заміни не наводиться; зазвичай автори 

обмежуються  емпіричними  та  інтуїтивними  обґрунтуваннями.  Оскільки  така  ситуація 

виникає  досить  часто,  то  постає  питання:  чи  можна  при  оцінці  криптографічної  стійкості 

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

криптостійкості)  алгоритм? Саме  відповіді на  це  питання,  а  також  на  деякі  суміжні  з ним, 

присвячена ця доповідь. 

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

модульного  та  покомпонентного  додавання  (віднімання)  векторів  є  дуже  малою.  Вона 

експоненційно  зменшується  із  зростанням  довжини  вектора.  Тому,  зокрема,  використання 

для аналізу стійкості БШ такої його модифікації, в якій модульне додавання замінюється на 

побітове, є некоректним, хоч і суттєво спрощує аналіз алгоритму. 

Крім цього, показано, що заміна операції в ключовому суматорі алгоритму або заміна 

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

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

може виявитись суттєво нижчою, чимвихідного. 

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

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

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

криптоаналізу. 

Л.В. Ковальчук, Н.В.Лисенко, С.М. Красніков. Порівняння операцій модульного та 

покомпонентного  додавання  на  множині  n-мірних  векторів  над  простим  скінченним 

полем 

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

операцій  покомпонентного  та  модульного  додавання  (віднімання)  векторів  є  дуже  малою. 

Вона  експоненційно  зменшується  із  зростанням  довжини  вектора.  Тому,  зокрема, 

використання для аналізу стійкості БШ такої його модифікації, в якій модульне додавання 

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

Крім цього, показано, що заміна операції в ключовому суматорі алгоритму або заміна 

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

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

може виявитись суттєво нижчою, чимвихідного. 

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

оцінка стійкості блокових алгоритмів. 

36 

L.V.  Kovalchuk,  N.V.  Lysenko,  S.M.  Krasnikov.  The comparison of the component-wise 

and modular addition of n-dimensional vector space over a prime finite field. 

The results obtained show that the probability of coincidence of modular and component-

wise addition (subtraction) of vectors is very small. It decreases exponentially when the length of 
vectors grows. So using such modification of block cipher instead of original cipher to estimate the 
security of origin cipher is not correct. 

Also it is shown that any changes of key adder operations or of substitution block without 

previous investigations are dangerous and may decrease cryptographic security. 

Keywords: bit-by-bit  and

  modular addition, 

block cipher  modification, block cipher 

durability evaluation

. 

37 

УДК 004.056.55:519.2 

ДОКАЗОВА СТІЙКІСТЬ УСКЛАДНЕНИХ СХЕМ ФЕЙСТЕЛЯ ДО 

ДИФЕРЕНЦІАЛЬНОГО ТА ЛІНІЙНОГО КРИПТОАНАЛІЗУ 

*С.В. Яковлєв, к.т.н., ст. викладач 

*

Фізико-технічний інститут НТУУ «КПІ» 

e-mail: yasv@rl.kiev.ua 

Схема Фейстеля – ітеративна схема симетричного шифрування, яка лежить в основі 

багатьох  сучасних  блочних  шифрів,  включаючи  шифри  DES  та  ГОСТ.  Один  раунд  схеми 

Фейстеля має вигляд 

))

(

,

(

)

,

(

y

f

x

y

y

x

F

k

k

⊕

=

, де 

)

,

(

y

x

 – 

блок вхідних даних, розбитий на дві 

рівні  за  довжиною  частини, 

k

f   – 

бієктивна  раундова  функція,  яка  може  відрізнятись  на 

окремих  раундах.  Для  схем  Фейстеля  були  одержані  оцінки  доказової  стійкості  до 

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

диференціалів  та  лінійні  потенціали.  Зокрема,  Аокі  та  Ота  показали  [2],  що  імовірності 

трираундових  диференціалів  схеми  Фейстеля,  що  є  марковською  відносно  операції  ⊕,  не 
перевищують величини 

2

p

, де p – максимальна імовірність диференціалів функції 

k

f

; для 

немарковських схем Фейстеля аналогічний результат було одержано Ковальчук [1]. Ніберг 

довела  відповідну  оцінку  для  трираундових  лінійних  потенціалів  (іншими  словами  – 

імовірностей лінійних апроксимацій) марковської схеми Фейстеля [3]. 

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

Фейстеля,  що  включають  в  себе  додаткові  лінійні  перетворення  на  кожному  раунді.  Так, 

один  раунд  шифру  Blowfish  [4]  має  вигляд 

)))

(

(

),

(

(

)

,

(

y

f

x

y

y

x

F

k

k

π

π

⊕

=

,  де  π  –  деяка 

перестановка,  унікальна  для  кожного  раунду;  а  один  раунд  шифру  LBlock  [5],  що 

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

))

(

)

(

,

(

)

,

(

y

f

x

y

y

x

F

k

k

⊕

=

ρ

,  де  ρ  – 

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

результати оцінювання стійкості формально не можуть бути застосовані. 

В  даній  роботі  розглядається  модифікована  схема  Фейстеля  із  додатковими 

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

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

)))

(

(

)

(

),

(

(

)

,

(

y

f

x

y

y

x

F

k

k

µ

λ

µ

⊕

=

,  де  λ  та  µ  –  деякі  лінійні  бієктивні 

перетворення,  які  можуть  відрізнятись  на  кожному  раунді.  Очевидно,  що  схеми  шифрів 
Blowfish 

та LBlock є частковими випадками запропонованої модифікованої схеми Фейстеля. 

Була доведена наступна теорема. 

Теорема 1. Імовірності трираундових диференціалів модифікованої схеми Фейстеля із 

додатковими лінійними ускладненнями не перевищують величини 

}

,

,

max{

3

1

3

2

2

1

p

p

p

p

p

p

, де 

i

p  – 

максимум імовірності диференціалу i-тої раундової функції. 

Теорема  1  справедлива  навіть  для  немарковських  шифрів,  що  мають  відповідну 

структуру. Якщо ж кожна раундова функція модифікованої схеми Фейстеля матиме вигляд 

)

(

)

(

k

x

g

y

f

k

⊕

=

,  де  g  –  деяке  нелінійне  перетворення  (тобто  ця  схема  буде  марковською 

відносно операції ⊕), то додатково має місце наступна теорема. 

Теорема  2.  Трираундові  лінійні  потенціали  модифікованої  схеми  Фейстеля  із 

додатковими  лінійними  ускладненнями,  раундові  функції  якої  мають  вигляд 

)

(

)

(

k

x

g

y

f

k

⊕

=

,  не  перевищує  величини 

}

,

,

max{

3

1

3

2

2

1

q

q

q

q

q

q

,  де 

i

q   – 

максимальний 

лінійний потенціал i-тої раундової функції. 

Таким  чином,  можемо  констатувати,  що  використання  додаткових  лінійних 

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

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

підвищує її). 

38 

Література 
1. 

Ковальчук Л.В. Дослідження різницевих характеристик раундової функції блочних 

шифрів  MISTY1  та  MISTY2  /  Л.В.  Ковальчук,  А.О.    Шерстюк  //  Прикладная 

радиоэлектроника. – №3. – 2009. – С. 15–27. 

2. Aoki K. Stricter Evaluation for the Maximum Average of Differential Probability and the 

Maximum Average of Linear Probability / K. Aoki, K. Ohta // Proceedings of SCIS'96, SCIS96-4A. 
– 

1996. [японською мовою] 

3. Nyberg K. Linear Approximation of Block Ciphers / K.  Nyberg  // EUROCRYPT’94. – 

Lecture Notes in Computer Science, vol. 950. – Springer Verlag, 1994. 

4. Schneier B. Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish) / 

B. Schneier // Fast Software Encryption, Cambridge Security Workshop Proceedings (December 
1993). – Springer-Verlag. – 1994. – pp. 191-204. 

5. Wu, W. LBlock: A Lightweight Block Cipher. / W. Wu, L. Zhang // In: Lopez, J., Tsudik, 

G. (eds.) ACNS 2011. – LNCS. – vol. 6715. – 2011. – pp. 327-344. 

С.В. Яковлєв. 

Доказова 

стійкість 

ускладнених 

схем 

Фейстеля 

до 

диференціального та лінійного криптоаналізу. 

В  роботі  розглянуто  модифіковану  схему  Фейстеля  із  додатковими  лінійними 

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

блокового шифрування Blowfish та LBlock. Одержано оцінки доказової стійкості схеми, що 

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

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

Ключові  слова:  схема  Фейстеля,  Blowfish,  LBlock,  диференціальний  криптоаналіз, 

лінійний криптоаналіз, доказова стійкість. 

S.V. Yakovliev.  Provable  Security  of  Complicated  Feistel  Schemes  against  Differential 

and Linear Cryptanalysis. 

We consider modified Feistel scheme with additional linear transformations in every round 

of encryption. Blowfish and LBlock cipher schemes can be described as variants of proposed 
modification. We evaluate provable security of modified Feistel scheme against differential and 
linear cryptanalysis. It has been shown that proposed modification is as resistant to last ones as the 
original Feistel scheme. 

Keywords: Feistel scheme, Blowfish, LBlock, differential cryptanalysis, linear cryptanalysis, 

provable security. 

39 

УДК 004.56 
 

ОСОБЛИВОСТІ ПОБУДОВИ ЗАХИЩЕНИХ СИСТЕМ ОБМІНУ 

МУЛЬТИМЕДІЙНОЮ ІНФОРМАЦІЄЮ НА БАЗІ НЕРОЗКРИВНИХ ШИФРІВ 

Н.І. Алішов, д-р техн. наук, проф.; В.А. Марченко, канд. техн. наук, с.н.с.; 

Сігнаєвський К.М.; Кульбачний Д.В; С.В. Зінченко; М.О. Бойко аспірант 

*Інститут кібернетики ім. В.М. Глушкова НАНУ 

*Науково-виробничий центр “Інфозахист” 

e-mail: infozahist@ukr.net 

Сучасні системи обміну  мультимедійною інформацією представляють собою велике 

різноманіття  різних  програмних,  апаратних  і  програмно-апаратних  комплексів.  Які 

виконують  ряд  задач  зокрема  це:  трансляція  аудіо-відео  потоку  через  мережу;  організація 

телефонії та відео-телефонії. 
 

Для  побудови  подібних  систем  використовується  стек  мережевих  протоколів[1].  В 

цьому стеці виділено три функціональні задачі: 

1. 

Організація управління(сигналізація) послугою(RTSP). 

2. 

Забезпечення необхідної якості(QoS)(RSVP, RTCP). 

3. 

Реалізація передачі мультимедіа(Транспорт)(RTP). 

Типовою є практика при реалізації телефонії через інтернет(VoIP) трафік сигналізації 

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

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

Сучасні аудіо та відео кодеки, що застосовуються в потокових мультимедійних системах, 

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

якості  аудіо  або  відео  ряду.  Ця  особливість  значно  спрощує  розробку  систем  шифрування 

для  потокових  систем,  але  в  той  же  час,  висуває  ряд  вимог  до  криптосистем,  що 

застосовуються при шифруванні потоків даних: 

• 

потоковий режим роботи; 

• 

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

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

було  використано  алгоритм  непрямого  шифрування  [2],  що  відноситься  до  класу 

нерозкривних шифрів[3]. 
 

Було проведено ряд експериментів з отриманим комплексом захисту. В ході яких 

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

Зокрема: 

• 

генерація великих масивів істинно-випадкових чисел; 

• 

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

учасниками сеансу зв’язку; 

• 

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

інформаційні системи. 

Література 

1.  Wallingford Theodore. Switching to VoIP. – O'Reilly Media, 2009. – 504 p. 
2. 

Алишов  Н.И.,  Марченко  В.А.,  Оруджева  С.Г.  Косвенная  стеганография  как  новый 

способ передачи секретной информации // Комп'ютерні засоби, мережі та системи: зб. наук. 

пр. – К.: НАНУ, Ін-т кібернетики, 2009. – № 8. – С. 105–112. 

3. 

Зубов А. Совершенные шифры. — М.: Гелиос АРВ, 2003. – 160 с. 

Н.І.  Алішов,  В.А.  Марченко,  С.В.  Зінченко,  М.О.  Бойко  Особливості  побудови 

захищених систем обміну мультимедійною інформацією на базі нерозкривних шифрів 

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

інформацією.  Показано  особливості  реалізації  захищених  інформаційних  систем  для 

організації  VoIP.  Запропоновано  використання  нерозкривних  алгоритмів  для  організації 

40