Криптостійкість алгоритму DES

Нелінійність перетворень в DES засобами тільки S-блоків, у разі, якщо вони мають слабину, дозволяє здійснювати контроль за шифрованого листуванням. Вибір S-блоків вимагає дотримання декількох умов:

• Кожен рядок кожного блоку повинна бути перестановкою множини {0,1,2,......, 15}

• S-блоки не повинні бути лінійною або афінною функцією своїх аргументів.

• Зміна одного біта на вході S-блоку повинно приводити до зміни принаймні двох бітів на виході.

• Для кожного S-блоку і будь-якого аргументу х значення S (x) і повинні розрізнятися принаймні двома бітами.

Через невеликого числа можливих ключів (всього 256), з'являється можливість їх повного перебору на швидкодіючої обчислювальної техніки за реальний час. У 1998 році The Electronic Foundation використовуючи спеціальний комп'ютер DES-Cracker, вдалося зламати DES за 3 дні.

В алгоритмі DES існують слабкі і частково-слабкі ключі. Слабкими ключами називається ключі k такі що DESk (DESk (x)) = x, x - блок 64 біт. Частково-слабкі ключі - пари ключів (k1, k2) такі що DESk1 (DESk2 (x)) = x

Відомі 4 слабких ключа, вони наведені в таблиці 9. Для кожного слабкого ключа існує 232 «постійні точки», тобто таких 64-бітових блоків х, в яких DESk (x) = x

Таблиця 9. DES-Слабкі ключі

Слабкі ключі (hexadecimal) C0 D0

0101-0101-0101-0101 [0] 28 [0] 28

FEFE-FEFE-FEFE-FEFE [1] 28 [1] 28

1F1F-1F1F-0E0E-0E0E [0] 28 [1] 28

E0E0-E0E0-F1F1-F1F1 [1] 28 [0] 28

[0] 28 позначає вектор, що складається з 28 нульових бітів.

Існують 6 частково-слабких пар ключів, вони приведені в таблиці 10. Для кожного з 12 частково-слабких ключів існують 232 «анти-постійні точки», тобто такі блоки х, що

Таблиця 10. Частково-слабкі ключі

C0 D0 Пари частково-слабких ключів C0 D0

[01] 14 [01] 14 01FE-01FE-01FE-01FE, ---- FE01-FE01-FE01-FE01 [10] 14 [10] 14

[01] 14 [01] 14 1FE0-1FE0-1FE0-1FE0, ---- E0F1-E0F1-E0F1-E0F1 [10] 14 [10] 14

[01] 14 [0] 28 01E0-01E0-01F1-01F1, ---- E001-E001-F101-F101 [10] 14 [0] 28

[01] 14 [1] 28 1FFE-1FFE-0EFE-0EFE, ---- FE1F-FE1F-FE0E-FE0E [0] 28 [1] 28

[0] 28 [01] 14 O11F-011F-010E-010E, ---- 1F01-1F01-0E01-0E01 [0] 28 [10] 14

[1] 28 [01] 14 E0FE-E0FE-F1FE-F1FE, ---- FEE0-FEE0-FEF1-FEF1 [1] 28 [10] 14

Відомі атаки на DES.

Повний пошук 1 - Незначний 255

Лінійний Криптоаналіз 243 (85%) - Для тексту 243

Лінійний Криптоаналіз 238 (10%) - Для тексту 250

Диффер. Криптоаналіз - 247 Для тексту 247

Диффер. Криптоаналіз 255 - Для тексту 255

• Метод повного пошуку вимагає одну відому пару шифрованого і розшифрованого тексту, незначний обсяг пам'яті, і для його виконання потрібні 255 кроків.

• Диференціальний криптоаналіз - першу таку атаку на DES заявили Biham й Shamir. Ця атака вимагає шифрування 247 відкритих текстів обраних нападаючим, і для її виконання потрібні 247 кроків. Теоретично будучи крапкою розриву, ця атака непрактична через надмірні вимоги до підбору даних і складності організації атаки по обраному відкритому тексту. Самі автори цієї атаки Biham й Shamir заявили, що вважають DES захищеним для такої атаки.

• Лінійний криптоаналіз розроблений Matsui. Цей метод дозволяє відновити ключ DES за допомогою аналізу 243 відомих відкритих текстів, при цьому потрібно 243 кроків для виконання. Перший експериментальний криптоаналіз DES, заснований на відкритті Matsui, був успішно виконаний протягом 50 днів на автоматизованих робочих місцях 12 HP 9735.

Для лінійної та диференціальної атак потрібно досить великий обсяг пам'яті для збереження вибраних (відомих) відкритих текстів до початку атак.