Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА 1. ОСНОВНЫЕ СВОЙСТВА И МЕТОДЫ АНАЛИЗА ПОТОЧНЫХ ШИФРОВ 10
І.Ї. Основные понятия 10
1.2. Классификация алгоритмов поточного шифрования 12
1.3. Программно реализуемые алгоритмы поточного шифрования, предложенные в открытой литературе 15
1.3.1. Программно реализуемые регистровые алгоритмы поточного шифрования 16
1.3.2. Программно реализуемые нерегистр о вые алгоритмы поточного шифрования І9
1.4. Обзор результатов по анализу алгоритма поточного шифрования RC4 21
1.4.1. Описание алгоритма поточного шифрования RC4 22
1.4.2. Построение линейной модели алгоритма RC4 22
1.4.3. Распределение биграммв гамме RC4 23
1.4.4. Метод восстановления начального состояния RC4 по гамме, основанный на подходе "ветвей и границ" 25
1.4.5. Методы криптоанализа RC4, основанные на предсказывающих и благоприятных состояниях 27
1.4.6. Алгоритм вскрытии RC4, основанный на методе связанных ключей 29
1.4.7. Свойства алгоритма генерации начальной подстановки RC4 30
ГЛАВА 2. А1ІАЛИЗ АЛГОРИТМА ПОТОЧНОГО ШИФРОВАНИЯ RC4 32
2.1. Цикловая структура алгоритма RC4 32
2.1.1. Циклы длины m(m-l) алгоритма RC4 32
2.1.2. Изоморфные циклы в алгоритме RC4 34
2.2. Статистические свойства алгоритма RC4 37
2.2.1. Определение вероятностной модели 37
2.2.2. Распределение первых знаков в гамме RC4 38
2.2.3. Распределение бнграмм н гамме RC4 40
2.2.5- Критерий различения последовательности RC4 от случайной равновероятной последовательности 41
2.3. Число ключей алгоритма RC4, приводящих к начальным подстановкам с произвольной фиксированной цикловой структурой 44
2.4. Распределение і-грамм в начальной подстановки RC4 58
2.5. Распределение первого знака алгоритма RC4 с учетом t-грамм 71
2.6. Заключение 75
ГЛАВА 3. РАЗЛИЧНЫЕ МОДИФИКАЦИИ АЛГОРИТМА RC4 И ИХ АНАЛИЗ 77
3,1 Описание семейства алгоритмов GI 77
3.2. Среднее число решений заведомо совместной системы случайных линейных уравнений специального вида над кольцом вычетов 79
3.3. Длина гаммы, необходимая для восстановления начального состояния GI 84
3.4 Свойства семейства алгоритмов GI 87
3.6. Методы восстановления начального состояния алгоритма GI 90
3.7. Метод криптоанализа алгоритма поточного шифрования 1ВАА 95
3.8. Метод криптоанализа алгоритма поточного шифрования ISAAC 9
3.9. Заключение 103
ГЛАВА 4. АНАЛИЗ АЛГОРИТМА ПОТОЧНОГО ШИФРОВАНИЯ SOLITAIRE 104
4.1. Описание алгоритма Solitaire 104
4.2. Свойства групп преобразований, порожденных алгоритмом Solitaire 106
4.3. Свойства полугруппы преобразований
4.4. Свойства группы преобразований,, порожденной автоматом Ар 117
4.5. Заключение 119
ГЛАВА 5. АНАЛИЗ АЛГОРИТМОВ СЕМВЙСТВА ВЕСТА ФИРМЫ «ЛЛН-КРИПТО»... 120
5.1. Описание алгоритмов поточного шифрования семейства Веста фирмы ЛАН-Крипто. 120
5.1.1. Описание алгоритма поточного шифрования Веста-2М 120
5.1.2. Описание алгоритма поточного шифрования Веста-2 121
5.2. Оценка расстояния единственности для алгоритмов Веста-2 и Веста-2М 123
5.3. Метод определения начального состояния алгоритма Веста-2М с тождественной перестановкой к 123
5.4. Метод определения начального состояния алгоритма Веста-2М 127
5.5. Метод определения ключа алгоритма Веста-2 с тождественной перестановкой я 129
5.6. Метод определения начального состояния алгоритма Веста-2 131
5.7. Определение начального состояния алгоритма Веста-2 с произвольной перестановкой я 133
5.S. Слабые состояния алгоритма Веста-2 135
5.9. Групповые свойства алгоритма Веста 140
5.10. Заключение 143
СПИСОК ЛИТЕРАТУРЫ 144
ОСНОВНЫП ОБОЗНАЧЕНИЯ 150
Введение к работе
В настоящее время в мире происходит активное развитие электронной коммерции. При разработке систем электронной коммерции фактор безопасности играет первостепенную роль. При этом типовой задачей является создание системы работы с партнерами, предоставляющей защищенный доступ к динамически обновляемой информации. В некоторых случаях система предоставляет возможность оформления заказа и резервирования тавара. Для этого она должна обеспечивать аутентификации, невозможности отказа от авторства и конфиденциальности пользователя. Большинство производителей компьютеров, все крупные компьютерные дистрибьюторы, а также многие из докомпьютерных международных корпораций уже используют подобные системы в России.
Для таких крупнейших корпораций как Bosch, Merisel или Xerox, защищенные системы разработаны в России специалистами самих компаний или профессиональными контр акторам и. Некоторые компании, например, ШМ, используют стандартную международную систему, адаптированную для российских реалий. Объединяет все эти системы, имеющие свои подсистемы защиты, использование стандартных средств Интернет для доступа к информации и осуществления бизнес-транзакций.
Одним из эффективных способов создания подсистемы защиты в системах электронной коммерции на сегодняшний день является применение криптографических методов защиты информации (шифрование, идентификация, имитозащита). Основу большинства криптографических методов составляют симметричные алгоритмы шифрования, которые принято подразделять на блочные и поточные. Скорость работы поточных алгоритмов обычно значительно превышает скорость работы блочных.
Поскольку Интернет технологии требуют высоких скоростей, то одной из актуальных задач в криптографии является разработка и реализация высокоскоростных программно реализуемых поточных алгоритмов шифрования, обеспечивающих высокую надежность защиты информации, с хорошими техническими и эксплуатационными свойствами. К настоящему времени значительная часть предложенных в открытой литературе поточных шифров основана регистрах сдвига над полем GF(2).
В значительной степени это объясняется разработанной теорией и удобством при аппаратной реализации алгоритмов шифрования. Для алгоритмов» основанных на регистрах сдвига над полем GF(2), достаточно хорошо разработаны методы синтеза и криптоанализа, в тоже время относительно мало изучены высокоскоростные программно реализуемые нерегпстровые поточные алгоритмы и практически не развита теория их синтеза и методов криптоагіализа, хотя при программной реализации они могут быть предпочтительнее.
Существенное повышение производительности микропроцессоров к 80-м годам вызвало в криптографии усиление интереса к программным методам реализации криптоалгоритмов как возможной альтернативе аппаратным схемам. Одним из самых первых подобных алгоритмов шифрования, получившим широкое распространение в электронной коммерции, стал RC4 (также известный как алгоритм ARCFGUR). Он, например, используется во многих платежных системах. В России, кроме RC4 программно реализуемыми поточными шифрами, используемыми в электронной коммерции, являются Веста-2, Веста-2М. Поэтому основное внимание в диссертации уделяется как программно реализуемым неригистровым шифрам: RC4, его модификациям (IA, ШЛА, ISAAC), так и регистровым: Веста-2, Веста-2М. Рассмотренные алгоритмы включают большинство наиболее распространенные среди программно реализуемых поточных алгоритмов шифрования. Единство исследований достигается общей математической моделью, изложенной на теоретик о-автомати ом языке, едиными математическими методами.
Целью диссертационной работы является разработка общих математических моделей, включающих ряд алгоритмов шифрования и методов их криптоанализа; исследование криптографических свойств (те оретико-автоматных, теоретик о-груп новых, теоретико вероятностных) программно реализуемых поточных алгоритмов шифрования RC и различных его обобщений Gl (1А, IBAA, ISAAC), Solitaire, Веста.
Для достижения поставленной цели, используя единую те о ретн ко-автоматну ю модель, были решены следующие задачи:
• Проведен обзор современных программно реализуемых поточных алгоритмов и методов их криптоанализа в рамках этой модели;
• Введено в рамках тсорети ко- автомати ой модели семейство алгоритмов поточного шифрования GI, обобщающее ряд алгоритмов шифрования (ІА, ШЛА, ISAAC), предложенных в открытой литературе, и получена верхняя оценка числа знаков, необходимых для восстановления начального состояния;
• Описан ряд криптографических свойств алгоритмов RC4, GI, Solitaire, Веста;
• Разработаны методы восстановления состояния по гамме алгоритмов GI и Веста, основанные на их алгебраических свойствах.
Отметим, что в последние 10 лет активно исследовались следующие программно реализуемые поточные алгоритмы: Pike, Scop, Dagger, Sober, Sober l6, Bmgl, Sober32, RSC, Liii, Leviathan, RC4, Wake, Seal, Twoprime, ISAAC, IA, 1BAA, Chameleon, Panama, Rabbit, Solitaire, Веста, причем, из них только RC4, Wake, Веста используются практически.
Исследованием и разработкой алгоритмов, рассматриваемых в диссертации, занимались следующие известные криптографы; A. Shamir, J. Golic, R. Rivest, В, Schneier, L. Knudsen, V. Rijmen, B. Preneel, S. Fluhrer, D. McGrew, \V. Meier, R. Jenkins, Л.Н. Лебедев.
Диссертация состоит из введения, пяти глав, списка литературы из 14S наименований. Работа изложена на 150 страницах с рисунками и таблицами.
В имеющейся открытой литературе по поточным шифрам, как и шифрам вообще, в большинстве своем явно недостаточное использование в изложение доказательной базы, оно часто носит описательный характер. В связи с этим в первой главе, следуя работам отечественных мате мати ко в-крипто графов, а также Рюппєля, в рамках единой математической модели на языке теории автоматов, выполнен обзор современных программно реализуемых алгоритмов поточного шифрования и методов их анализа. Основное внимание в обзоре уделено результатам, полученным с 1993 по 2003 г. по анализу алгоритма RC4,
Целью второй главы является исследование алгебраических и вероятностно-статистических свойств алгоритма поточного шифрования RC4, Алгоритм RC4 зависит от параметра ш=2\ натуральное т? 2, (для практических приложений выбирается т=256).
Так полиостью описаны вес самые короткие циклы длины (/м(/н-1)) графа функции переходов алгоритма RC4 и приведен метод восстановления состояний, порождающих эти циклы, по гамме. Построен изоморфизм между циклами в графе функции переходов RC4 и показано, что число изоморфных циклов является делителем числа т.
Получено распределение частот -грамм (к==\, 2) в гамме алгоритма RC4 при предположении, что начальная подстановка выбирается случайно и равновероятно из 5 . Данный результат является обобщением и усилением результатов, полученных A. Shamir, I. Mantin и S. Fluhrer; D. Построены критерии отношения правдоподобия на основе обнаруженных неравно вероятностей в распределении первых знаков и биграмм, т.е. ищется неравновсроятность в распределении знаков в L-граммах (z,1,...,zf), (-2 "-»2г) и
При различении последовательности, выработанной алгоритмом RC4, от случайной равновероятной последовательности:
а) для критерия отношения правдоподобия с произвольно заданным уровнем значимости а и мощностью р, основанного на неравноверолтности первого выходного знака zi (кроме случая ij=2jo) объем выборки равен л=0(/я3);
b) для критериев отношения правдоподобия с произвольно заданным уровнем значимости а и мощностью р, основанных на неравновероятности второго выходного знака Zi? или на неравновероятности в распределение биграмм, или на неравно вероятности первого выходного знака zi при ij=2jo объем выборки равен v п= О(т), Получено распределение /-грамм подстановки. С учетом найденных г- неравномарностен в распределении /-грамм подстановки получено распределение перного знака гаммы RC4 при предположении, что ключ выбирается случайно и равновероятно из т Также исследуется метод генерации начального состояния криптоалгоритма RC4. Найдено число всех ключей криптоалгоритма длины пи приводящих к начальным подстановкам с произвольной фиксированной цикловой структурой. Задача оказалась эквивалентной проблеме порождения симметрической группы Sm системой транспозиций с ограничениями, которая решалась с применением методов комбинаторного анализа. Показано, что число Q(ai,...,am) различных произведений транспозиций {m-\jm) ..(\J2)(0ji)i где jk€{О,т-1 }tk = 1тш, порождающих подстановки с фиксированной цикловой структурой {1 12 2.,.т "}, I -(Хі+2-а2+..Лт-{хт=т9 равно
Получено, чем больше число неподвижных элементов в подстановке, тем больше вероятность ее генерации. Поэтому полученные результаты позволяют рекомендовать при применении метода полного перебора для восстановления начального состояния криптоалгоритма RC4 начинать опробование с тождественной подстановки» а затем о и робо ваты J одстаї ювки с наибольшим числом неподвижных элементов,
В третьей главе введено семейство алгоритмов поточного шифрования GI, в результаїе чего, известные алгоритмы (ІА, 1ВАА, ISAAC, предложенные Р. Дженкинсом), представляются в общей теоретико-автоматной модели. Семейство алгоритмов GI, также как и алгоритмы 1А, IBAA, ISAAC, является обобщением алгоритма RC4,
Показано, что задача восстановления по гамме начального состояния GJ сводится к решению системы уравнений над кольцом вычетов и получена верхняя оценка числа знаков гаммы, необходимых для определения по гамме хотя бы одного начального состояния из класса эквивалентных состояний. Теория систем случайных уравнений развивалась в работах В.Е, Степанова, Г.В. Валакина, В.Ф. Колчина, И.Н, Коваленко, А,А. Левитской, В.А. Коиытцева, А.В. Лапшина, А,В, Шаповалова и других. Связь между системами уравнений в GF(2) и графов впервые была отмечена В.Е. Степановым. Практически все работы рассматривают системы случайных уравнений над конечным полем, поэтому полученные в этих раоотах результаты не всегда удается применить для систем случайных уравнений над кольцом. Полученные в диссертации результаты опираются на работы В.Ф. Кол чина.
Алгоритм, принадлежащий семейству GI, определяется шестью функциями ф, р, а, 5, X, с, которые зависят от параметров b, mcN. При ряде ограничений на эти шесть функций описаны теоретико-автоматные свойства GI. Как следствие показано, что алгоритм IA также удовлстворяет этим свойствам.
Также описаны алгоритмы, являющиеся гомоморфным образом G1 (при некотором ограничении на функции ф, р, о, 3, , с), и па основе построенного гомоморфизма предложен метод их вскрытия по гамме. Получено, что трудоемкость метода равна Tt-2 "" -т(2\пт+ 2/я-М) Э.О., где Подпараметр метода. Трудоемкость метода полного перебора равна Т„=2 " " т In т + т2 э.о.. Рассмотрены свойства функций (р, р, a, $ , Xi используемых в 1АТ и предложен метод
„ .т\х\т- гЪтг . , восстановления начального состояния по гамме трудоемкостью 1г=(- - +4т) _n.m_l л _ -b-m-l ЯЇІППІ + /Н2
2 э.о.. Отмстим, что трудоемкость метода полного перебора равна 2 э.о.
Описан класс слабых состояний алгоритма GI, трудоемкость восстановления которых существенно меньше, чем приведенная выше с использованием метода гомоморфизмов.
Полученная трудоемкость для этих состоянии равна 7j=2 ° (3 2т). В случае ЇА эту трудоемкость удалось существенно понизить и она не превышает — т2 э.о,(при т=25в раьна98-10ээ,о.) Также рассмотрен метод восстановления начального состояния алгоритмов 1ВАА, ISAAC по гамме, основанный на частичной линеаризации алгоритмов и зависящий от р. Получено, что трудоемкость восстановления начального состояния алгоритмов IBAA и ISAAC при т- » равна т4-2 ™- .«..(iS +D.z" 1 ЭЛ., где параметр 0-0 в алгоритме IBAA.
В четвертой главе рассматриваются групповые свойства алгоритма поточного шифрования " Solitaire "(" Пасьянс") предложенного Б. Шнайсром в 1999 г.. Согласно замыслу автора он предназначен для применения в качестве ручного шифра ("paper-and-pencil cipher") и построен па основе перемешивания колоды игральных карт. Алгоритм зависит от параметров т, лєМ, которые предлагается брать равными т=26г /7=54. Функция переходов F представима в виде композиции четырех преобразований F-F\F2 F /%
Поскольку изучение преобразования F и полугруппы F непосредственно является проблематичным, поэтому рассматривались свойства полугрупп Fi , Рг , FbF2 , F],р2 , Р,р2,Кз , Р,р2,Нз,р4 и свойства групп, порожденных обратимыми модификациями преобразования F. В силу того, что F есть подполугруппа из Рьр2,Рз1Р-і , то ряд полученных результатов непосредственно переносится па F . Так показано, что полугруппа Fi делит полугруппу F]r Fj t а F — полугруппу Fr, Fy . Кроме того, F], F2, Гз = Fi, Рз = F2, і . Описаны свойства полугруппы преобразований, порожденной автоматом, моделирующим алгоритм генерации начального состояния алгоритма Solitaire. Известно, что импримитивность может являться слабостью Solitaire.
В пятой главе предложены методы восстановления начального состояния алгоритмов поточного шифрования Веста-2 и Веста-2М, разработанных в 1995-1993 ГГ. фирмой «ЛАН
Крипто». Алгоритм Веста-2 используется в коммерческих продуктах этой фирмы, Веста-2М является стандартом газовой промышленности России. С криптографической точки зрения алгоритмы относятся к классу фильтрующих генераторов, в которых используется линейный регистр сдвига над полем GF(p), р-простос число порядка 2м.
v Методов анализа фильтрующих гснератороЕ с регистрами над полем GF(p) в открытой литературе предложено мало. Основная часть разработанных методов применима г" только к анализу комбинирующих генераторов с линейными регистрами над полем GF(2).
Поэтому, предложенные методы прежде всего представляют интерес, как попытка анализа такого класса алгоритмов Развитый подход позволяет частично линеаризовать некоторый класс фильтрующих генераторов над полем GF(p) Его применение показано на примере алгоритмов Веста-2 и Веста-2М с тождественной перестановкой л. Получено, что трудоемкость предложенных методов для алгоритмов Всста-2М, Веста-2 с тождественной перестановкой я одинакова и в среднем равна Тм =2 э,о.. Заметим, что трудоемкость метода полного перебора равна Тпср-2544 э,о„
Также решается задача определения начального состояния алгоритмов Всста-2М, Веста-2 с реальной перестановкой я. Она сводится к восстановлению начального состояния линейного регистра по гамме. Для алгоритмов Веста-2М, Веста-2 с реальной перестановкой тс частичная линеаризация, как для тождественной перестановки -к, не получается. Но в силу алгоритмов, также удалось построить линейные соотношения. Получено, что трудоемкость предложенных методов для алгоритма Веста-2М в среднем равна Т»Ъ)= 23 3 4 э.о., для алгоритма Веста-2 - 1м 2 э.о..
Описан класс слабых состояний шифра Веста-2, названных благоприятными. Если состояние является А-благоприятным, то трудоемкость метода определения начального состояния алгоритма Веста-2 по гамме г :
a) прик-11 не превышает 236элементарных операций;
b) при 8 к \ I не превышает 25t элементарных операций.
С помощью операции сплетения описана группа семейства Веста,