Диференціальний криптоаналіз блоково-динамічного алгоритму шифрування


ВСТУП

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

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

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

РЕЗУЛЬТАТИ

Згідно з джерелом [4] для злому блоково-динамічного шифру методом диференціального аналізу необхідно 224 Пар відкритого тексту. Для 4-раундового блоково-динамічного шифру трудомісткість становить 232, при 6 раундах - трудомісткість 267, при 7 раундах - трудомісткість 2131.

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

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

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

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

. (1)

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

. (2)

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

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

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

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

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

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

Для довжини ключа m=2 символи "еквівалентні ключі" мають вигляд: AA~A, BB~B і т. д. Кожний символ алфавіту ключа може утворити таку пару однакових символів. Всього таких пар однакових символів може бути 256 (розмір алфавіту ASCII та ANSI). Загальна кількість можливих пар становить 2562. Тому імовірність появи еквівалентного ключа при 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-раундового варіанта блоково-динамічного шифру методом диференціального криптоаналізу.

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

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

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

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

. (6)

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

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

графік залежності трудомісткості е злому блоково-динамічного шифру методом диференціального криптоаналізу для звичайного () та слабкого ключа (---) від кількості раундів 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с.

Похожие статьи




Диференціальний криптоаналіз блоково-динамічного алгоритму шифрування

Предыдущая | Следующая