Закон Шнайера

image
У 1998 році відомий американський криптограф Брюс Шнайер написав:
Будь, починаючи з самого безглуздого любителя і закінчуючи кращим криптографом, може створити алгоритм, який він сам не в змозі зламати.
Переформулювання цієї цитати, запропонована журналістом Корі Доктороу в 2004 році, стала відома як Закон Шнайера:
Кожна людина може винайти систему безпеки, яку він був би не в силах зламати.

Дуже гарною ілюстрацією до закону Шнайера, на мій погляд, є спроби посилити алгоритм шифрування DES.

Подвійне шифрування
DES був прийнятий як стандарт в 1977 році. Довжина ключа нового стандарту становила 56 біт, досить велике число по тим часам. Однак закон Мура невблаганний, і деякі криптографи вже тоді почали бити на сполох.
Одними з перших, хто піддав критиці довжину ключа нового стандарту були відомі батьки-засновники криптографії з відкритим ключем: Уітфілд Діффі і Мартіном Хеллманом. В одній зі своїх статей вони стверджували, що 56-бітний ключ занадто малий і залишає можливість для атаки повного перебору.

У світлі вищезазначеного зауваження цілком логічним виглядають спроби збільшити стійкість алгоритму DES, використовуючи техніку багаторазового шифрування. Цей спосіб дозволяє штучно збільшити довжину ключа, застосовуючи кілька разів операцію шифрування з різними ключами.
На перший погляд може здатися, що для вирішення проблеми DES достатньо збільшити довжину ключа вдвічі, тобто використовувати наступну схему як шифрування і розшифровки:
C=EK2 (EK1 (P)),
P=DK1 (DK2 ©),

де C — шифртекст; P — відкритий текст; EK (P) і DK (З) — процедури шифрування і розшифровки відповідно.
Наведена схема збільшує простір ключа до 2112 і робить атаку грубою силою безглуздою витівкою.

Здавалося б рішення знайдено. Але в цей самий момент настав час згадати про Закон Шнайера. Якщо ви створили схему шифрування і не можете знайти в ній недоліки, це не означає що їх немає.
У 1981 році Ральф Меркл і Мартін Хеллман детально розбирають безпека подвійного шифрування і описують спосіб, що дозволяє відновити ключ шифрування не за 2112 операцій шифрування, а за відносно дріб'язкові 257.
Метод, запропонований Мерклем і Хеллманом відноситься до класу атак на основі відкритих текстів, і застосуємо у разі якщо зловмисникові відома пара відкритий-закритий текст.
Суть атаки полягає в наступному. Атакуючому відомий відкритий текст P і відповідний йому шифртекст З=EK2 (EK1(P)).
Для розкриття ключа, атакуючий здійснює перебір всіх можливих 256 варіантів ключа K1 і записує в таблицю T1 значення {EK1(P), K1}.
Потім використовуючи значення, атакуючий перебирає 256 варіантів ключа K2 і записує в таблицю T2 значення {DK2©, K2}.
Відсортувавши таблиці T1 і T2 атакуючий в якості ймовірних ключів приймає такі K1 і K2, для яких EK1(P) = DK2©.
Описана атака називається «зустріч посередині», тому що з одного боку виконується шифрування, а з іншого розшифровка. Отримані «в середині» результати порівнюються.

Потрійне шифрування
У 1978 році Вальтер Тачман запропонував використовувати потрійне шифрування для збільшення стійкості алгоритму DES. У схемі Тачмана також використовується два ключі K1 та K2, але процес шифрування і розшифровки виглядає наступним чином:
C=EK1 (DK2 (EK1(P)))
P=DK1 (EK2 (DK1©)).
Цей спосіб захищений проти атаки «зустріч посередині». Навіть якщо атакуючий сформує таблицю {DK1©, K1}, для проведення атаки йому необхідно буде отримати всі можливі значення {DK2((EK1(P)), K1||K2}, що становить 2112 записів і зрозуміло не представляється реальним.
Але і метод Тачмана не довго вважався надійним.

Меркл і Хеллман описали варіант атаки з обраним відкритим текстом на схему потрійного шифрування.
У запропонованій Меклем і Хеллманом атаки зловмисникові доступний т.зв. який розшифровує оракул. Це означає, що зловмисник може відправити на вхід шифрувальної функції будь-яке повідомлення і отримати його зашифрований аналог.
Атака Тьмяніла-Хеллмана на потрійне шифрування зводиться до наступних дій:
  • атакуючий здійснює перебір всіх можливих 256 варіантів ключа K2, виробляє розшифровку блоку, що складається з нульових байтів і записує в таблицю T1 значення {DK2(0), K2}
  • атакуючий для кожного з 256 варіантів ключа K1, виробляє розшифровку блоку, що складається з нульових байтів: DK1(0). Значення DK1(0) атакуючий відправляє на вхід шифрующему оракула і розшифровує отриманий від оракула відповідь з допомогою підбирається ключа K1: DK1(Enc(DK1(0))). Отримане значення і варіант ключа K1 {DK1(Enc(DK1(0))), K1} записується в таблицю T2
  • Відсортувавши таблиці T1 і T2 атакуючий в якості ймовірних ключів приймає такі K1 і K2, для яких
    DK1(Enc(DK1(0))) = DK2(0).
Суть методу не зовсім очевидна. Для роз'яснень розпишемо що являє собою функція Enc(). Це стисла запис потрійного шифрування, тобто Enc(x) = EK1 (DK2 (EK1(x))).
В атаці Тьмяніла-Хеллмана атакуючий обчислює DK1(Enc(DK1(0))). Таким чином, якщо K1 вірно вгаданий в результаті виходить вираз DK1(EK1 (DK2 (EK1(DK1(0))))) = DK2(0).
Якщо отримане значення є в таблиці T1, то ключі K1 та K2 вибираються в якості ймовірних кандидатів.
Для реалізації атаки потрібно 257 операцій шифрування, що значно відрізняється від очікуваної стійкості потрійного шифрування 2112.
Зрозуміло атаки описані Мерклем і Хеллманом носять більш теоретичний характер і їх практична реалізація дуже малоймовірно, але вони дуже добре показують, як легко можна припуститися помилки при проектуванні криптосистем.

Закон Шнайера
Закон Шнайера застерігає від використання неперевірених систем безпеки і особливості систем, спроектовані самостійно. Обидва наведених вище варіанти вирішення проблеми довжини ключа DES були запропоновані професійними криптографами і тим не менш мали дуже серйозні недоліки, які були упущені при проектуванні. Наївно вважати, що аматор зможе створити стійку систему.
Філ Ціммерманн, творець PGP, написав з цього приводу наступне:
Коли я вчився в коледжі в 70-х я придумав, як мені тоді здавалося, ідеальну схему шифрування. Простий генератор псевдовипадкових чисел генерував гаму, яка підсумовувалася з відкритим текстом. Схема була стійкою проти частотного аналізу шифртекста і була зовсім не взламываема для спецслужб, що володіє величезними обчислювальними потужностями.
Роки потому я знайшов схожу схему у деяких підручниках з криптографії. Класно. Інші криптографи думають у схожому напрямку. На жаль, схема була описана в якості простого домашнього завдання: взломайте схему, використовуючи базові методи криптоаналізу.
Якщо ви вважаєте, що створили ідеально стійку систему, не поспішайте використовувати її у своєму проекті. Згадайте про закон Шнайера і краще скористайтеся широко відомим методом.

Посилання
Коментарі Брюса Шнайера про його законі.
Merkle, Hellman — On the security of multiple encryption
Phil Zimmermann on PGP

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.