Interested Article - LEX (шифр)

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

Введение

Название шифра 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{aligned}out32&=\left(\left(t_{0}\&0xFF00FF\right)<<8\right)\oplus \left(t_{2}\&0xFF00FF\right),\\\end{aligned}}

где 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$ . Это гарантирует, что сложность атаки будет сравнима со сложностью полного перебора. Инициализирующий вектор может быть открытым, но тогда он необходимо должен быть полностью случайным, чтобы избежать атаки . В случае с 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 бит. Кроме того, плюсом шифра является то, что могут использоваться уже готовые реализации используемого блочного шифра, что сокращает время и средства на разработку.

См. также

Примечания

(неопр.) . Дата обращения: 30 ноября 2011. 25 апреля 2018 года.
J. Hong and P. Sarkar, "Rediscovery of time memory tradeoffs, " 2005. от 1 июня 2014 на Wayback Machine