Ідеальний шифр, який програв на практиці

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

Що таке шифр Вернама?

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

Одиниця на виході XOR буде тільки в тому випадку коли на два входи приходять різні біти:

$$C = M \oplus K \\ M = C \oplus K$$

Де:

• C - це шифротекст
• M - повідомлення у відкритому вигляді
• K - секретний ключ, такої ж довжини як і повідомлення або більшої

Шифр Вернама є основою одноразового блокнота (One-Time Pad). Його ключова особливість у тому, що за умови повністю випадкового ключа, такої ж довжини, як повідомлення, і одноразового використання, шифр має доказову ідеальну секретність, шифртекст не містить жодної інформації про відкритий текст.

Шифрування/дешифрування за допомогою шифра Вернама

Щоб зашифрувати/дешифрувати повідомлення, потрібно зробити XOR з секретним ключем.

Розглянемо цей процес на практиці.

Наше повідомлення буде таким:

Hello

Якщо перевести його за допомогою таблиці ASCII, отримаємо послідовність з 5 байт:

48 65 6c 6c 6f

Наш секретний ключ повинен теж бути довжиною 5 байт або більший, візьмемо 5 випадкових байтів в hex форматі:

8a b4 aa 51 0d

Вони нічого не значать, це “випадкова” послідовність з моєї голови.

Спробуємо зашифровати наше повідомлення за допомогою CyberChef:

В результаті отримуємо:

c2 d1 c6 3d 62

Це і є наш шифротекст.

Спробуємо дешифрувати, також за допомогою CyberChef:

В результаті отримаємо наше повідомлення:

Hello

В чому складність його зламу?

Ми використовуємо ключ довжиною 5 байт. Для сучасних комп’ютерів повний перебір такого простору ключів не становить складності: завдяки малій розмірності простору та простоті операції XOR, перебір може бути виконаний за хвилини або навіть секунди залежно від реалізації та використаного апаратного забезпечення.

Але є цікава деталь.

5 байт - це 40 біт:

$$5 * 8 = 40$$

За допомогою 40 біт ми можемо створити:

$$2^\text{40} = 1 099 511 627 776 \text{комбінацій}$$

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

Припустимо що перебираючи ключі він вирішив перевірити ключ 8e 95 f5 0c 25 для шифротексту: Зловмисник отримав текст, але він не знає це саме те що він шукав чи ні.

Кожен додатковий байт множить простір можливих повідомлень на 256, що робить повний перебір експоненційно складнішим.

Загальна кількість можливих повідомлень можна обчислити за формулою:

$$N(n) = 2^{8n}$$

Чому cлід використовувати одноразовий ключ?

Припустимо що один і той самий ключ K використали для двох повідомлень:

$$C_1 = M_1 \oplus K \\ C_2 = M_2 \oplus K$$

Зловмисник робить XOR двох шифртекстів:

$$C_1 \oplus C_2 = M_1 \oplus K \oplus M_2 \oplus K$$

Ключі в такому випадку зникають:

$$C_1 \oplus C_2 = M_1 \oplus M_2$$

Many Time Pad Attack

Припустимо що ми перехопили повідомлення.

56 ed 13 c6 3e
7d e9 11 8a 24
7c fd 06 8a 30
75 ed 19 c3 23
6a e7 1b cb 28

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

Починаємо аналізувати:

$$C_1 = 56\ ed\ 13\ c6\ 3e \\ C_2 = 7d\ e9\ 11\ 8a\ 24 \\ C_3 = 7c\ fd\ 06\ 8a\ 30 \\ C_4 = 75\ ed\ 19\ c3\ 23 \\ C_5 = 6a\ e7\ 1b\ cb\ 28$$

Та бачимо що:

$$C_2[3] == C_3[3]$$

Це значить що там стоять однакові символи.

Прибігаємо до частотного аналізу та припускаємо що там стоїть пробіл (20 в ASCII Hex).

$$C_2[3] == C_3[3] == \text{" "}$$

Робимо XOR:

$$(C_1[3] \oplus C_2[3]) \oplus 20 = 6c\ (\text{l в ASCII}) \\ (C_2[3] \oplus C_4[3]) \oplus 20 = 69\ (\text{i в ASCII}) \\ (C_2[3] \oplus C_5[3]) \oplus 20 = 61\ (\text{a в ASCII}) \\$$

Бачимо що це дає нам символи, робимо припущення що це саме ті символи які ми шукали. Тепер наші повідомлення виглядають так:

---l-
--- -
--- -
---i-
---a-

Це дає все ще не дало нам результат тому продовжуємо робити припущення. Перше повідомлення може бути привітанням - слово hello дуже добре туди підходить, тому перевіримо його:

$$C_1 \oplus C_2 \oplus \text{hello} = \text{Can u} \\ C_1 \oplus C_3 \oplus \text{hello} = \text{Buy a} \\ C_1 \oplus C_4 \oplus \text{hello} = \text{Kefir} \\ C_1 \oplus C_5 \oplus \text{hello} = \text{Today} \\$$

І ось тепер ми отримали такий результат:

hello
Can u
Buy a
Kefir
Today

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

Також ми все ще не можемо точно виявити ключ, бо в нас може бути багато комбінацій де використовуються різні регістри:

$$C_1 \oplus \text{hello} = \text{68 65 6c 6c 6f} \\ C_1 \oplus \text{Hello} = \text{48 65 6c 6c 6f} \\ C_1 \oplus \text{HEllo} = \text{48 45 6c 6c 6f} \\ ... \\ C_1 \oplus \text{HELlO} = \text{48 45 4c 6c 4f}$$

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

Чим більше в нас буде шифротекстів, тим легше нам буде коригувати результати та відновити початковий ключ.

Ми не просто грали в угадайку, а робили припущення, які потім перевіряли. Ця атака все ще складна, але можлива.

Проект Венона

У роки Холодної війни Радянський Союз використовував теоретично досконалий і непіддатливий до злому метод - шифр Вернама (одноразовий блокнот). Його стійкість базується на абсолютно випадкових ключах, які ніколи не повторюються.

Американські криптоаналітики розпочали надсекретний проєкт “Венона”. Їхньою метою було зламати радянські дипломатичні шифри. Вони перехоплювали радянські повідомлення та почали їх аналізувати.

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

Найнадійніша в теорії система була зламана через практичні недоліки в її реалізації, що призвело до одного з найгучніших розвідувальних провалів в історії.

Чому в сучасному світі майже не використовують шифр Вернама?

Хоча шифр Вернама є дуже простим, щоб гарантувати повну секретність треба використовувати його як одноразовий блокнот:

• ключі повинні бути такої ж або більшої довжини за повідомлення
• ключі повинні бути повністю випадковими
• ключі не повинні повторюватися

Повтор ключа (як у випадку Венони) миттєво руйнує абсолютну стійкість, і це вже не теоретична, а реальна історична проблема.

Саме тут і виникає головна проблема: передача й зберігання секретного ключа, розмір якого не менший за повідомлення, для кожного окремого сеансу зв’язку.

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

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

Резюме

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

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

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

Будь-яка помилка в реалізації, зокрема повторне використання ключа, миттєво руйнує його ідеальну стійкість.

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

Сучасна криптографія надає перевагу симетричним шифрам які показують практичну стійкість (наприклад AES про який вже писав статтю), де ми можемо використовувати короткий ключ для будь-якої довжини повідомлення, через простоту та можливість масштабування системи.

Завдання для самоперевірки

1. Спробуйте самостійно зашифрувати повідомлення зі своїм ключем
2. Опишіть що відбудеться якщо ключ буде довшим за повідомлення
3. Підберіть такий ключ до вашого шифротекст щоб він давав інше повідомлення
4. Спробуйте самостійно розшифрувати перехоплені шифротексти, які використовують один ключ:

C1 = 43 fe 10 ad 42
C2 = 4a e9 19 e1 58
C3 = 4d e9 19 a4 0d
C4 = 59 f2 1b a9 59
C5 = 45 f4 0b fe 0d

Підказки:

• Повідомлення - це частини одного діалогу, який містить питання
• Повідомлення містять розмовні англійські слова з максимальною довжиною 5 символів