Data Encryption Standard

Data Encryption Standard (DES) — это симметричный блочный шифр, разработанный в 1970-х годах в США и принятый в качестве федерального стандарта шифрования данных (FIPS PUB 46) в 1977 году. DES стал первым общедоступным и широко применяемым криптографическим алгоритмом, который использовался для защиты конфиденциальной, но несекретной информации правительственными учреждениями и коммерческими организациями. Несмотря на то, что в начале XXI века он был признан устаревшим из-за недостаточной длины ключа, DES сыграл ключевую роль в развитии современной криптографии и лёг в основу более стойкого алгоритма Triple DES (3DES).

История

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

В начале 1970-х годов Национальное бюро стандартов США (NBS, ныне NIST) осознало необходимость в едином криптографическом стандарте для защиты правительственных и коммерческих данных. В 1973 году NBS объявило открытый конкурс на разработку алгоритма. На конкурс поступило несколько предложений, но ни одно из них не было признано полностью удовлетворительным. В 1974 году компания IBM представила алгоритм, основанный на её ранней разработке — шифре Lucifer, созданном под руководством Хорста Фейстеля. После доработки при участии Агентства национальной безопасности США (АНБ) алгоритм был принят в качестве стандарта.

В 1977 году NBS опубликовало спецификацию DES как Федерального стандарта обработки информации (FIPS PUB 46). Стандарт был рассчитан на пересмотр каждые пять лет, что позволяло оценивать его стойкость с учётом развития вычислительной техники.

Критика и роль АНБ

С самого начала стандартизация DES сопровождалась спорами. Основные претензии касались двух моментов:

1. Длина ключа. Первоначальный алгоритм IBM использовал 128-битный ключ, но в финальной версии он был сокращён до 56 бит. Критики полагали, что это было сделано по настоянию АНБ, чтобы правительство США могло взламывать шифрование при необходимости.
2. Секретные S-блоки. Внутренняя структура DES содержала так называемые S-блоки (таблицы подстановки), принцип построения которых не был раскрыт. Существовали опасения, что АНБ могло внедрить в них «чёрный ход». Позднее, после рассекречивания некоторых документов, было установлено, что S-блоки были спроектированы для защиты от дифференциального криптоанализа — метода, который был открыт в академической среде только в 1990-х годах.

Пересмотр и устаревание

DES пересматривался в 1983, 1988 и 1993 годах, каждый раз подтверждалась его пригодность. Однако к концу 1990-х годов вычислительные мощности позволили проводить атаки полным перебором 56-битного ключа за приемлемое время. В 1997 году в рамках открытого конкурса был взломан ключ DES за 96 дней, а в 1998 году организация Electronic Frontier Foundation (EFF) построила специализированное устройство «Deep Crack», которое взломало ключ за 56 часов.

В 1999 году NIST объявил о том, что DES больше не является стандартом, и рекомендовал переходить на Advanced Encryption Standard (AES). Окончательно стандарт FIPS 46 был отозван в 2005 году.

Алгоритм работы

DES является блочным шифром Фейстеля. Это означает, что шифрование и расшифрование выполняются по одной и той же структуре, но с обратным порядком использования раундовых ключей.

Основные параметры

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

Процесс шифрования

1. Начальная перестановка (IP). 64-битный блок данных подвергается фиксированной перестановке битов.
2. Разделение на половины. Блок делится на левую (L0) и правую (R0) половины по 32 бита каждая.
3. 16 раундов. В каждом раунде (i от 1 до 16) выполняются следующие действия:

• Функция Фейстеля (F) применяется к правой половине (Ri-1) и раундовому ключу (Ki).
• Полученный результат складывается по модулю 2 (XOR) с левой половиной (Li-1).
• Половины меняются местами: новая левая половина (Li) становится старой правой (Ri-1), а новая правая половина (Ri) — результатом XOR.
• Функция F состоит из четырёх этапов: расширение (Expansion) правой половины до 48 бит, сложение XOR с 48-битным раундовым ключом, подстановка через 8 S-блоков (каждый преобразует 6 бит в 4 бита) и финальная перестановка (P-box).

1. Конечная перестановка (IP⁻¹). После 16-го раунда выполняется обратная начальной перестановка, и результирующий 64-битный блок является зашифрованным текстом.

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

Из 56-битного эффективного ключа генерируются 16 различных 48-битных раундовых ключей. Процесс включает:

• Разделение ключа на две 28-битные половины.
• Циклический сдвиг каждой половины влево на 1 или 2 бита (в зависимости от номера раунда).
• Выборка 48 бит из сдвинутых половин с помощью фиксированной перестановки (Compression Permutation).

Виды и модификации

Triple DES (3DES)

Самой распространённой модификацией DES является Triple DES, описанный в стандартах FIPS 46-3 и NIST SP 800-67. Он применяет алгоритм DES трижды к каждому блоку данных. Существуют два основных варианта:

• 2TDEA (два ключа): Шифрование выполняется с ключом K1, затем расшифрование с ключом K2, и снова шифрование с K1. Эффективная длина ключа — 112 бит.
• 3TDEA (три ключа): Шифрование, расшифрование и шифрование выполняются с тремя разными ключами (K1, K2, K3). Эффективная длина ключа — 168 бит.

Triple DES был рекомендован в качестве временной замены DES, пока разрабатывался AES. Он до сих пор используется в некоторых устаревших системах (например, в финансовом секторе для обработки транзакций по картам), но NIST официально запретил его использование после 2023 года для нового оборудования.

DESX

Вариант, предложенный Роном Ривестом, в котором перед шифрованием DES блок данных складывается XOR с дополнительным 64-битным ключом (whitening), а после шифрования — ещё с одним. Это увеличивает стойкость к атакам полным перебором без усложнения самого алгоритма.

Криптоанализ и стойкость

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

Основная уязвимость DES — короткий 56-битный ключ. В 1998 году EFF продемонстрировала, что специализированное устройство «Deep Crack» стоимостью около 250 000 долларов может взломать ключ DES в среднем за 4,5 дня. С развитием облачных вычислений и графических процессоров (GPU) взлом DES стал доступен практически любому энтузиасту за несколько часов или дней.

Дифференциальный криптоанализ

Этот метод был впервые открыт в академической среде в 1990 году Эли Бихамом и Ади Шамиром. Он основан на анализе влияния разности между двумя открытыми текстами на разность их шифротекстов. Для взлома полного 16-раундового DES требуется около 2^47 выбранных открытых текстов. Однако, как выяснилось позже, разработчики DES из IBM и АНБ знали об этом методе ещё в 1970-х годах и спроектировали S-блоки так, чтобы сделать шифр максимально устойчивым к данной атаке.

Линейный криптоанализ

Предложенный Мицуру Мацуи в 1993 году, этот метод основан на аппроксимации нелинейных S-блоков линейными функциями. Для взлома DES с помощью линейного криптоанализа требуется около 2^43 известных открытых текстов. Это более эффективная атака, чем дифференциальная, но она всё равно требует огромного объёма данных, что делает её малоприменимой на практике для перехвата реального трафика.

Применение

Несмотря на устаревание, DES и его варианты оказали огромное влияние на индустрию:

• Финансовые системы: Стандарт ANSI X3.92 и его производные (например, PIN-блоки в банкоматах) десятилетиями использовали DES. Многие системы до сих пор поддерживают 3DES для обратной совместимости.
• Протоколы безопасности: Ранние версии SSL/TLS, SSH, IPsec и Kerberos включали DES в качестве одного из поддерживаемых шифров.
• Смарт-карты и аппаратные модули безопасности (HSM): Многие старые модели использовали DES для шифрования данных на чипе.
• Образовательные цели: DES является классическим примером блочного шифра Фейстеля и широко изучается в курсах криптографии для иллюстрации принципов проектирования и криптоанализа.

Наследие

DES стал первым открытым криптографическим стандартом, который подвергся массовому анализу со стороны академического сообщества. Его публичная спецификация и последующие попытки взлома стимулировали развитие таких областей, как дифференциальный и линейный криптоанализ. Конструкция сети Фейстеля, используемая в DES, позже была применена в более современных алгоритмах, таких как Blowfish, Twofish и RC5. В 2001 году на смену DES пришёл Advanced Encryption Standard (AES), основанный на алгоритме Rijndael, который обеспечивает большую стойкость и производительность.

Источники

• FIPS PUB 46-3: Data Encryption Standard (DES) (1999, отозван в 2005).
• NIST Special Publication 800-67: Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher.
• Bruce Schneier. Applied Cryptography, 2nd Edition. — John Wiley & Sons, 1996.
• Eli Biham, Adi Shamir. Differential Cryptanalysis of the Data Encryption Standard. — Springer-Verlag, 1993.
• Mitsuru Matsui. Linear Cryptanalysis Method for DES Cipher. — EUROCRYPT, 1993.
• Electronic Frontier Foundation. Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design. — O'Reilly Media, 1998.