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

Введение

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

Описание

Шифр 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 шифрований выбирается другой инициализирующий вектор и работа продолжается. В улучшенной версии шифра после 2³² различных инициализирующих векторов, секретный ключ К меняется^[2].

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

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

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

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

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

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

Для поточных шифров наиболее интересным является вопрос о периоде получаемой последовательности в гамме.

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

Для стойкости поточного шифра к атакам основанным на компромиссе время-память необходимо выполнение условий . Это гарантирует, что сложность атаки будет сравнима со сложностью полного перебора. Инициализирующий вектор может быть открытым, но тогда он необходимо должен быть полностью случайным, чтобы избежать атаки tradeoff-resynchronyzation^[3]. В случае с LEX бит, где Block — состояние блока открытого текста во время шифрования. Внутреннее состояние соответствует паре в начале и во время шифрования. Таким образом, бит, что достаточно для сведения возможности атаки на нет.

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

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

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

См. также

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

Примечания

1. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.190.4521
2. ↑ Данное улучшение было предложено после обнаружения уязвимости шифра к скользящей атаке
3. http://eprint.iacr.org/2005/090