LOKI97

Поделись знанием:
Перейти к: навигация, поиск
LOKI97
Создатель:

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, и некоторые потенциальные уязвимости.

При разработке 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, изменение одного бита входных данных в одном из раундов с относительно высокой вероятностью (порядка <math>2^{-10}</math>) повлечет за собой изменение одного бита в выходных данных, что делает дифференциальную атаку успешной как максимум за <math>2^{56}</math> попыток. В то же время несбалансированность F-функции делает успешным линейный криптоанализ при известных <math>2^{56}</math> шифруемых сообщениях. В то же время автор в описании алгоритма оценивал стойкость LOKI97 на несколько порядков большей (предполагалось, что для взлома необходимо обладать как минимум <math>2^{70}</math> шифротекстами). Этот анализ недостатков алгоритма не позволил шифру LOKI97 пройти в следующий тур конкурса AES.

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

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

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-блоков. Построены так, чтобы иметь максимальную нелинейность (отсюда и выбор кубической функции и нечетная степень поля Галуа), имеют хорошую устойчивость к дифференциальному криптоанализа, а также создают лавинный эффект при использовании функции. Используются блоки разной длины 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 бита перемешиваются по следующей схеме:

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

Пример использования алгоритма

Ключ: 000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F

Текст: 000102030405060708090A0B0C0D0E0F

Шифр: 75080E359F10FE640144B35C57128DAD

См. также

Напишите отзыв о статье "LOKI97"

Примечания

  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

Ссылки

Потоковые шифры

A3 • A5 • A8 • Decim • MICKEY • RC4 • Rabbit • Salsa20 • SEAL • SOSEMANUK • Trivium • VMPC

Сеть Фейстеля

ГОСТ 28147-89 • Blowfish • Camellia • CAST-128 • CAST-256 • CIPHERUNICORN-A • CIPHERUNICORN-E • CLEFIA • Cobra • DFC • DEAL • DES • DESX • E2 • EnRUPT • FEAL • FNAm2 • HPC • IDEA • KASUMI • Khufu • LOKI97 • MARS • MISTY1 • NewDES • Raiden • RC5 • RC6 • RTEA • SEED • Sinople • Skipjack • SM4 • TEA • Triple DES • Twofish • XTEA • XXTEA

SP-сеть

Кузнечик • 3-WAY • ABC • AES (Rijndael) • Akelarre • Anubis • ARIA • BaseKing • BassOmatic • BelT • CRYPTON • Diamond2 • Grand Cru • Hierocrypt-L1 • Hierocrypt-3 • KHAZAD • Lucifer • Present • Rainbow • SAFER • Serpent • SHARK • SQUARE • Threefish

Другие

FROG • NUSH • REDOC • SHACAL • SC2000


<imagemap>: неверное или отсутствующее изображение

 Для улучшения этой статьи желательно?:

Отрывок, характеризующий LOKI97

– Раненые, вот кто! Это нельзя, маменька; это ни на что не похоже… Нет, маменька, голубушка, это не то, простите, пожалуйста, голубушка… Маменька, ну что нам то, что мы увезем, вы посмотрите только, что на дворе… Маменька!.. Это не может быть!..
Граф стоял у окна и, не поворачивая лица, слушал слова Наташи. Вдруг он засопел носом и приблизил свое лицо к окну.
Графиня взглянула на дочь, увидала ее пристыженное за мать лицо, увидала ее волнение, поняла, отчего муж теперь не оглядывался на нее, и с растерянным видом оглянулась вокруг себя.
– Ах, да делайте, как хотите! Разве я мешаю кому нибудь! – сказала она, еще не вдруг сдаваясь.
– Маменька, голубушка, простите меня!
Но графиня оттолкнула дочь и подошла к графу.
– Mon cher, ты распорядись, как надо… Я ведь не знаю этого, – сказала она, виновато опуская глаза.
– Яйца… яйца курицу учат… – сквозь счастливые слезы проговорил граф и обнял жену, которая рада была скрыть на его груди свое пристыженное лицо.
– Папенька, маменька! Можно распорядиться? Можно?.. – спрашивала Наташа. – Мы все таки возьмем все самое нужное… – говорила Наташа.
Граф утвердительно кивнул ей головой, и Наташа тем быстрым бегом, которым она бегивала в горелки, побежала по зале в переднюю и по лестнице на двор.
Люди собрались около Наташи и до тех пор не могли поверить тому странному приказанию, которое она передавала, пока сам граф именем своей жены не подтвердил приказания о том, чтобы отдавать все подводы под раненых, а сундуки сносить в кладовые. Поняв приказание, люди с радостью и хлопотливостью принялись за новое дело. Прислуге теперь это не только не казалось странным, но, напротив, казалось, что это не могло быть иначе, точно так же, как за четверть часа перед этим никому не только не казалось странным, что оставляют раненых, а берут вещи, но казалось, что не могло быть иначе.
Все домашние, как бы выплачивая за то, что они раньше не взялись за это, принялись с хлопотливостью за новое дело размещения раненых. Раненые повыползли из своих комнат и с радостными бледными лицами окружили подводы. В соседних домах тоже разнесся слух, что есть подводы, и на двор к Ростовым стали приходить раненые из других домов. Многие из раненых просили не снимать вещей и только посадить их сверху. Но раз начавшееся дело свалки вещей уже не могло остановиться. Было все равно, оставлять все или половину. На дворе лежали неубранные сундуки с посудой, с бронзой, с картинами, зеркалами, которые так старательно укладывали в прошлую ночь, и всё искали и находили возможность сложить то и то и отдать еще и еще подводы.
– Четверых еще можно взять, – говорил управляющий, – я свою повозку отдаю, а то куда же их?
– Да отдайте мою гардеробную, – говорила графиня. – Дуняша со мной сядет в карету.
Отдали еще и гардеробную повозку и отправили ее за ранеными через два дома. Все домашние и прислуга были весело оживлены. Наташа находилась в восторженно счастливом оживлении, которого она давно не испытывала.
– Куда же его привязать? – говорили люди, прилаживая сундук к узкой запятке кареты, – надо хоть одну подводу оставить.
– Да с чем он? – спрашивала Наташа.
– С книгами графскими.
– Оставьте. Васильич уберет. Это не нужно.
В бричке все было полно людей; сомневались о том, куда сядет Петр Ильич.
– Он на козлы. Ведь ты на козлы, Петя? – кричала Наташа.
Соня не переставая хлопотала тоже; но цель хлопот ее была противоположна цели Наташи. Она убирала те вещи, которые должны были остаться; записывала их, по желанию графини, и старалась захватить с собой как можно больше.


Во втором часу заложенные и уложенные четыре экипажа Ростовых стояли у подъезда. Подводы с ранеными одна за другой съезжали со двора.
Коляска, в которой везли князя Андрея, проезжая мимо крыльца, обратила на себя внимание Сони, устраивавшей вместе с девушкой сиденья для графини в ее огромной высокой карете, стоявшей у подъезда.
– Это чья же коляска? – спросила Соня, высунувшись в окно кареты.
– А вы разве не знали, барышня? – отвечала горничная. – Князь раненый: он у нас ночевал и тоже с нами едут.
– Да кто это? Как фамилия?
– Самый наш жених бывший, князь Болконский! – вздыхая, отвечала горничная. – Говорят, при смерти.
Соня выскочила из кареты и побежала к графине. Графиня, уже одетая по дорожному, в шали и шляпе, усталая, ходила по гостиной, ожидая домашних, с тем чтобы посидеть с закрытыми дверями и помолиться перед отъездом. Наташи не было в комнате.
– Maman, – сказала Соня, – князь Андрей здесь, раненый, при смерти. Он едет с нами.
Графиня испуганно открыла глаза и, схватив за руку Соню, оглянулась.
– Наташа? – проговорила она.
И для Сони и для графини известие это имело в первую минуту только одно значение. Они знали свою Наташу, и ужас о том, что будет с нею при этом известии, заглушал для них всякое сочувствие к человеку, которого они обе любили.
– Наташа не знает еще; но он едет с нами, – сказала Соня.
– Ты говоришь, при смерти?
Соня кивнула головой.
Графиня обняла Соню и заплакала.
«Пути господни неисповедимы!» – думала она, чувствуя, что во всем, что делалось теперь, начинала выступать скрывавшаяся прежде от взгляда людей всемогущая рука.
– Ну, мама, все готово. О чем вы?.. – спросила с оживленным лицом Наташа, вбегая в комнату.
– Ни о чем, – сказала графиня. – Готово, так поедем. – И графиня нагнулась к своему ридикюлю, чтобы скрыть расстроенное лицо. Соня обняла Наташу и поцеловала ее.
Наташа вопросительно взглянула на нее.
– Что ты? Что такое случилось?
– Ничего… Нет…
– Очень дурное для меня?.. Что такое? – спрашивала чуткая Наташа.
Соня вздохнула и ничего не ответила. Граф, Петя, m me Schoss, Мавра Кузминишна, Васильич вошли в гостиную, и, затворив двери, все сели и молча, не глядя друг на друга, посидели несколько секунд.
Граф первый встал и, громко вздохнув, стал креститься на образ. Все сделали то же. Потом граф стал обнимать Мавру Кузминишну и Васильича, которые оставались в Москве, и, в то время как они ловили его руку и целовали его в плечо, слегка трепал их по спине, приговаривая что то неясное, ласково успокоительное. Графиня ушла в образную, и Соня нашла ее там на коленях перед разрозненно по стене остававшимися образами. (Самые дорогие по семейным преданиям образа везлись с собою.)
На крыльце и на дворе уезжавшие люди с кинжалами и саблями, которыми их вооружил Петя, с заправленными панталонами в сапоги и туго перепоясанные ремнями и кушаками, прощались с теми, которые оставались.
Как и всегда при отъездах, многое было забыто и не так уложено, и довольно долго два гайдука стояли с обеих сторон отворенной дверцы и ступенек кареты, готовясь подсадить графиню, в то время как бегали девушки с подушками, узелками из дому в кареты, и коляску, и бричку, и обратно.
– Век свой все перезабудут! – говорила графиня. – Ведь ты знаешь, что я не могу так сидеть. – И Дуняша, стиснув зубы и не отвечая, с выражением упрека на лице, бросилась в карету переделывать сиденье.
– Ах, народ этот! – говорил граф, покачивая головой.
Старый кучер Ефим, с которым одним только решалась ездить графиня, сидя высоко на своих козлах, даже не оглядывался на то, что делалось позади его. Он тридцатилетним опытом знал, что не скоро еще ему скажут «с богом!» и что когда скажут, то еще два раза остановят его и пошлют за забытыми вещами, и уже после этого еще раз остановят, и графиня сама высунется к нему в окно и попросит его Христом богом ехать осторожнее на спусках. Он знал это и потому терпеливее своих лошадей (в особенности левого рыжего – Сокола, который бил ногой и, пережевывая, перебирал удила) ожидал того, что будет. Наконец все уселись; ступеньки собрались и закинулись в карету, дверка захлопнулась, послали за шкатулкой, графиня высунулась и сказала, что должно. Тогда Ефим медленно снял шляпу с своей головы и стал креститься. Форейтор и все люди сделали то же.
– С богом! – сказал Ефим, надев шляпу. – Вытягивай! – Форейтор тронул. Правый дышловой влег в хомут, хрустнули высокие рессоры, и качнулся кузов. Лакей на ходу вскочил на козлы. Встряхнуло карету при выезде со двора на тряскую мостовую, так же встряхнуло другие экипажи, и поезд тронулся вверх по улице. В каретах, коляске и бричке все крестились на церковь, которая была напротив. Остававшиеся в Москве люди шли по обоим бокам экипажей, провожая их.


Источник — «http://wiki-org.ru/wiki/index.php?title=LOKI97&oldid=79193777»