Кто владеет информацией — тот владеет миром.

Ротшильд

Пока другие только пытаются понять законы рынка, используй их!

Терморектальный криптоанализTM



Алгоритм 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 ослабило алгоритм.

Остапенко Денис aka Sharp, 2006

Соглашение о приватности информации

 

строительные материалы http://spb-sovtrans.ru/

Hosted by uCoz