Обобщённая сеть Фейстеля

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

История

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

Обобщённая сеть Фейстеля (ОСФ) была впервые формально описана в 1989 году Крисом Блэком и Филипом Рогэем в контексте построения блочных шифров с переменным числом ветвей. Идея состояла в том, чтобы увеличить количество параллельно обрабатываемых частей блока, что особенно актуально для современных процессоров с поддержкой SIMD-инструкций (Single Instruction, Multiple Data). В 1990-х годах ОСФ активно исследовалась в работах таких криптографов, как Серж Воденэ, Жак Патарен и Ларс Кнудсен.

Принцип работы

В обобщённой сети Фейстеля блок данных размером \( n \) бит делится на \( k \) ветвей (подблоков), где \( k \geq 2 \). Обычно \( k \) выбирается равным степени двойки (например, 4, 8, 16). На каждом раунде выполняется следующая последовательность операций:

1. Применение раундовой функции: К одной из ветвей (например, к первой) применяется нелинейная раундовая функция \( F \), зависящая от раундового ключа.
2. Комбинирование: Результат функции \( F \) комбинируется с другой ветвью (например, второй) с помощью операции XOR (или другой обратимой операции, такой как сложение по модулю \( 2^m \)).
3. Циклический сдвиг: Ветви циклически сдвигаются влево или вправо, чтобы на следующем раунде функция применялась к другой ветви.

Формально для \( k \) ветвей \( X_1, X_2, \dots, X_k \) на раунде \( r \) выполняется:

• \( X_1' = X_1 \oplus F_r(X_2) \)
• \( X_2' = X_2 \)
• \( X_3' = X_3 \)
• ...
• \( X_k' = X_k \)
• Затем ветви циклически сдвигаются: \( (X_1', X_2', \dots, X_k') \rightarrow (X_2', X_3', \dots, X_k', X_1') \).

В некоторых вариантах ОСФ функция \( F \) применяется не к одной, а к нескольким ветвям одновременно, или комбинирование выполняется не с одной, а с несколькими ветвями.

Отличия от классической сети Фейстеля

Виды обобщённых сетей Фейстеля

Сеть Фейстеля с 4 ветвями (Type-1)

Наиболее распространённая разновидность, где блок делится на 4 равные части. На каждом раунде функция \( F \) применяется к первой ветви, результат XOR-ится со второй, затем ветви циклически сдвигаются. Примеры шифров: CAST-256, MARS (частично).

Сеть Фейстеля с 8 ветвями (Type-2)

Используется в шифрах, ориентированных на высокую скорость, например, в RC6 (вариант с 8 ветвями). Позволяет эффективно задействовать SIMD-инструкции современных процессоров.

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

В этом варианте операция комбинирования не является XOR, а используется некоммутативная операция, например, умножение в конечном поле. Это усложняет криптоанализ, но требует более сложных вычислений.

Сеть Фейстеля с переменным числом ветвей

Некоторые шифры, такие как Threefish (используется в хеш-функции Skein), позволяют адаптивно изменять число ветвей в зависимости от размера блока. Например, для блока 256 бит используются 4 ветви по 64 бита, для блока 1024 бита — 16 ветвей по 64 бита.

Применение

Обобщённые сети Фейстеля используются в ряде современных блочных шифров и хеш-функций:

• CAST-256 — блочный шифр с размером блока 128 бит, использующий 4-ветвевую ОСФ. Был финалистом конкурса AES (Advanced Encryption Standard).
• MARS — блочный шифр, разработанный IBM, финалист AES. Использует гибридную структуру, включающую элементы ОСФ.
• RC6 — блочный шифр, финалист AES, основанный на сети Фейстеля с 4 ветвями.
• Threefish — блочный шифр, лежащий в основе хеш-функции Skein (финалист конкурса SHA-3). Использует ОСФ с числом ветвей от 4 до 16.
• Blowfish (частично) — хотя Blowfish использует классическую сеть Фейстеля, его модификации (например, Twofish) применяют элементы ОСФ.

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

Обобщённые сети Фейстеля обладают рядом преимуществ с точки зрения криптоанализа:

• Устойчивость к дифференциальному криптоанализу: Увеличение числа ветвей снижает вероятность появления дифференциальных характеристик с высокой вероятностью.
• Устойчивость к линейному криптоанализу: Параллельная обработка ветвей затрудняет построение линейных аппроксимаций.
• Устойчивость к атакам на основе связанных ключей: В некоторых реализациях ОСФ (например, Threefish) специально спроектированы для минимизации влияния связанных ключей.

Однако ОСФ не лишена недостатков. При большом числе ветвей (например, 16) требуется большее количество раундов для достижения полного диффузионного перемешивания данных. Это может снизить скорость шифрования, несмотря на параллелизм. Кроме того, некоторые варианты ОСФ уязвимы к атакам типа «встреча посередине» (meet-in-the-middle), если число ветвей слишком велико.

Сравнение с другими конструкциями

Сеть Фейстеля vs. SP-сеть

Обобщённая сеть Фейстеля отличается от SP-сети (Substitution-Permutation Network) тем, что в ОСФ функция шифрования не обязательно должна быть обратимой, а в SP-сети все операции (подстановка и перестановка) обратимы. SP-сети, как правило, обеспечивают более быстрое диффузионное перемешивание, но требуют больше ресурсов для реализации обратного шифрования.

Сеть Фейстеля vs. ARX-конструкции

ARX-конструкции (Addition, Rotation, XOR) часто используют ОСФ для повышения параллелизма. Например, шифр Threefish полностью построен на ARX-операциях в рамках ОСФ. Это позволяет достичь высокой скорости на современных процессорах.

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

• Обобщённая сеть Фейстеля с 4 ветвями используется в шифре CAST-256, который был разработан канадскими криптографами Карлайлом Адамсом и Стаффордом Таваресом.
• Шифр Threefish, использующий ОСФ с 16 ветвями, был предложен в 2008 году и стал финалистом конкурса SHA-3, но уступил Keccak.
• В 2012 году исследователи из Университета Левена (Бельгия) показали, что ОСФ с 8 ветвями может быть взломана с помощью атаки на основе связанных ключей при определённых условиях, что привело к ужесточению требований к числу раундов в новых шифрах.

Источники

• Блэк К., Рогэй Ф. «Обобщённые сети Фейстеля и их криптоанализ» (1989).
• Воденэ С. «Криптография: теория и практика» (2005).
• Кнудсен Л. «Дифференциальный криптоанализ обобщённых сетей Фейстеля» (1998).
• Адамс К., Таварес С. «CAST-256: блочный шифр с обобщённой сетью Фейстеля» (1998).
• Спецификация шифра Threefish (Skein) — NIST, 2010.