ДИФЕРЕНЦІАЛЬНИЙ КРИПТОАНАЛІЗ БЛОКОВО-ДИНАМІЧНОГО АЛГОРИТМУ ШИФРУВАННЯ

С.М. Білан, канд. техн. наук, доц.; І.М. Шварц, здобувач

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

ПОСТАВЛЕННЯ ЗАВДАННЯ

Для проведення аналізу візьмемо, що відомі відкрите повідомлення та шифрований текст, що йому відповідає, а також алгоритм блоково-динамічного шифрування[1,2] з відповідним криптографічним протоколом [3]. Необхідно знайти Р-блок, S-блоки, ключ, необхідну кількість відритих текстів і трудомісткість розкриття блоково-динамічного шифру, наявність слабких ключів та імовірність їх появи.

РЕЗУЛЬТАТИ

Згідно з джерелом [4] для злому блоково-динамічного шифру методом диференціального аналізу необхідно 2²⁴ пар відкритого тексту. Для 4-раундового блоково-динамічного шифру трудомісткість становить 2³², при 6 раундах - трудомісткість 2⁶⁷, при 7 раундах - трудомісткість 2¹³¹.

На основі даних проведений регресійний аналіз залежності трудомісткості Е від кількості раундів r при використанні диференціального криптоаналізу блоково-динамічного шифрування. Результати цього аналізу наведені на рис. 1, де суцільною лінією показана експериментальна крива, а штриховою - теоретична, передбачена за допомогою рівняння регресії експоненціального типу, наведеного на вільній ділянці графіка. Для зручності оцінювався показник х степеня 2 замість самої трудомісткості. Отримане значення квадрата коефіцієнта кореляції R²=0,9732 свідчить про достатньо точні значення коефіцієнтів регресійного рівняння.

Рисунок 1 - Залежність показника х ступеня 2 трудомісткості е від кількості раундів

Одержане регресійне рівняння відносно х має вигляд

. (1)

Для трудомісткості Е рівняння регресії має вигляд

. (2)

Застосовуючи рівняння (1), (2), можна спрогнозувати трудомісткість розкриття блоково-динамічного шифру з числом раундів більше 7.

Таким чином, при здійсненні атаки за допомогою диференціального криптоаналізу для варіантів блоково-динамічного шифру з кількістю раундів більше 5 його ефективність поступається методу повного перебору, середня трудомісткість якого при довжині ключа m=56 становить 2^56-1=2⁵⁵. Тому диференціальний криптоаналіз не є ефективним для повного 16 раундового блоково-динамічного шифру.

Для кожного короткого ключа є принаймні один еквівалентний більш довгий ключ; наприклад, A, AA, AAA і т.д. є еквівалентними ключами. Тобто еквівалентними ключами блоково-динамічного шифру є ключі, що складаються з цілої кількості періодичних частин, і при шифруванні однакових даних цими ключами отримується однаковий шифротекст, що обумовлено особливістю блоково-динамічного алгоритму.

Для позначення еквівалентності будемо використовувати знак еквівалентності ~, наприклад ABAB~AB, AABAABAAB~AAB.

Очевидно, що для відкриття еквівалентного ключа меншої довжини трудомісткість суттєво знижується, що дає підставу вважати такий ключ слабким. Назвемо такий ключ слабким ключем 1-го роду.

Для довжини ключа m=2 символи “еквівалентні ключі” мають вигляд: AA~A, BB~B і т.д. Кожний символ алфавіту ключа може утворити таку пару однакових символів. Всього таких пар однакових символів може бути 256 (розмір алфавіту ASCII та ANSI). Загальна кількість можливих пар становить 256². Тому імовірність появи еквівалентного ключа при m=2 становить

.

При m=3 еквівалентні ключі мають вигляд AAA~A, BBB~B і т.д. Тому імовірність появи еквівалентного ключа при m=3 становить

.

При m=4 еквівалентні ключі можуть мати вигляд, як AAAA~A, BBBB~B і т.д., так і ABAB~AB, BCBC~BC і т.д. Тому імовірність появи еквівалентного ключа при m=4 становить

.

При m=5 еквівалентні ключі мають вигляд: AAAAA~A, BBBBB~B і тд. Тому імовірність появи еквівалентного ключа при m=5 становить

.

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

Для парної довжини ключа закономірність імовірності появи еквівалентного ключа має вигляд

, (3)

тобто є постійною.

Для непарної довжини ключа закономірність імовірності появи еквівалентного ключа має вигляд

, (4)

тобто залежить від довжини ключа.

На основі результатів досліджень автора [4] відомо, що при відомих S-блоках диференціальний криптоаналіз може розкрити Р-масив за допомогою

(5)

На основі формули (5) побудуємо графік залежності кількості відкритих текстів k_ВТ, необхідних для злому блоково-динамічного шифру методом диференціального криптоаналізу залежно від кількості раундів r. Цей графік зображений на рис. 2. Вісь ординат представлена у логарифмічній системі координат. На цьому графіку горизонтальними штрихпунктирними лініями показані характеристики сучасних модулів оперативної пам'яті та жорстких дисків.

З графіка, зображеного на рис. 2, бачимо, що для розміщення відкритих текстів в оперативній пам'яті комп'ютера, об'єму оперативної пам'яті сучасних персональних комп'ютерів достатньо лише для злому 3-раундового варіанта блоково-динамічного шифру методом диференціального криптоаналізу.

Рисунок 2 - Графік залежності кількості відкритих текстів k_ВТ, необхідних для злому блоково-динамічного шифру

При розміщенні відкритих текстів на жорсткому диску комп'ютера, об'єму жорстких дисків сучасних персональних комп'ютерів достатньо лише для злому 4-раундового варіанта блоково-динамічного шифру методом диференціального криптоаналізу, при цьому різко впаде швидкодія злому тому, що жорсткі диски значно повільніші за оперативну пам'ять.

Встановлено, що для деяких слабких ключів, які генерують погані S-блоки, тобто S-блоки, в яких принаймні 2 елементи збігаються. (вірогідність вибору такого ключа становить pII=2-14). Назвемо ці ключі слабкими ключами 2-го роду. Трудомісткість розкриття Р-масиву, утвореного слабким ключем 2-го роду, обчислюється за формулою [4]:

 . (6)

Аналіз графіка, наведеного на рис. 3, показав, що трудомісткість Е злому блоково-динамічного шифру методом диференціального криптоаналізу для слабкого ключа значно нижча, ніж для звичайного, причому зі зростанням кількості раундів r ця різниця зростає.

Рисунок 3 - Графік залежності трудомісткості Е злому блоково-динамічного шифру методом диференціального криптоаналізу для звичайного () та слабкого ключа (---) від кількості раундів r

До імовірності появи слабкого ключа 1-го роду (еквівалентного ключа) рІ додамо імовірність появи слабкого ключа 2-го роду рІІ і отримаємо загальну імовірність появи слабкого ключа р3:

. (7)

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

. (8)

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

. (9)

Імовірність появи звичайного (неслабкого) ключа q можна обчислити за формулою, як для імовірності сумісних подій:

(10)

Використовуючи формули (2), (6), (8), (10), можна вивести узагальнену формулу трудомісткості взлому блоково-динамічного шифру методом диференціального криптоаналізу, на основі знаходження середнього пропорційного до імовірності сумісних подій:

, (11)

де Е_(зв), Е_(сл) - трудомісткості відкриття звичайного та слабкого ключа відповідно.

ВИСНОВКИ

У результаті проведеного диференціального криптоаналізу блоково-динамічного шифру було визначено імовірність появи слабких ключів 1-го та 2-го роду, яка суттєво змінюється від парності розміру та довжини ключа, яка знаходиться в межах .... Встановлено, що кращу криптостійкість мають ключі (серед слабких) з непарним розміром ключа. Визначено також кількість відкритих текстів, необхідних для диференціального криптоаналізу блоково-динамічного шифру, в кількості ..., залежно від кількості раундів. Для повного (16-раундового) варіанта блоково-динамічного шифру такий об'єм оперативної пам'яті на сьогоднішній день є недосяжним. Знайдено також залежність трудомісткості диференціального криптоаналізу блоково-динамічного шифру як для слабкого, так і для звичайного ключа, а також виведено узагальнену формулу для знаходження трудомісткості, яка для повного (16-раундового) варіанта блоково-динамічного шифру становить , що унеможливлює його відкриття диференціальним методом криптоаналізу. Крім того, при здійсненні атаки за допомогою диференціального криптоаналізу для варіантів блоково-динамічного шифру з кількістю раундів більше 5 його ефективність поступається методу повного перебору.

Summary

A possibility of implementation of the differential analysis to examine a steady of the block-dynamic ciphering algorithm has been considered. It was proved, that the proposed algorithm is firm enough against differential method of cryptographic analysis.

СПИСОК ЛІТЕРАТУРИ

1 С.М. Білан, І.М. Шварц. Вдосконалення алгоритму Blowfish з метою підвищення криптостійкості та швидкодії під час передачі інформації по каналах зв'язку //Реєстрація, зберігання та обробка даних. - 2005. - №1, Т.7. - С. 97-102.

2 Деклараційний патент на винахід №8897, кл. 7H04L 9/04. Спосіб блочного шифрування даних // С.М. Білан, І.М. Шварц; Опубл. 15.08.05. - Бюл. № 8.

3 С.М. Білан, І.М. Шварц. Криптографічні протоколи блокового-динамічного шифрування // Математичне моделювання. - 2005. - №1(13) - С. 71-73.

4 Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С. - 2-е издание. - М.: Дело, 2003. - 524с.