Шифр Сатаны!⁠⁠

Здравствуйте, ребятушки! Сегодня у нас на повестке шифр из самых недр преисподней. У одного из предков современной блочной криптографии буквально было имя Lucifer — прямо в служебных документах IBM, без иронии и без маркетинга.

Никакого дьявола. Виноват лимит на длину имени файла

В конце 1960-х в исследовательском центре IBM в Йорктаун-Хайтс шла разработка системы защиты данных под кодовым названием Demonstration. Операционная система не умела в длинные имена файлов — и Demonstration пришлось сократить до Demon. А дальше кто-то из инженеров решил, что раз уж «демон», можно и доиграть словами. Так появился Lucifer.

Человек, который сбежал от нацистов, чтобы придумать шифр для американской армии

Автора Lucifer звали Хорст Фейстель, и его собственная биография тянет на отдельный сценарий фильма, который никто не снимет. Да и зачем, можно же снимать сказки и ремейки старых фильмов, ведь на такую историю финансирование не получишь, не то, что… Стоп! Статья же про криптографию.

Хорст Фейстель родился в Берлине 30 января 1915 года. В 1934 году транзитом через Швейцарию он эмигрировал в США (не стал ждать повестки в военкомат, в Германии всеобщая воинская повинность была официально введена в 1935 году) где получил степень бакалавра по физике в MIT, а затем магистра в Гарварде.

Во время Второй мировой войны Фейстель, как уроженец Германии, находился под домашним арестом. Американское гражданство он получил только 31 января 1944 года. Уже на следующий день ему дали допуск к работе и он приступил к работе в Air Force Cambridge Research Center — над системами радиолокационного опознавания «свой-чужой».

После войны были лаборатория Линкольна при MIT, MITRE, а в 1968 году — исследовательский центр IBM в Йорктаун-Хайтс. Именно там Фейстель занялся криптографией и вместе с коллегами начал разрабатывать Lucifer.

Что вообще такое «сеть Фейстеля»

Если убрать формулы — идея почти неприлично простая для того, что защищало банковские и государственные данные полвека.

Блок данных режется пополам — на левую L и правую R части. Дальше несколько раундов подряд повторяется одно и то же:

1. Правая половина R проходит через функцию F вместе с ключом раунда. F может быть сколь угодно сложной и даже необратимой — и это нормально.

2. Результат складывается с левой половиной L по модулю 2 — то есть выполняется операция XOR.

3. Половины меняются местами, и всё повторяется заново.

Гениальность — в одной детали: чтобы расшифровать сообщение, не нужно уметь обращать функцию F. Достаточно прогнать раунды в обратном порядке, используя ключи в обратной последовательности.

Именно поэтому внутрь F можно засунуть довольно сложную начинку — например, нелинейные S-блоки — не боясь, что шифр станет невозможно расшифровать.

Вехи создания

У Lucifer было несколько версий, и Фейстель с коллегами постепенно усложняли конструкцию. Начиналось всё с 48-битного блока и 48-битного ключа, затем появились варианты с другими параметрами. В одной из версий Джона Л. Смита использовались 64-битный ключ и 32-битный блок.

А затем появился Lucifer с 128-битным блоком и 128-битным ключом, построенный уже на сети Фейстеля. Именно эта версия особенно важна для нашей истории: из неё выросла конструкция, которая в итоге привела IBM к DES (созвучно с death, они что там, не крещенные? Так по загробному миру фанатеть...).

То, ради чего вообще статья затевалась

Визуализация данного алгоритма, а точнее упрощенная версия сети Фейстеля представляет собой левую активную панель (где и будем экспериментировать, менять значения) и правую панель, что бы видеть подробно каждый шаг, но в тоже время иметь объективное представление обо всех этапах алгоритма.

Шаг 2 - собственно фиксируем байт, с которым будем работать далее, тут не очень интересно, показывать нечего, жмём Далее

Что еще хочется отметить Я никогда не устану повторять ... если мы говорим именно о защите чувствительной информации криптографией, которая регулируется государством (не важно каким) на данный момент на каждом этапе (создание, доставка на объекты, загрузка ключа) присутствует человеческий фактор. А человек это брешь в любой системе безопасности. Ну если уж не брешь, то слабое место. Anyway двигаемся дальше.

Сразу подстелю себе соломку - визуализация этого прекрасного алгоритма это моя упрощенная интерпретация. Цель - донести идею наиболее простым языком, что бы отличать магию от ловкости рук.

Сделка с дьяволом: могло ли АНБ оставить в DES бэкдор?

Ну что, с сетью Фейстеля разобрались и даже немного поиграли. Теперь вернёмся к Lucifer — потому что именно здесь начинается самая интересная часть истории.

В 1973 году американское Национальное бюро стандартов (NBS, ныне NIST) объявило конкурс на единый стандарт шифрования для гражданских ведомств. IBM предложила доработанный Lucifer. Работу над ним возглавили Уолтер Тачмен и Карл Мейер.

И тут в историю вошло АНБ.

АНБ узнало, что Уолтер Тачмен из IBM работает над новой версией Lucifer. Агентство оформило ему допуск к секретной информации (в переводе с бусурманского - к гос. тайне) и подключилось к совместной работе над шифром.

Дальше возник вопрос, который до сих пор делает историю DES такой интересной:

а нельзя ли встроить в шифр секретный вход для тех, кто знает, где его искать?

Бэкдор, которого никто не должен увидеть

На первый взгляд идея кажется вполне реалистичной.

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

АНБ участвовало в их разработке, но принципы проектирования долгое время не раскрывались.

Отсюда и подозрение: а вдруг внутри S-блоков спрятана математическая лазейка?

Такую возможность обсуждали вполне официально. В документах того времени фигурирует понятие trapdoor — условно говоря, секретная дверь, позволяющая обойти обычную защиту алгоритма. Если такая дверь существует, обладателю секретного знания не обязательно знать ключ пользователя. Он получает другой путь к расшифровке.

Но доказательств того, что подобную дверь действительно оставили, найдено не было.

А вот ключ действительно укоротили

Зато здесь никаких теорий заговора не требуется.

В процессе стандартизации АНБ настояло на сокращении длины ключа. Обсуждались разные варианты, а в итоге остановились на 56 битах.

При этом АНБ участвовало и в разработке S-блоков.

Получилась странная комбинация: одну часть защиты сделали слабее, а другую — загадочным образом изменили в закрытом режиме.

В 1977 году DES стал федеральным стандартом США — FIPS PUB 46.

И почти сразу появились вопросы.

«56 бит? Вы серьёзно?»

В том же году Уитфилд Диффи и Мартин Хеллман опубликовали статью с недвусмысленным названием — Exhaustive Cryptanalysis of the NBS Data Encryption Standard.

В рамках теоретического подхода они посчитали стоимость специальной машины для перебора ключей DES и получили оценку около $20 миллионов за систему, способную найти ключ примерно за сутки. Но короткий ключ был не единственной причиной для подозрений.

Оставался вопрос: что именно АНБ сделало с S-блоками?

В 1978 году специальный комитет Сената США расследовал участие АНБ в создании DES. Скрытой математической «двери» в алгоритме не обнаружили. Но выяснилось, что АНБ действительно убедило IBM согласиться на сокращённый ключ и участвовало в разработке S-блоков. То есть подозрения имели под собой почву. Просто доказательств бэкдора не нашли. И на этом историю можно было бы закончить. Но тогда мы не получили бы главный твист.

Тайна, которую скрывали почти 20 лет

В 1990 году Эли Бихам и Ади Шамир опубликовали метод дифференциального криптоанализа — мощный способ атаковать блочные шифры. И тут выяснилось кое-что странное.

DES оказался очень хорошо защищён от этой атаки.

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

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

И вот здесь появляется настоящий вопрос.

Откуда IBM знала об этой атаке в 1974 году?

IBM утверждала, что разработала соответствующие методы самостоятельно. Историки также обсуждали возможность того, что определённые знания пришли от АНБ. Но документального доказательства того, что АНБ передало IBM готовый метод дифференциального криптоанализа, нет. Поэтому здесь заканчиваются факты и начинаются исторические вопросы.

Но парадокс остаётся:

АНБ действительно вмешалось в разработку DES.
АНБ действительно добилось более короткого ключа.
АНБ действительно участвовало в разработке S-блоков.
Но доказательств, что оно оставило бэкдор, нет.

А спустя двадцать лет выяснилось, что S-блоки были спроектированы гораздо умнее, чем могла знать публика.

Диффи и Хеллман всё-таки оказались правы

Оставалась другая проблема — 56-битный ключ. В 1998 году Electronic Frontier Foundation построила специализированную машину Deep Crack менее чем за $250 000.

Она перебирала ключи DES со скоростью около 88 миллиардов ключей в секунду и нашла нужный ключ за 56 часов.

Год спустя EFF вместе с distributed.net сделали это уже за 22 часа 15 минут.

То, что в 1977 году казалось машиной за десятки миллионов долларов, спустя два десятилетия превратилось в относительно доступный специализированный компьютер.

DES было пора на пенсию. Lucifer умер да здавствует... Кхе, кхе

Но сеть Фейстеля никуда не делась

Да, DES устарел, а идея Фейстеля — нет.

На сети Фейстеля или её модификациях построены Blowfish, Twofish, Camellia, KASUMI и другие шифры. Похожие конструкции используются и в форматно-сохраняющем шифровании.

А по другую сторону железного занавеса существовала своя история.

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

В 2001 году NIST утвердил новый стандарт — AES. Он уже не использовал сеть Фейстеля, а был построен на другой архитектуре — подстановочно-перестановочной сети, но это уже совсем другая история.

Lucifer умер. DES тоже.

А идея одного немецкого гражданина, эмигрировавшего в США, продолжает жить.

И всё началось с довольно простой мысли: разделить блок пополам, немного покрутить одну половину, смешать её с другой — и повторить.

И в заключении хотелось бы сказать: "Помните алгоритмы шифрования - это всё здорово, но самое главное, берегите себя и своих близких".