Сети Фейстеля: строительные блоки современных шифров

В начале 1970-х годов Хорст Фейстель, работавший в исследовательском подразделении IBM, занимался шифром «Люцифер», когда пришёл к фундаментальной идее: обратимый шифр можно построить с помощью необратимой раундовой функции.

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

В шифре Фейстеля входной блок разделяется на две равные половины: L (левая) и R (правая). В каждом раунде раундовая функция F применяется к R, результат складывается с L операцией XOR, после чего половины меняются местами.

После n раундов обе половины объединяются для получения шифротекста. Обмен половин гарантирует, что в чередующихся раундах обрабатываются обе половины и тщательно перемешиваются.

Раундовая функция F в сети Фейстеля принимает правую половину и подключ раунда в качестве входных данных и выдаёт результат, который складывается с левой половиной операцией XOR. Важно, что F не обязана быть обратимой.

F может быть сколь угодно сложной: это может быть любая комбинация подстановок, перестановок, операций XOR и модульной арифметики. Чем сложнее и нелинейнее F, тем сильнее шифр, поскольку при расшифровании обращать F не требуется.

Расшифрование в шифре Фейстеля использует в точности ту же структуру, что и шифрование, но применяет подключи раундов в обратном порядке. Это возможно, потому что XOR является собственной обратной операцией: если A XOR B = C, то C XOR B = A.

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

Математическая элегантность сетей Фейстеля заключается в том, что структура с XOR гарантирует обратимость независимо от того, как работает F. Даже если F является односторонней функцией, такой как SHA-256, общий шифр Фейстеля остаётся обратимым.

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

Стандарт шифрования данных (DES), опубликованный в 1977 году, — это 16-раундовый шифр Фейстеля, работающий с блоками размером 64 бита и ключом размером 56 бит. В каждом раунде используется отдельный подключ размером 48 бит, полученный из основного ключа.

Раундовая функция DES включает перестановку расширения, операцию XOR с подключом, восемь S-блоков, обеспечивающих нелинейность, и перестановку с помощью P-блока. В совокупности они обеспечивают запутывание и рассеивание, требуемые принципами проектирования шифров Шеннона.

Блоуфиш, разработанный Брюсом Шнайером в 1993 году, — это шифр Фейстеля с переменной длиной ключа от 32 до 448 бит и 16 раундами. В нём используются зависящие от ключа S-блоки, что делает атаки с предварительными вычислениями непрактичными.

Туфиш, финалист конкурса по выбору усовершенствованного стандарта шифрования, развивает идеи Блоуфиша, используя блоки размером 128 бит и 16 раундов. Оба шифра до сих пор не взломаны и применяются, например, в алгоритмах хеширования паролей на основе модифицированного Блоуфиша.

Сбалансированный шифр Фейстеля разделяет блок на две равные половины. В несбалансированной сети Фейстеля половины имеют разный размер, например соотношение 3/4 к 1/4.

Несбалансированные сети Фейстеля могут обеспечивать преимущества в безопасности в определённых условиях и используются в некоторых специализированных шифрах. Семейство шифров CAST использует сбалансированную 64-битную структуру Фейстеля.

В 1988 году Майкл Люби и Чарльз Ракофф доказали, что трёхраундовая сеть Фейстеля с псевдослучайными раундовыми функциями является стойкой псевдослучайной перестановкой (PRP), а четырёхраундовая версия — сильной PRP.

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

Сеть подстановок и перестановок (SPN), используемая усовершенствованным стандартом шифрования, применяет подстановку и перестановку ко всему блоку одновременно, а не к половине блока в каждом раунде. Это обеспечивает более быстрое рассеивание.

Усовершенствованный стандарт шифрования достигает полного рассеивания всего за 4 раунда, тогда как структуре Фейстеля DES требуется больше раундов для сопоставимого рассеивания. Структура SPN усовершенствованного стандарта шифрования также лучше соответствует архитектурам современных процессоров с инструкциями SIMD.

Теорема Люби—Ракоффа рассматривает раундовую функцию F как по-настоящему случайную функцию. На практике F является псевдослучайной функцией — шифром или хешем с ключом, — а не настоящим случайным оракулом.

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

Проверьте своё понимание построения сетей Фейстеля.

Сети Фейстеля — это структуры блочных шифров, использующие раундовую функцию, которая не обязана быть обратимой. Расшифрование выполняется с помощью той же структуры в обратном порядке, с подключами, применяемыми в обратной последовательности.

DES, Блоуфиш и Туфиш — шифры Фейстеля. Теорема Люби—Ракоффа предоставляет теоретические гарантии безопасности. Усовершенствованный стандарт шифрования вместо этого использует структуру SPN, обеспечивающую лучшее рассеивание за один раунд.