LEX (шифр)

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

Введение

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

Описание

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

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

Ключевой частью шифра является решение, какие байты извлекать из промежуточного состояния и с какой частотой. Автор шифра предлагает извлекать байты B 1 = ( b 0 , 0 , b 0 , 2 , b 2 , 0 , b 2 , 2 ) {displaystyle 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 ) {displaystyle B_{2}=(b_{0,1},b_{0,3},b_{2,1},b_{2,3})} в каждом четном (см. рис.2). Порядок байтов не имеет значения для безопасности, но важен для скорости шифрования. Вышеизложенный порядок байтов позволяет их извлечь из текущего состояния всего за 4 шага с помощью формулы:

o u t 32 = ( ( t 0 & 0 x F F 00 F F ) << 8 ) ⊕ ( t 2 & 0 x F F 00 F F ) , {displaystyle {egin{aligned}out32&=left(left(t_{0}&0xFF00FF ight)<<8 ight)oplus left(t_{2}&0xFF00FF ight),end{aligned}}}

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

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

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

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

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

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

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

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

Для стойкости поточного шифра к атакам основанным на компромиссе время-память необходимо выполнение условий | K | = | I V | = | S t a t e | / 2 {displaystyle |K|=|IV|=|State|/2} . Это гарантирует, что сложность атаки будет сравнима со сложностью полного перебора. Инициализирующий вектор может быть открытым, но тогда он необходимо должен быть полностью случайным, чтобы избежать атаки tradeoff-resynchronization. В случае с LEX | K | = | I V | = | B l o c k | = 128 {displaystyle |K|=|IV|=|Block|=128} бит, где Block — состояние блока открытого текста во время шифрования. Внутреннее состояние соответствует паре ( K , I V ) {displaystyle (K,IV)} в начале и ( B l o c k , K e y ) {displaystyle (Block,Key)} во время шифрования. Таким образом, | K | + | I V | = | K | + | S | = 256 {displaystyle |K|+|IV|=|K|+|S|=256} бит, что достаточно для сведения возможности атаки на нет.

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

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

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

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