автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Построение новых статистических тестов и их применение в криптографии

На правах рукописи

Виктор Александрович Монарев

Построение новых статистических тестов и их применение в криптографии

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 2005

Работа выполнена в Институте вычислительных технологий СО РАН

Научный руководитель дтн, профессор Рябко Борис Яковлевич

Официальные оппоненты: д ф.-м н., профессор Дьячков Аркадий Георгиевич.

к ф.-м.н., доцент Соловьева Фаина Ивановна

Ведущая организация Институт проблем передачи информации РАН

Защита состоится 28.12.2005 г. в 16 00 на заседании диссертационного совета Д 003 046.01 при Институте вычислительных технологий СО РАН по адресу:

пр. академика М.А. Лаврентьева, дом 6, 630090, Новосибирск, Россия Телефон-(383) 3306150, Факс (383) 3306342 E-mail- ict@ict.nsc.ru

С диссертацией можно ознакомиться в читальном зале вычислительной математики и информатики отделения ГПНТБ СО РАН

Автореферат разослан 20 ноября 2005 года.

Ученый секретарь диссертационного совета д.ф.-м н., профессор

Чубаров Л.Б.

гооб-4 1146974

Общая характеристика работы

Актуальность темы

Статистические тесты находят применение в самых различных областях, включая анализ генераторов случайных и псевдослучайных чисел, и ряд задач криптографии. Поэтому задача построения новых эффективных статистических тестов и разработка алгоритмов эффективной реализации находится в центре внимания многих исследователей.

В настоящее время используется много методов (или тестов) для проверки генераторов случайных и псевдослучайных чисел. Все эти методы рассматриваются в рамках математической статистики Точная постановка задачи следующая: проверяется гипотеза Не, о том, что источник порождает символы из алфавита {0,1} независимо и вероятности этих символов равны 1/2 против альтернативной гипотезы Н\, что последовательность порождается стационарным и эргодическим источником и Но не выполняется. Для краткости, в дальнейшем, будем называть эту задачу тестом (или проверкой) на случайность.

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

Некоторые проблемы современной криптографии также связаны с тестами на случайность. Прежде всего это относится к так называемым блоковым и потоковым шифрам. Приведем их краткое описание. Блоковые шифры обычно используют некоторое преобразования к блокам данных фиксированной длины (обычно 64 бита или 128 бит) К современным блоковым шифрам предъявляется обязательное требование: они в некотором режиме использования (описанном ниже) должны работать, как "хороший" генератор псевдослучайных чисел. Для проверки же "качества" построенных шифров в этом режиме используют статистические тесты. Если же это условие не выполняется, то такой шифр не рекомендуют к применению (в частности, это требование предъявлялось в проводимом в США в 1999-2000 г. конкурсе на "блоковый шифр 21-го века").

Задача построения статистических тестов для генераторов случайных и псевдослучайных чисел привлекает внимание многих исследователей Об актуальности это проблемы, в частности, говорит то, что в 2000г. Национальный

институт стандартов и технологий США (NIST) провел специальное исследования и опубликовал 16 статистических тестов, которые рекомендованы для применения в криптографических приложениях. Основные результаты в этой области принадлежат У. Маурэру (U.Maurer), Д. Кнуту (D.Knuth), Б. Шнай-еру (В. Shneier), Р.Ривесту (R. Rivest) и ряду других исследователей Однако, несмотря на многочисленные работы, задача построения эффективных тестов далека от своего разрешения. Цель работы:

1. Построение новых эффективных статистических тестов и разработка алгоритмов их реализации (в т.ч. для многопроцессорных компьютеров).

2. Применение построенных тестов к экспериментальному анализу известных генераторов псевдослучайных чисел.

3. Применение разработанных методов к задаче анализа стойкости блоковых шифров.

Научная новизна результатов:

1. Разработаны новые эффективные статистические тесты: "порядковый" и тесты, основанные на алгоритмах сжатия. Построены новые алгоритмы и структуры данных для эффективной реализации статистических тестов

2. Экспериментально исследован широкий ряд практически применяемых генераторов псевдослучайных чисел при помощи новых тестов.

3. Разработана и экспериментально исследована новая статистическая атака на блоковые шифры.

Практическая ценность результатов:

1. Разработанные методы тестирования позволяют эффективно проверять генераторы случайных и псевдослучайных чисел.

2. Экспериментально исследован ряд известных генераторов псевдослучайных чисел и даны рекомендации по их применению.

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

Внедрение результатов работы: Работа по теме диссертации была выполнена в рамках проектов: Российского фонда фундаментальных исследований (грант 03-01-00495) и INTAS (Grant 00-738). Результаты используются при чтении курса "Современные методы защиты информации", а также при выполнении дипломных проектов в Новосибирском государственном университете и Сибирском государственном университете телекоммуникаций и информатики.

Апробация работ и публикации: Основные результаты работы докладывались и обсуждались на следующих российских и международных конференциях: International Symposium on Information Theory (Chicago, 2004), Tpe-

тья общероссийская конференция "Математика и безопасность информационных технологий" (Москва, 2004), а также на семинарах Института вычислительных технологий СО РАН (Новосибирск).

По теме диссертации опубликовано: 1 электронная публикация. 5 печатных работ, том числе 3 статьи.

Основные положения, выносимые на защиту:

1 Разработаны методы эффективного тестирования генераторов случайных и псевдослучайных чисел.

2. Показано, что мощность новых тестов выше чем у ранее известных, включая методы, рекомендуемые NIST.

3. Разработаны алгоритмы и структуры данных для эффективной реализации новых статистических критериев.

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

Структура и объём работы Диссертация состоит из введения, трёх глав, заключения и списка литературы. Диссертация содержит 111 страниц машинописного текста, 1 рисунок и 20 таблиц. Список литературы включает 72 наименования.

Краткое содержание работы

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

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

Один из самых известных статистических тестов для проверки гипотезы о том, что для некоторого источника, который порождает буквы из алфавита А = {oj,..., as}, S > 1, выполнена гипотеза:

H0-.p(a1)=p01,....p(as)=p°s, (1)

против альтернативной гипотезы Н\, являющейся отрицанием Но, это критерий хи-квадрат При применении критерия хи-квадрат подсчитывается значе-

ние

где - частота символа а, в выборке 11,.. ,хп. Известно, что г2 асимптотически приближается с распределению хи-квадрат с к — 1 степенью свободы.

Задача тестирования (псевдо)случайных последовательностей чисел формулируется следующим образом Пусть некоторый источник, который порождает буквы из алфавита А = {ах,.. ,Ов},5> 1, необходимо по выборке х1;.. , х, порождаемой источником, проверить гипотезу

против альтернативной гипотезы Н1, что источник является стационарным, эргодическим и Но не выполняется. Ясно, что это частный случай и критерий хи-квадрат здесь применим.

Кратко опишем вариант основного алгоритма тестирования При тестировании в каждый момент времени I буквы алфавита А упорядочены (и занумерованы) в соответствии с убыванием (невозрастанием) частот рг{а),а € А. После анализа очередной буквы Xt+\ частота этой буквы увеличива-

ется па 1, а частоты остальных букв остаются прежними. Более формально:

(Первоначальный порядок i/°(a), о. G Л, задается произвольно, затем буквы упорядочиваются в соответствии с частотами г/'41.) Обозначим через 1'(а) номер буквы а € А после обработки элементов выборки xi,... ,xt.

При применении описываемого теста множество всех номеров {1,2, , 5} заранее, до анализа выборки, разбивается на два непересекающихся подмножества А\ = {1,2,..., и Ai — {к+1, k-i-2,..., 5}. Затем по выборке Xi, ,хп подсчитывается количество номеров f{xt), t = 1,2,... ,п принадлежащих подмножеству j4j,j = 1,2, которое мы обозначим через fr При выполнении На вероятность того, что if(x4) принадлежит множеству А3, пропорциональна количеству его элементов, т.е. равна \A,\jS. Затем по критерию хи-квадрат (х2) проверяется гипотеза

против альтернативной гипотезы Щ — -'Щ.

Пример. Пусть А = {1,2,3,4}, первоначальный порядок {1,2,3,4}, к = 2 и дана выборка 1,4,2,1,4,5 Рассмотрим состав множества А\ и частоту У\

Яо : p(ai) = ... = p(as) = 1/5

(2)

если xt+i — а, если а ф xt+i .

Я{?(*0 6 А,} = \A,\/S,

(3)

после обработки каждого символа выборки (данные приведены в таблице). Далее подсчитываем величину х2:

2 (^-З)2 (6 — — З)2 _ 2 1 ~ 3 + 3 ~3'

и сравниваем с табличным значением распределения хи-квадраг (известно, что х2 асимптотически приближается к распределению хи-квадрат с одной степенью свободы). Делаем вывод, что данную последовательность можно считать случайной. Отметим, что для простоты была рассмотрена выборка объёмом 6, в то время, как рекомендуемый объём должен быть равен 5.5¡к. В таблице показано, как изменяются частоты и множество Л1 после обработки каждого элемента выборки. Так, например, после обработки пятого элемента выборки частота попадания в А1 = {1,4} была равна двум.

Элемент выборки Ау "41) р\2) ^(3)

1 1 {1,2} 1 0 0 0

4 1 {М} 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(п1ой2 п). Для эффективной реализации статистических тестов использовались измененные структуры хеш-таблицы и бинарного дерева поиска.

Один из разделов первой главы посвящен статистическим тестам основанным на алгоритмах сжатия. Необходимо отметить, что идея проверки на случайность с помощью алгоритмов сжатия тесно связана с определением случайности и сложности. Например, Колмогоров А.Н предложил измерять случайность последовательности, неформально, как длину программы, которая может воспроизвести эту последовательность. Таким образом, случайность (или Колмогоровская сложность) конечной последовательности это тоже самое, что и кратчайшая ее запись. Известно, что Колмогоровская сложность невычислима и следовательно не может непосредственно применяться для тестирования на случайность. С другой стороны, любой алгоритм неискажающего сжатия текстов может рассматриваться, как метод, оценивающий сверху Колмогоров-скую сложность Действительно, если рассмотреть бинарное слово х, некоторый метод сжатия ф и ф{х) код слова х то ясно, что \Ф(х)\ не меньше Кол-

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

Пусть А конечный алфавит. Через А" обозначим множество всех слов длины п из букв, где п пелое число. По определению, A' U^Li Ап и это множество всех бесконечных слов х2,... , х„ из букв алфавита А.

Определение 1. Методом сжатия данных (или кодом) iр называется множество отображений <рп, таких что Ап —> {0,1}*,п = 1,2,... для пары различных слов х, у е А" -рп(х) ф <рп(у)-

Неформально, это означает, что код <р может быть применен для сжатия сообщения произвольной длины п, п > 0 из букв алфавита А и сообщение может быть разархивировано (декодировано), если метод сжатия известен

Теперь кратко опишем новый статистический тест, который может быть основан на любом коде if. Пусть п некоторое целое положительное число и Но гипотеза о том, что все слова из алфавита А" равномерно распределены, то есть р(и) — \А\~п для произвольного и е А" (здесь и далее через |х| обозначим длину, если х слово, и число элементов, если х множество). Пусть требуемый уровень значимости равен 1 — а (или ошибка первого рода равна а), а > 0. Основная идея теста проста и естественна: хорошо сжимаемое слово должно быть признано неслучайным и гипотеза Но должна быть отвергнута. В работе показано, что можно определить критическое значение для предлагаемого теста:

ta = п log IА| — log(l/a) — 1. (4)

здесь и далее log х = log2 х.

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

В криптографии статистическая проверка генераторов также является одной из актуальных задач. В частности, для этих целей Институтом стандартов и технологий США (NIST) был рекомендован ряд статистических тестов. Группа специалистов NIST выбрала 16 самых мощных тестов и реализовала их в виде удобной программы. Эта программа находится в свободном доступе и каждый заинтересованный специалист может использовать её, чтобы проверить генератор (псевдо)случайных чисел.

В диссертации проведён сравнительный анализ новых тестов и тестов, рекомендуемых MST. Для этого использовались линейные конгруэнтные генераторы. С их помощью получают последовательность целых чисел Хп из диапазона от 0 до m — 1, где m- параметр. Линейный конгруэнтный генератор полностью

определяется с помощью четырех параметров а, Ь, т, Хв по формуле

Хп = (аХп-1 + b) mod т. (5)

Известно, что младшие знаки порождаемых по формуле(5) чисел часто далеки от случайно распределенных, поэтому обычно рекомендуется использовать только старшие знаки в качестве случайных чисел Следуя этой рекомендации, из порождаемых генератором значений выделялся или "старший бит", или "старший байт" (варианты, обозначаемые в дальнейшем R\ и Д6, соответственно) Точнее, в режиме R\ для четного т старший бит уп вычислялся по формуле

' 0, если Хп < m/2 — 1, если Х„ > т/2,

а для нечетного - как

У,

если Хп < т/2 — 1, если Хп > т/2, если Х„ — (т — 1)/2,

где Л - пустое слово.

В режиме йя восьмибитовое слово уп ' извлекается" из Х„ по формуле

л _ М 256 Хп/т* \, если А"п < т*, Уп~\А, если Хп > т*.

где т* = 25б(_т/256], а целое число [256Х„/т* ] записано как восьмибитовое слово.

Выло показано, что новые тесты существенно лучше находят отклонения от случайности В таблице 1 приведены результаты тестирования порядковым тестом и тестами Х13Т, линейного конгруэнтного генератора ЛАИБи. Каждый метод применялся к тестированию ста выборок и подсчитывались величины <Эа, равные, по определению, количеству случаев, когда значение критерия превышало квантиль порядка о распределения этого критерия. (Так, для порядкового теста подсчитывало«, количество случаев, когда значение х2 в (2) превышало квантиль порядка а распределения х2 с одной степенью свободы). В тесте 1 и тесте 2 использовались выборки 105 и 10е бит соответственно. Из таблицы видно, что порядковый тест паходит отклонения от случайности существенно лучше (все параметры тестов приведены в таблице).

Методы Qo 01 Параметры

тест 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 Matchings - 2 m-10

Overlapping 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 (R.Rivest, 1987), SEAL (P.Rogway, 1994), ISAAK (Jr.Jenkins, 1996), VMPC (Z. BartoSz, 2003), RC5 (R.Rivest, 1994), TEA (D Wheeler, 1994), SNOW (P.Ekdahl, 2002), Henkos (D Bucerzan, 2004).

МТ19937 (М.Ма1зито1о, 1998), ТТ800 (М.Ма15итого, 1992)

В третьей главе описывается новая статистическая атака на блоковые шифры.

* Блоковые шифры с секретным ключом находят самое широкое применение

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

ния надежных блоковых шифров, так и поиск эффективных криптоаналити-ческих атак на эти шифры (т е методов определения секретного ключа шифра на основе экспериментов с зашифрованными сообщениями) Исследования в этих областях ведутся параллельно и часто одними и теми же исследователями и, как правило, изобретение новой атаки приводит к появлению шифров, к ней устойчивых. Отметим сразу, что для криптографии представляют интерес атаки, которые менее трудоемки, чем метод "прямого" перебора ключей Например, если некоторая атака требует перебора 2Ш ключей вместо, скажем, 2250, требуемых для полного перебора, то и такал атака представляет интерес для криптологии Обзор современных блоковых шифров, методов их построения и анализа, а также различных типов атак, может быть найден во многих статьях и монографиях среди которых мы отметим работы В. Шнайера (В. ЭсЬпекг), А. Бирюкова, Р. Кнудсена (И. КписЬеп), в которых описаны десятки современных шифров и атак. Об актуальности проблемы свидетельствует и наличие многочисленных национальных и международных программ и конкурсов, направленных на построение надежных блоковых шифров, проводимых в настоящее время в США, странах Европейского сообщества, Японии, Корее.

Большинство блоковых шифров могут быть описаны как функция, определенная па множестве всех двоичных слов длины (I -Ь к) и принимающая значения в множест ве двоичных слов длины I, где I - длина шифруемого слова (или блока) и длина зашифрованного слова, а к - длина (секретного) ключа. В современных шифрах длина блока обычно 128 или 64 бита, а длина ключа у разных шифров (и разных режимов использования одного шифра) принимает значения от нескольких десятков бит до нескольких тысяч Например, у шифра АЕЭ, победителя проводимого в 1999-2001 г в США конкурса на бло-! ковый шифр 21-ого века, длина блока I равна 128 бит, а длина ключа может

принимать три значения - 128, 196 и 256 бит. У других популярных шифров 11С5 и ЯСб, предложенных Р.Ривестом (И Пгуея!;) длина блока может быть 4 32, 64 или 128 бит. а длина ключа в разных вариантах принимает значепия

от 64 до нескольких тысяч бит. Стоит отметить, что 11С5 и ЯС6 имеют очень простое описание и, по-видимому поэтому, являются одними из самых популярных объектов криптоанализа в последние годы В работах Б. Шнайера (В. ЗсЬпе1ег), Р. Кнудсена (I! КпиФчеп), Т. Шимояма (Т ЭЫтоуата) и др . опи-

саны результаты криптоанализа шифров RC5 и RC6 и делается вывод об их высокой устойчивости ко всем описанным в литературе атакам.

Процесс шифрования во многих, если не во всех, современных блоковых шифрах разбивается на последовательность сравнительно простых этапов, часто называемых раундами. В ходе каждого нового раунда проводится шифрование данных, полученных на предыдущем этапе с так называемым ключом раунда В RC5, RC6 и многих других шифрах количество раундов является параметром и часто криптоаналитики исследуют "стойкость1' шифров как функцию числа раундов. Одна из пелей такого анализа - нахождение числа раундов, гарантирующих высокую надежность шифра.

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

Описываемый нами метод относится к классу aiaK с выбираемым шифруемым текстом (chosen ciphertexts attack). При реализации этой атаки крипто-аналитик может подавать на вход шифра любой текст, анализировать полученное зашифрованное сообщение, затем, базируясь на результатах этого анализа, подавать новое сообщение и тд. Цель атаки - нахождение (секретного) ключа, причем при этом предполагается, что криптоаналитик знает все характеристики шифра, кроме этого ключа. Такие атаки представляют практический интерес и считается, что современные блоковые шифры должны быть стойки к ним.

Рассмотрим шифры, в которых кодируемое битовое (двоичное) сообщение является блоком длины 1,1 > 1, и шифруется при помощи ключа К, являющегося словом из \К\ случайно выбранных бит. (Здесь и ниже |м| длина и, если и слово, и мощность и, если и множество.)

У большинства современных шифров существует этап инициализации, в ходе которого начальный ключ К преобразуется в так называемые ключи раундов ki, кг, .., кт, которые используются последовательно для шифрования на разных этапах Схематично процесс шифрования для RC5, RC6 и многих других шифров можно представить как цепочку "элементарных" этапов (или раундов) шифрования.

Xi = Епст\{хо, ki),x2 = EncT2(xi, ki),..., xr — Encrr(xr~lt kr), (6) где xo исходное l— битовое слово, которое необходимо зашифровать, Епсг,—

операция (функция) шифрования на г— ом этапе, к, - ключ, используемый на г— ом этапе, х,— ¡— битовое слово, являющееся "выходом" г—ого этапа и "входом" (г + 1)— ого, и, наконец, хг— результат шифрования. В разных шифрах эта процедура осуществляется по разному, причем это зависит не только от шифра, но и от звачений длин блока и ключа (к, I) и числа раундов (г), которые для многих шифров являются параметрами. Например, для шифра RC5 длина блока может принимать значения 32, 64 или 128 бит, количество раундов может быть любым целым числом, а длина ключа должна быть кратна 8 и может принимать любое значение, начиная с 8 бит. Отметим, что значения I — 64, г = 12, к = 128 рекомендованы разработчиками и широко исследованы Часто рассматриваются и схемы, в которых длина ключа К равна суммарной длине ключей раундов (\К\ = £i=i \К\), что для многих шифров эквивалентно их независимому выбору Дешифрование проводится по схеме, обратной к шифрованию:

3V-i = Decrr(xr, K),xr-2 = Decrr-i(xr-i,kr-i), ...,х0 = Decr^xuh), (7)

где используются те же ключи раундов, а операции Deer, являются обратыми к этапам кодирования Епсг,

Оценим трудоемкость атаки полного перебора Для ее проведения достаг точно иметь одно зашифрованное сообщение (двоичное слово), длина которого не меньше длины ключа. Затем необходимо пытаться дешифровать это зашифрованное сообщение, последовательно перебирая все возможные ключи в каком-либо порядке и сравнивая полученный результат с исходным, незашифрованным, текстом; совпадение означает, что неизвестный ключ найден. Обычно предполагается, что ключ принимает любое значение из множества всех двоичных слов длины \К\ с вероятностью поэтому среднее значе-

ние числа перебираемых ключей равно (\К\ + 1)/2.

К современным блоковым шифрам предъявляется много различных требований, одно из которых можно сформулировать следующим образом: любое зашифрованное сообщение должно быть "похоже" на реализацию бернуллиев-ского процесса, в которой вероятность порождения нуля и единицы равна 1/2. (В дальнейшем для краткости мы будем называть такие последовательности случайными). В частности, все шифры, принимавшие участие в конкурсе на шифр 21-ого века, проводившемся в США в 1999- 2001 г.г. проверялись на выполнение этого условия. Мы не будем останавливаться на логическом анализе этого требования (которое, в некотором смысле, вообще невыполнимо), а приведем пример, поясняющий его смысл. Для эти о мы определим /-битовое слово а, как двоичную запись числа L г = 0,1,2,.. , 21 — 1, где, как и ранее, I -длина блока рассматриваемого шифра (те. а0 -состоит из I—битовой цепочки двоичных нулей, а\ из (1 — 1) пуля и единицы, аг- из [I — 2) нулей, после которых идет последовательность 10 и т.д.) От современного блокового шифра

требуется, чтобы при любом значении ключа последовательность ¿-битовых слов

Encr(a0)Encr(a1)Encr(a2) ■. ,

рассматриваемая как двоичная последовательность, была статистически неотличима от случайной (здесь Encr(at) означает зашифрованное слово а,). Это требование, в частности, позволяет использовать блоковые шифры как генераторы псевдослучайных чисел.

Перейдем теперь к описанию предлагаемой статистической атаки на блоковые шифры, у которых кодирование и декодирование разбивается на последовательность раундов (6) и (7), начав с очень неформального предварительного рассмотрения. При этом мы будем использовать совершенно нестрогие термины "более" и "менее" случайные последовательности, понимая под этим, что некоторая последовательность более случайна, чем другая, если отклонения от случайности у первой достоверно выявляются при бблыпей длине, чем у второй (при этом предполагается, что используется некоторый статистический тест при одном и том же уровне значимости. Другое "определение" более случайной последовательности - величина статистики критерия для этой последовательности меньше, чем для менее случайной). Предположим, что на вход шифра, ключ которого неизвестен, подаются последовательно слова айа\о>2 — Очевидно, эта последовательность "очень" неслучайна. Последовательность

Епсгх(ао, A;1)£ncr1(a1, ki)Encri(a2,fci)...,

после первого раунда шифрования, которую мы обозначим через /3о0г ■•■, "более" случайна, чем исходная; получаемая после второго раунда последовательность

Encrs[fio, к2)Епсг2{13г,к2)Епсг2{р2, к2) ■ ■.,

еще более случайна и т.д. Наконец, полученная после последнего раунда последовательность Ш0Ш1Ш2 • • • более случайна, чем предыдущая. Это неформальное утверждение подтверждается экспериментально в приведенных ниже данных для шифра RC5 и в довольно многочисленных работах практически для всех известных шифров рассматриваемого типа; объяснение этого факта довольно очевидно - шифрование на каждом раунде приводит к "перемешиванию" и, тем самым, повышает "случайность" шифруемых данных. Отметим и очевидное следствие - при дешифрировании последовательности ui0u)iu>2 ■ ■ ■ по схеме (7) случайность получаемых данных последовательно уменьшается. Это, конечно, справедливо только в том случае, когда при дешифровании используются "истинные" ключи раундов. Если же при "дешифровании" скажем на первом раунде xr_j = Decrr(xr, кт) (соответствующем последнему раунду при шифровании, см. (6),(7)) вместо истинного ключа кг используется какое-либо другое слово /с* той же длины, то эффект преобразования Decrr(xr,k*), будет

таков же. как при шифровании - выходная последовательность будет более случайна, чем входная Это важное для нал наблюдение в общем виде состоит в следующем- при дешифровании на ^-ом раунде при исполъзовани "неправильного" ключа к' (вместо "правильного" ключа к3) случайность выходной последовательности возрастает, тогда как при использовании "правильного" к3 - убывает.

При использовании новых статистических гестов (стопка кнш, порядковый и адашивный) возникает проблема нехватки вычислительных мощностей Компьютеры с одним процессором не справляются с этой задачей поскольку, например, для проверки гипотезы Но при большом размере алфавита (5 велико) необходимо хранить л/Б чисел в памяти. У персональных компьютеров есть ограничение на оперативную память и её может не хватить для тестирования стойких криптографических генераторов Существует также проблема скорости вычислений, поэтому тесты были реализованы с использованием параллельных вычислений. Для реализации тестов на многопроцессорных компьютерах были разработаны структуры данных и алгоритмы их взаимодействия В таблице 2 приведены результаты тестирования шифра 11С5 на больших выборках, которые показывают, что отклонения от случайности фиксируются до 8 раунда

Таблица 2: Проверка гипотезы о случайности для

различного числа раундов при уровне значимости 0.01.

раунд длина № количество ключей гипотеза о случайности отвергнута

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

Приведены результаты реализации атаки для шифра НС 5 с использованием параллельных вычислений. Для этого был разработан алгоритм атаки для многопроцессорного компьютера и использованы вычислительные мощности Сибирского суперкомпьютерного центра ИВМиГ СО РАН

В заключении кратко сформулированы основные результаты диссертационной работы:

1. Разработаны новые эффективные статистические тесты' порядковый тест и тест, основанный на алгоритмах сжатия. Показано, что мощность новых тестов выше, чем у ранее существовавших методов.

2. Построены новые алгоритмы и структуры данных для эффективной реализации статистических тестов- стопки книг и порядкового теста, которые уменьшают сложность вычислений до 0(nlog2(«)) (порядковый тест) и 0(п)(столка книг), где п - объём выборки.

3. Экспериментально исследованы широкий ряд практически применяемых генераторов псевдослучайных чисел.

4. Разработана и экспериментально исследована новая статистическая атака на блоковые шифры. При помощи этой атаки проверена "стойкость" шифра RC5 для различного числа раундов.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. В.А Монарев, Б.Я. Рябко Экспериментальный анализ генераторов псевдослучайных чисел при помощи нового статистического теста. // ЖВМ и МФ. 2004,- Т.44, N.5. - С 812-816.

2 В. Ryabko, V. Monarev, Yu. Shokin. Using Universal Coding Approach to Randomness Testing.// International Symposium on Information Theory, Proceedings. Chicago, 2004.

3. Б.Я. Рябко, B.A. Монарев, Ю.И. Шохин. Новый класс статистических тестов для случайных чисел и его применение в задачах криптографии. // Третья общероссийская конференция "Математика и безопасность информационных технологий", Москва, 2004.

4. В. Ya. Ryabko, V.A. Monarev. Using information theory approach to randomness testing. // Journal of Statistical Planning and Inference, 2005, - Vol. 133, N.l, - PP. 95-110.

5 Б Я. Рябко, B.A. Монарев. Экспериментальное исследование методов прогнозирования, базирующихся на алгоритмах сжатия данных // Проблемы передачи информации, 2005 - Т.21. - С.74-76.

6 В Ya. Ryabko, A.N. Fionov, V.A. Monarev, Yu.I Shokin Using information theory approach to randomness testing. / / The 2nd Russian-German Advanced Research Workshop on Computational Science and High Performance Computing. Stuttgart, Germany, 2005. Электронная публикация трудов конференции.

í

(

4

Виктор Александрович Монарев

Построение новых статистических тестов и их применение в криптографии

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 10 10. 2005, формат бумаги 60x84/16, отпечатано на ризографе, шрифт №10, изд. л. 1,1, заказ № 109 , тираж 80. СибГУТИ 630102, Новосибирск, ул. Кирова 86

124282

РНБ Русский фонд

2006-4 26721

1. Описание тестов, структур данных, алгоритмов

1.1 Теоретические основы

1.2 Описание тестов

1.3 Структуры и алгоритмы

1.4 Применение алгоритмов сжатия для тестирования на случайность

1.5 Двуличные процессы и выбор длины блока для тестирования

Актуальность темы

Статистические тесты находят применение в самых различных областях, включая анализ генераторов случайных и псевдослучайных чисел, и ряд задач криптографии. Поэтому задача построения новых эффективных статистических тестов и разработка алгоритмов эффективной реализации находится в центре внимания многих исследователей.

В настоящее время используется много методов (или тестов) для проверки генераторов случайных и псевдослучайных чисел. Все эти методы рассматриваются в рамках математической статистики. Точная постановка задачи следующая: проверяется гипотеза 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. Разработанные методы тестирования позволяют эффективно проверять генераторы случайных и псевдослучайных чисел.

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

Апробация работ и публикации: Основные результаты работы докладывались и обсуждались на следующих российских и международных конференциях: International Symposium on Information Theory (Chicago, 2004), Третья общероссийская конференция "Математика и безопасность информационных тех нологий" (Москва, 2004), а также на семинарах Института вычислительных технологий СО РАН (Новосибирск).

По теме диссертации опубликовано : 1 электронная публикация, 5 печатных работ, том числе 3 статьи. Основные положения, выносимые на защиту:

1. Разработаны методы эффективного тестирования генераторов случайных и псевдослучайных чисел.

2. Показано, что мощность новых тестов выше чем у ранее известных, включая методы, рекомендуемые NIST.

3. Разработаны алгоритмы и структуры данных для эффективной реализации новых статистических критериев.

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

Краткое содержание работы

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

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

Один из самых известных статистических тестов для проверки гипотезы о том, что для некоторого источника, который порождает буквы из алфавита А = {ai,., as}, S > 1, выполнена гипотеза: против альтернативной гипотезы Hi, являющейся отрицанием Hq, это критерий хи-квадрат. При применении критерия хи-квадрат подсчитывается значение где щ - частота символа аг- в выборке xi,. ,хп. Известно, что

Но : р(ах) = р?,. ,р(а5) = p°s,

1) х2 асимптотически приближается с распределению хи-квадрат с к — 1 степенью свободы.

Задача тестирования (псевдо)случайных последовательностей чисел формулируется следующим образом. Пусть некоторый источник, который порождает буквы из алфавита А = {ai,., as}, S 1, необходимо по выборке . ,хп, порождаемой источником, проверить гипотезу

Яо : p(ai) = . = p(as) = 1 /S (2) против альтернативной гипотезы что источник является стационарным, эргодическим и Щ не выполняется. Ясно, что это частный случай и критерий хи-квадрат здесь применим.

Кратко опишем вариант основного алгоритма тестирования. При тестировании в каждый момент времени t буквы алфавита А упорядочены (и занумерованы) в соответствии с убыванием (невозрастанием) частот z^(a), а £ А. После анализа очередной буквы xt+i частота этой буквы vt+1{xt+i) увеличивается на 1, а частоты остальных букв остаются прежними. Более формально: у\а) + если xt+i = а > v (а) — < i' (a), если а ф xt+i.

Первоначальный порядок z/°(a),a G А, задается произвольно, затем буквы упорядочиваются в соответствии с частотами vt+1). Обозначим через Р{а) номер буквы а £ А после обработки элементов выборки ., xt.

При применении описываемого теста множество всех номеров {1,2,., S} заранее, до анализа выборки, разбивается на два непересекающихся подмножества А\ = {1,2,.,А;}, и у42 = {к + 1, к + 2,., S}. Затем по выборке xi,.,xn подсчиты-вается количество номеров t = 1,2, .,п принадлежащих подмножеству Aj,j = 1,2, которое мы обозначим через Vj. При выполнении Но вероятность того, что P(xt) принадлежит множеству Aj, пропорциональна количеству его элементов, т.е. равна \Aj\/S. Затем по критерию хи-квадрат (х2) проверяется гипотеза Щ:

3) против альтернативной гипотезы Щ =

Пример. Пусть А = {1, 2, 3,4}, первоначальный порядок {1,2,3,4}, к — 2 и дана выборка 1,4,2,1,4,5. Рассмотрим состав множества А\ и частоту v\ после обработки каждого символа выборки (данные приведены в таблице). Далее подсчитываем величину ж2:

2 (^-З)2 (6 — z/i — З)2 2 л I

3 3 3' и сравниваем с табличным значением распределения хи-квадрат известно, что х2 асимптотически приближается к распределению хи-квадрат с одной степенью свободы). Делаем вывод, что данную последовательность можно считать случайной. Отметим, что для простоты была рассмотрена выборка объёмом 6, в то время, как рекомендуемый объём должен быть равен bS/k. В таблице показано, как изменяются частоты и множество А\ после обработки каждого элемента выборки. Так, например, после обработки пятого элемента выборки частота попадания в А\ — {1,4} была равна двум.

Элемент выборки А! i/*(3) i/*(4)

1 1 {1,2} 1 0 0 0

4 1 {М} 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* lX=i Ап и А°° это множество всех бесконечных слов ж2,., хп из букв алфавита А.

Определение 1. Методом сжатия данных (или кодом) ip называется множество отображений (рп, таких что (рп : Ап —> {0,1}*, п = 1,2,. для пары различных слов х,у £ Ап <рп(х) ф 4>п{у)

Неформально, это означает, что код <р может быть применен для сжатия сообщения произвольной длины п, п > 0 из букв алфавита А и сообщение может быть разархивировано (декодировано), если метод сжатия известен.

Теперь кратко опишем новый статистический тест, который может быть основан на любом коде ср. Пусть п некоторое целое положительное число и Hq гипотеза о том, что все слова из алфавита Ап равномерно распределены, то есть р(и) = \А\~п для произвольного и б Ап (здесь и далее через |ж| обозначим длину, если х слово, и число элементов, если х множество). Пусть требуемый уровень значимости равен 1 — а (или ошибка первого рода равна а), а > 0. Основная идея теста проста и естественна: хорошо сжимаемое слово должно быть признано неслучайным и гипотеза Hq должна быть отвергнута. В работе показано, что можно определить критическое значение для предлагаемого теста: ta — п l°g | А| — log(l/а) — 1, (4) здесь и далее log х = log2 х.

Вторая глава диссертации посвящена тестированию генераторов (псевдо)случайных чисел, которые используются на практике. Случайные числа широко применяются в численных методах, имитационном моделировании и полученные результаты могут существенно зависеть от "качества" используемого генератора. Поэтому, прежде чем использовать какой либо датчик случайных чисел, исследователь должен проверить его с помощью всевозможных статистических тестов.

В криптографии статистическая проверка генераторов также является одной из актуальных задач. В частности, для этих целей Институтом стандартов и технологий США (NIST) был рекомендован ряд статистических тестов. Группа специалистов NIST выбрала 16 самых мощных тестов и реализовала их в виде удобной программы. Эта программа находится в свободном доступе и каждый заинтересованный специалист может использовать её, чтобы проверить генератор (псевдо)случайных чисел.

В диссертации проведён сравнительный анализ новых тестов и тестов, рекомендуемых NIST. Для этого использовались линейные конгруэнтные генераторы. С их помощью получают последовательность целых чисел Хп из диапазона от 0 до га — 1, где га- параметр. Линейный конгруэнтный генератор полностью определяется с помощью четырех параметров а, Ь, га, Xq по формуле

Хп = (aXn 1 + Ъ) mod т. (5)

Известно, что младшие знаки порождаемых по формуле(2.1) чисел часто далеки от случайно распределенных, поэтому обычно рекомендуется использовать только старшие знаки в качестве случайных чисел. Следуя этой рекомендации, из порождаемых генератором значений выделялся или "старший бит", или "старший байт" (варианты, обозначаемые в дальнейшем R\ и соответственно). Точнее, в режиме R\ для четного т старший бит уп вычислялся по формуле

Г 0, если Хп < т/2 — 1,

Уп—\

11, если Хп > т/2, а для нечетного - как

10, если Хп < т/2 — 1, 1, если Хп > т/2, А, если Хп = (т — 1)/2, где А - пустое слово.

В режиме R§ восьмибитовое слово уп "извлекается" из Хп по формуле

Г [ 256 Хп/т* J, если Хп < т*, Уп = \

I А, если Хп > т*. где т* = 256[m/256j, а целое число [256 Хп/т* J записано как восьмибитовое слово.

Было показано, что новые тесты существенно лучше находят отклонения от случайности. В таблице 1 приведены результаты тестирования порядковым тестом и тестами NIST, линейного конгруэнтного генератора RANDU. Каждый метод применялся к тестированию ста выборок и подсчитывались величины Qa, равные, по определению, количеству случаев, когда значение критерия превышало квантиль порядка а распределения этого критерия. (Так, для порядкового теста подсчитывалось количество случаев, когда значение х2 в (1.5) превышало квантиль порядка а распределения %2 с одной степенью свободы). В тесте 1 и тесте 2 использовались выборки 105 и 106 бит соответственно. Из таблицы видно, что порядковый тест находит отклонения от случайности существенно лучше (все параметры тестов приведены в таблице).

Методы 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 отклонил гипотезу Hq только в одном случае из ста, в то время как порядковый забраковал все 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, и шифруется при помощи ключа К, являющегося словом из \К\ случайно выбранных бит. (Здесь и ниже \и\ длина и, если и слово, и мощность и1 если и множество.)

У большинства современных шифров существует этап инициал изации, в ходе которого начальный ключ К преобразуется в так называемые ключи раундов &2, ■ • •> К, которые используются последовательно для шифрования на разных этапах. Схематично процесс шифрования для RC5, RC6 и многих других шифров можно представить как цепочку "элементарных" этапов (или раундов) шифрования.

Х\ — Encr\(xQ, &i), Х2 = Encr2(xi, £2), ■ ■ ■ ,xr = Encrr(xr-1, kr), в) где xq исходное l— битовое слово, которое необходимо зашифровать, Enari— операция (функция) шифрования на г— ом этапе, к{ - ключ, используемый на г— ом этапе, Х{— I— битовое слово, являющееся "выходом" г—ого этапа и "входом" (г + 1)— ого, и, наконец, хг— результат шифрования. В разных шифрах эта процедура осуществляется по разному, причем это зависит не только от шифра, но и от значений длин блока и ключа (к, I) и числа раундов (г), которые для многих шифров являются параметрами. Например, для шифра RC5 длина блока может принимать значения 32, 64 или 128 бит, количество раундов может быть любым целым числом, а длина ключа должна быть кратна 8 и может принимать любое значение, начиная с 8 бит. Отметим, что значения I = 64, г = 12, к = 128 рекомендованы разработчиками и широко исследованы. Часто рассматриваются и схемы, в которых длина ключа К равна суммарной длине ключей раундов (\К\ = 1^1)> чт0 Для многих шифров эквивалентно их независимому выбору. Дешифрование проводится по схеме, обратной к шифрованию: xT-i = Decrr(xr, kr)yxr-2 = Decrr-i(ccri, kr-1),., xq = Decri(xi,

7) где используются те же ключи раундов, а операции Decri являются обратыми к этапам кодирования Епсгг.

Оценим трудоемкость атаки полного перебора. Для ее проведения достаточно иметь одно зашифрованное сообщение (двоичное слово), длина которого не меньше длины ключа. Затем необходимо пытаться дешифровать это зашифрованное сообщение, последовательно перебирая все возможные ключи в каком-либо порядке и сравнивая полученный результат с исходным, незашифрованным, текстом; совпадение означает, что неизвестный ключ найден. Обычно предполагается, что ключ принимает любое значение из множества всех двоичных слов длины \К\ с вероятностью поэтому среднее значение числа перебираемых ключей равно (\К\ + 1)/2.

К современным блоковым шифрам предъявляется много различных требований, одно из которых можно сформулировать следующим образом: любое зашифрованное сообщение должно быть "похоже" на реализацию бернуллиевского процесса, в которой вероятность порождения нуля и единицы равна 1/2. (В дальнейшем для краткости мы будем называть такие последовательности случайными). В частности, все шифры, принимавшие участие в. конкурсе на шифр 21-ого века, проводившемся в США в 1999- 2001 г.г. проверялись на выполнение этого условия. Мы не будем останавливаться на логическом анализе этого требования (которое, в некотором смысле, вообще невыполнимо), а приведем пример, поясняющий его смысл. Для этого мы определим /-битовое слово оц как двоичную запись числа i, г = 0,1,2,.,2г — 1 , где, как и ранее, / - длина блока рассматриваемого шифра (т.е. ао -состоит из /—битовой цепочки двоичных нулей, а\ из (/ — 1) нуля и единицы, а^- из (I — 2) нулей, после которых идет последовательность 10 и т.д.) От современного блокового шифра требуется, чтобы при любом значении ключа последовательность /-битовых слов

Encr(aQ]Encr(oii)Encr(a2)., рассматриваемая как двоичная последовательность, была статистически неотличима от случайной (здесь Encr(a>i) означает зашифрованное слово щ .). Это требование, в частности, позволяет использовать блоковые шифры как генераторы псевдослучайных чисел.

Перейдем теперь к описанию предлагаемой статистической атаки на блоковые шифры, у которых кодирование и декодирование разбивается на последовательность раундов (3.1) и (3.2), начав с очень неформального предварительного рассмотрения. При этом мы будем использовать совершенно нестрогие термины "более" и "менее" случайные последовательности, понимая под этим, что некоторая последовательность более случайна, чем другая, если отклонения от случайности у первой достоверно выявляются при большей длине, чем у второй. (При этом предполагается, что используется некоторый статистический тест при одном и том же уровне значимости. Другое "определение" более случайной последовательности - величина статистики критерия для этой последовательности меньше, чем для менее случайной). Предположим, что на вход шифра, ключ которого неизвестен, подаются последовательно слова ceoceia^ ■ • • Очевидно, эта последовательность "очень" неслучайна. Последовательность

Encri(o>o, ki)Encri(ai, ki)Encri(a2, ki) ., после первого раунда шифрования, которую мы обозначим через Pq/3i ., "более" случайна, чем исходная; получаемая после второго раунда последовательность

Encr2((30, k2)Encr2{(3i, к2)Епсг2((32, к2)., еще более случайна и т.д. Наконец, полученная после последнего раунда последовательность ujqUiuj2 . более случайна, чем предыдущая. Это неформальное утверждение подтверждается экспериментально в приведенных ниже данных для шифра RC5 и в довольно многочисленных работах практически для всех известных шифров рассматриваемого типа; объяснение этого факта довольно очевидно - шифрование на каждом раунде приводит к "перемешиванию" и, тем самым, повышает "случайность" шифруемых данных. Отметим и очевидное следствие - при дешифровании последовательности • ■ • по схеме

3.2) случайность получаемых данных последовательно уменьшается. Это, конечно, справедливо только в том случае, когда при дешифровании используются "истинные" ключи раундов. Если же при "дешифровании" скажем на первом раунде xr-i = Decrr(xr,kr) (соответствующем последнему раунду при шифровании, см. (3.1),(3.2)) вместо истинного ключа кг используется какое-либо другое слово к* той же длины, то эффект преобразования DecrT(xr,k*), будет таков же, как при шифровании - выходная последовательность будет более случайна, чем входная. Это важное для нас наблюдение в общем виде состоит в следующем: при дешифровании на j-ом раунде при использовани "неправильного" ключа Щ (вместо "правильного" ключа kj) случайность выходной последовательности возрастает, тогда как при использовании "правильного" kj - убывает.

При использовании новых статистических тестов (стопка книг, порядковый и адаптивный) возникает проблема нехватки вычислительных мощностей. Компьютеры с одним процессором не справляются с этой задачей поскольку, например, для проверки гипотезы Hq при большом размере алфавита (S велико) необходимо хранить Vs чисел в памяти. У персональных компьютеров есть ограничение на оперативную память до 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 с использованием параллельных вычислений. Для этого был разработан алгоритм атаки для многопроцессорного компьютера и использованы вычислительные мощности Сибирского суперкомпьютерного центра ИВМиГ СО РАН.

1. Колмогоров А.Н. Три подхода к определению понятия "количество информации".// Пробл. передачи информ., т.1, с.З-11.

2. Billingsley P., Ergodic theory and information.//Wiley, New York, 1965.

3. Martin- Lof P. The definition of random sequences.// Information and Control, v.9, pp.602-619, 1966.

4. Zvonkin A.K., Levin L.A. The complexity of finite objects and concepts of information and randomness through the algorithm theory.// Uspehi Math. Nauk, v. 25, n.6. 1970.

5. Рябко Б.Я. Прогноз случайных последовательностей и универсальное кодирование.// Пробл. передачи информ., т.24н.2, СюЗ-14.1988.

6. Morvai G., Yakowitz S. J., Algoet P.H. Weakly convergent nonparametric forecasting of stationary time series.// IEEE Trans. Inform. Theory, v.43, 1997, pp. 483 498

7. Kieffer J. Prediction and Information Theory, Preprint, 1998.//(available at ftp: //oz. ее. umn. edu/ users/kieffer/pap er s/prediction. p df/)

8. Algoet P., Universal Schemes for Learning the Best Nonlinear Predictor Given the Infinite Past and Side Information.// IEEE Trans. Inform. Theory, v. 45, pp. 1165-1185, 1999.

9. Nobel A.B. On optimal sequential prediction.// IEEE Trans. Inform. Theory, v.49, 2003, n.l. pp.83-98.

10. Кукушкина О.В., Поликарпов А.А., Хмелев Д.В. Определение авторства текста с использованием буквенной и грамматической информации.// Пробл. передачи информ., 2001, т. 37, н. 2, с. 96 109.

11. Колчин В.Ф. Севастьянов Б.А., Чистяков В.П. Случайные распределения.// Наука. Москва. 1976.

12. R. Cilibrasi, R. de Wolf, P. Vitanyi, Algorithmic clustering of music, Submitted.//(available at: http: //arxiv.org/archive/cs/0303025)

13. B. Ya. Ryabko, F. Topsoe. On Asymptotically Optimal Methods of Prediction and Adaptive Coding for Markov Source.//J. of Complexity,2002, Vol. 18, No. 1, pp. 224-241.

14. Gallager R.G. Information Theory and Reliable Communication. // Wiley, New York,1968.

15. Ryabko B.Ya. The complexity and effectiveness of prediction algorithms.// J. of Complexity, 1994. v. 10, pp.281-295.

16. Biryukov A. Block Ciphers and Stream Ciphers: The State of the Art.// Cryptology ePrint Archive: Report 2004/094. (http://eprint.iacr.org/2004/094/)

17. Gilbert H., Handschuch H., Joux A., Vaudenay S. A Statistical Attack on RC6.// Fast Software Encryption, (Lecture Notes in Computer Science, vol. 1978), pp.64-74, 2001.

18. Knudsen R.L., Meier W. Correlation in RC6. Private communication.// (Available at http://www.ii.uib.no/ larsr/papers/rc6.ps ).

19. Knuth D.E. The art of computer programming.// Vol.1-3. Addison Wesley, 1981.

20. Kendall M.G., Stuart A. The advanced theory of statistics.// Vol.2. Inference and Reletionship. Charles Griffin, London, 1961.

21. Menzes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography.// CRC Press, 1996.

22. J.Nechvatal and others. Report on the Development of the Advanced Encryption Standart (AES).// 2000, in: http: //csrc.nist.gov/encryption / aes / round2 / r2report. pdf

23. A.Rukhin and others. A statistical test suite for random and pseudorandom number generators for cryptographic applications.// NIST Special Publication 800-22 (with revision dated May,15, 2001). http://csrc.nist.gov/rng/SP800-22b.pdf

24. Maurer U.M. A universal statistical test for random bit generators.// J. of Cryptology, v.6.n.l, 1993, pp.55-61.

25. Рябко Б.Я., Пестунов А.И. Стопка книг как новый статистический тест для случайных чисел.// Проблемы передачи информации, т. 40, н. 1, 2004, с.73-78.

26. Рябко Б.Я., Стогниенко B.C. ,Шокин Ю.И. Адаптивный критерий хи-квадрат для различения близких гипотез при большом числе классов и его применение к некоторым задачам криптографии.// Проблемы передачи информации, т. 30, н. 2, 2003, с. 53-62.

27. Рябко Б.Я., Фионов А.Н. Основы современной криптографии для специалистов в информационных технологиях.// М., "Научный мир", 2004.

28. Schneier В. Applied Cryptography.// N.-Y., Wiley, 1996.

29. Schneier В. A Self-Study Course in Block-Cipher Cryptanalysis. // Cryptologia, v.24, n.l, Jan 2000, pp. 18-34.

30. J.Soto,L.Bassham. Randomness testing of the advanced encryption standard finalist candidates./ / In: Proceedings AES3, . 2001, New- York, http: //csrc.nist.gov/encryption/aes / round2 / conf3 / papers / 30-jsoto.pdf

31. Maurer U. A universal statistical test for random bit generators.// Adv. in Cryptology CRYPTO'90, Proceedings, Springer-Verlag, 1991, pp. 409-420.

32. Knuth D.E. The Art of Computer Programming, vol. 2: Seminumerical algorithms.// Addison-Wesley, Reading, MA:1981, 2nd ed.

33. Ryabko B. Ya., Stognienko V. S., Shokin Yu. I. A new test for randomness and its application to some cryptographic problems.// J. of Statist. Planning and Inference. 2003 (accepted; available online, see doi:10.1016/S0378-3758(03)00149-6).

34. Rukhin A., Soto J., Nechvatal J., et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications.// NIST Special Publ. 800-22 (with revision dated May,15,2001). http://csrc.nist.gov/rng/SP800-22b.pdf

35. Park S.K., Miller K.W. Random number generators: good ones are hard to find.// Comm. ACM.1988.V.31.P.1192-1201.

36. Ripley B.D. Thoughts on pseudorandom number generators.// J. Comput. Appl. Math.1990. V.31.P.153-163.

37. Monahan J.F. Accuracy in random number generation.// Math. Сотр. 1985.V.45.P.559-568.

38. Dagpunar J. Principles of Random Variate Generation.// Clarendon Press. Oxford: 1988.

39. Ugrin-Sparac G. Stochastic investigations of pseudo-random number generators.// Computing.1991.V.46.P.53-65.

40. L'Ecuyer P. Tests Based on Sum-Functions of Spacings for Uniform Random Numbers.// J. Statistical Computation and Simulation.1997. V.59.P.251-269.

41. Jennergren L.P. Another method for random number generation on microcomputers.// Simulation. 1983.V.41.P.79.

42. Marsaglia G. The structure of linear congruential sequences.// Applic. Number Theory Numer. Analys.New York.Academic Press: 1972. P.248-285.

43. Fishman G.S. Monte Carlo: concepts, algorithms, and applications, volume 1 of springer series in operations research.//New York,Springer: 1996.

44. Anderson S.L. Random number generators on vector supercomputers and other advanced architectures./ / SI AM Rev. 1990. V.32.P.221-251.

45. Smith J.T. С++ For scientists and engeneers.//New York: 1991. McGraw-Hill Book. Company.

46. Percus O.E., Whitlock P.A. Theory and Application of Marsaglia's monkey test for pseudorandom number generators.// ACM Trans, on Modeling and Comput. Simulation. 1995.V.5 P.87-100.

47. Moeschlin 0., Grycko E., Pohl C., Steinert F. Experimental Stochastics.// Berlin, Heidelberg: 1998. Springer.

48. Entacher К. A collection of classical pseudorandom number generators with linear structures advanced version.// http://crypto.mat.sbg.ac.at/results/karl/server/server.html

49. L'Ecuyer P. Tables of linear congruential generators of different sizes and good lattice structure.// Math. Comput.l999.V.68.P.249 260.

50. Grube A. Mehrfach rekursiv-erzeugte Pseudo-Zufallszahlen.// Z. fur angewandte Math, und Mechanik, 53:T223-T225, 1973.

51. Hartel F. Zufallszahlen fur Simulationsmodelle.// PhD thesis, Hochschule St. Gallen fur Wirtschafts-, Rechts- und Sozialwissenschaften, St. Gallen, 1994.

52. L'Ecuyer P., Blouin F. Linear congruential generators of order k>l.// In M. Abrams, P. Haigh, and J. Comfort, editors, Proceedings of the 1988 Winter Simulation Conference, IEEE Press, pages 432-439, 1988.

53. Hellekalek P.: Inversive pseudorandom number generators: concepts, results, and links.// In Alexopoulos, C. and Kang, K. and Lilegdon, W.R. and Goldsman, D., editor(s), Proceedings of the 1995 Winter Simulation Conference, pp. 255-262. , 1995.

54. Hastad J., Shamir A. The cryptographic security of truncated linearly related variables.// In Proceedings of the 17th ACM Symposium on Theory of Computing, page 356-362, 1985.

55. Marsalia G. Random numbers fall mainly in the planes. Proc. N.A.S., 61:25-28, 1968.

56. Simon J. Shepherd, Cryptanalysis of the GSM A5 Cipher Algorithm.// IEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141, London, 1994.

57. Matsumoto, M. and Nishimura, Т., Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator.// ACM Transactions on Modeling and Computer Simulation,1998, Vol. 8, No. 1, pp 3-30.

58. Marius Oliver Gheorghita and Dominic Bucerzan. Henkos stream cipher.//Cryptology ePrint Archive: Report 2004/080 (http://eprint.iacr.org/2004/080).

59. Robert J. Jenkins Jr., ISAAC and RC4.// 1993-1996 (http://www.burtleburtle.net/bob/rand/isaac.html).

60. Rogaway P., Coppersmith D., A software optimized encryption algorithm.// Workshop on software encryption, Cambridge, 1993.

61. Mironov I., (Not So) Random Shuffles of RC4.// Proceedings of CRYPTO 2002.

62. Matsumoto M., Kurita Y., Twisted GFSR generators.// ACM TOMACS,1992, vol.2, pp. 179-194.

63. New European Schemes for Signatures, Integrity, and Encryption, IST-1999-12324 (https: //www.cosic.esat.kuleuven.ac.be/nessie/)ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

64. Монарев В.А., Рябко Б.Я. Экспериментальный анализ генераторов псевдослучайных чисел при помощи нового статистического теста. //ЖВМ и МФ. 2004, Т.44, N.5. - С.812--816.

65. Ryabko В., Monarev V., Shokin Yu., Using Universal. Coding Approach to Randomness Testing.// International Symposium on Information Theory, Proceedings. Chicago, 2004.

66. Рябко Б.Я., В.А. Монарев, Ю.И. Шокин. Новый класс ста-• тистических тестов для случайных чисел и его применениев задачах криптографии. // Третья общероссийская конференция "Математика и безопасность информационных технологий", Москва, 2004.

67. Ryabko В. Ya., Monarev V.A., Using information theory approach to randomness testing. // Journal of Statistical Planning and Inference, 2005, -Vol. 133, N.l, -PP. 95-110.

68. Рябко Б.Я., Монарев В.А., Экспериментальное исследование методов прогнозирования, базирующихся на алгоритмах сжатия данных.// Проблемы передачи информации, 2005. В.1, Т.21, -С.74-76.