DES

DES — это симметричный блочный шифр, разработанный корпорацией IBM в 1970-х годах и принятый в 1977 году в качестве стандарта правительством США для защиты несекретной информации. Полное название — Data Encryption Standard (стандарт шифрования данных). Он стал первым широко распространённым криптографическим алгоритмом, открыто опубликованным и стандартизированным на национальном уровне. DES использует ключ длиной 56 бит и обрабатывает данные блоками по 64 бита, выполняя 16 раундов преобразований, основанных на сети Фейстеля. Со временем, в первую очередь из-за недостаточной длины ключа, DES был признан уязвимым для атак полным перебором и в 2001 году формально заменён более стойким стандартом AES.

История

Разработка и стандартизация

Предпосылкой к созданию DES стала потребность правительства США и финансового сектора в едином, надёжном и открытом стандарте защиты цифровых данных, передаваемых по незащищённым каналам. В 1972 году Национальное бюро стандартов США (NBS, ныне NIST) объявило конкурс на создание такого алгоритма.

Корпорация IBM, имевшая опыт в криптографии (включая разработку шифра «Люцифер», созданного Хорстом Фейстелем), представила свой алгоритм. В 1976 году после доработки и консультаций с Агентством национальной безопасности США (АНБ) этот алгоритм был принят в качестве федерального стандарта, официально опубликован в 1977 году (FIPS PUB 46). Участие АНБ вызвало подозрения по поводу возможного внедрения «чёрного хода» и намеренного ослабления ключа, что впоследствии подтвердилось в рассекреченных документах: АНБ настояло на сокращении длины ключа с 128 до 56 бит и модификации S-блоков.

Использование и кризис

DES быстро завоевал популярность и стал стандартом де-факто в банковской сфере, электронной коммерции и государственных учреждениях США. Он использовался для защиты финансовых транзакций по каналам автоматических кассовых аппаратов, сетям SWIFT, а также для шифрования документов.

Однако уже в 1990-х годах растущая вычислительная мощность компьютеров сделала DES уязвимым. В 1997 году исследователи продемонстрировали возможность взлома DES полным перебором за несколько месяцев. В 1998 году Electronic Frontier Foundation (EFF) за $250 000 построила специальную машину «Deep Crack», способную взломать DES за 56 часов. Это стало концом эпохи DES как надёжного шифра. В 1999 году совместная атака с использованием Deep Crack и 100 000 добровольцев по сети расправилась с ключом DES за 22 часа.

Переход к Triple DES и AES

В ответ на уязвимость DES была разработана более стойкая версия — тройной DES (Triple DES, 3DES), который применял алгоритм DES трижды с двумя или тремя разными ключами (эффективная длина ключа около 112–168 бит). В 2001 году NIST официально принял новый стандарт AES (Advanced Encryption Standard) на основе алгоритма Rijndael, полностью заменивший DES. Тем не менее, 3DES продолжал использоваться до 2023 года, когда NIST рекомендовал вывести его из обращения по причинам медленной работы и снижения безопасности.

Устройство и алгоритм

DES является блочным шифром, работающим по схеме сети Фейстеля. Это означает, что блок открытого текста делится пополам (левая и правая части), затем правая часть преобразуется с помощью функции раунда и ключа, после чего результаты складываются по модулю 2 (XOR) с левой частью, и половинки меняются местами.

Основные компоненты

• Размер блока: 64 бита (8 байт).
• Размер ключа: 64 бита, но эффективных только 56 бит (8 бит используются как биты чётности).
• Число раундов: 16.

Функция раунда (F)

Функция F принимает на вход 32-битный полублок и 48-битный раундовый ключ. Её этапы:

1. Расширение (Expansion): 32-битный полублок расширяется до 48 бит с помощью таблицы перестановок (E-box), дублирующей некоторые биты.
2. Сложение с ключом (Key XOR): 48-битный результат складывается по модулю 2 с 48-битным раундовым ключом.
3. Подстановка S-блоков (Substitution): 48-битная комбинация разбивается на 8 групп по 6 бит. Каждая группа поступает на вход своего S-блока — нелинейного преобразователя, заменяющего 6-битный вход на 4-битный выход. Каждый из 8 S-блоков представляет собой таблицу 4×16, в которой строки и столбцы задаются определёнными битами входа. Спроектированы для обеспечения нелинейности (диффузии и конфузии).
4. Перестановка (Permutation, P-box): 32-битный результат всех S-блоков проходит через фиксированную перестановку, определяющую, какой бит из какого S-блока куда попадёт.

Генерация раундовых ключей (Key Schedule)

Из 56-битного ключа (после удаления битов чётности) генерируются 16 различных 48-битных раундовых ключей:

1. Перестановка выборки (Permuted Choice 1, PC-1): Удаление битов чётности и перестановка битов, деление на две 28-битные половины (C0 и D0).
2. Циклические сдвиги: Для каждого раунда i обе половины сдвигаются на 1 или 2 позиции (по определённому расписанию).
3. Перестановка выборки (Permuted Choice 2, PC-2): Из объединённых 56-битных половин выбирается 48 бит, которые становятся раундовым ключом.

Шифрование и дешифрование

Процесс шифрования состоит из начальной перестановки (IP), 16 раундов сети Фейстеля с функциями F и ключами, и конечной перестановки (IP-1), обратной начальной. Для дешифрования используется тот же алгоритм, но ключи подаются в обратном порядке (начиная с k16, затем k15 и т. д.), что является свойством сети Фейстеля.

Криптостойкость и уязвимости

Длина ключа

Главное и очевидное слабое место DES — длина ключа в 56 бит. Полный перебор всех 2^56 (около 7,2×10^16) ключей стал возможен с развитием электроники. К 2000-м годам стоимость взлома DES полным перебором оценивалась в несколько тысяч долларов.

Устойчивость к дифференциальному и линейному криптоанализу

DES был спроектирован таким образом, чтобы быть устойчивым к дифференциальному криптоанализу (разработанному Aдемом и Бихемом в конце 1980-х). Сам факт защиты от этого метода, ранее неизвестного публике, косвенно подтверждал, что АНБ знало о нём. Линейный криптоанализ (Мицуру Мацуи, 1993) открыл теоретически доступный путь атаки на DES, требующий 2^47 известных открытых текстов, что на практике было затруднительно, но показало теоретическую слабость.

S-блоки

Проектирование S-блоков было одним из главных источников подозрений. Рассекреченные документы показали, что АНБ участвовало в их оптимизации, введя определённые нелинейные свойства, которые делали алгоритм более стойким к дифференциальному криптоанализу, чем если бы блоки оставались первоначальными (как у «Люцифера»). Однако это также привело к тому, что S-блоки не стали публично обоснованными, что нарушало идею открытого стандарта.

Атаки по времени и по побочным каналам

Как и многие аппаратные шифры, DES может быть уязвим для атак по времени выполнения, по электромагнитному излучению или по потребляемой мощности (side-channel attacks). Внедрение программных реализаций может частично нивелировать эту угрозу.

Варианты и потомки

Triple DES (3DES)

В ответ на короткий ключ DES был разработан тройной DES. Алгоритм применяет DES трижды: зашифровать первым ключом (K1), расшифровать вторым (K2) и снова зашифровать третьим (K1 или K3).

• EDE (Encrypt-Decrypt-Encrypt): Наиболее распространённая схема. При K1=K2=K3 получается обычный DES (обратная совместимость).
• Варианты ключей: Три независимых ключа (168bit total) или два ключа (K1, K2, K1 — 112bit total).
• Недостатки: Медленный (в 3 раза медленнее DES), имеет проблемы с безопасностью при использовании коротких ключей (112 бит) и уязвим для атак на основе связанных ключей. В 2023 году NIST окончательно исключил 3DES из списка рекомендованных алгоритмов.

DES-X

Вариант, в котором перед раундами DES к открытому тексту добавляется 64-битный предварительный ключ (whitening), а после — ещё один 64-битный. Общая длина ключа — 184 бита (56+64+64), но эффективная стойкость оценивается в 119 бит. Простая и более быстрая альтернатива 3DES.

ГОСТ 28147-89 (Советский аналог)

В 1989 году в СССР был принят собственный стандарт шифрования — ГОСТ 28147-89. Он также является блочным шифром с 32 раундами, блоком 64 бита и ключом 256 бит. Алгоритм не был получен из DES, но представляет собой самостоятельную разработку, основанную на сходной структуре сети Фейстеля. В 2015 году в России был принят новый стандарт ГОСТ Р 34.12-2015, включающий блочные шифры «Магма» (64-битный блок, ключ 256 бит) и «Кузнечик» (128-битный блок, ключ 256 бит), которые фактически заменили ГОСТ 28147-89.

Применение

Несмотря на официальный вывод из употребления, DES и его варианты (прежде всего 3DES) оставили глубокий след в криптографии и информационных технологиях:

• Банковские сети: DES десятилетиями защищал транзакции в банкоматах (ATM), системах обмена электронными сообщениями SWIFT, а также в платёжных протоколах Visa и MasterCard. До сих пор огромное количество устаревших банковских терминалов работают на 3DES.
• Unix и пароли: Алгоритм DES (а точнее, его модификация «Crypt(3)» с солью) использовался для хеширования паролей пользователей в Unix-системах. Хотя он давно устарел для этой цели, его наследие состоит в том, что понятие «salt» (соль) и «hash» для паролей были популяризированы им.
• Стандарты безопасности: DES стал базой для множества стандартов, включая Kerberos, S/MIME, PPTP (версия 1) и Wi-Fi Protected Access (WPA) — в последнем 3DES был одним из вариантов.
• Криптографическое образование: DES — основная модель для изучения блочных шифров, сети Фейстеля и методов криптоанализа в вузах. Его простота (относительно современных шифров) позволяет легко демонстрировать принципы работы и уязвимости.

Интересные факты

1. «Чёрный вход» АНБ: В течение 20 лет ходили слухи, что АНБ намеренно ослабило DES. В 2015 году рассекреченные документы подтвердили это: АНБ действительно настояло на уменьшении длины ключа до 56 бит и модифицировало S-блоки. Однако мотивация была двойственной: с одной стороны, чтобы иметь возможность взламывать шифрование других стран, с другой — чтобы предотвратить принятие слабого алгоритма, который можно атаковать.
2. «Голубые книги»: Исходные описания DES из FIPS PUB 46 были опубликованы в виде «синих книг» (Blue Books) правительства США, которые стали библиографической редкостью у криптографов.
3. 90-минутный взлом: В 2004 году группа российских студентов под руководством профессора Алексея Савинского провела демонстрацию аппаратного взлома DES с помощью FPGA-ускорителей. При бюджете около $15 000 они показали возможность подбора ключа за несколько часов. Результат был представлен на конференциях по кибербезопасности.
4. Музей в Мюнхене: Оригинальная машина «Deep Crack» (EFF) сейчас находится в постоянной экспозиции Немецкого музея в Мюнхене как экспонат, иллюстрирующий уязвимость классической криптографии перед вычислительной мощностью.

Источники

• National Institute of Standards and Technology (NIST). Data Encryption Standard (DES). FIPS PUB 46-3, 1999.
• Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. Handbook of Applied Cryptography. CRC Press, 1996.
• Schneier, B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons, 1996.
• Diffie, W., & Hellman, M. Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Computer, 1977.
• Electronic Frontier Foundation. Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design. O'Reilly Media, 1998.
• Shamir, A., & Biham, E. Differential Cryptanalysis of the Data Encryption Standard. Springer, 1993.
• Мацуи, М. Linear Cryptanalysis Method for DES Cipher. Advances in Cryptology – EUROCRYPT'93.
• Федеральный закон «Об информации, информационных технологиях и о защите информации» (в части требований к криптографии).