Phelix

Phelix — высокоскоростной поточный шифр, использующий одноразовый код аутентичности сообщения. Шифр был представлен на конкурсе eSTREAM в 2004 году. Авторами являются Брюс Шнайер, Дуг Уитинг, Стефан Люкс и Фредерик Мюллер. Алгоритм содержит операции сложения по модулю 2³², сложения по модулю 2 и циклический сдвиг; Phelix использует 256-битный ключ и 128-битную метку времени. Некоторыми криптографами были выражены опасения насчёт возможности получения секретного ключа при некорректном использовании шифра.

Предтечей к Phelix стал шифр Helix, построенный на простейших операциях, но он оказался взломан. Усовершенствованный Helix получил название Phelix, но и он был отвергнут на конкурсе eCrypt. Причина отказа была спорной — атаки основывались на подборе метки времени, что являлось слабым местом и других шифров, но разработчики заявили, что их шифр устойчив к данного рода атакам. Оказалось, что шифр взламывается дифференциально-линейным криптоанализом, хотя стойкости шифра в других условиях это не угрожает. В итоге Phelix не был допущен к третьему раунду конкурса, за некоторую самонадеянность и неаккуратность авторов. Помимо всего этого, появился ряд теоретических работ, в которых утверждалось, что смешение операций add-xor-shift не дает необходимой нелинейности, но на практике взломов не было. Теперь дизайн Phelix предлагается авторами к использованию в Skein и Threefish.

Обзор Phelix

Сложность алгоритма — 128 бит, что значит, для взлома шифра необходимо вычислить не менее [math]\displaystyle{ 2^{128} }[/math] блочных функций, образующих ключевую выходную последовательность. В Phelix используется ключ произвольной длины(от 128 до 256 бит), дополняемый до 256 бит, и 128-битная метка времени. Ключ считается секретным, метка времени по умолчанию считается всем известной. Шифр оптимизирован под 32-битные платформы, так как все операции происходят над 32-битными словами. Можно сказать, что Phelix — это «многораундовый простой шифр», так как в процессе создания шифротекста используются довольно простые сложение по модулю [math]\displaystyle{ 2^{32} }[/math], исключающее «ИЛИ» и перестановка битов.

Раунд Phelix

Начальное состояние представляет собой 9 слов [math]\displaystyle{ Z_i }[/math], по 32 бита каждое. Слова делятся на две группы: 5 «активных», которые участвуют в операциях функционального блока, и старые(«old»), которые участвуют лишь в образовании ключевого выходного потока, и хранятся в буфере блочной функции. Раунд шифрования показан на рисунке 1.Всего в блок входит 20 раундов (рисунок 2).

Один блок Phelix

Из-за большого сходства блока с пятью спиралями, шифр и получил своё название (penta-helix англ. пять спиралей) . В каждом блоке происходят следующие события: генерируется одно слово выходного потока(гамма), прибавляются два слова KeyMaterial [math]\displaystyle{ X_i }[/math] и одно слово открытого текста [math]\displaystyle{ P_i }[/math]. Выходное состояние текущего блока используется в качестве входного для последующего.

Соответственно, вычислений, показанных на рисунке 2, достаточно для обработки 4 байт сообщения. Как и в остальных поточных шифрах, шифртекст в Phelix- есть результат суммирования по модулю 2 открытого текста и keystream. На старте шифрования, начальное состояние определяется ключом и меткой времени. KeyWords [math]\displaystyle{ X_{ij} }[/math] зависят от значения и длины ключа, метки времени и номера блока. Атаки, основанные на угадывание внутреннего состояния, усложняются за счет прибавления keymaterial на этапе извлечения keystream. В конце сообщения выполняется дополнительная обработка, в ходе которой вырабатывается 128-битный тег, ответственный за аутентификацию сообщения.

Определение

Функция шифрования берет на вход ключ U переменной длины (до 256 бит), 128битную метку времени и открытый текст. Функция расшифровки — ключ, метку времени и тег, соответственно, и дает на выход либо открытый текст, либо ошибку, если аутентификация не будет пройдена. Пусть [math]\displaystyle{ L(x) }[/math] — длина последовательности байтов [math]\displaystyle{ x }[/math]. Тогда [math]\displaystyle{ L(U) }[/math]<32. Рабочий ключ К, состоящий из восьми 32-битных слов генерируется функцией смешивания ключа(keymixing). Метка времени имеет размер 16 байт. Если её длина меньше, то метку необходимо дополнить нулями до нужной длины. Шифртекст и открытый текст имеют одинаковую длину с ограничением [math]\displaystyle{ 2^{64} }[/math].Последнее слово открытого текста по умолчанию дополняется нулями до длины 32 бита, если длина слова не кратна 32 битам. Функция шифрования может принять на вход пустое сообщение, тогда её выходом будет только код аутентичности сообщения (MAC).

Блочная функция

Phelix состоит из последовательности блоков, каждому из которых присвоен свой уникальный номер, согласно порядку следования. На входе каждого блока имеется пять «активных» слов. На выход блока идет также пять слов [math]\displaystyle{ Z_0^i }[/math],[math]\displaystyle{ Z_1^i }[/math],[math]\displaystyle{ Z_2^i }[/math],[math]\displaystyle{ Z_3^i }[/math],[math]\displaystyle{ Z_4^i }[/math], которые будут представлять вход следующего блока [math]\displaystyle{ Z_0^{i+1} }[/math],[math]\displaystyle{ Z_1^{i+1} }[/math],[math]\displaystyle{ Z_2^{i+1} }[/math],[math]\displaystyle{ Z_3^{i+1} }[/math],[math]\displaystyle{ Z_4^{i+1} }[/math]. В [math]\displaystyle{ i }[/math]-ом блоке также используются в качестве входных два ключевых слова [math]\displaystyle{ X_{i,0} }[/math] и [math]\displaystyle{ X_{i,1} }[/math], одно слово открытого текста [math]\displaystyle{ P_i }[/math] и слово предыдущего внутреннего состояния [math]\displaystyle{ Z_4^{i-4} }[/math].

На рисунке 2 дана полная иллюстрация блочной функции. Все значения являются 32-битными словами; По традиции, исключающее ИЛИ имеет обозначение [math]\displaystyle{ \oplus }[/math] , перестановка — <<< ,сложение по модулю — [math]\displaystyle{ + }[/math]. Блочную функцию можно представить в виде последовательности двух «полублочных» H, определяемых следующим образом.

Полублочная функция

Таким образом для слов, участвующих в операциях блока верны следующие уравнения. [math]\displaystyle{ (Y_0^i,Y_1^i,Y_2^i,Y_3^i,Y_4^i):=H(Z_0^i,Z_1^i,Z_2^i,Z_3^i,Z_4^i,0,X_{i,0}) ; (Z_0^{i+1},Z_1^{i+1},Z_2^{i+1},Z_3^{i+1},Z_4^{i+1}):=H(Y_0^i,Y_1^i,Y_2^i,Y_3^i,Y_4^i,P_i,X_{i,1}) }[/math] Каждый блок производит одно слово ключевого потока [math]\displaystyle{ S_i=Y_4^i+Z_4^{i-4} }[/math]. Шифртекст, как обычно, определяется следующим образом: [math]\displaystyle{ C_i=P_i+S_i }[/math].

Ключевые слова для каждого блока

Расширенные ключевые слова определяются рабочим ключом К, меткой времени N, длиной входного ключа U и номером блока. Сначала расширяется метка времени до восьми слов по правилу: [math]\displaystyle{ N_k:=(k mod 4)-N_{k-4}(mod2^{32}) }[/math]. Далее ключевые слова для блока i вычисляются следующим образом:

Ключевые слова

где все операции выполняются по модулю [math]\displaystyle{ 2^{32} }[/math]

Инициализация

Шифрование начинается с установки внутреннего состояния:

Начальное состояние

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

Шифрование

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

В зависимости от [math]\displaystyle{ L(P) mod 4 }[/math], в последнем слове выходного ключевого потока используется от 1 до 4 байт.

Код аутентичности

После того как был зашифрован последний байт открытого текста, приходит время для генерации MAC. Выполняется операция XOR для [math]\displaystyle{ Z_0^k }[/math] и 0x912d94f1. Далее обновленное внутреннее состояние обрабатывается последовательно восемью блоками. В роли слов открытого текста здесь выступают [math]\displaystyle{ L(P) mod 4 }[/math], вырабатываемый выходной ключевой поток никак не используется. После постобработки внутреннего состояния четыре последовательных блока берутся за генерацию MAC тега, используя в качестве слов открытого текста все тот же [math]\displaystyle{ L(P) mod 4 }[/math].

Функция генерации ключа фиксированной длины(keymixing)

Функция генерации ключа фиксированной длины отображает ключ произвольной длины в ключ длины 256 бит. Сначала берется функция R, определяемая следующим образом:

Key Mixing

Потом ключ U дополняется нулями до длины 256 бит, и 32-битным словам ключа присваиваются значения [math]\displaystyle{ K_{32},...,K_{39} }[/math]. Рабочий ключ вводится следующим образом для k=7,…,0: [math]\displaystyle{ (K_{4i},...,K_{4i+3}):=R(K_{4i+4},...,K_{4i+7}) \oplus (K_{4i+8},...,K_{4i+11}) }[/math]

Расшифровка

Расшифровка практически идентична шифрованию, за единственными отличиями:

• [math]\displaystyle{ S_i }[/math] , генерируемая при первом применении Н-функции, используется для расшифрования шифртекста, производя слово открытого текста, используемого в дальнейшем во втором применение функции H.
• После того как тег был получен, он сравнивается с ожидаемым, и если они не равны, то сообщение уничтожается.

Производительность

Phelix оптимизирован для 32-битных платформ. Авторы утверждают, что он может достигнуть до восьми циклов на байт на современных 86-разрядных процессорах.

Ниже приведены показатели производительности FPGA оборудования:

Xilinx Чип	Фрагменты	FPGA Мбит/с	GE оценка	Описание реализации
XC2S100-5	1198	960.0	20404	(A) Полный раунд 160-битная модель
XC2S100-5	1077	750.0	18080	(B) Полу-раунд 160-битная модель
XC2S30-5	264	3.2	12314	(C) 32-разрядный канал передачи данных

Helix

Phelix представляет собой слегка изменённую форму раннего шифра, Helix, опубликованный в 2003 году Нильсом Фергюсоном, Даг Уайтингом, Брюсом Шнайером, Джоном Келси, Стефаном Лаксом и Тадайоши Коно; Phelix добавляет 128 бит для внутреннего состояния.

В 2004 году Мюллер опубликовал две атаки на Helix. Первое имеет сложность 2⁸⁸ и требует 2¹² адаптивно подобранного открытого текста слов, но требует случайные числа для повторного использования. Соурадиути Пол и Барт Пренель позднее показали, что число адаптивно подобранного открытого текста слов атаки Мюллера может быть уменьшено в 3 раза в худшем случае, используя их оптимальные алгоритмы для решения дифференцальных уравнений сложения. В последующей разработке, Соурадиути Пол и Барт Пренель показали, что атака выше может быть реализована с выбранных открытых текстов (CP), а не адаптивно подобранных (ACP) со сложностью данных 2^35.64 CP’s. Вторая атака Мюллера на Helix является отличительной атакой, которая требует 2¹¹⁴ слов выбранного открытого текста.

Разработка Phelix в значительной мере мотивирована дифференциальной атакой Мюллера.

Безопасность

Авторы сообщают, что Phelix не должен использоваться, пока он не получил дополнительного криптоанализа.

Хунцзюнь Ву и Барт Пренель, авторы дифференциальной атаки, выражают беспокойство тем, что каждое слово открытого текста влияет на ключевой поток, минуя достаточные конфузионные и диффузионные слоя. Они утверждают, что это свойственный недостаток в структуре Helix и Phelix. Авторы приходят к выводу, что Phelix небезопасен.

Аппаратная реализация

Phelix можно реализовать многими разными способами. На рисунке ниже показано одно из возможных воплощений в жизнь на интегральной схеме специального назначения (ASIC).

Схемы в криптографии

• n_expand: Конвертирует метку времени произвольной длины в метку длины 192 бита.
• key_mix: Конвертирует ключ переменной длины в ключ длины 256 бит.
• sub_key_gen: Генерирует ключевые слова [math]\displaystyle{ X_{i,0},X_{i,1} }[/math] для каждого блока.
• ini_dp: Инициализация.
• H_func: Реализация логики H-функции.
• FIFO: Память, реализующая принцип first in first out FIFO.

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

Литература

• D. Whiting, B. Schneier, S. Lucks, and F. Muller, Phelix: Fast Encryption and Authentication in a Single Cryptographic Primitive (includes source code)
• T. Good, W. Chelton, M. Benaissa: Review of stream cipher candidates from a low resource hardware perspective (PDF)
• Yaser Esmaeili Salehani, Hadi Ahmadi: A Chosen-key Distinguishing Attack on Phelix, submitted to eSTREAM [withdrawn 2006-10-14]
• Niels Ferguson, Doug Whiting, Bruce Schneier, John Kelsey, Stefan Lucks and Tadayoshi Kohno, Helix: Fast Encryption and Authentication in a Single Cryptographic Primitive, Fast Software Encryption — FSE 2003, pp330-346 (PDF).
• Frédéric Muller, Differential Attacks against the Helix Stream Cipher, FSE 2004, pp94-108.
• Souradyuti Paul and Bart Preneel, Solving Systems of Differential Equations of Addition, ACISP 2005. Full version (PDF)
• Souradyuti Paul and Bart Preneel, Near Optimal Algorithms for Solving Differential Equations of Addition With Batch Queries, Indocrypt 2005. Full version (PDF)

Ссылки

• eStream page on Phelix
• «Differential Attacks against Phelix» by Hongjun Wu and Bart Preneel