Разработка DES и шифр Люцифера

В 1971 году Хорст Фейстель из исследовательского центра IBM разработал шифр под названием Lucifer в рамках проекта по обеспечению безопасности банковских операций для Lloyd's of London. Lucifer был одним из первых современных блочных шифров и использовал ключ размером 128 бит и блоки размером 128 бит.

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

DES применяет 16 раундов структуры Фейстеля к блокам размером 64 бита. В каждом раунде 64-битный блок разделяется на две половины по 32 бита. Правая половина расширяется до 48 бит, объединяется операцией XOR с подключом размером 48 бит, проходит через S-блоки, переставляется и объединяется операцией XOR с левой половиной.

Затем половины меняются местами, и процесс повторяется. После 16 раундов конечная перестановка создаёт 64-битный шифротекст. Расшифровка использует ту же структуру, но подключи применяются в обратном порядке.

DES шифрует данные блоками размером 64 бита (8 байт). Такой фиксированный размер блока подходил для аппаратного обеспечения 1977 года, но со временем стал фактором риска для безопасности. При обработке достаточного объёма данных коллизии из-за парадокса дней рождения становятся вероятными.

Для блоков размером 64 бита статистические закономерности проявляются примерно после 2^32 блоков (около 32 ГБ данных, зашифрованных с одним и тем же ключом). Атака Sweet32 сделала 3DES небезопасным для больших объёмов трафика, например HTTPS.

DES использует ключ размером 64 бита, но 8 бит являются битами чётности и используются для обнаружения ошибок, а не для шифрования. Поэтому эффективная длина ключа составляет всего 56 бит.

Это означает, что существует всего 2^56 (примерно 72 квадриллиона) возможных ключей DES. По стандартам 1977 года этого считалось достаточно. К 1997 году было наглядно доказано, что такой ключ может взломать целеустремлённый противник.

DES начинается с начальной перестановки (IP), которая изменяет порядок 64 битов блока открытого текста, и заканчивается конечной перестановкой (IP^-1), являющейся её точной обратной операцией. Эти перестановки не повышают криптографическую стойкость.

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

Восемь S-блоков (блоков подстановки) являются основой нелинейности DES. Каждый S-блок получает 6 входных битов и выдаёт 4 выходных бита с помощью фиксированной таблицы поиска. Внешние 2 бита выбирают строку, а внутренние 4 бита — столбец.

Без нелинейности, обеспечиваемой S-блоками, DES был бы полностью линейным шифром, который можно было бы тривиально взломать с помощью линейной алгебры. Конкретная конструкция S-блоков DES обеспечивает устойчивость к дифференциальному криптоанализу.

После S-блоков DES применяет перестановку P-блока, изменяющую порядок 32 выходных битов S-блоков. Это обеспечивает диффузию: результат каждого S-блока распространяется так, чтобы влиять на несколько S-блоков в следующем раунде.

P-блок был тщательно спроектирован для максимальной диффузии: каждый выходной бит одного S-блока влияет как минимум на два разных S-блока в следующем раунде, обеспечивая быстрое лавинное распространение.

DES выводит 16 различных 48-битных подключей из 56-битного главного ключа — по одному для каждого раунда. Расписание ключей начинается с применения перестановочного выбора (PC-1), который удаляет биты чётности и меняет порядок битов ключа.

56 битов разделяются на две 28-битные половины, которые в каждом раунде циклически сдвигаются влево на 1 или 2 позиции. Затем перестановочный выбор (PC-2) выбирает 48 из 56 битов, формируя подключ каждого раунда.

NSA сотрудничало с IBM при разработке DES, уменьшив длину ключа со 128 битов шифра «Люцифер» до 56 битов и изменив конструкцию S-блоков. Это вызвало многолетние споры о том, были ли внедрены потайные уязвимости.

В 1990-х годах представители NSA подтвердили, что усилили S-блоки против дифференциального криптоанализа — метода, открытого IBM в 1974 году. NSA знало о дифференциальном криптоанализе за несколько лет до академического сообщества, что указывает: организация сделала DES более устойчивым, а не менее защищённым.

DES был принят как федеральный стандарт обработки информации 46 в январе 1977 года после конкурсной оценки. Он стал стандартным шифром для несекретных государственных данных и получил широкое распространение в банковской сфере и промышленности.

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

Сам по себе DES является блочным шифром и шифрует ровно 64 бита за раз. Реальные сообщения длиннее, поэтому режимы работы определяют, как применять шифр к нескольким блокам. К распространённым режимам относятся ECB (шифрование каждого блока независимо), CBC (применение XOR к каждому блоку с предыдущим шифротекстом перед шифрованием), CFB, OFB и CTR.

ECB — самый слабый режим: одинаковые блоки открытого текста дают одинаковые блоки шифротекста, из-за чего становятся видны закономерности. Режимы CBC и CTR устраняют эту уязвимость и предпочтительны для практического использования DES и тройного DES.

DES развился из шифра Lucifer компании IBM в 16-раундовый шифр Фейстеля с 64-битными блоками и эффективными ключами длиной 56 битов. Его безопасность обеспечивают 8 нелинейных S-блоков, создающих запутывание, P-блок, обеспечивающий рассеивание, и 16 раундов, усиливающих лавинный эффект.

Участие NSA в разработке S-блоков вызывало споры, но в итоге повысило устойчивость к дифференциальному криптоанализу. 56-битный ключ DES, рассчитанный на аппаратное обеспечение 1977 года, к концу 1990-х оказался недостаточно защищённым.