Просмотр кода страницы LOKI97

{{Карточка блочного шифра
|название      = LOKI97
|создатель     = {{iw|Lawrie Brown}}
|создан        = [[1997]] г.
|опубликован   = [[1998]] г.
|размер ключа  = 128/192/256 бит
|размер блока  = 128 бит
|число раундов = 16
|тип           = [[Сеть Фейстеля]]
}}

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

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

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

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

== Криптостойкость ==
LOKI97 был первым опубликованным кандидатом в конкурсе Advanced Encryption Standard, был в достаточно краткие сроки анализирован и атакован. В работе «Weaknesses in LOKI97»<ref>[[Кнудсен, Ларс|L.R. Knudsen]] and [[Рэймен, Винсент|V. Rijmen]], «Weaknesses in LOKI97», Proceedings of the 2nd AES Candidate Conference, Rome, March 22-23, 1999, pp. 168—174</ref> (Rijmen & Knudsen, 1999) было выявлено, что алгоритм имеет ряд недостатков, которые делают его уязвимым для [[дифференциальный криптоанализ|дифференциального]] и [[линейный криптоанализ|линейного криптоанализа]].

Согласно исследованиям, проведенным в рамках конкурса AES, изменение одного бита входных данных в одном из раундов с относительно высокой вероятностью (порядка <math>2^{-10}</math>) повлечет за собой изменение одного бита в выходных данных, что делает дифференциальную атаку успешной как максимум за <math>2^{56}</math> попыток. В то же время несбалансированность F-функции делает успешным линейный криптоанализ при известных <math>2^{56}</math> шифруемых сообщениях. В то же время автор в описании алгоритма оценивал стойкость LOKI97 на несколько порядков большей (предполагалось, что для взлома необходимо обладать как минимум <math>2^{70}</math> шифротекстами). Этот анализ недостатков алгоритма не позволил шифру LOKI97 пройти в следующий тур конкурса AES.
{{начало цитаты}}
Современный 128-битный блочный шифр должен противостоять дифференциальному и линейному криптоанализу лучше чем LOKI97.
{{oq|en|  
A contemporary block cipher with a 128-bit block ought to resist differential and linear attack muck better than LOKI97.}}
{{конец цитаты}}

== Спецификация алгоритма LOKI97<ref>Laurence Brown, Josef Pieprzyk, Introducing the new LOKI97 Block Cipher</ref> ==
[[Файл:loki97-a.gif|thumbnail|right|Схема алгоритма]]
LOKI97 преобразует 128-битный блок исходного текста в 128 бит шифротекста. [[Шифрование]] происходит следующим образом:
128 бит исходного блока [L|R] делится на 2 64-битных слова

<math>L_{\text{0}}=L</math>

<math>R_{\text{0}}=R</math>

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

<math>R_{\text{i}} = L_{\text{i-1}} \oplus f(R_{\text{i-1}}+SK_{\text{3i-2}},SK_{\text{3i-1}})</math>

<math>L_{\text{i}} = R_{\text{i-1}}+SK_{\text{3i-2}}+SK_{\text{3i}}</math>

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

<math>R_{\text{i-1}} = L_{\text{i}} \oplus f(R_{\text{i}}-SK_{\text{3i}},SK_{\text{3i-1}})</math>

<math>L_{\text{i-1}} = R_{\text{i}}-SK_{\text{3i}}-SK_{\text{3i-2}}</math>

== Инициализация ключей LOKI97 ==
В самом алгоритме используется 256-битный ключ, однако ключ, выданный пользователям может быть 256-ти, 192-х, а также 128-битным. Соответственно, если дан 256-битный ключ <math>[K_{\text{a}}|K_{\text{b}}|K_{\text{c}}|K_{\text{d}}]</math>, тогда

<math>[K4_{\text{0}}|K3_{\text{0}}|K2_{\text{0}}|K1_{\text{0}}] = [K_{\text{a}}|K_{\text{b}}|K_{\text{c}}|K_{\text{d}}]</math>

если дан 192-битный ключ <math>[K_{\text{a}}|K_{\text{b}}|K_{\text{c}}]</math>, тогда

<math>[K4_{\text{0}}|K3_{\text{0}}|K2_{\text{0}}|K1_{\text{0}}] = [K_{\text{a}}|K_{\text{b}}|K_{\text{c}}|f(K_{\text{a}},K_{\text{b}})] </math>

и если дан 128-битный ключ <math>[K_{\text{a}}|K_{\text{b}}] </math>, тогда

<math>[K4_{\text{0}}|K3_{\text{0}}|K2_{\text{0}}|K1_{\text{0}}] = [K_{\text{a}}|K_{\text{b}}|f(K_{\text{b}},K_{\text{a}})|f(K_{\text{a}},K_{\text{b}})] </math>

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

Для получения промежуточных ключей с одинаковой эффективностью к атакам используется функция g, один из этапов которой — прибавление постоянной, по словам автора «[[золотое сечение|золотого сечения]]». Полученный на входе ключ проходит через 48 итераций следующих действий (i=1,48), создавая 48 промежуточных ключей <math>SK_{\text{i}}</math>

<math>SK_{\text{i}} = K1_{\text{i}} = K4_{\text{i-1}} \oplus g_{\text{i}}(K1_{\text{i-1}},K3_{\text{i-1}},K2_{\text{i-1}})</math>

<math>K4_{\text{i}} = K4_{\text{i-1}} </math>

<math>K3_{\text{i}} = K3_{\text{i-1}} </math>

<math>K2_{\text{i}} = K2_{\text{i-1}} </math>

,где

<math>g_{\text{i}}(K1,K3,K2)=f(K1+K3+(\Delta*i),K2)</math>

<math>\Delta = (\sqrt{5}-1)*2^{\text{63}} = 9E3779B97F4A7C15_{\text{16}}</math>

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

== Функция f(A,B) ==
Функцию можно описать следующим выражением

<math>f(A,B) = Sb(P(Sa(E(KP(A,B)))),B)</math>,
в котором:

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

<math> KP([A_l|A_r],SK_r) = \left [ ((A_l \And \sim SK_r) \mid (A_r \And SK_r)) \mid ((A_r \And \sim SK_r) \mid (A_l \And SK_r)) \right ] </math>

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

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

<math>\left [4-0\mid 63-56\mid 58-48\mid 52-40\mid 42-32\mid 34-24\mid 28-16\mid 18-8\mid 12-0\right ]</math>.

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

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

<math>    S1(x) = ((inverted x \oplus 1FFF)^3 ~\mathrm{mod}~ 2911) \And FF,  in ~GF~(2^{13})</math>

<math>    S2(x) = ((inverted x \oplus  7FF)^3~ \mathrm{mod}~  AA7) \And FF,  in~ GF~(2^{11})</math>

Операция <math>A \And FF </math> выбирает 8 младших битов из числа A.

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

{| class="wikitable"
|-
|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 является основным путём перемешивания битов. При её построении преследовалась цель максимально уменьшить вероятность появления закономерностей в распределении входных и выходных битов. Как и в предыдущих версиях алгоритма, по словам автора, за основу был взят [[латинский квадрат]].

== См. также ==
* [[Advanced Encryption Standard|AES]]
* [[DES]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://web.archive.org/web/20040410222536/http://www.unsw.adfa.edu.au/~lpb/research/loki97/ Домашняя страница LOKI97]{{ref-en}}
* [https://web.archive.org/web/20040727114019/http://www.unsw.adfa.edu.au/~lpb/papers/ssp97/loki97b.html The design of LOKI97]{{ref-en}}
* [ftp://ftp.esat.kuleuven.ac.be/pub/COSIC/rijmen/loki97.pdf Weakness in LOKI97]{{ref-en}}

{{симметричные криптоалгоритмы}}

{{Нет источников |дата=2024-10-19}}

[[Категория:Сеть Фейстеля]]