Содержание к диссертации
Введение
1. Описание тестов, структур данных, алгоритмов
1.1 Теоретические основы 24
1.2 Описание тестов 25
1.3 Структуры и алгоритмы 31
1.4 Применение алгоритмов сжатия для тестирования на случайность 38
1.5 Двуличные процессы и выбор длины блока для тестирования 44
1.6 Приложение 48
2. Тестирование генераторов случайных чисел
2.1 Сравнение эффективности методов 51
2.2 Анализ генераторов псевдослучайных чисел, использующихся на практике 61
2.2.1 Линейные конгруэнтые генераторы 61
2.2.2 Другие типы генераторов . 66
2.2.3 Тестирование популярных генераторов псевдослучайных чисел 68
3. Новая статистическая атака на блоковые шифры
3.1 Описание метода 72
3.2 Эксперименты с шифром RC5 85
3.2.1 Исследования устойчивости шифра RC5 85
3.2.2 Схема реализации тестов на МВС-1000 92
3.2.3 Результаты реализации атаки RC5 96
3.2.4 Схема реализации атаки на МВС-1000 99
Заключение
- Структуры и алгоритмы
- Двуличные процессы и выбор длины блока для тестирования
- Анализ генераторов псевдослучайных чисел, использующихся на практике
- Исследования устойчивости шифра RC5
Введение к работе
Актуальность темы
Статистические тесты находят применение в самых различных областях, включая анализ генераторов случайных и псевдослучайных чисел, и ряд задач криптографии. Поэтому задача построения новых эффективных статистических тестов и разработка алгоритмов эффективной реализации находится в центре внимания многих исследователей.
В настоящее время используется много методов (или тестов) для проверки генераторов случайных и псевдослучайных чисел. Все эти методы рассматриваются в рамках математической статистики. Точная постановка задачи следующая: проверяется гипотеза HQ О том, что источник порождает символы из алфавита {0,1} независимо и вероятности этих символов равны 1/2 против альтернативной гипотезы Hi, что последовательность порождается стационарным и эргодическим источником и Щ не выполняется. Для краткости, в дальнейшем, будем называть эту задачу тестом (или проверкой) на случайность.
В криптографии и других приложениях используются генераторы случайных и псевдослучайных чисел. Генераторы случайных чисел используют некоторый физический источник данных для получения случайной последовательности. Он может быть основан на квантовых эффектах, на шумах в электрических цепях и т.п. Такие генераторы рекомендуется регулярно проверять на "случайность" выходной последовательности. Именно в этой области общие статистические тесты оказываются незаменимыми. Генераторы псевдослучайных чисел вы числяют последовательность чисел. Такие генераторы также необходимо проверять при помощи статистических тестов до их практического применения.
Некоторые проблемы современной криптографии также связаны с тестами на случайность. Прежде всего это относится к так называемым блоковым и потоковым шифрам. Приведем их краткое описание. Блоковые шифры обычно используют некоторое преобразования к блокам данных фиксированной длины (обычно 64 бита или 128 бит). К современным блоковым шифрам предъявляется обязательное требование: они в некотором режиме использования (описанном ниже) должны работать, как "хороший" генератор псевдослучайных чисел. Для проверки же "качества" построенных шифров в этом режиме используют статистические тесты. Если же это условие не выполняется, то такой шифр не рекомендуют к применению (в частности, это требование предъявлялось в проводимом в США в 1999-2000 г.г. конкурсе на "блоковый шифр 21-го века").
Задача построения статистических тестов для генераторов случайных и псевдослучайных чисел привлекает внимание многих исследователей. Об актуальности это проблемы, в частности, говорит то, что в 2000г. Национальный институт стандартов и технологий США (NIST) провел специальное исследования и опубликовал 16 статистических тестов, которые рекомендованы для применения в криптографических приложениях. Основные результаты в этой области принадлежат У. Маурэ-ру (U.Maurer), Д. Кнуту (D.Knuth), Б. Шнайеру (В. Shneier), Р.Ривесту (R. Rivest) и ряду других исследователей. Однако, несмотря на многочисленные работы, задача построения эффективных тестов далека от своего разрешения. Цель работы:
1. Построение новых эффективных статистических тестов и разработка алгоритмов их реализации (в т.ч. для многопроцессорных компьютеров).
2. Применение построенных тестов к экспериментальному анализу известных генераторов псевдослучайных чисел.
3. Применение разработанных методов к задаче анализа стойкости блоковых шифров.
Научная новизна результатов:
1. Разработаны новые эффективные статистические тесты: "порядковый" и тесты, основанные на алгоритмах сжатия. Построены новые алгоритмы и структуры данных для эффективной реализации статистических тестов.
2. Экспериментально исследован широкий ряд практически применяемых генераторов псевдослучайных чисел при помощи новых тестов.
3. Разработана и экспериментально исследована новая статистическая атака на блоковые шифры.
Практическая ценность результатов:
1. Разработанные методы тестирования позволяют эффективно проверять генераторы случайных и псевдослучайных чисел.
Экспериментально исследован ряд известных генераторов псев дослучайных чисел и даны рекомендации по их применению. 3. Предложена новая атака на блоковые шифры, базирующаяся на статистических тестах, которая позволяет обнаруживать "слабые места" блоковых шифров.
Апробация работ и публикации: Основные результаты работы докладывались и обсуждались на следующих российских и международных конференциях: International Symposium on Information Theory (Chicago, 2004), Третья общероссийская конференция "Математика и безопасность информационных технологий" (Москва, 2004), а также на семинарах Института вычислительных технологий СО РАН (Новосибирск).
По теме диссертации опубликовано : 1 электронная публикация, 5 печатных работ, том числе 3 статьи. Основные положения, выносимые на защиту:
1. Разработаны методы эффективного тестирования генераторов случайных и псевдослучайных чисел.
2. Показано, что мощность новых тестов выше чем у ранее известных, включая методы, рекомендуемые NIST.
3. Разработаны алгоритмы и структуры данных для эффективной реализации новых статистических критериев.
4. Предложена и экспериментально исследована новая статистическая атака на блоковые шифры, которая в некоторых случаях позволяет по выбранному шифротексту находить секретный ключ за время меньшее чем полный перебор ключей.
Краткое содержание работы
Во введении обосновывается актуальность разработки новых эффективных статистических тестов, формулируются цели и задачи исследований, приводятся основные положения диссертации, выносимые на защиту.
В первой главе формулируется задача тестирования (псевдослучайных последовательностей чисел. Излагаются алгоритмы новых статистических критериев. Описываются структуры данных, необходимые для эффективной реализации новых статистических тестов, и анализируется сложность вычислений. Все алгоритмы описаны (и реализованы) для многопроцессорных компьютеров. Теоретически обосновывается эффективность теста, базирующегося на алгоритмах сжатия данных.
Один из самых известных статистических тестов для проверки гипотезы о том, что для некоторого источника, который порождает буквы из алфавита А = {ai,..., as}, S 1, выполнена гипотеза:
Ho:p(ai)=p01,...,p(as)=pOs, (1)
против альтернативной гипотезы Щ, являющейся отрицанием i?o, это критерий хи-квадрат. При применении критерия хи-квадрат подсчитывается значение 2 _ А рг - Пр°{)2 г-і прх где V{ - частота символа аг- в выборке х±,..., хп . Известно, что х1 асимптотически приближается с распределению хи-квадрат с к — 1 степенью свободы.
Задача тестирования (псевдо)случайных последовательностей ф чисел формулируется следующим образом. Пусть некоторый источник, который порождает буквы из алфавита A = {а\,..., as}, S 1, необходимо по выборке х\,..., хп , порождаемой источником, проверить гипотезу #о : р(сц) = ... = p(as) = 1/S (2) против альтернативной гипотезы Н\, что источник является стационарным, эргодическим и Щ не выполняется. Ясно, что это частный случай и критерий хи-квадрат здесь применим.
Кратко опишем вариант основного алгоритма тестирования. При тестировании в каждый момент времени t буквы алфавита А упорядочены (и занумерованы) в соответствии с убыванием (невозрастанием) частот (а), а Є А. После анализа очередной буквы xt+\ частота этой буквы vt+1{xt+i) увеличивается на 1, а частоты остальных букв остаются прежними. Более формально:
t+i, л f р (а) + 1 если ж +1 = а v (а) = I Vі(а), если а ф xt+i.
(Первоначальный порядок ТУ0(а),а Є А, задается произвольно, ф затем буквы упорядочиваются в соответствии с частотами vt+1).
Обозначим через Iі (а) номер буквы а Є А после обработки элементов выборки Х\, ... ,xt.
При применении описываемого теста множество всех номеров {1,2,..., S} заранее, до анализа выборки, разбивается на два непересекающихся подмножества Лі = {1,2,...,А;}, и = {/: + 1, к + 2,..., S}. Затем по выборке х\,..., хп подсчиты-вается количество номеров Iі (xt), t = 1,2,..., п принадлежа Ш щих подмножеству Aj,j = 1, 2, которое мы обозначим через Vj. При выполнении Щ вероятность того, что Iі(xt) принадлежит множеству Aj, пропорциональна количеству его элементов, т.е. равна \Aj\/S. Затем по критерию хи-квадрат (х2) проверяется гипотеза Щ:
Р{ )€ } = Л,-/5, (3)
против альтернативной гипотезы Щ = - Щ.
Пример. Пусть А = {1, 2, 3,4}, первоначальный порядок {1,2,3,4}, к = 2 и дана выборка 1,4,2,1,4,5. Рассмотрим состав множества А\ и частоту v\ после обработки каждого символа выборки (данные приведены в таблице). Далее подсчитываем величину ,( -2 (6- -3)2_2 3 3 3 и сравниваем с табличным значением распределения хи-квадрат (известно, что х2 асимптотически приближается к распределению хи-квадрат с одной степенью свободы). Делаем вывод, что данную последовательность можно считать случайной. Отметим, что для простоты была рассмотрена выборка объёмом 6, в то время, как рекомендуемый объём должен быть равен bS/k. В таблице показано, как изменяются частоты и множество А\ после обработки каждого элемента выборки. Так, например, после обработки пятого элемента выборки частота попадания в А\ — {1,4} была равна двум.
Элемент выборки v\ Аг v\l) v\2) i/ (3) i/ (4)
1 1 {1,2} 1 0 0 0
4 1 {Ml 1 0 0 1
2 1 {1,2} 1 1 0 1
1 2 {1,2} 2 1 0 1
4 2 {1,4} 2 1 0 2
3 2 { 1,4} 2 1 1 2
В диссертационной работе описаны структуры данных, при использовании которых число операций, необходимое для тестирования выборки размера п, не превосходит 0(nlog2n). Для эффективной реализации статистических тестов использовались измененные структуры хеш-таблицы и бинарного дерева поиска.
Один из разделов первой главы посвящен статистическим тестам основанным на алгоритмах сжатия. Необходимо отметить, что идея проверки на случайность с помощью алгоритмов сжатия тесно связана с определением случайности и сложности. Например, А.Н. Колмогоров предложил измерять случайность последовательности неформально как длину программы, которая может воспроизвести эту последовательность. Таким образом, случайность (или Колмогоровская сложность) конечной последовательности это тоже самое, что и кратчайшая её запись. Известно, что Колмогоровская сложность невычислима и следовательно не может непосредственно применяться для тестирования на случайность. С другой стороны, любой алгоритм неискажающего сжатия текстов может рассматриваться, как метод, оценивающий сверху Колмогоровскую сложность. Действительно, если рассмотреть бинарное слово х, некоторый метод сжатия ф и ф(х) код слова х то ясно, что \ф{х)\ не меньше Колмогоровской сложности слова х. Поэтому идея использования методов сжатия для тестирования случайных последовательностей вполне обоснована.
Пусть А конечный алфавит. Через Ап обозначим множество всех слов длины п из букв, где п целое число. По определению, A U Li Ап и А°° это множество всех бесконечных слов х\, ж2,..., хп из букв алфавита А.
Определение 1. Методом сжатия данных (или кодом) ср называется множество отображений срп, таких что срп : Ап —» {0,1} , п = 1, 2,... для пары различных слов ж, у Є Ап -рп{х) ф
Неформально, это означает, что код (/? может быть применен для сжатия сообщения произвольной длины п п 0 из букв алфавита А и сообщение может быть разархивировано (декодировано), если метод сжатия известен.
Теперь кратко опишем новый статистический тест, который может быть основан на любом коде (р. Пусть п некоторое целое положительное число и HQ гипотеза о том, что все слова из алфавита Ап равномерно распределены, то есть р(и) = \А\ п для произвольного и Є А71 (здесь и далее через ж обозначим длину, если х слово, и число элементов, если х множество). Пусть требуемый уровень значимости равен 1-а (или ошибка первого рода равна а), а 0. Основная идея теста проста и естественна: хорошо сжимаемое слово должно быть признано неслучайным и гипотеза Но должна быть отвергнута. В работе показано, что можно определить критическое значение для предлагаемого теста:
a = nlogA-log(l/cO-l, (4)
здесь и далее log х = log2 х.
Вторая глава диссертации посвящена тестированию генераторов (псевдо)случайных чисел, которые используются на практике. Случайные числа широко применяются в численных методах, имитационном моделировании и полученные результаты могут существенно зависеть от "качества" используемого генератора. Поэтому, прежде чем использовать какой либо датчик случайных чисел, исследователь должен проверить его с помощью всевозможных статистических тестов.
В криптографии статистическая проверка генераторов также является одной из актуальных задач. В частности, для этих целей Институтом стандартов и технологий США (NIST) был рекомендован ряд статистических тестов. Группа специалистов NIST выбрала 16 самых мощных тестов и реализовала их в виде удобной программы. Эта программа находится в свободном доступе и каждый заинтересованный специалист может использовать её, чтобы проверить генератор (псевдо)случайных чисел.
В диссертации проведён сравнительный анализ новых тестов и тестов, рекомендуемых NIST. Для этого использовались линейные конгруэнтные генераторы. С их помощью получают последовательность целых чисел Хп из диапазона от 0 до га — 1, где га- параметр. Линейный конгруэнтный генератор полностью определяется с помощью четырех параметров а, Ь, га, XQ
по формуле
Хп = (aXn_i + Ъ) mod т. (5)
Известно, что младшие знаки порождаемых по формуле(2.1) чисел часто далеки от случайно распределенных, поэтому обычно рекомендуется использовать только старшие знаки в качестве случайных чисел. Следуя этой рекомендации, из порождаемых генератором значений выделялся или "старший бит", или "старший байт" (варианты, обозначаемые в дальнейшем R\ и Rs, соответственно). Точнее, в режиме R\ для четного т старший бит уп вычислялся по формуле
Г 0, если Хп т/2 — 1, і 1, если Хп т/2, а для нечетного - как 0, если Хп т/2 — 1, 1, если Хп т/2, Л, если Хп = (т — 1)/2 ,
где Л - пустое слово.
В режиме . восьмибитовое слово уп "извлекается" из Хп по формуле
Ґ [ 256 Хп/т J, если Хп т , Уп = і
I Л, если Хп т .
где т = 256 [m/256j, а целое число _ 256 Хп/т J записано как восьмибитовое слово.
Было показано, что новые тесты существенно лучше находят отклонения от случайности. В таблице 1 приведены результаты тестирования порядковым тестом и тестами NIST, линейного конгруэнтного генератора RANDU. Каждый метод применялся к тестированию ста выборок и подсчитывались величины Qa, равные, по определению, количеству случаев, когда значение критерия превышало квантиль порядка а распределения этого критерия. (Так, для порядкового теста подсчитывалось количество случаев, когда значение х2 в (1.5) превышало квантиль порядка а распределения %2 с одной степенью свободы). В тесте 1 и тесте 2 использовались выборки 105 и 106 бит соответственно. Из таблицы видно, что порядковый тест находит отклонения от случайности существенно лучше (все параметры тестов приведены в таблице).
Таблица 1: сравнение мощности тестов.
Методы Qo.oi Параметры
тест 1 тест 2 тест 1 тест 2
Порядковый 76 100 s = 18, r=2, Ai = 2000
Frequency 1 2 Block Frequency 2 0 M=10000 M=20000
Cumulative Sums 1 1 Runs 2 1 Longest Run of Ones 1 0 Rank 1 0 Discrete Fourier Transform 0 1 Nonperiodic Template Matchings - 2 m=10
Overlapping Template Matchings - 2 m=10
Universal Statistical - 1 L=7, Q=1280
Approximate Entropy 2 7 m=ll m=14
Random Excursions 0 2 Random Excursions Variant 0 2 Serial 2 2 m=13 m=8
Lempel -Ziv Complexity 3 1 Linear Complexity 2 3 M=5000 M=2500
Например, один из рекомендованных NIST тестов был DFT (Discrete Fourier Transform). Алгоритм этого теста изначально построен так, что позволяет находить отклонение от случайности в случае линейных конгруэнтных генераторов, но даже этот тест находит отклонения от случайности хуже чем порядковый тест. Во втором тесте DFT отклонил гипотезу #о только в одном случае из ста, в то время как порядковый забраковал все 100 выборок. Таким образом, мы видим, что мощность нового теста существенно выше чем у тестов, предлагаемых NIST.
В главе 2 также приведены результаты тестирования известных генераторов псевдослучайных чисел. Рассмотрены различные классы генераторов и даны практические указания к применению: линейные конгруэнтные генераторы, мультипликативные генераторы (MRG), инверсионные генераторы (ICG), а также известные генераторы RC4, SEAL, ISAAK, VMPC, RC5, TEA, SNOW, Henkos, MT19937, TT800, A5.
В третьей главе описывается новая статистическая атака на блоковые шифры.
Блоковые шифры с секретным ключом находят самое широкое применение в системах защиты передаваемой и хранимой информации и некоторые исследователи из-за этого называют их "рабочей лошадью" криптографии. Такое широкое практическое применение делает актуальными как задачи построения надежных блоковых шифров, так и поиск эффективных крип-тоаналитических атак на эти шифры (т.е. методов определения секретного ключа шифра на основе экспериментов с зашифрованными сообщениями). Исследования в этих областях ведутся параллельно и часто одними и теми же исследователями и, как правило, изобретение новой атаки приводит к появлению шифров, к ней устойчивых. Отметим сразу, что для криптографии представляют интерес атаки, которые менее трудоемки, чем метод "прямого" перебора ключей. Например, если некоторая атака требует перебора 2200 ключей вместо, скажем, 2250, требуемых для полного перебора, то и такая атака представляет интерес для криптологии. Обзор современных блоковых шифров, методов их построения и анализа, а также различных типов атак, может быть найден во многих статьях и монографиях, среди которых мы отметим работы Б. Шнайера (В. Schneier), А. Бирюкова, Р. Кнудсена (R. Knudsen), в которых описаны десятки современных шифров и атак. Об актуальности проблемы свидетельствует и наличие многочисленных национальных и международных программ и конкурсов, направленных на построение надежных блоковых шифров, проводимых в настоящее время в США, странах Европейского сообщества, Японии, Корее.
Большинство блоковых шифров могут быть описаны как функция, определенная на множестве всех двоичных слов длины (I + к) и принимающая значения в множестве двоичных слов длины /, где I - длина шифруемого слова (или блока) и длина зашифрованного слова, а к - длина (секретного) ключа. В современных шифрах длина блока обычно 128 или 64 бита, а длина ключа у разных шифров (и разных режимов использования одного шифра) принимает значения от нескольких десятков бит до нескольких тысяч. Например, у шифра AES, победителя проводимого в 1999-2001 г. в США конкурса на блоковый шифр 21-ого века, длина блока I равна 128 бит, а длина ключа может принимать три значения -128, 196 и 256 бит. У других популярных шифров RC5 и RC6, предложенных Р.Ривестом (R. Rivest) длина блока может быть 32, 64 или 128 бит, а длина ключа в разных вариантах принимает значения от 64 до нескольких тысяч бит. Стоит отметить, что RC5 и RC6 имеют очень простое описание и, по-видимому поэтому, являются одними из самых популярных объектов криптоанализа в последние годы. В ра ботах Б. Шнайера (В. Schneier), Р. Кнудсена (R. Knudsen), Т. Шимояма (T.Shimoyama) и др., описаны результаты криптоанализа шифров RC5 и RC6 и делается вывод об их высокой устойчивости ко всем описанным в литературе атакам.
Процесс шифрования во многих, если не во всех, современных блоковых шифрах разбивается на последовательность сравнительно простых этапов, часто называемых раундами. В ходе каждого нового раунда проводится шифрование данных, полученных на предыдущем этапе с так называемым ключом раунда. В RC5, RG6 и многих других шифрах количество раундов является параметром и часто криптоаналитики исследуют "стойкость" шифров как функцию числа раундов. Одна из целей такого анализа - нахождение числа раундов, гарантирующих высокую надежность шифра.
В данной работе описывается новая атака на блоковые шифры данного типа, которая была названа общестатистической, и в качестве примера исследуется возможность ее применения для криптоанализа шифра RC5. Приведенные экспериментальные данные позволяют сделать вывод о том, что эта атака может быть применена и что для некоторых режимов этого шифра ее трудоемкость может быть существенно меньше, чем у прямого перебора. Здесь стоит отметить, что хотя предлагаемая нами атака ранее не описывалась и является новой, но исследование статистических свойств блоковых шифров уже использовалось в криптоанализе.
Описываемый нами метод относится к классу атак с выбираемым шифруемым текстом (chosen ciphertexts attack). При ре ализации этой атаки криптоаналитик может подавать на вход шифра любой текст, анализировать полученное зашифрованное сообщение, затем, базируясь на результатах этого анализа, подавать новое сообщение и т.д. Цель атаки - нахождение (секретного) ключа, причем при этом предполагается, что криптоаналитик знает все характеристики шифра, кроме этого ключа. Такие атаки представляют практический интерес и считается, что современные блоковые шифры должны быть стойки к ним.
Рассмотрим шифры, в которых кодируемое битовое (двоичное) сообщение является блоком длины 1,1 1, и шифруется при помощи ключа К, являющегося словом из \К\ случайно выбранных бит. (Здесь и ниже \и\ длина и, если и слово, и мощность к, если и множество.)
У большинства современных шифров существует этап инициализации, в ходе которого начальный ключ К преобразуется в так называемые ключи раундов к\, &2, • •, К, которые используются последовательно для шифрования на разных этапах. Схематично процесс шифрования для RC5, RC6 и многих других шифров можно представить как цепочку "элементарных" этапов (или раундов) шифрования.
х\ — Encri(xQ, ki): Х2 = Епсг2(хі, ),..., xr = Encrr(xr-i, fcr), (6) где XQ исходное l— битовое слово, которое необходимо зашифровать, ЕПСГІ— операция (функция) шифрования на г— ом этапе, кі - ключ, используемый на г— ом этапе, Х{— I— битовое слово, являющееся "выходом" г—ого этапа и "входом" (г + 1)— ого, и, наконец, хт— результат шифрования. В разных шифрах эта процедура осуществляется по разному, причем это зависит не только от шифра, но и от значений длин блока и ключа (к, I) и числа раундов (г), которые для многих шифров являются параметрами. Например, для шифра RC5 длина блока может принимать значения 32, 64 или 128 бит, количество раундов может быть любым целым числом, а длина ключа должна быть кратна 8 и может принимать любое значение, начиная с 8 бит. Отметим, что значения I = 64, г = 12, к = 128 рекомендованы разработчиками и широко исследованы. Часто рассматриваются и схемы, в которых длина ключа К равна суммарной длине ключей раундов (if = YA=I 1 I) ЧТ0 ДЛЯ МНОГИХ шифров эквивалентно их независимому выбору. Дешифрование проводится по схеме, обратной к шифрованию:
xT-i = Decrr(xr, kr),xr-2 = Decrr-i(xr-i, &v_i),..., XQ = Decri(xi, k\)
(?) где используются те же ключи раундов, а операции Decri являются обратыми к этапам кодирования Епсг\.
Оценим трудоемкость атаки полного перебора. Для ее проведения достаточно иметь одно зашифрованное сообщение (двоичное слово), длина которого не меньше длины ключа. Затем необходимо пытаться дешифровать это зашифрованное сообщение, последовательно перебирая все возможные ключи в каком-либо порядке и сравнивая полученный результат с исходным, незашифрованным, текстом; совпадение означает, что неизвестный ключ найден. Обычно предполагается, что ключ принимает любое значение из множества всех двоичных слов длины \К\ с вероятностью 2 \к\ поэтому среднее значение числа перебира емых ключей равно (\К\ + 1)/2.
К современным блоковым шифрам предъявляется много различных требований, одно из которых можно сформулировать следующим образом: любое зашифрованное сообщение должно быть "похоже" на реализацию бернуллиевского процесса, в которой вероятность порождения нуля и единицы равна 1/2. (В дальнейшем для краткости мы будем называть такие последовательности случайными). В частности, все шифры, принимавшие участие в. конкурсе на шифр 21-ого века, проводившемся в США в 1999- 2001 г.г. проверялись на выполнение этого условия. Мы не будем останавливаться на логическом анализе этого требования (которое, в некотором смысле, вообще невыполнимо), а приведем пример, поясняющий его смысл. Для этого мы определим /-битовое слово а{ как двоичную запись числа і, г = 0,1,2,...,2г — 1 , где, как и ранее, / - длина блока рассматриваемого шифра (т.е. 0 -состоит из /—битовой цепочки двоичных нулей, а\ из (/ — 1) нуля и единицы, «2- из (I — 2) нулей, после которых идет последовательность 10 и т.д.) От современного блокового шифра требуется, чтобы при любом значении ключа последовательность /-битовых слов Епсг(ао)Епсг(аі)Епсг(а2). •.,
рассматриваемая как двоичная последовательность, была статистически неотличима от случайной (здесь Encr(ai) означает зашифрованное слово ai .). Это требование, в частности, позволяет использовать блоковые шифры как генераторы псевдослучайных чисел.
Перейдем теперь к описанию предлагаемой статистической атаки на блоковые шифры, у которых кодирование и декодирование разбивается на последовательность раундов (3.1) и (3.2), начав с очень неформального предварительного рассмотрения. При этом мы будем использовать совершенно нестрогие термины "более" и "менее" случайные последовательности, понимая под этим, что некоторая последовательность более случайна, чем другая, если отклонения от случайности у первой достоверно выявляются при большей длине, чем у второй. (При этом предполагается, что используется некоторый статистический тест при одном и том же уровне значимости. Другое "определение" более случайной последовательности - величина статистики критерия для этой последовательности меньше, чем для менее случайной). Предположим, что на вход шифра, ключ которого неизвестен, подаются последовательно слова ceoceic • • Очевидно, эта последовательность "очень" неслучайна. Последовательность Encri(o o, ki)Encri(ai, ki)Encri(a2, к{)..., после первого раунда шифрования, которую мы обозначим через PQPI ..., "более" случайна, чем исходная; получаемая после второго раунда последовательность Encr2((3o, k2)Encr2(Pi, k2)Encr2((32, к2)..., еще более случайна и т.д. Наконец, полученная после последнего раунда последовательность UJQUIUJ2 ... более случайна, чем предыдущая. Это неформальное утверждение подтверждается экспериментально в приведенных ниже данных для шифра RC5 и в довольно многочисленных работах практически для всех известных шифров рассматриваемого типа; объяснение этого факта довольно очевидно - шифрование на каждом раунде приводит к "перемешиванию" и, тем самым, повышает "случайность" шифруемых данных. Отметим и очевидное следствие - при дешифровании последовательности UJQUJ\IJJ2 ... ПО схеме (3.2) случайность получаемых данных последовательно уменьшается. Это, конечно, справедливо только в том случае, когда при дешифровании используются "истинные" ключи раундов. Если же при "дешифровании" скажем на первом раунде хг-\ = Decrr(xr,kr) (соответствующем последнему раунду при шифровании, см. (3.1),(3.2)) вместо истинного ключа кт используется какое-либо другое слово к той же длины, то эффект преобразования DecrT(xr,k ), будет таков же, как при шифровании - выходная последовательность будет более случайна, чем входная. Это важное для нас наблюдение в общем виде состоит в следующем: при дешифровании на j-ом раунде при использовани "неправильного" ключа Щ (вместо "правильного" ключа kj) случайность выходной последовательности возрастает, тогда как при использовании "правильного" kj - убывает.
При использовании новых статистических тестов (стопка книг порядковый и адаптивный) возникает проблема нехватки вычислительных мощностей. Компьютеры с одним процессором не справляются с этой задачей поскольку, например, для проверки гипотезы До при большом размере алфавита (S велико) необходимо хранить л/S чисел в памяти. У персональных ком пьютеров есть ограничение на оперативную память до 2Гб и этого может не хватить для тестирования стойких криптографических генераторов. Существует также проблема скорости вычислений, поэтому тесты были реализованы с использованием параллельных вычислений. Для реализации тестов на многопроцессорных компьютерах были разработаны структуры данных и алгоритмы их взаимодействия. В Таблице 2 приведены результаты тестирования шифра RC5 на больших выборках, которые показывают, что отклонения от случайности фиксируются до 8 раунда.
Таблица 2: Проверка гипотезы о случайности для различного числа раундов при уровне значимости 0.01. раунд длина количество гипотеза о случайности W ключей отвергнута 5 228 30 30 5.5 229 22 10 6 231 6 6 6.5 232 6 6 7 232 6 5 7.5 2зз 6 5 8 237 3 2
Приведены результаты реализации атаки для шифра RC5 с использованием параллельных вычислений. Для этого был разработан алгоритм атаки для многопроцессорного компьютера и использованы вычислительные мощности Сибирского суперкомпьютерного центра ИВМиГ СО РАН.
Структуры и алгоритмы
В данном разделе опишем структуры данных, которые позволяют эффективно реализовать описанные выше тесты на практике. Для реализации теста RSS (адаптивный хи-квадрат), мы рекомендуем применение структуры хеш-таблицы с прямой адресацией. Эта структура позволяет эффективно хранить данные, не теряя лишней оперативной памяти, что существенно при обработки больших выборок. Опишем данную структуру данных. Алгоритмическая постановка задачи следующая: рассматривается некоторая последовательность положительных чисел жі,..., xn , которая разбивается на две части xi,..., хт и xm+i,. Необходимо запомнить все значения х\,..., хт в некоторое множество В и подсчитать сколько чисел из xm+i,..., хп попадает в В.
Это классическая реализация хеш-таблицы. При выполнении условия М 1.5т количество операций сравнения для каждого выборочного значения в среднем не превосходит 3. Ясно, что такой подход более эффективен чем реализация через деревья, поскольку количество операций сравнения в случае дерева равно log2 п. Опишем алгоритм реализации метода стопка книг. Рассматриваем упрощённый вариант, то есть алфавит А разбивается на два множества. Полагаем, что А это подмножество натуральных чисел А = {0,1, 2,..., iV}, первоначальный порядок обычный, А\ = {0,1,..., к — 1}. Для реализации этого метода используется структура хеш-таблицы в изменённом варианте. Сначала определим структуру D,s,ls,rs , где D - поле данных (иначе говоря, некоторое число), a s:ls, и rs - адреса структур такого типа (указатели на область памяти). Для простоты, все поля адресного типа в названии будут содержать букву 5. Массив адресов Т размера М 1.5т. Определим переменные end, begin указатели на структуры и массив структур В размера k + l (обозначение B[i).ls означает, что мы рассматриваем поле Is структуры В[г\). Если рассматривать отдельно тройки B[i].D, B[i].ls, B[i].rs , то они образуют обычный двухсвязный список, где begin и end указывают на начало и конец соответственно. Массив Т и пары B[i].D,B[i].s образуют обычную хеш-таблицу для хранения чисел (повторим, D поле данных). В качестве хеш-функции берём, как и в предыдущем алгоритме, операцию взятия по модулю М. Таким образом, в начальный момент элементы Т[ъ] указывают на структуры В[г], для любого 0 і к — 1, остальные Т[і] нулевые адреса. Элемент -В[г] (0 і к — 1) имеет вид: D — г, s-нулевой адрес, Is- указатель на В[г — 1] и rs- указатель на B[i +1]. Элементы В[0] ж В[к — 1] имеют аналогичный вид, за исключением того, что Is - пустой указатель для ВЩ и rs - пустой указатель для В [к — 1]. Полагаем, что begin - адрес В[0] и end - адрес В [к — 1]. И наконец, элемент В[к] - пустой элемент и free -его адрес (см. Рисунок). Таким образом, мы имеем хеш-таблицу с непрямой адресацией, внутри которой "встроен" двусвязный список, где begin и end начало и конец списка соответственно.
Этот алгоритм обладает высокой скоростью и существенно быстрей чем в случае использования древовидных структур. Немного поясним основную идею алгоритма. Для того, чтобы эффективно реализовать стопку книг, необходимо эффективно хранить элементы множества В, то есть нужно, чтобы поиск элемента в этом множестве осуществлялся, как можно быст рее (для этого используем хеш-таблицу). Также, необходимо запомнить структуру самой стопки, то есть последовательность в какой числа идут друг за другом (для этого нужен двусвяз-ный список). С помощью списка мы быстро можем удалить последний элемент или поместить произвольный элемент в начало списка.
Далее опишем алгоритм реализации порядкового теста. На практике использовался упрощённый вариант алгоритма (г = 2, см. описание алгоритма пункт 2.1). В качестве начального порядка использовался естественный порядок. Для реализации этого алгоритма нужно использовать дерево поиска и хеш-таблицу. В хеш-таблице храним все пришедшие элементы с их частотами. В дереве поиска храним те элементы, которые содержатся в множестве А\ (пусть Л = к). В начальный момент хеш-таблица пустая, дерево, поиска содержит числа {1,2,.. . ,к}. В дереве поиска используется следующий порядок: для момента времени t считаем х у, если Vі {х) vb{y). Если частоты Vі(х) = Vі{у) равны, то порядок обратный естественному (храним в множестве А\ числа с наименьшими номерами). Поскольку выборочные числа близки к случайным, то поиск по дереву будет осуществляться за 0(log2n) операций (где п -размер выборки). Краткая схема обработки элемента х.
Двуличные процессы и выбор длины блока для тестирования
Существуют двуличные процессы, которые с одной стороны далеки от случайных, но с другой стороны отклонения от случайности могут быть найдены только если длина блока s велика.
Двуличные процессы можно описать следующим образом. Для двуличных процессов, которые генерируют буквы из алфавита {0,1}, предельная энтропия Шеннона (сильно) меньше чем 1 на символ и, с другой стороны, энтропия для блока s-ro порядка hs максимальна (hs равна 1 бит на символ) при подходящем выборе s. Опишем два семейства двуличных процессов Т(к,тт) и Т(&, 7г), где к = 1, 2,..., и 7г Є (0,1) параметры. Процессы Т(к,тг) и Т(к, 7г) это Марковские процессы с памятью равной к, которые генерируют буквы из алфавита {0,1}. Определим их по индукции. Процесс Т(1,7г) задаётся условными вероятностями -Рг(і;7Г) (0/0) = 7г, Рт(1,тг)(0/1) = 1 — тг (очевидно, Рт(і)7Г)(1/0) = 1—7г, Py(i)7r)(l/1) = 7г) и положим, что процесс Т(1,7г) определен -Pf(i,7r)(0/0) = 1 — 7г, іт(і)7Г)(0/1) = 7г. Полагаем, что Т(&, 7г) и T(fc, 7г) определяют T(fc+1, 7Г) и T(fc+1,7г) следующим образом Рт{к+1,ж)(0/0и) = РТ(Й!ТГ)(0/ "),РТ(А;+117Г)(1/0 ) = PT(fci7r)(l/u), PT(fc+i, )(0/lw) = Pf(fc)7r)(0/w),PT(fc+1)7r)(l/lw) - Рг(М(1», и, аналогично, Pf i O/Ou) = Pf{k (0/u),Pf{k+lj7r)(l/0u) = Pf(jfe T)(l/«), +1,.)(0/1 ) = Рты{0/и), Pf{k+l 7r){l/lu) = PT(k,,)(l/u) для всех и Є - (где vu конкатенация слов v и и). Например, (2,.)(0/00) = тг,Ртм(0/01) = 1 - тг,Рт(2)7г)(0/10) = 1 - 7Г, (2,,)(0/11)= 7Г. Следующее утверждение показывает, что двуличные процессы существуют. Теорема 3. Для каждого -к Є (0,1) энтропия Шеннона s-го порядка (hs) процессов Т(&, 7г) и Т(к, 7г) равна 1 биту на символ для s = 0,1,..., к, а предельная энтропия Шенопа (hoo) равна — (7rlog27T + (1 — 7г) log2(l — 7г)). Доказательство теоремы приведено в Приложении к главе, но рассмотрим пример "типичных" последовательностей для про цессов Т(1,7г) и Т(1,7г) для 7г, скажем, 1/5. Это будут следую щие последовательности: 010101101010100101... и 000011111000 111111000 Видно, что каждая из последовательностей содер жит примерно половину 1 и половину 0 (именно поэтому эн тропия Шеннона первого порядка равна 1 биту на символ). С другой стороны, обе последовательности не выглядят как слу чайные, потому что они, очевидно, имеют слишком длинные под слова вида 101010.. или 000..11111... (Другими словами, энтропия Шеннона второго порядка значительно меньше 1 на символ.) Однако, если статистический тест основан на оценке частоты только 0 и 1 , то такой тест не сможет найти отклонения от случайности.
Таким образом, мы вернемся к вопросу о выборе длинны блока для теста и будем учитывать существование двуличных процессов. Казалось бы, что длинну блока необходимо выбирать как можно больше, но это не так. Следующий неформальный анализ может быть полезен для выбора длинны блока.
Случайные числа широко применяются в численных методах, имитационном моделировании, и "качество" полученных результатов может существенно зависеть от "качества" используемого генератора. Поэтому, прежде чем использовать какой либо датчик случайных чисел, исследователь должен проверить его с помощью статистических тестов.
В криптографии проверка статистическая проверка генераторов также является одной из актуальных задач. Для этих целей Институтом стандартов и технологий CIIIA(NIST) был рекомендован ряд статистических тестов. Группа специалистов NIST на основе теоретического анализа и экспериментов выбрала 16 самых мощных тестов и реализовала их в виде пакета программ. Он находится находится в свободном доступе и каждый специалист может "скачать" её с сайта NIST(CM. [35]), что бы проверить интересующий его генератор (псевдо)случайных чисел.
При применении порядкового теста и других, выборка, состоящая из последовательности из нулей и единиц (полученных в режиме R\ или R%) разбивалась на блоки длины s, где s 1 -параметр. Затем каждый блок рассматривался как целое число из диапазона 0,1,..., 2s — 1 чисел и по последовательности этих чисел проверялась гипотеза Щ (см. (1.5)) о равномерном распределении этих чисел (с S = 2s) против альтернативной гипотезы Hi = -ii?o Для сравнения предлагаемых тестов и методов из [35] использовался генератор RANDU (LCG(231, 216 + 3, 0,1)) в режиме R% (описание RANDU дано в [36]). Например из таблицы 2.1 следует, что было проверено сто выборок по 106 и сто по 105 бит, полученных с помощью генератора RANDU в режиме R%. При тестировании по порядковому методу последовательность разбивалась на подслова длины 18 бит (s = 18), а множество всех номеров {1,2,..., S} разбивалось на две непересекающихся части А\ = {1,..., 5120}, А2 = {5121,..., 2s}, (см. описание метода).
Анализ генераторов псевдослучайных чисел, использующихся на практике
В этом разделе описываются результаты применения порядкового метода к тестированию генераторов, приведенных в обзоре [49]. Важно отметить, что многие из них практически используются в виде "встроенных" генераторов в реальных компиляторах (С, Pascal, Fortran, см. [49]) и поэтому используются многими специалистами для проведения расчётов.
Сначала все генераторы исследовались в режиме R$. При тестировании использовалось 50 выборок по 1 500 000 байт для каждого генератора (кроме генератора RANDU, рассмотренного в предыдущем разделе). Анализ этой таблицы показывает, что все генераторы, кроме трех (APPLE, Borosh-Kmith, Anderson), явно бракуются порядковым тестом. Это легко показать с использованием "обычного" статистического анализа. Например, для всех, кроме трех указанных, генераторов количество случаев, когда вычисленная по выборке величина х2 (95%ный квантиль) достоверно превышают ожидаемое среднее значение (2.5 РІЗ 50).
Генераторы APPLE, Borosh-Knuth, Anderson, которые лучше всех прошли тест были проверены повторно. В повторном тесте использовалось 50 выборок по 4 000 000 байт. После второго теста "не забракованным" остался только один генератор Anderson. Отметим, что в режиме R\ все генераторы успешно прошли тесты. Нам кажется, что полученные данные, во-первых, позволяют сравнить "качество" приведенных генераторов, во-вторых, дают представление о предельных длинах последовательностей, при превышении которых они явно не случайны, и, наконец, показывают, что при необходимости использования длинных последовательностей псевдослучайных чисел целесообразно использовать порядковый метод для предварительного тестирования данных генератора.
Как было показано, в этом режиме линейные конгруэнтные генераторы показывают самые лучшие результаты, но необходимо учитывать, что это сильно скажется на скорости генератора. Ясно, например, что режим R24 быстрее более чем в 24 раза, поэтому необходимо проверить различные режимы. В Таблице 2.7 приведены параметры тестов, которыми проверялись генераторы. Например, тест 2 использует выборку объёма 20 224 при размере множества \Ai\ — 225. Из результатов тестирования видно, что можно рекомендовать линейные конгруэнтные генераторы если используется модуль больше чем 260. При чем, можно сделать вывод, что режим R24 не хуже чем режим R8. Тесты 1-2 повторялись по 100 раз на независимых выборках. Тесты 3-4, в виду своей трудоёмкости, выполнялись по 20 раз.
При подходящих параметрах MRG имеет период тк — 1. Список таких параметров можно найти в [51],[52] и [53]. В таблице приведены результаты тестирования ряда MRG, которые были рекомендованы к применению в [53]. Генераторы были проверены в режиме R24. Все генераторы кроме одного прошли все тесты. Таким образом, MRG можно рекомендовать для практического использования если количество слагаемых больше чем два. Можно заметить некоторую закономерность: если у любого конгруэнтного reHepaTopa(LCG или MRG) период равен около 2ті, то новые статистические тесты бракуют его если брать размер алфавита сравнимый с л/п, то есть на выборке 0( /п).
Необходимо отметить, что несмотря на свои неплохие статистические свойства конгруэнтные генераторы не рекомендуют применять в криптографии. Последовательности сгенерирова ны такими генераторами к сожалению предсказуемы. Например, для LCG, если модуль т известен, то параметры а и Ь можно подобрать по двум соседним числам такой последовательности. В 1960 году Марсалия(см. [56]) первым поставил под вопрос о "случайном поведении" последовательностей, полученных с помощью LCG. В последствии были дискредитированы мультипликативные конгруэнтные генераторы (см. [55]).
Исследования устойчивости шифра RC5
Мы начнем описание с экспериментального анализа "степени случайности" зашифрованных сообщений в зависимости от числа раундов, точнее, полу раундов, как упоминалось выше. (Используя выражения типа "3,5" раунда вместо, скажем, 7-ой полу раунд. К сожалению, эта терминология является общепринятой в работах, касающихся RC5, RC6 и ряда других шифров).
Первый вопрос, который мы исследовали экспериментально1, касался возможности различения зашифрованных при помощи RC5 "простых", явно не случайных, последовательностей при разном числе (полу)раундов. Для этого мы использовали в качестве исходной "неслучайной" вышеупомянутую последовательность oii,i = 0,1,..., где а.{ - запись числа і в двоичной системе счисления, под которую отводится 64 бита. (Напомним, что мы рассматриваем RC5 с длиной шифруемого блока 64 бита.) Во всех случаях указанная последовательность зашифровывалась при помощи указанного шифра с заданным количеством полу раундов и по полученной последовательности проверялась гипотеза HQ О ТОМ ЧТО двоичная последовательность порождается бернуллиевским источником с равными вероятностями нуля и единицы, против альтернативной гипотезы Hi, являющейся отрицанием Щ. В дальнейшем, для того чтобы избегать длинных повторов, мы будем называть эту задачу "гипотезой о случайности".
Понятно, что выбор статистического теста для проверки гипотез играет важную роль в описываемой атаке, поэтому мы кратко остановимся на этом вопросе. В настоящее время имеется довольно много работ, посвященных построению и исследованию тестов для проверки гипотезы о случайности, что, по-видимому, объясняется важностью этой задачи для криптографии, численных методов и других многочисленных приложений. Так, Институт стандартов и технологий США (NIST) недавно провел исследование известных тестов для проверки гипотезы о случайности и рекомендовал 16 методов для практического применения в криптографии, см. [23]. В [68] показано, что недавно описанные в [34, 25] тесты превосходят методы из [23], что подтверждалось и нашими предварительными расчетами, связанными с RC5. Поэтому мы использовали для анализа тесты "стопка книг" и "адаптивный хи-квадрат" из [34, 25], соответственно. Оказалось, что мощность теста "стопка книг", в среднем выше, чем у адаптивного теста хи-квадрат, но скорость вычислений у последнего значительно выше и он более удобен для реализации на многопроцессорном компьютере. Поэтому предпочтение было отдано этому тесту и все приводимые ниже данные получены для него.
Для большего числа раундов мы проводили вычисления с меньшим числом вариантов (или повторений), т.к. в этом случае требуются последовательности большей длины и, соответственно, большее время вычислений. Снова проверялась гипотеза о случайности (Щ) для той же зашифрованной последовательности o oai...a t-i с разными (случайно выбранными) ключами и разным числом раундов; результаты приведены в таблице 3.2. Мы видим, что зашифрованная последовательность aoai...at-i довольно надежно различается от случайной до 8 раунда.
К сожалению, проведение расчетов по этой схеме для большего числа раундов оказалось практически невозможным из-за резкого увеличения времени вычислений. (Действительно, при этой схеме для каждого полу раунда проводятся вычисления для 330 файлов одной длины - 3 серии, 11 ключей полу раунда и 100 подпоследовательностей.) В следующей таблице 3.4 приведены результаты для 4 и 4,5 раундов, в которых использовалась последовательность (3.5) длиной 227 байт. Она зашифровывалась с случайно выбранным ключом а затем расшифровывалась на полраунда один раз с правильным ключом полу раунда, и 5 раз с неправильными, случайно выбранными. Эти вычисления повторялись 10 раз; все остальные условия были те же, что и в ранее описанных экспериментах. Мы видим, что при 4 раундах шифрования расшифрованные с правильным ключом последовательности признаны неслучайными в 10 случаях из 10, тогда как "расшифрованные" с неправильным ключом - только в 4 или 3 случаях из 10. Аналогично, при 4,5 раундах расшифрованные с правильным ключом последовательности признаны неслучайными в 5 случаях из 10, а все, "расшифрованные" с неправильным ключом, признаны случайными.
Мы видим, что данные, приведенные в таблицах 1-4 подтверждают предположения, выполнение которых необходимо для принципиальной возможности проведения предлагаемой атаки: во-первых, "случайность" зашифрованной последовательности возрастает при увеличении числа полу раундов и, во-вторых, "случайность" последовательности, "расшифрованной" с неправильным ключом полу раунда, больше, чем у расшифрованной с правильным ключом.
Таким образом, приведенные нами данные экспериментов показывают, что условия, необходимые для проведения общей статистической атаки на шифр RC5 выполняются. Это, в свою очередь, позволяет сделать вывод о принципиальной возможности проведения этой атаки на шифр RC5 в том случае, когда он используется в режимах, использующих не более 8 раундов. Кроме того, полученные данные позволяют также предположить, что статистическая атака может быть применима и к другим шифрам рассматриваемого вида.
Схема реализации тестов на МВС-1000 При использовании новых статистических тестов (стопка книг порядковый и адаптивный) возникает проблема нехватки вычислительной мощности. Компьютеры с одним процессором не справляются с этой задаче, поскольку например, для проверки гипотезы Щ при большом размере алфавита (5 велико) необходимо хранить y/S чисел в памяти. У персональных компьютеров есть ограничение на оперативную память до 2Гб и этого может не хватить для тестирования стойких криптографических генераторов. Существует нехватка не только оперативной памяти, но и скорости вычислений, поэтому тесты были реализованы с использованием параллельных вычислений. Опишем схему реализации теста адаптивный хи-квадрат на суперкомпьютере.
Таким образом, имеем М вычислительных модулей, которые могут производить вычисления независимо друг от друга и соединены между собой линией связи, то есть данные могут быть переданы от одного модуля другому. Необходимо проверить генератор G с помощью теста адаптивный хи-квадрат (сокращённо RSS). Генератор G может быть двух типов. Первый тип, это генераторы который генерируют последовательность хі,...,хп в одном направлении, то есть чтобы узнать хп необходимо узнать все предыдущие значения (например, RC4 именно такой генератор). Примером генератора второго типа может служить SEAL или любой генератор основанный на блоковом шифре.
Рассмотрим сначала генераторы первого типа. Так как генерация проиходит в одном направлении, то выборку х\, х ..., хп невозможно вычислить быстрее чем это сделает один вычислительный модуль, то есть её нельзя вычислить параллельно. Поэтому на каждом вычислительном модуле генерируется вся выборка. Модуль с номером г обрабатывает следующим её образом: из всех выборочных значений обрабатываем только те Xj, для которых выполнено:
