Оцінка стійкості криптоалгоритмів

Сучасні інформаційні технології/4. Інформаційна безпека

Д.С. Коваленко, А.Б. Елізаров, В.О. Варова

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

Оцінка стійкості криптоалгоритмів

Вступ

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

Криптографічний захист інформації – вид захисту інформації, що реалізується шляхом перетворення інформації з використанням спеціальних (ключових) даних з метою приховування/відновлення змісту інформації, підтвердження її справжності, цілісності, авторства тощо.

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

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

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

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

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

Оцінка надійності криптоалгоритмів залежно від довжини ключа

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

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

Таблиця 1

Час, необхідний для повного перебору ключів

Назва машини	Потужність (FLOPS)	56 біт *7.2Е16**	64біта *1.8E19**	80 біт *1.2Е24**	100 біт *1.26Е30**
Intel ASCI Red	1.333*Е12	14 годин	5 міс.	28460 років	3.01*Е10
Hitachi/Tsukuba CP-PACS	3.68*Е11	52 год.	18міс.	102676 років	1.09*Е11
SGI/Cray T3E	2.65*Е11	69 год.	51 міс.	143256 років	1.51*Е11
Fujitsu Numerical Wind Tunnel	2.3*Е11	171 год.	60 міс.	164592 роки	1.74*Е11
Hitachi SR2201	2.2*Е11	178 год.	61міс.	172720 років	1.82*Е11

Алгоритм ГОСТ 28147-89 використовує таблицю підстановок розміром 512 біт. Загальне число можливих таблиць складає 1.33*Е36 і повний час перебору становить 3.162*Е16 років. Для алгоритму IDEA довжина ключа становить 128 біт і повний час перебору складає 8.09*Е18 років. Навіть якщо буде використаний суперкомп'ютер, який складається зі ста тисяч процесорів з максимально можливою швидкістю в 1016 операцій/секунду для розшифрування ГОСТу знадобиться 4.21*Е7 років, а для IDEA - 1.08*Е10 років.

Із проведеного дослідження можна зробити висновок, що для забезпечення надійності досить використовувати алгоритми з довжиною ключа не менше 64 бітів, а застосовувати алгоритми з довжиною ключа більше 128 біт економічно не вигідно. Однак, як правило, для генерації ключа використовується пароль, який в свою чергу часто містить лише символи латинського алфавіту. У такому випадку для забезпечення необхідного захисту потрібно використовувати пароль не коротше 12 символів, що відповідає 56-бітному ключу, а 16-символьний пароль відповідає 75-бітному ключу і гарантує достатній захист від прямої атаки.

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

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

Для проведення криптоаналізу необхідна велика кількість зашифрованих текстів та відповідних їм відкритих текстів. У найзагальнішому вигляді метод виглядає наступним чином:

1) з множини шифротекстів за спеціальною методикою відбираються пари шифротекстів, що відрізняються фіксованими бітами;

2) на підставі аналізу кожної пари отримують варіанти ключа з різними ймовірностями;

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

Розглянемо метод диференційного криптоаналізу на прикладі алгоритму DES. Нагадаємо коротко основні відомості про DES.

DES - блочний шифр з 16 циклами. На вхід алгоритму подається 64-бітний блок даних. Потім здійснюється перестановка біт у вихідному блоці за фіксованою схемою, і потім він ділиться на дві 32-бітові половини: L і R. Далі для i = 1, ..., 16:L_i = R_i-1;

R_i = L_i-1 XOR f(R_i-1,K_i).

Після 16 циклів, L і R міняються місцями. Тепер L і R об'єднуються, і знову здійснюється перестановка бітів - отримуємо зашифрований текст.

Функція f - цикліна функція - виконує основну роботу по закриттю повідомлення. Спочатку здійснюється перестановка 32 вхідних біт та їх розширення до 48 біт. Потім, 48 біт діляться на вісім 6-бітових блоків. Кожен блок проходить через таблицю підстановки, на виході якого виходить 4-бітове значення. Ці вихідні 32 біта знову переставляються (див. рис. 1).

Використовуючи диференційний криптоаналіз, ми можемо отримати 48-бітний ключ на останньому циклі. Решта 8 біт виходять прямим перебором.

Розглянемо детальніше суть методу. Криптоаналітику відомий зашифрований текст. Виконавши перестановку, він отримає Li і Ri - лівий і правий 32-бітові блоки на останньому циклі і вхідне значення для циклічної функції f. Розглянемо значення, оброблювані цією функцією для двох різних шифротекстів, отриманих на одному ключі. Нехай на вхід надходять значення X = Ri і X '= Ri', їх різниця становить DX = X Е X '. Розширивши її за таблицею E, визначимо різницю DA = A Е A '. Після складання з ключем виходять значення B і B ', невідомі криптоаналітику, але ці значення можна припускати з певною ймовірністю:DB =B Е B'=( A Е K_i)( A' Е K_i)=A Е A'= DA.

Рис. 1. Циклічна функція DES

Якщо розглядати кожен блок підстановки окремо, то для кожного вихідного DC існує 16 пар C і C ¢, які дають цю різницю. У свою чергу, є 64 можливих пари B і B 'для заданої різниці DC. Однак, в середньому менше 16 пар B і B 'задовольняють умові B Е B' = DB.

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

У розглянутій постановці успіх атаки сильно залежить від числа циклів і для 16-циклового DES ця атака є значною мірою теоретичною. Для її здійснення потрібні величезні часові ресурси і об'єми даних, що робить її надзвичайно складною для практичної реалізації .

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

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

· якщо для генерації ключа використовується пароль, то він повинен бути не коротше 12 символів;

Висновки

У ході проведеної роботи був проведений аналіз сучасних методів злому криптографічних алгоритмів.

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

Література:

1. Biham E., Shamir A. Диференційний криптоаналіз стандарту шифрування даних – К.: Springer-Verlag, 1993.

2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы. — М.: Триумф, 2002.

3. Matsui M. Лінійний криптоаналіз метод Cipher DES. - Досягнення в галузі криптології. – К.: Springer-Verlag, 1994.

4. Сюэцзя Лай и Джеймс Месси Предложение нового блочного стандарта шифрования. – М.: Триумф, 1990.

5. The First Experimental Cryptanalysis of the Data Encryption Standard. Advances in Cryptology-CRYPTO '94, Proceedings. New York, NY: Springer-Verlag, 1994.