Несбалансированная сеть Фейстеля

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

История

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

Необходимость в несбалансированной сети возникла в конце 1990-х — начале 2000-х годов в связи с развитием мобильных устройств и встраиваемых систем, где требовались шифры с нестандартными размерами блока (например, 128, 192 или 256 бит) и высокой скоростью на 8-битных процессорах. Первым широко известным шифром, реализующим этот принцип, стал BEAR (1995) Росса Андерсона и Эли Бихама. Впоследствии несбалансированные сети были использованы в шифрах LION, RABBIT, а также в некоторых режимах работы блочных шифров.

Устройство и принцип работы

Несбалансированная сеть Фейстеля (англ. Unbalanced Feistel Network, UFN) оперирует блоком данных, который делится на левую часть L и правую часть R, причём размеры этих частей могут быть произвольными (например, 96 и 32 бита, 64 и 64 бита, 128 и 0 бит — последний случай вырождается в подстановочно-перестановочную сеть). На каждом раунде выполняется преобразование:

1. Функция раунда \( F \) применяется к одной из частей (обычно к меньшей) с использованием раундового ключа \( K_i \).
2. Результат функции складывается по модулю 2 (XOR) с другой частью.
3. Части могут меняться местами (перестановка) или оставаться на своих местах в зависимости от реализации.

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

Математическое описание

Пусть блок данных \( B \) имеет длину \( n \) бит. Он делится на левую часть \( L \) длиной \( a \) бит и правую часть \( R \) длиной \( b \) бит, где \( a + b = n \), и \( a \neq b \) (обычно \( a > b \) или \( a < b \)). Один раунд несбалансированной сети Фейстеля описывается так:

\[ \begin{aligned} L_{i+1} &= R_i \\ R_{i+1} &= L_i \oplus F(R_i, K_i) \end{aligned} \]

или, в альтернативной реализации:

\[ \begin{aligned} L_{i+1} &= L_i \oplus F(R_i, K_i) \\ R_{i+1} &= R_i \end{aligned} \]

где \( \oplus \) — операция XOR, \( F \) — раундовая функция (обычно включает подстановки, перестановки и нелинейные преобразования), \( K_i \) — раундовый ключ.

Классификация

Несбалансированные сети Фейстеля делятся по нескольким признакам:

По соотношению размеров частей

• Слабо несбалансированные: размеры частей различаются незначительно (например, 64 и 56 бит). Требуют большего числа раундов для полного перемешивания.
• Сильно несбалансированные: одна часть значительно меньше другой (например, 128 и 8 бит). Позволяют строить шифры с очень высокой скоростью на маломощных процессорах, но требуют ещё больше раундов.

По числу обрабатываемых частей

• Двухчастные (классические): блок делится на две части.
• Многочастные: блок делится на три или более частей, каждая из которых обрабатывается своей функцией. Пример — шифр MARS (финалист конкурса AES).

По направлению обработки

• Прямые: функция применяется к правой части, результат XORится с левой.
• Обратные: функция применяется к левой части, результат XORится с правой.

Примеры шифров

BEAR и LION

Шифры BEAR и LION, предложенные Россом Андерсоном и Эли Бихамом в 1995 году, являются классическими примерами несбалансированных сетей. Они используют хеш-функции и потоковые шифры в качестве раундовых функций. BEAR работает с блоками переменной длины (до 2^64 бит) и состоит из трёх раундов, каждый из которых использует хеш-функцию. LION — упрощённая версия, использующая только два раунда.

RABBIT

Шифр RABBIT (2003) основан на несбалансированной сети Фейстеля с 8-битными частями. Он оптимизирован для аппаратной реализации и использует 128-битный блок и 128-битный ключ. RABBIT был представлен на конкурсе eSTREAM и вошёл в финальный портфель профиля 2 (программные реализации).

MARS

Шифр MARS (1998) — финалист конкурса AES. Он использует многочастную несбалансированную сеть: блок делится на четыре 32-битных слова. На каждом раунде обрабатываются два слова, а остальные два остаются неизменными. MARS сочетает свойства сети Фейстеля и подстановочно-перестановочной сети.

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

Преимущества

• Гибкость размера блока: можно создавать шифры с произвольной длиной блока (например, 128, 192, 256 бит), не привязываясь к степеням двойки.
• Высокая скорость на маломощных процессорах: сильно несбалансированные сети позволяют обрабатывать большие блоки данных, используя только малую часть блока в каждом раунде. Это снижает количество операций на байт.
• Простота реализации: базовая структура легко реализуется как в программном, так и в аппаратном обеспечении.

Недостатки

• Большее число раундов: для достижения полного перемешивания данных требуется значительно больше раундов, чем в сбалансированной сети. Например, для шифра с размерами частей 128 и 8 бит может потребоваться 16–32 раунда.
• Сложность анализа: несбалансированные сети хуже изучены с точки зрения криптоанализа. Существуют атаки, использующие дисбаланс, например, атаки на основе линейного и дифференциального криптоанализа.
• Ограниченная диффузия: из-за того, что часть блока остаётся неизменной на нескольких раундах, может потребоваться специальное проектирование раундовой функции для обеспечения быстрого распространения изменений.

Применение

Несбалансированные сети Фейстеля применяются в:

• Блочных шифрах для встраиваемых систем: например, в микроконтроллерах с 8-битной архитектурой, где обработка 32-битных слов неэффективна.
• Режимах работы блочных шифров: некоторые режимы (например, XTS) могут быть реализованы на основе несбалансированной сети.
• Криптографических хеш-функциях: конструкции на основе сети Фейстеля используются в некоторых хеш-функциях (например, в MD6).
• Поточных шифрах: некоторые поточные шифры (например, RABBIT) используют несбалансированную сеть для генерации псевдослучайной последовательности.

Криптоанализ

Несбалансированные сети Фейстеля подвержены тем же типам атак, что и сбалансированные, но с некоторыми особенностями:

• Линейный криптоанализ: из-за неравномерного распределения битов в блоке линейные аппроксимации могут быть более эффективными для меньшей части.
• Дифференциальный криптоанализ: атаки могут использовать разности, которые затрагивают только одну часть блока, что снижает сложность.
• Атаки на основе связанных ключей: некоторые реализации несбалансированных сетей уязвимы к атакам, использующим зависимость раундовых ключей от размера частей.

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

Источники

• Anderson R., Biham E. «Two Practical and Provably Secure Block Ciphers: BEAR and LION» — 1995.
• Schneier B. «Applied Cryptography: Protocols, Algorithms, and Source Code in C» — 1996.
• Menezes A., van Oorschot P., Vanstone S. «Handbook of Applied Cryptography» — 1996.
• Knudsen L., Robshaw M. «The Block Cipher Companion» — 2011.
• Спецификация шифра RABBIT — проект eSTREAM, 2003.
• Спецификация шифра MARS — финалист конкурса AES, 1998.