СОВРЕМЕННЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ/4. Информационная безопасность

ЄЛІЗАРОВ А.Б., РЯБИЙ М.О., ШКАРУПА Д.В., ГОРІНШТЕЙН М.Л.

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

СУЧАСНІ МЕТОДИ РОЗКРИТТЯ АЛГОРИТМІВ ШИФРУВАННЯ

Вступ.

Останні десятиліття спостерігається небувалий бум в області криптології. Це пов'язане з тим, що її досягнення стали застосовуватись не тільки у вузьких відомчих колах, але й у житті мільйонів громадян. З кожним роком різко збільшується число відкритих робіт з питань криптології, а криптоаналіз стає однією з областей досліджень, що найактивніше розвиваються. При цьому розробляються нові і удосконалюються відомі методи криптоаналізу алгоритмів шифрування. Велика кількість алгоритмів, стійкість яких не викликала особливих сумнівів, виявилися успішно розкритими. Науково-технічна революція сприяє розвитку криптоаналізу. Завдяки сучасній комп'ютерній техніці стали можливими деякі методи нападів на алгоритми шифрування, які рахувалися не практичними а лише теоретичними[1].

Постановка проблеми. Здійснюючи атаку, криптоаналітик може ставити за мету рішення наступних завдань:

1. Одержання відкритого тексту із зашифрованого.

2. Обчислення ключа шифрування.

У загальному випадку, друге з перерахованих завдань є істотно більш складним, чим перше. Однак, маючи ключ шифрування, криптоаналітик може згодом розшифровувати всі дані, зашифровані знайденим ключем. Така атака (у випадку її успішного здійснення) називається повним розкриттям алгоритму шифрування [3]. Тому перед тим як надати перевагу тому чи іншому методові шифрування важливо перевірити на власному досвіді його крипостійкість.

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

1. Метод грубої сили (повного перебору)

Метод грубої сили припускає перебір всіх можливих варіантів ключа шифрування до знаходження шуканого ключа [1].

Нехай розмір ключа шифрування в бітах дорівнює b. Відповідно, існує 2^b варіантів ключа. Криптоаналітик повинен методично перебрати всі можливі ключі, тобто застосувати як ключ значення 0, потім 1, 2, 3 і т.д. до максимально можливого (2^b - 1). У результаті ключ шифрування обов'язково буде знайдений, причому в середньому такий пошук зажадає 2^b/2, тобто 2^b-1 тестових операцій шифрування.

Зрозуміло, що необхідно мати який-небудь критерій правильності знайденого ключа. З атакою з відомим відкритим текстом все достатньо просто - при тестуванні кожного ключа K_x шифротекст C розшифровується (у результаті виходить якесь значення M') і рівняється з відповідним йому відкритим текстом M; збіг M = M' говорить про те, що шуканий ключ знайдений.

Трохи складніше з атакою на основі шифротекста. У цьому випадку необхідна наявність якої-небудь додаткової інформації про відкритий текст, наприклад:

· Якщо відкритий текст є осмисленим текстом на якій-небудь мові, перехоплений шифротекст повинен мати достатній розмір для однозначного розшифрування в осмислений текст (мінімально достатній для цього розмір називається крапкою одиничності).

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

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

2. Метод "зустрічі посередині"

Даний метод криптоаналізу заснований на "парадоксі днів народження" [3]. Відомо, що якщо вважати, що дні народження розподілені рівномірно, то в групі з 24 чоловік з імовірністю 0,5 у двох чоловік дні народження збігаються. У загальному виді цей парадокс формулюється так: якщо предметів вибираються з поверненням із деякої сукупності розміром b , то ймовірність того, що два з них збіжаться .

Якщо множина ключів криптоалгоритму замкнуто щодо композиції, тобто для будь-яких ключів k_i і k_j найдеться ключ k_r такий, що результат шифрування будь-якого тексту послідовно на k_i і k_j однакова криптограмі зашифрована ключем k_r, тобто F(k_j, F(k_i, x)) = F(k_r, x), то тоді можна скористатися цією властивістю. Нехай нам потрібно знайти ключ k_r. Тоді для знаходження ключа k_r необхідно знайти еквівалентну йому пари ключів k_i і k_j[3]. Нехай відомий відкритий текст x і його криптограма y. Для тексту x будуємо базу даних, що містить випадкова безліч ключів k' і відповідних криптограм w=F(k',x), і впорядковуємо її по криптограмах w. Обсяг бази даних вибираємо , де - потужність безлічі ключів k'. Потім підбираємо випадковим образом ключі k" для розшифровки текстів y і результат розшифровки v=F(k",y) порівнюємо з базою даних. Якщо текст v виявиться рівним однієї із криптограм w, то ключ k'k" еквівалентний шуканому ключу k. Цей метод також застосовується, якщо множина ключів містить досить велику підмножину, що є напівгрупою.

Позначимо загальну кількість можливих ключів k . Тимчасова

складність методу становить . Множник враховує складність

сортування. Необхідна пам’ять рівна біт або блокам.

3. Диференційний криптоаналіз

Диференційний метод криптоаналізу був запропонований Э.Біхамом й А.Шаміром в 1990 р. [2]. Диференціальний криптоаналіз - це спроба розкриття секретного ключа блокових шифрів, які засновані на повторному застосуванні криптографічно слабкої цифрової операції шифрування r раз. При аналізі передбачається, що на кожному циклі використається свій підключ шифрування. Диференціальний криптоаналіз може використати як обрані, так і відомі відкриті тексти. Конкретний спосіб диференціального криптоаналізу залежить від аналізуємого алгоритму шифрування.

Успіх таких спроб розкриття r-циклічного шифру залежить від існування диференціалів (r-1)-го циклу, які мають велику ймовірність. Диференціал і-го циклу визначається як пара (a,b)_і така, що пари різних відкритих текстів x, x` c різницею a може привести до пари вихідних текстів y, y` після і-ого циклу, що мають різницю b (для відповідного поняття різниці). Ймовірність і-циклового диференціала (a,b)_і - це умовна ймовірність P(D y(і)=b | D x=a) того, що різниця D y(і) пари шифротекстів (y,y`) після і-ого циклу дорівнює b за умови, що пара текстів (x,x`) має різницю D x=a; відкритий текст x і підключи циклів k⁽¹⁾ , k⁽²⁾ ,...., k^(і) незалежні і рівно ймовірні.

Основна процедура диференціального криптоаналізу r-циклічного шифру з використанням обраних відкритих текстів може бути наступною:

1. Шукаємо множину (r-1)-циклових диференціалів (a₁,b₁)_r-1, (a₂,b₂)_r-1,....,(a_s,b_s)_r-1. Впорядковуємо цю множину диференціалів по величині їхньої ймовірності.

2. Вибираємо відкритий текст x довільним чином і обчислюємо x` так, щоб різниця між x і x` була рівна a₁. Тексти x і x` шифруються на справжньому ключі і після r циклів одержуємо пари шифротекстів y(r), y`(r). Припускаємо, що на виході передостаннього (r-1)-ого циклу різниця шифротекстів дорівнює найбільш ймовірній: D y(r-1)=b 1. Для трійки (D y(r-1), y(r), y`(r)) знаходимо кожне можливе значення підключа останнього циклу k^(r). Додаємо його до кількості появ кожного такого значення підключа k^(r).

3. Повторюємо п.2 доти, поки одне або кілька значень підключа k^(r) не стане з'являтися частіше інших. Беремо цей підключ або множину таких підключів як криптографічне рішення для підключа k^(r).

4. Повторюємо пункти 1-3 для передостаннього циклу, при цьому значення y(r-1) обчислюються розшифруванням шифротекстів на знайденому підключі останнього циклу k^(r). Далі діємо аналогічно, поки не будуть розкриті ключі всіх циклів шифрування [3].

4. Лінійний криптоаналіз

Лінійний криптоаналіз винайшов японський криптолог Міцуру Мацуі (Mіtsuru Matsuі). Цей метод використовує лінійні наближення перетворень, що виконуються алгоритмом шифрування. Даний метод дозволяє знайти ключ, маючи досить велику кількість пар (незашифрований текст, зашифрована текст). Розглянемо основні принципи, на яких базується лінійний криптоаналіз. Лінійний криптоаналіз базується на тому, що існує можливість замінити нелінійну функцію її лінійним аналогом [1].

Метою лінійного криптоаналізу є пошук лінійного рівняння виду

P_i1P_i2… P_iaC_j1C_j2…C_jb = K_k1K_k2…K_kc (1), де P_n, C_n і K_n - n-і біти відкритого тексту, шифротекста й ключа відповідно.

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

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

Рівняння складаються в такий спосіб. Обчислюються значення лівої частини для великої кількості пар відповідних фрагментів незашифрованого й зашифрованого блоків. Якщо результат дорівнює нулю більш ніж у половині випадків, то вважають, що K_k1K_k2…K_kc = 0. Якщо в більшості випадків виходить 1 - K_k1K_k2…K_kc = 1. У такий спосіб одержують систему рівнянь, рішенням якої є ключ. Як й у випадку диференціального криптоаналізу, результати лінійного криптоаналізу повинні враховуватися при розробці алгоритмів симетричного крипто аналізу [1].

Досить часто лінійний криптоаналіз використовується в сукупності з атакою методом "грубої сили" - певні біти ключа виявляють за допомогою лінійного криптоаналізу, після чого виконується вичерпний пошук за можливим значенням інших біт

Лінійний криптоаналіз має одну досить корисну властивість: за певних умов співвідношення (1) може бути перетворене до наступного:

C_j1C_j2…C_jb = K_k1K_k2…K_kc

У даному співвідношенні повністю відсутні біти відкритого тексту, тобто за допомогою лінійного криптоаналізу можна побудувати атаку на основі тільки шифротекста, що ще більше розширює область застосування лінійного криптоаналізу, оскільки атака, що вимагає тільки перехоплений шифротекст, є найбільш практичною [1].

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

Література:

1) Методы криптоанализа. – <http://www.i2r.ru>.

2) Атаки на алгоритмы шифрования. –<http://www.bytemag.ru>.

3) Алгоритмы блочного шифрования. – < http://www.az.ru/defence>.