LOKI97

LOKI97 — 128-битный 16-цикловой симметричный блочный шифр с 128-256-битным пользовательским ключом, используемым как для зашифрования, так и для расшифрования сообщений. Разработан Lawrie Brown совместно с J.Pieprzyk и J.Seberry. Имеет структуру сбалансированной петли сети Фейстеля с использованием 16 циклов и сложной функцией f, которая объединяет два S-P слоя.

LOKI97
Создатель Lawrie Brown[англ.]
Создан 1997 г.
Опубликован 1998 г.
Размер ключа 128/192/256 бит
Размер блока 128 бит
Число раундов 16
Тип Сеть Фейстеля

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

При разработке LOKI97 были учтены особенности существующих на этот момент симметричных алгоритмов, учтены их уязвимости и достоинства. В частности, в своей статье «Предварительные наброски по доработке LOKI», 15 декабря 1997 года автор алгоритма L. Brown исследует Blowfish, CAST, IDEA, TEA, ICE, SAFER и ряд других алгоритмов. В этой статье были рассмотрены уязвимости исходного алгоритма — LOKI91, предшественника LOKI97, имеющего недостаток в механизме выработки ключей, который позволял, теоретически, использовать механизм «грубой силы» для атаки.

Шифр LOKI97 не патентован, свободен для использования, позиционируется автором как замена DES и другим блочным алгоритмам. Предшественниками являются алгоритмы LOKI89 и LOKI91. Реализован в библиотеке mcrypt, ряде свободных программ шифрования, существует плагин для Total Commander с поддержкой LOKI97.

Криптостойкость

править

LOKI97 был первым опубликованным кандидатом в конкурсе Advanced Encryption Standard, был в достаточно краткие сроки анализирован и атакован. В работе «Weaknesses in LOKI97»[1] (Rijmen & Knudsen, 1999) было выявлено, что алгоритм имеет ряд недостатков, которые делают его уязвимым для дифференциального и линейного криптоанализа.

Согласно исследованиям, проведенным в рамках конкурса AES, изменение одного бита входных данных в одном из раундов с относительно высокой вероятностью (порядка  ) повлечет за собой изменение одного бита в выходных данных, что делает дифференциальную атаку успешной как максимум за   попыток. В то же время несбалансированность F-функции делает успешным линейный криптоанализ при известных   шифруемых сообщениях. В то же время автор в описании алгоритма оценивал стойкость LOKI97 на несколько порядков большей (предполагалось, что для взлома необходимо обладать как минимум   шифротекстами). Этот анализ недостатков алгоритма не позволил шифру LOKI97 пройти в следующий тур конкурса AES.

Современный 128-битный блочный шифр должен противостоять дифференциальному и линейному криптоанализу лучше чем LOKI97.

Спецификация алгоритма LOKI97[2]

править
 
Схема алгоритма

LOKI97 преобразует 128-битный блок исходного текста в 128 бит шифротекста. Шифрование происходит следующим образом: 128 бит исходного блока [L|R] делится на 2 64-битных слова

 

 

После чего эти слова проходят 16 раундов сбалансированной сети Фейстеля по следующему алгоритму:

 

 

Каждый раунд использует как операцию XOR, так и сложение (по модулю 2:64) 64-битных слов, что увеличивает стойкость алгоритма к взлому. Функция F(F,B) обеспечивает максимальное смешивание всех входных битов функции, её описание будет дано ниже. Процесс расшифровки аналогичен алгоритму получения шифртекста: 16 шагов (от 16 до 1го)

 

 

Инициализация ключей LOKI97

править

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

 

если дан 192-битный ключ  , тогда

 

и если дан 128-битный ключ  , тогда

 

Для усложнения коротких (128-битных) и простых (например, нулевых) ключей при генерации использовалась функция F, используемая в алгоритме далее.

Для получения промежуточных ключей с одинаковой эффективностью к атакам используется функция g, один из этапов которой — прибавление постоянной, по словам автора «золотого сечения». Полученный на входе ключ проходит через 48 итераций следующих действий (i=1,48), создавая 48 промежуточных ключей  

 

 

 

 

,где

 

 

При дешифровке сообщения промежуточные ключи используются в обратном порядке.

Функция f(A,B)

править

Функцию можно описать следующим выражением

 , в котором:

Функция перемешивания битов. Разбивает входное 64-битное слово А на 2 32-битных и младшие 32 бита слова В и на выходе дает 64-битный результат согласно формуле:

 

С помощью обмена битами с промежуточным ключом и частью входных данных, функция KP перермешивает биты для усложнения процесса сопоставления входных и выходных данных поступающих с и на S-блоки.

Функция расширения. Преобразует входное 64-битное слово в 96-битное по следующему закону:

 .

Функция построена таким образом, что биты каждый бит на её входе попадает в 2 S-блока.

Sa(A), Sb(A)

править

2 группы S-блоков. Построены так, чтобы иметь максимальную нелинейность (отсюда и выбор кубической функции и нечетная степень поля Галуа), имеют хорошую устойчивость к дифференциальному криптоанализа, а также создают лавинный эффект при использовании функции. Используются блоки разной длины S1 — 13 бит, S2 — 11 бит.  , и  . Входные данные для Sa(C) — 96-битное слово на выходе функции E(B). Старшими битами слова для Sb(C) являются старшие 32 бита слова B, использованого как одно из входных для всей функции F(A,B), а младшими — результат действия функции P(D). Входные данные для S-блоков инвертируются для уменьшения вероятности преобразований вида 0-> 0, 1 -> 1. s-блоки считаются по следующим формулам

 

 

Операция   выбирает 8 младших битов из числа A.

Перестановка выходных данных функции Sa(A). 64 бита перемешиваются по следующей схеме:

56 48 40 32 24 16 08 00 57 49 41 33 25 17 09 01
58 50 42 34 26 18 10 02 59 51 43 35 27 19 11 03
60 52 44 36 28 20 12 04 61 53 45 37 29 21 13 05
62 54 46 38 30 22 14 06 63 55 47 39 31 23 15 07

Функция P является основным путём перемешивания битов. При её построении преследовалась цель максимально уменьшить вероятность появления закономерностей в распределении входных и выходных битов. Как и в предыдущих версиях алгоритма, по словам автора, за основу был взят латинский квадрат.

См. также

править

Примечания

править
  1. L.R. Knudsen and V. Rijmen, «Weaknesses in LOKI97», Proceedings of the 2nd AES Candidate Conference, Rome, March 22-23, 1999, pp. 168—174
  2. Laurence Brown, Josef Pieprzyk, Introducing the new LOKI97 Block Cipher

Ссылки

править