Предварительные наброски по доработке LOKI.

Draft - 15 Дек.97

Dr Lawrie Brown

School of Computer Science, Australian Defence Force Academy, Canberra, Australia

Email: Lawrie.Brown@adfa.oz.au

 

Аннотация.

Эта статья представляет мои наброски по доработке LOKI - блочного шифра с секретным ключом .В настоящий момент я предлагаю использовать его для 16-битного шифра Фейстеля со 128-битными данными и 256-битным ключевым расписанием, которое может быть получено из 128 , 192 или 256-битных ключей.16 циклов вычисления данных используют сбалансированную петлю Фейстеля со сложной функцией f , которая объединяет два S-P слоя .256-битный алгоритм выработки ключей использует 33 цикла несбалансированной петли Фейстеля, применяющей ту же сложную функцию f для генерации вспомогательных ключей.

Введение.

LOKI91 - это 64-битный 16 - цикловой симметричный блочный шифр с 64- битным пользовательским ключом. Первоначально он был спроектирован L.Brown, J.Pieprzyk и J.Seberry в 1990 [BrPS90],и позже доработан L.Brown, M.Kwan, J.Pieprzyk и J.Seberry [BKPS91] (и переименован в LOKI91), с улучшенной устойчивостью к разностному анализу.

Первоначальная версия LOKI89 была исследована Biham и Shamir [BiSh91], и Knudsen [Knud91]. Они определили , что хотя версия LOKI89 с уменьшенным количеством циклов и чувствительна к разностному анализу, но полная 16-цикловая версия - нет.

Последующая доработка LOKI91 по усилению стойкости была исследована Knudsen[Knud92]. Он определил , что нет характеристик, позволяющих с достаточно высокой вероятностью успешно проводить разностный анализ ; что размер отображения f-функции в LOKI91 равен 8/13x2__ ; а также что есть атака по выбранному открытому тексту , которая уменьшает поиск полным перебором ключей в LOKI91 почти в 4 раза, используя 232+2
выбранных открытых текстов . В последующих статьях
Knudsen [Knud94] обсудил концепцию слабых хэш - ключей в LOKI.

Biham [Biha94c] ввел несколько новых типов криптоатак , которые используют соотношения между вспомогательными ключами . Он применил такую атаку к обеим версиям LOKI. Для LOKI91 сложность подхода порядка O(261) - что быстрее , чем полный перебор и сравнимо с результатами Knudsen-а.

Tokita, Sorimachi и Matsui [ToSM94] исследовали чувствительность LOKI91 к линейному анализу и выяснили , что версии с 12-ю и более циклами устойчивы к нему. Впоследствии Knudsen и Robshaw [KnRo96] провели выгодные улучшения по эффективности поиска , используя нелинейную аппроксимацию , но 12 и более циклов LOKI91 все еще остаются устойчивыми. Недавно Sakurai и Furuya[SaFu97] описали последующее увеличивающееся развитие..

В настоящее время LOKI91 считается шифром , действительно обеспечивающим защиту, устойчивым как к линейному, так и к разностному анализу , а его основные недостатки - это линейное ключевое расписание , из-за которого шифр чувствителен к некоторым атакам , связанным с ключом ; и размер ключа , который, исходя из этих атак, необходимо брать 260

LOKI91 был описан в Schneier [Schn96] , что привело к непрерывному продолжающемуся интересу его использования организациями , ищущими незагроможденный алгоритм шифрования . Похоже, что это продолжится в связи с реализацией небольшой быстрой Java-версии в публично доступной криптобиблиотеке [Crypt97].

Доработка LOKI.

Основные причины дальнейшей доработки LOKI - это слабости, обусловленные его алгоримтом выработки ключей, и происходящее развитие в области аппаратного обеспечения (продемонстрированное недавно восстановление грубой "животной" силой 56-битного ключа DES[RSAD97] ),которое наглядно демонстрирует малые размеры ключевого пространства.

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

Факторы безопасности.

Knudsen [Knud93] определил следующие необходимые условия безопаснос-ти для шифра Фейстеля:

Основываясь на этих условиях , выше привед╠нных рассмотрениях LOKI91 и комментариях по разработке блочных шифров в Schneier[Schn96], некоторые выводы, которые, как я думаю, необходимо рассмотреть с точки зрения перспектив безопасности, включают следующее :

Факторы реализации.

Результаты рассмотрения перспектив исполнения включают в себя :

Уроки других шифров.

При доработке я искал разнообразные моменты, чтобы учесть их, у шифров, которые были реализованы после первоначальной версии LOKI. Описание этих шифров взято из Schneier[Schn96] (если нет дополнительных отметок).

BLOWFISH

64 - битный , 16 - цикловой блочный шифр Фейстеля с переменной длиной ключа , разработан B.Schneier в 1994. Использует четыре больших 8*32- битовых случайных S - блоков , генерируемых из поставляемого ключа , выходы которых смешиваются с использованием обычного сложения и сложения по модулю 2. Результат - быстрый шифр, при условии неизменности ключа. Ключевое расписание длинное и сложное. Vaudenay [Vaud96] описал атаки на уменьшенной по циклам версии и отметил некоторые недостатки , обусловленные использованием рассеянных S - блоков .

CAST

64 - битный , 8 - цикловой блочный шифр Фейстеля c 64 - битным ключом, разработанный C.Adams и S.Tavares в 1993.Использует шесть 8*32 - битовых

S - блоков ( из них некоторые используют данные , а некоторые - ключ), выходы которых смешиваются с помощью xor. Эти S - блоки разработаны и предназначены для прикладных систем. Vaudenay [Vaud96] также прокомментировал CAST и его использование рассеянных S - блоков , даже если они разработаны не случайным образом.

ICE

64 - битный , 16 - цикловой блочный шифр Фейстеля c 64 - битным ключом

(хотя возможны варианты) , разработан в 1997 .Использует ключевые перестановки наряду со неизменными , высоко нелинейными S - блоками.

IDEA

64 - битный , 8 - цикловой итеративный блочный шифр с 128 - битным ключом, разработанный X.Lai и J.Massey в 1990. Используется концепция

"смешения операций различных алгебраических структур".

SAFER

64 - битный , 6 - цикловой или больше , итеративный блочный шифр с 64 или 128 - битовым ключом , разработанный J.Massey в 1994. Использует цикл, скомбинированный из множества функциональных уровней, с тремя слоями PHT - линейных операций для обеспечения эффекта лавинности .Анализ серьезных ослаблений в первоначальном ключевом расписании ,включающий Knudsen[Knud95], а также анализ Knudsen и Berson [KnBe96] успешной разностной атаки на 5 - цикловой версии . Они отметили также , что PHT - преобразования - это основной источник ослаблений , которые допускают атаку.

SPEED

переменные входные данные (64, 128 или 256) , и ключ (48 - 256 ) и цикловой (>32) блочной шифр , использующий несбалансированную сеть , разработанный Zheng в 1997 [Zhen]. Использует ключевые биты нелинейной булевой операции , а данные зависимы от циклического сдвига в каждом цикле, с большим числом циклов , нуждающихся в простой цикловой функции и ограниченного рассеяния на цикл.

TEA

простой 64 - битный , 32 - цикловой блочный шифр Фейстеля со 128 - битным ключом , разработанный Wheeler и Needham [WhNe94]в 1994. Используется очень простой фунциональный цикл , скомбинированный из варианта сложения и xor -а наряду с левым и правым сдвигом для обеспечения нелинейности. Все это повторяется достаточно большое число циклов для обеспечения достаточной сложности.

Отметим следующие моменты :

случайность против расчета в S - блоках

Schneier[Schn96] цитируя L.O'Connor отметил , что для больших S - блоков использование случайных - хороший выбор. Но обычно существуют части "плохих" блоков , что и наблюдается. Я чувствую себя более комфортно с мыслью о разработке S - блоков с гарантированными характеристиками. Недостаток в том , что они известны и могут быть исследованы (зато получать мы их будем правильными :-)

использование несовместных операторов смешения

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

сложность одного цикла против количества циклов

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

Предложения по LOKI97.

LOKI97 - 16-цикловой шифр Фейстеля на 128 - битовых данных использующий сложную нелинейную функцию f(A,B) с 256- битовым алгоритмом выработки ключей, который может быть получен с использованием 128, 192 и 256 - битовых ключей.

Вычисления данных.

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

L0 = L

R0 = R

Затем они пропускаются через 16 циклов (i = 1,16) сбалансированной петли Фейстеля:
   
Ri = Li-1 xor f(Ri-1+SK3i-2,SK3i-1)

Li = Ri-1+SK3i-2+SK3i

Результирующее 128 - битовое значение выхода ( шифртекст) составляется следующим образом: 
    
     [R16|L16]

после последнего цикла, то есть не меняя местами, как обычно в циклах.

Функция f(A,B) должна быть создана так, чтобы гарантировать максимальный лавинный эффект между всеми входными битами функции. Текущее предложение для этой функции f(A,B) приводится ниже.

Обратим внимание на использование "симметричных" преобразований (сложения) на R также, как и более общее преобразование L xor- ом с выходом функции . Это формирует несравнимую группу с xor- ом , используемым на выходах из предыдущих циклов и, следовательно, обеспечивает некоторое рассеивание входных битов на входе функции также как и сокрытие последнего входного значения .

Таким образом, полное преобразование данных выглядит :

При расшифровке вычисления включают в себя разбиение шифртекста:

L16 = L

R16 = R

И затем прохождение по циклам в обратном порядке, т. е. используя 16 циклов     (i = 1,16)
     
     Ri-1 = Li xor f(Ri-SK3i,SK3i-1)
     Li-1 = Ri-SK3i-SK3i-2

128 - битное значение открытого текста получается как   

  [R0|L0]

Алгоритм Выработки Ключей.

LOKI97 использует алгоритм выработки ключей, базирующийся на несбалансированной петле Фейстеля (как у Schneier и Kelsey [ScKe96]), оперирующий четырьмя 64 - байтовыми словами. Используется та же функция f(A,B) , как и при вычислении данных, чтобы обеспечить достаточную нелинейность для гарантии того, что вычислить связанные ключи трудно.

Алгоритм выработки ключей устанавливает  четыре 64-битных слова [K40|K30|K20|K10] на основании размера предлагаемого ключа следующим образом :

При заданном 256-битном ключе [Ka|Kb|Kc|Kd] получим
[K40|K30|K20|K10] = [Ka|Kb|Kc|Kd]

При заданном 192-битном ключе [Ka|Kb|Kc]получим

[K40|K30|K20|K10] = [Ka|Kb|Kc|f(Ka,Kb)]

При заданном 128-битном ключе [Ka|Kb] получим

[K40|K30|K20|K10] = [Ka|Kb|f(Kb,Ka)|f(Ka,Kb)]

Затем они пропускаются через 48 циклов (i = 1,48) для получения 48 вспомогательных ключей :

      SKi = K1i = K4i-1 xor gi(K1i-1,K3i-1,K2i-1)
      K4i = K3i-1
      K3i = K2i-1
      K2i = K1i-1
где
        gi(K1,K3,K2)=f(K1+K3+(Delta*i),K2)
      Delta = (sqrt(5)-1)*263 = 9E3779B97F4A7C1516

Три цикла алгоритма выработки ключей требуются для создания трех вспомо-гательных ключей каждого цикла вычисления данных .Так, требуется всего 48 циклов для алгоритма выработки ключей, эквивалентных примерно трем зашифровывающим вычислениям .

Добавление формы К1+К3+(Delta*i) в группу, несовместимую с xor-ом, используемым на выходе предыдущего цикла , - такое же, как и при вычислении данных. Оно включает умножение по модулю 264 на Delta - значение , полученное из "золотого" соотношения для уменьшения проблем симметричности.

Расшифровывание использует ключи в обратном порядке , добавляя замену вспомогательного ключа SK3i-2 на SK3i и наоборот. Это необходимо , чтобы высчитать первоначально зашифрованное значение , и не существует укороченного варианта без этого действия.

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

Сильно нелинейная функция f(A,B) имеет два 64 - битных входных значения A и B, которые обрабатываются с использованием двух "слоев" S - блоков с высочайшей степенью нелинейности для получения 64 - битного выхода . Испльзуются две перестановки для гарантии максимального лавинного эффекта между всеми битами функции.

Основное новшество в предлагаемой мною разработке - это использование двух уровней S-P петли вместо одного , как в большинстве других существующих сейчас шифров Фейстеля .Оно используется как для обеспечения максимального желаемого лавинного эффекта , так и для того чтобы минимизировать возможность существования подходящих разностных и линейных характеристик (для осуществления атак).Наличие ключевой перестановки на входе функции , перенаправляющее различные входы S - блоков, гарантирует, что предугадать то, в какой S - блок попадет отдельный входной бит , - весьма сложно . Это увеличивает сложность получения любой полезной для атаки характеристики.

 

Данная функция выглядит следующим образом :

f(A,B) = Sb ( P ( Sa ( E ( KP ( A,B ) ) ) ), B)


Графически это выглядит так :

 

В деталях, различные составляющие операций таковы :

KP()

очень простая ключевая перестановка , которая разбивает 64 - битный вход А на два 32 - битных слова , и использует нижние ( т.е. наиболее значимые ) 32 бита входа В , чтобы определить необходимо ли поменять соответствующие пары битов в этих словах (если бит ключа 1), или же нет (если бит ключа 0) , похожая на ту ,что используется в ICE [Kwan97]. Может быть вычислено как :

KP([Al|Ar],SKr) = [((Al & ~SKr)|(Ar & SKr)) | ((Ar & ~SKr)|(Al & SKr))]

E()

Расширяющая функция , похожая на соответствующую в LOKI91,но измененная в плане более быстрого выполнения , которая разбивает на пересекающиеся группы по 13 или 11 бит (S1 или S2 соответственно ), так что по крайней мере несколько бит влияют на два S - блока одновременно, и, с учетом предыдущего сложения, это означает ,что все биты имеют некоторое влияние на множество S - блоков. Таким образом, Е распределяет 64 бита входного значения на 96 битов выходного :

[4-0,63-56|58-48|52-40|42-32|34-24|28-16|18-8|12-0].

Sa(), Sb()

две колонки S - блоков , выполненных просто конкатенацией блоков S1 и S2 (описанных ниже) , так что

Sa() = [S1,S2,S1,S2,S2,S1,S2,S1] и Sb()=[S2,S2,S1,S1,S2,S2,S1,S1].

В Sa() входы смешаны (вход + ключ из выхода Е), а в Sb() верхние биты - это только ключевые биты (из нижних , более значимых 32 битов В) .

Р()

перестановка, рассеивающая выходы  S - блоков полностью по 64 - битной длине , используя регулярный шаблон латинского квадрата, похожий на LOKI91, но с такими незначительными изменениями, что один и тот же выход никогда не войдет в соответствующий вход . Р распределяет входные биты [63-0] так:

[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]

Я полагаю, что эта функция будет выполнима с 24 табличными заданиями(8 на каждый из Sa,P и Sb) , плюс несколько and-ов, or-ов, xor-ов , сдвигов и сложений на каждый цикл .Это сделает ее выполнение реально быстрым и эффективным .

S-блоки.

S - блоки, выбранные для LOKI97 используют возведение в куб в нечетном поле Галуа GF(2n ) , т.к. оно имеет несколько очень удобных свойств (таких как сильная нелинейность и относительно однообразный профиль xor). Чтобы количество входов было нечетно, в S1 используется 13 входных битов, а в  S2- 11 битов. Они распределяются так, как описано выше, чтобы объединиться для работы над каждым входным блоком. Входное значение инвертируется (так, что входы 0 или 1 никогда не дадут выходов 0 или 1), и выходное значение маскируется в выбранные 8 нижних выходных битов . Функции  S - блоков таковы : 
     
     S1[x] = ((x xor 1FFF)3 mod 2911) & FF,  in GF(213)

      S2[x] = ((x xor  7FF)3 mod  AA7) & FF,  in GF(211)

 

(заметим , что все константы приведены в 16-ричной системе , а все вычисления сделаны как полиномиальные в GF(2n) )

Контрольная тройка .

Сертификационная тройка (пример LOKI97), такова:

LOKI97 key: 000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F

LOKI97 plain: 000102030405060708090A0B0C0D0E0F

LOKI97 cipher: 75080E359F10FE640144B35C57128DAD

Беглый криптоанализ.

Мой беглый взгляд на криптоанализ говорит о том что :

Алгоритм выработки ключей

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

зашифрование

сильно нелинейная функция f(А, В) имеет компоненты , напрямую зависящие от ключа и полный лавинный эффект над 64 битами входа А , но в тоже время лишь частичный эффект входа В за один проход. Функция должна противостоять как разностному , так и линейному анализу . Уже после трех циклов должна быть полная зависимость от входа и ключа (заметим , что имеет место неполная зависимость L от L-битов после первого цикла).

Для дальнейшей работы вероятно должно быть рассмотрено следующее различие : L половинки имеют постоянное сложение по модулю 2, а R половинки имеют постоянную арифметическую разность. Это может отменить действие вспомогательных ключей на первом цикле, и позволить сравнение циклового выхода , но только нулевые отличия дадут шанс получить распространение на следующий цикл .Также финальная ключевая перестановка должна неплохо уничтожить все возможности.

Безотлагательные вопросы.

На этой ранней стадии основные моменты , на которые я бы хотел обратить внимание - это :

1. выглядит ли основная структура разумной ?

2. имеем ли мы верный баланс сложности : данные против компонент алгоритма выработки ключей ?

3. достаточно ли добавка Delta маскирует симметричность в ключевом расписании ?

4. правильно ли выбрано число циклов (помня о необходимости достаточного запаса безопасности для предполагаемо долгой жизни шифра ) ?

Выводы.

Эта статья включает мои предварительные и предполагающиеся мысли по поводу доработки LOKI. Любая или же все из них (в т. числе и уже имеющихся) - это предмет для полного пересмотра и коренных или других изменений по ту сторону воображения !

Благодарность.

Работа проводилась в течение специальной программы обучения в 1997г., во время посещения NTNU в Trondheim, Norwey, и CCSR,UOW, Wollongong. Я бы хотел поблагодарить моих коллег из этих институтов за их участие и поддержку.

 

Ссылки.

AES97
"Advanced Encryption Standard Call", NIST, 1997. http://csrc.ncsl.nist.gov/encryption/aes/aes_home.htm.
BKPS91
Lawrence Brown, Matthew Kwan, Josef Pieprzyk, Jennifer Seberry, "Improving Resistance to Differential Cryptanalysis and the Redesign of LOKI", in Advances in Cryptology - Asiacrypt'91, Lecture Notes in Computer Science, Vol 739, Springer-Verlag, pp 36-50, 1991.
BiSh91
Eli Biham, Adi Shamir, "Differential Cryptanalysis Snefru, Kharfe, REDOC-II, LOKI and Lucifer", in Advances in Cryptology - Crypto'91, Lecture Notes in Computer Science, Vol 576, Springer-Verlag, pp 156-171, 1991.
Biha94c
Eli Biham, "New Types of Cryptanalytic Attacks Using Related Keys", Journal of Cryptology, Vol 7, No 4, pp 229-246, 1994.
BrPS90
Lawrence Brown, Josef Pieprzyk, Jennifer Seberry, "LOKI - A Cryptographic Primitive for Authentication and Secrecy Applications", in Advances in Cryptology: Auscrypt '90, Lecture Notes in Computer Science, Vol 453, Springer-Verlag, pp 229-236, 1990.
Cryp97
"Cryptix Java Cryptographic Library", 1997. http://www.systemics.com/docs/cryptix/.
KnBe96
Lars Knudsen, Thomas A. Berson, "Truncated Differentials of SAFER", in Fast Software Encryption 3, Lecture Notes in Computer Science, Vol 1039, Springer-Verlag, pp 15-26, 1996.
KnRo96
Lars Knudsen, M.J.B. Robshaw, "Non-linear Approximations in Linear Cryptanalysis", in Advances in Cryptology - Eurocrypt'96, Lecture Notes in Computer Science, Vol 1070, Springer-Verlag, pp 224-236, 1996.
Knud91
Lars Knudsen, "Cryptanalysis of LOKI", in Advances in Cryptology - Asiacrypt'91, Lecture Notes in Computer Science, Vol 739, Springer-Verlag, pp 22-35, 1991.
Knud92
Lars Knudsen, "Cryptanalysis of LOKI91", in Advances in Cryptology - Auscrypt'92, Lecture Notes in Computer Science, Vol 718, Springer-Verlag, pp 196-208, 1992.
Knud93
Lars Knudsen, "Practically Secure Feistel Ciphers", in Fast Software Encryption, Lecture Notes in Computer Science, Vol 809, Springer-Verlag, pp 211-221, 1993.
Knud94
Lars Knudsen, "New potentially "weak" keys for DES and LOKI", in Advances in Cryptology - Eurocrypt '94, Lecture Notes in Computer Science, Vol 950, Springer-Verlag, pp 419-424, 1994.
Knud95
Lars Knudsen, "A Key-Schedule Weakness in SAFER K-64", in Advances in Cryptology - Crypto'95, Lecture Notes in Computer Science, Vol 963, Springer-Verlag, pp 274-286, 1995.
Kwan97
Matthew Kwan, "The Design of the ICE Encryption Algorithm", in Fast Software Encryption 4, Springer-Verlag, 1997. http://www.cs.mu.oz.au/~mkwan/ice/paper.html.
RSAD97
"Government encryption standard DES takes a fall", RSA Data Security Inc, 1997. http://www.rsa.com/des/.
SaFu97
Kouichi Sakurai, Souichi Furuya, "Improving Linear Cryptanalysis of LOKI91 by Probabalistic Counting Method", in Fast Software Encryption 4, Springer-Verlag, 1997.
ScKe96
Bruce Schneier, John Kelsey, "Unbalanced Feistel Networks and Block Cipher Design", in Fast Software Encryption 3, Lecture Notes in Computer Science, Vol 1039, Springer-Verlag, pp 121-144, 1996.
Schn96
Bruce Schneier, "Applied Cryptography - Protocols, Algorithms and Source Code in C", 2nd edn, John Wiley and Sons, New York, 1996.
ToSM94
Toshio Tokita, Tohru Sorimachi, Mitsuru Matsui, "Linear cryptanalysis of LOKI and S2DES", in Advances in Cryptology - Asiacrypt '94,, Lecture Notes in Computer Science, Vol 917, Springer-Verlag, pp 293-306, 1994.
Vaud96
Serge Vaudenay, "On the Weak Keys of Blowfish", in Fast Software Encryption 3, Lecture Notes in Computer Science, Vol 1039, Springer-Verlag, pp 27-32, 1996.
WhNe94
David J. Wheeler, Roger M. Needham, "TEA, a Tiny Encryption Algorithm", in Fast Software Encryption 2, Lecture Notes in Computer Science, Vol 1008, Springer-Verlag, pp 363-366, 1994. http://www.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html.
Zhen97
Yuliang Zheng, "The SPEED Cipher", in Financial Cryptography'97, BWI, Anquilla, pp 24-28, Feb 1997. http://pscit-www.fcit.monash.edu.au/~yuliang/pubs/speedc.tar.Z.

The latest version of this paper may be found at: http://www.adfa.edu.au/~lpb/papers/ssp97/loki97a.html.

Last updated: 15 Dec 97.