LEX (шифр)

LEX (LEX-128, LEX-192, LEX-256) — поточный шифр, разработанный Алексом Бирюковым (Alex Biryukov). Шифр участвовал в конкурсе eSTREAM и дошел до 3 этапа, но, тем не менее, не был выбран для финального портфолио ^[1].

Введение

Название шифра LEX происходит от термина англ. Leak EXtraction. За основу берется некоторый блочный шифр и идея заключается в выводе частей внутреннего состояния блочного шифра на определенных раундах в выходную гамму для поточного шифрования (возможно, после применения некоторой фильтрующей функции). Такой метод может быть применен к любому блочному шифру, но в каждом случае необходимо тщательное изучение, какие части внутреннего состояния извлекать и с какой частотой. В основном это зависит от раундовой функции блочного шифра и используемого им алгоритма генерации раундовых ключей.

Описание

Рис.1 Инициализация и генерирование выходной гаммы для 128-битной версии шифра

Рис.2 Байты, извлекаемые из матрицы состояния на нечетных (odd) и четных (even) раундах (подсвечены серым)

Шифр LEX в оригинальном варианте использует AES в режиме Output Feedback (OFB): в каждом раунде извлекаются 4 определенных байта из матрицы состояния. Версии LEX-128, LEX-192 и LEX-256 отличаются длиной используемого при шифровании ключа: соответственно 128, 192 и 256 бит. Различия с AES в том, что криптоаналитик никогда не видит всего 128-битного шифротекста, а только порции промежуточного состояния.

Сначала, некоторый инициализирующий вектор (IV) шифруется AES с ключом K, чтобы получить S = AES_k(IV). Далее S повторно многократно шифруется в режиме OFB и в это время на каждом раунде извлекается 32 бита из матрицы состояния (см. рис.1). После 500 шифрований выбирается другой ключ K и работа продолжается..

Ключевой частью шифра является решение, какие байты извлекать из промежуточного состояния и с какой частотой. Автор шифра предлагает извлекать байты $B_1 = (b_{0,0}, b_{0,2}, b_{2,0}, b_{2,2})$ в каждом нечетном раунде и байты $B_2 = (b_{0,1}, b_{0,3}, b_{2,1}, b_{2,3} )$ в каждом четном (см. рис.2). Порядок байтов не имеет значения для безопасности, но важен для скорости шифрования. Вышеизложенный порядок байтов позволяет их извлечь из текущего состояния всего за 4 шага с помощью формулы:

$\begin{align} out32 &= \left( \left( t_0 \& 0xFF00FF \right) << 8 \right) \oplus \left( t_2 \& 0xFF00FF \right) , \\ \end{align}$

где t₀ и t₂ соответственно нулевая и вторая строки в матрице промежуточного состояния.

Выбор именно этих позиций байтов мотивирован следующим: оба множества $B_1$ и $B_2$ инвариантны относительно операции ShiftRows, применяемой в AES (первая строка не сдвигается, третья сдвигается на две позиции). Использование разных множеств на четных и нечетных раундах гарантирует, что входные и выходные байты на двух соседних раундах не будут связаны только операциями SubBytes и MixColumns. Таким образом, атакующий будет вынужден анализировать два последовательных раунда шифрования. Два раунда обеспечивают полное рассеивание в статистике шифра, что ограничивает атакующего в использовании принципа разделяй и властвуй.

На последнем этапе происходит сложение по модулю 2 выходной гаммы с открытым текстом.

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

Период выходной последовательности

Для поточных шифров наиболее интересным является вопрос о периоде получаемой последовательности в гамме. Так как LEX использует AES, то выходная последовательность (гамма) зациклится, когда зациклится последовательность шифротекстов, генерируемых AES. Если бы AES генерировал последовательность, неотличимую от случайной, для одного ключа, то длина последовательности составляла бы $O(2^{128})$.

Если выходной поток представляет из себя случайные перестановки 128-битного блока, он может быть опознан как неслучайный после обнаружения отсутствия 128-битных коллизий в потоке из 2⁶⁴ выходных блоков. В случае с LEX, так как используются только части внутреннего состояния AES на каждом раунде, отображение внутреннего состояния на выход не взаимно-однозначно и, следовательно, такие коллизии будут случаться.

Атаки время-память

Для стойкости поточного шифра к атакам основанным на компромиссе время-память необходимо выполнение условий $|K| = |IV| = |State|/2$. Это гарантирует, что сложность атаки будет сравнима со сложностью полного перебора. Инициализирующий вектор может быть открытым, но тогда он необходимо должен быть полностью случайным, чтобы избежать атаки tradeoff-resynchronyzation^[2]. В случае с LEX $|K| = |IV| = |Block| = 128$ бит, где Block — состояние блока открытого текста во время шифрования. Внутреннее состояние соответствует паре $(K, IV)$ в начале и $(Block, Key)$ во время шифрования. Таким образом, $|K|+|IV| = |K|+|S| = 256$ бит, что достаточно для сведения возможности атаки на нет.

Алгебраические атаки

Данный вид атак еще до конца не изучен и может быть очень мощным. Возможность его применения к LEX должна быть тщательно изучена. Ожидается, что замена ключа после 500 шифрований позволит избежать таких атак. Нацелясь на определенный ключ, криптоаналитик сможет получить только 500 блоков выходной гаммы; а после замены ключа составленная им система уравнений станет устаревшей.

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

За цикл работы AES дает на выходе 128 бит шифротекста для всех вариантов ключа (128, 192, 256 бит), в то время как LEX, построенный на AES, даст 32*N_r(где N_r — количество раундов при данной длине ключа) битов шифрованного текста. Таким образом, ожидается, что LEX превзойдет в производительности AES примерно в 2,5, 3 и 3,5 раза соответственно для ключей в 128, 192 и 256 бит. Кроме того, плюсом шифра является то, что могут использоваться уже готовые реализации используемого блочного шифра, что сокращает время и средства на разработку.

См. также

• Гаммирование
• Режим шифрования

Примечания

1. ↑ CiteSeerX — Cryptanalysis of the Stream Cipher LEX
2. ↑ J. Hong and P. Sarkar, “Rediscovery of time memory tradeoffs,” 2005. http://eprint.iacr.org/2005/090

Ссылки

1. [1] A New 128-bit Key Stream Cipher LEX
2. [2] A New Attack on the LEX Stream Cipher
3. [3] Algebraic Cryptanalysis of a Small-Scale Version of Stream Cipher LEX