Алгоритм Lucifer

Lucifer часто называют «первым алгоритмом шифрования для гражданских применений». На самом деле Lucifer представляет собой не один алгоритм, а целое семейство связанных между собой (разработанных в рамках одноименной исследовательской программы по компьютерной криптографии фирмы IBM), но созданных в разное время, алгоритмов блочного симметричного шифрования данных.

По словам Брюса Шнайера, «существует, по меньшей мере, два различных алгоритма с таким именем, что привело к заметной путанице». А посвященная алгоритму Lucifer статья в интернет-энциклопедии «Wikipedia» упоминает о четырех вариантах этого алгоритма.


Рассмотрим поочередно различные варианты алгоритма Lucifer.


Вариант № 1
Исходный вариант алгоритма Lucifer был разработан коллективом специалистов из компании ЕВМ под руководством Хорста Фейстеля (Horst Feistel). Этот вариант алгоритма был запатентован компанией ЕВМ в 1971 г. (патент выдан в 1974 г.), его подробное описание можно найти в патенте США №3798359. Этот вариант алгоритма шифрует данные блоками по 48 битов, используя при этом 48-битный ключ шифрования.

Алгоритм является подстановочно-перестановочной сетью. В процессе шифрования выполняется 16 раундов преобразований (это рекомендованное автором алгоритма количество раундов), в каждом из которых над обрабатываемым блоком данных производятся следующие действия:
1. Обеспечение обратной связи. Выполняется логическая операция «исключающее или» (XOR) между каждым битом обрабатываемого блока и предыдущим значением того же бита в случае, если аналогичный бит ключа раунда имеет единичное значение; в противном случае операция не выполняется. Предыдущие значения каждого обрабатываемого бита сохраняются в регистре блока обратной связи. В первом раунде алгоритма блок обратной связи операцию XOR не выполняет, а только запоминает биты обрабатываемого блока для следующего раунда.
2. Перемешивающее преобразование. Выполняется нелинейное преобразование данных, полученных в результате предыдущей операции, путем табличной замены, зависящей от значения конкретного бита ключа раунда.
3. Рассеивающее преобразование, состоящее в простом перенаправлении входных битов таким образом, что значения всех входных битов меняются местами по определенному закону. Как и значения таблиц замен, сам закон, по которому выполняется рассеивание данных, не описан в патенте. Эта операция выполняется абсолютно независимо от значения ключа шифрования.
4. Наложение ключа. Выполняется путем побитового применения операции XOR к результату предыдущей операции и соответствующим битам ключа раунда. Как видно из приведенного описания, в каждом раунде шифрования требуется 108 битов ключевой информации:
48 битов для блока обратной связи;
12 битов для блока перемешивания;
48 битов для блока наложения ключа.

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

Очевиден и тот факт, что в описании алгоритма существует множество «белых пятен». Например, не приведены таблицы замен, нет подробного описания используемого линейного преобразования, отсутствует описание перестановки КЕР и т. д. Фактически патент устанавливает некий шаблон для разработки на его основе конкретных алгоритмов шифрования с «уточненными» процедурами.

Одновременно с патентом 30 июня 1971 г. Хорстом Фейстелем были поданы еще две заявки на патенты; обе предлагали специфические применения описанного выше алгоритма:
защиту данных, передаваемых и обрабатываемых в многотерминальных системах, с использованием алгоритма Lucifer; запатентованная схема подразумевает также обеспечение целостности данных, а также наличие двух режимов аутентификации пользователей: парольного и «запрос-ответ»;
многоступенчатое шифрование данных, обеспечивающее различные уровни защиты информации при ее передаче в многотерминальных системах;
эта схема также основана на применении алгоритма Lucifer.

Указанные патенты также были получены фирмой ЮМ в 1974 г. Вариант № 2
По современным меркам 48-битный размер ключа шифрования является абсолютно недостаточным; видимо, подобные мысли были и у разработчиков алгоритма Lucifer, поэтому уже в том же 1971 г. появился второй вариант алгоритма, шифрующий данные 64-битным ключом. Однако второй вариант шифровал блоками всего по 32 бита, что также явно недостаточно (поскольку при битном блоке после зашифровывания порядка 2 блоков открытого текста на одном и том же ключе начинает происходить утечка информации о шифруемых данных).

Этот вариант алгоритма, как и предыдущий, запатентован фирмой IBM и описан в патенте.

Между вариантами № 2 и № 1 существенно больше различий, чем сходств. Второй вариант алгоритма разбивает шифруемый 32-битный блок данных на два субблока по 16 битов и выполняет 16 раундов преобразований, в каждом из которых выполняется следующая последовательность операций:
Шифруемый блок данных разбивается на два субблока: А и В.

Этот вариант алгоритма описан гораздо более подробно, чем предыдущий: в патенте «белые пятна» отсутствуют, поэтому данный алгоритм может быть вполне реализован только с использованием содержащейся в патенте информации.

Как и в предыдущем случае, в патенте приведена подробнейшая информация для аппаратной реализации алгоритма, особенности программной реализации в патенте не рассматриваются.

Вариант № 3
Многократное повторение этих операций и представляет собой алгоритм шифрования.

В статье не указывается подавляющее большинство параметров алгоритма: нет ни точного количества раундов, ни значений таблиц замен и перестановок, не указаны размер блока и ключа (128-битные блоки и ключи указываются лишь в качестве возможных значений). Таким образом, данный вариант алгоритма Lucifer является еще более «шаблонным», чем вариант № 1.

Стоит отметить тот факт, что даже всемирно известные эксперты в области криптографии делают различные предположения о том, какой из вариантов алгоритма Lucifer был предшественником алгоритма DES. Например, «прямым предшественником» DES назван алгоритм, описанный в патенте (т. е. вариант № 2), тогда как сказано, что DES разработан на базе 128-битного алгоритма Lucifer, т. е. варианта № 3 (вариант № 4 появился существенно позже, чем DES, поэтому предшественником быть не мог). Видимо, решающим фактором в пользу алгоритма № 3 стоит считать тот факт, что описывающий DES патент ссылается именно на статью в качестве первоисточника.

Вариант № 4
Процедура расширения ключа решает задачу получения 16 ключей раундов по 72 бита каждый из исходного 128-битного ключа шифрования. Расширение выполняется весьма простым способом:
В качестве фрагмента KSt используется первый байт ключа шифрования (считая байты ключа слева направо, начиная с 1).
В качестве фрагмента KXt используются первые 8 байтов ключа шифрования (т. е. первый байт ключа используется в обоих фрагментах).

Ключ шифрования циклически сдвигается влево на 7 байтов, после чего аналогично «набираются» фрагменты ключа для следующего раунда.

В отличие от вариантов № 1 и № 3, вариант № 4 описан достаточно подробно для его реализации, как программной, так и аппаратной.

Криптоанализ вариантов алгоритма
Какие-либо криптоаналитические работы, посвященные вариантам № 1 и № 2 алгоритма Lucifer, не получили широкую известность. Двум последним вариантам «повезло» больше; известны следующие результаты их криптоанализа.

В 1991 г. Эли Бихам и Эди Шамир исследовали вариант № 3. Для определенности они использовали перестановку Р из алгоритма DES, а в качестве таблиц были взяты строки 3 и 4 таблицы замен алгоритма DES.

8-раундовый вариант № 3 с 32-битным блоком вскрывается при наличии всего 24 выбранных открытых текстов и соответствующих им шифртекстов путем выполнения порядка 221 тестовых операций шифрования.

В той же работе Бихам и Шамир описали возможную атаку на аналогичный алгоритм со 128-битным блоком, для успешного осуществления которой требуется 60-70 выбранных открытых текстов и порядка 253 операций шифрования.

Кроме того, Бихам и Шамир утверждали, что вариант № 4 является еще более слабым.

Последнее утверждение было доказано. В ней описана атака на вариант № 4 алгоритма Lucifer, в котором обнаружилось подмножество ключей (весьма большое — около 55 % всех возможных значений ключа), слабых к дифференциальному криптоанализу. При использовании ключа шифрования из данного подмножества алгоритм вскрывается при наличии 236 выбранных открытых текстов.

Данные криптоаналитические исследования развеяли широко распространенный миф о том, что «превращение» алгоритма Lucifer в DES ослабило алгоритм.