DES и 3DES

Июль 1998 года, Electronic Frontier Foundation выкатывает DES Cracker - стойку с 1856 чипами за $250 000. За 56 часов машина перебирает все 2^56 ключей DES и ломает зашифрованное сообщение. Алгоритм, утверждённый правительством США 21 год назад как национальный стандарт, оказывается прозрачным для энтузиастов с бюджетом среднего пентхауса.

• **Банковские системы (1980-2010)**: ATM-сети, SWIFT и платёжные терминалы шифровали PIN-блоки на DES, затем мигрировали на 3DES (стандарт ANSI X9.52). До 2024 года 3DES оставался обязательным в PCI DSS для legacy-карт
• **SET и SSL 2.0 (1995-1999)**: ранние протоколы электронной коммерции использовали 56-битный DES из-за экспортных ограничений США. После их отмены в 2000 году отрасль быстро переехала на AES-128 и AES-256
• **Kerberos v4**: вся аутентификация в локальных сетях Microsoft до 2000-х строилась на DES; v5 добавил поддержку 3DES, а современные реализации используют AES

Структура DES

В 1977 году NIST принял DES (Data Encryption Standard) на основе шифра Lucifer от IBM. Размер блока - 64 бита, ключ - 56 бит (8 байт по 7 бит, восьмой бит в каждом байте - проверка чётности). DES - это сеть Фейстеля из 16 раундов: блок делится на левую L и правую R половины, на каждом раунде выполняется L_{i+1} = R_i, R_{i+1} = L_i XOR F(R_i, K_i). Функция F - сердце шифра: расширение R до 48 бит, XOR с раундовым ключом, 8 параллельных S-боксов (6 бит -> 4 бита) и финальная P-перестановка.

Перестановки IP (initial) и FP (final, обратная к IP) не дают криптографической стойкости - они нужны были для аппаратной реализации в 1970-х (последовательная загрузка битов в регистры). S-боксы спроектированы NSA с учётом устойчивости к дифференциальному криптоанализу (открыт публично только в 1990 году Бихамом и Шамиром - NSA знала о нём за 15 лет до этого).

Расписание ключей

Из 64-битного входного ключа DES выбрасывает 8 битов чётности, оставляя 56 бит. Эти 56 бит делятся на две половины C0 и D0 по 28 бит. На каждом раунде обе половины циклически сдвигаются влево (на 1 или 2 бита по таблице), и из 56 объединённых бит выбираются 48 - это раундовый подключ K_i. Всего 16 подключей по 48 бит. Сдвиги выбраны так, что после 16 раундов суммарный сдвиг равен 28 - и регистр возвращается в начальное положение.

Слабые ключи DES: всего 4 ключа, для которых все 16 K_i одинаковы (например, все нули или все единицы в каждой половине C, D). Для слабого ключа DES(DES(x, K), K) = x - двойное шифрование возвращает исходный текст. Полуслабые пары: 6 пар ключей (K1, K2) таких, что DES_K1 = DES_K2^{-1}. На практике эти ключи легко исключить, но они показывают, что не всё пространство 2^56 равноценно.

Triple DES (3DES)

К концу 1990-х DES стал прозрачным для атак полным перебором: в 1998 году машина DES Cracker от EFF за $250 000 ломала DES за 56 часов. NIST не мог быстро принять новый стандарт, и появилось временное решение - 3DES: C = E_{K3}(D_{K2}(E_{K1}(P))). Три ключа по 56 бит дают суммарно 168 бит, но из-за meet-in-the-middle эффективная стойкость - 112 бит. Схема EDE (encrypt-decrypt-encrypt) вместо EEE обеспечивает обратную совместимость: если K1 = K2 = K3, то 3DES вырождается в обычный DES.

Варианты 3DES по количеству независимых ключей: 3-key 3DES (K1, K2, K3 независимы, 168 бит ключевого материала, 112 бит реальной стойкости) - использовался в финансовом секторе; 2-key 3DES (K1 = K3, K2 независим, 112 бит, реальная стойкость ~80 бит) - быстрее, но слабее. NIST отозвал 3DES в 2024 году из-за атаки Sweet32: при длинных сессиях с блоком 64 бита возникают коллизии после ~2^32 блоков (32 ГБ), что позволяет атаку на режимы CBC и CTR.

Атака Meet-in-the-Middle

Кажется логичным: если 2^56 мало, давайте применим DES дважды - 2DES с двумя независимыми ключами K1, K2 даст 112-битное пространство. Diffie и Hellman в 1977 году показали, что это не так. Атака meet-in-the-middle: для известной пары (P, C) перебираем все K1 и записываем X = E_{K1}(P) в таблицу; затем перебираем все K2 и проверяем D_{K2}(C) - совпадение с записью в таблице даёт кандидата (K1, K2). Сложность: 2 * 2^56 операций и 2^56 памяти - примерно как один DES.

Именно поэтому 3DES использует ТРИ применения, а не два: атака meet-in-the-middle на 3DES стоит ~2^112 операций (а не 2^168). Memory-time trade-off: на практике память дороже времени, и реальные атаки на 3DES требуют ~2^120 операций. Современные шифры (AES) спроектированы так, что нет известных атак лучше полного перебора (для AES-128 это 2^128 - на горизонте десятилетий невыполнимо).

Ключевые идеи

• **DES** - сеть Фейстеля из 16 раундов с 56-битным эффективным ключом (8 бит чётности отбрасываются). S-боксы спроектированы NSA для защиты от дифференциального криптоанализа
• **Расписание ключей** генерирует 16 раундовых подключей по 48 бит циклическими сдвигами двух 28-битных половин. Несколько слабых ключей дают одинаковые K_i для всех раундов
• **3DES (EDE)** утроил применение DES для продления жизни стандарта. Схема E(D(E)) обеспечивает обратную совместимость: K1=K2=K3 сводит 3DES к обычному DES
• **Meet-in-the-middle** - причина, по которой 2DES бесполезен (стойкость ~2^57), а 3DES имеет всего 112 бит вместо 168. Memory-time trade-off экономит один ключ из стека многократных шифрований

Связанные темы

DES Cracker за 56 часов из вступления показал главное: фиксированный ключ малого размера обречён против закона Мура. Это вынудило NIST объявить конкурс AES и заставило отрасль научиться оценивать атаки memory-time. DES стоит в центре сразу нескольких направлений криптографии:

• Блочные шифры: принципы — DES - канонический пример сети Фейстеля и принципов диффузии-конфузии Шеннона. Все обсуждаемые там S-боксы и avalanche effect конкретизируются на DES
• AES — Преемник DES, выбранный в 2001 году после открытого конкурса NIST. Использует не сеть Фейстеля, а SP-сеть, поддерживает 128/192/256-битные ключи
• Режимы шифрования — ECB, CBC, CTR, GCM применяют блочный шифр (DES, 3DES, AES) к сообщениям произвольной длины. Атака Sweet32 на 3DES возможна только в режиме CBC/CTR из-за 64-битного блока

Вопросы для размышления

• Если 2DES даёт стойкость всего 57 бит, то почему 4DES даст не 113, а всего 113 бит (а не 224)? Сформулируйте обобщённое правило для k-DES
• Sweet32 атакует 3DES именно из-за маленького блока в 64 бита. Если завтра обнаружится способ удвоить размер блока DES до 128 бит, имеет ли смысл возвращать 3DES в эксплуатацию или AES всё равно предпочтительнее?
• Почему IBM и NSA в 1970-х держали в секрете критерий проектирования S-боксов? Какой пример из дифференциального криптоанализа показывает, что 'security through obscurity' иногда работает (в отношении атак, не самих констант)?

Связанные уроки

• crypto-12-block-cipher-principles — Feistel-сеть и принципы блочных шифров - основа для DES
• crypto-14-aes — AES заменил DES - урок-преемник
• crypto-07-computational-complexity — 56-битный ключ DES: перебор как задача сложности
• alg-01-big-o — Brute-force атака на DES - O(2^56): Big O для cryptographic search space
• alg-35-bit-manipulation
• nt-03