Главная » 2014 » Сентябрь » 4 » Скачать Построение новых статистических тестов и их применение в криптографии. Монарев, Виктор Александрович бесплатно
08:54
Скачать Построение новых статистических тестов и их применение в криптографии. Монарев, Виктор Александрович бесплатно
Построение новых статистических тестов и их применение в криптографии
Диссертация
Автор: Монарев, Виктор Александрович
Название: Построение новых статистических тестов и их применение в криптографии
Справка: Монарев, Виктор Александрович. Построение новых статистических тестов и их применение в криптографии : диссертация кандидата физико-математических наук : 05.13.18 Новосибирск, 2005 111 c. : 61 06-1/279
Объем: 111 стр.
Информация: Новосибирск, 2005
Содержание:
1 Оиисание тестов, структур данных, алгоритмов
11 Теоретические основы
12 Онисание тестов
13 Структуры и алгоритмы
14 Применение алгоритмов сжатия для тестированияна случайность
15 Двуличные ироцессы и выбор длины блока длятестирования
16
Приложение
2 Тестирование генераторов случайных чисел
21 Сравнение эффективности методов
22 Анализ генераторов нсевдослучайных чисел,использующихся на практике
221 Линейные конгруэнтые генераторы
222 Другие тины генераторов
223 Тестирование популярных генераторовпсевдослучайных чисел
3 Н о в а я статистическая атака на блоковые ш и ф р ы
31 Описание метода
32 Эксперименты с шифром RC
321 Исследования устойчивости шифра RC
322 Схема реализации тестов на МВС-
323 Результаты реализации атаки RC
324 Схема реализации атаки на МВС-
Введение:
Актуальность темыСтатистические тесты находят применение в самых различныхобластях, включая анализ генераторов случайных и псевдослучайных чисел, и ряд задач криптографии. Поэтому задача построения новых эффективных статистических тестов и разработка алгоритмов эффективной реализации находится в центревнимания многих исследователей.В настоящее время используется много методов (или тестов)для проверки генераторов случайных и псевдослучайных чисел. Все эти методы рассматриваются в рамках математическойстатистики. Точная постановка задачи следующая: проверяетсягипотеза HQ О ТОМ, ЧТО ИСТОЧНИК порождает символы из алфавита {0,1} незаврхсимо и вероятности этих символов равны 1/2против альтернативной гипотезы iJi, что последовательностьпорождается стационарным и эргодическим источником и HQне выполняется. Для краткости, в дальнейшем, будем называтьэту задачу тестом (или проверкой) на случайность.В криптографии и других приложениях используются генераторы случайных и псевдослучайных чисел. Генераторы случайных чисел используют некоторый физический источник данных для получения случайной последовательности. Он можетбыть основан на квантовых эффектах, на шумах в электрических цепях и т.п. Такие генераторы рекомендуется регулярно проверять на "случайность" выходной последовательности.Именно в этой области общие статистические тесты оказываются незаменимыми. Генераторы псевдослучайных чисел вычисляют последовательность чисел. Такие генераторы такженеобходимо проверять при помощи статистических тестов доих практического применения.Некоторые проблемы современной криптографии также связаны с тестами на случайность. Прежде всего это относится ктак называемым блоковым и потоковым П1ифрам. Приведем ихкраткое опргсание. Блоковые П1ифры обычно используют некоторое преобразования к блокам данных фиксированной длины (обычно 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 Symposiumon Information Theory (Chicago, 2004), Третья общероссийскаяконференция "Математика и безопасность информационных технологий" (Москва, 2004), а также на семинарах Института вычислительных технологий СО РАН (Новосибирск).Но теме диссертации опубликовано : 1 электронная нубликаЩ1Я, 5 печатных работ, том числе 3 статьи.Основные полож:епия, выносимые на защиту:1. Разработаны методы эффективного тестирования генераторов случайных и псевдослучайных чисел.2. Ноказано, что мощность новых тестов выше чем у ранее известных, включая методы, рекомендуемые NIST.3. Разработаны алгоритмы и структуры данных для эффективной реализации новых статистических критериев.4. Нредложена и экснериментально исследована новая статистическая атака на блоковые шифры, которая в некоторых случаях позволяет по выбранному шифротексту находить секретный ключ за время меньшее чем полный перебор ключей.Краткое содерж:ание работыВо введении обосновывается актуальность разработки новых эффективных статистических тестов, формулируются целии задачи исследований, приводятся основные положения диссертации, выносимые на защиту.В первой главе формулируется задача тестирования (псевдо)случайных последовательностей чисел. Излагаются алгоритмы новых статистических критериев. Описываются структурыданных, необходимые для эффективной реализации новых статистических тестов, и анализируется сложность вычислений.Все алгоритмы описаны (и реализованы) для многопроцессорных компьютеров. Теоретически обосновывается эффективностьтеста, базирующегося на алгоритмах сжатия данных.Один из самых известных статистических тестов для проверки гипотезы о том, что для некоторого источника, которыйпорождает буквы из алфавита А = {ai,, as}, S > 1, выполнена гипотеза:нротив альтернативной гипотезы Щ, являющейся отрицаниемНо, это критерий хи-квадрат. При применении критерия хиквадрат подсчитывается значениек / п\2где Vi - частота символа а^ в выборке жх,, ж„ . Известно, чтох^ асимптотически приближается с распределению хи-квадратс к — 1 степенью свободы.Кратко опишем вариант основного алгоритма тестирования.Обозначим через /*(а) номер буквы а ^ А носле обработки элементов выборки xi, ,xt.При выполнении Щ вероятность того, что l^{xt) принадлежитмножеству Aj, пропорциональна количеству его элементов, т.е.равна lAjl/S'. Затем по критерию хи-квадрат (х^) проверяетсягипотеза Щ:против альтернативной гипотезы Щ = -^Щ. Пример. Пусть Л = {1, 2, 3,4}, первоначальный порядок {1,2,3,4},к = 2 и. дана выборка 1,4,2,1,4,5. Рассмотрим состав множества Ai и частоту щ после обработки каждого символа выборки(данные приведены в таблице). Далее подсчитываем величину2 _ (i/i - 3)2 (6 - Z/1 - 3)2 _ 2и сравнршаем с табличным значением распределения хи-квадрат(известно, что x^' асимптотически приближается к распределению хи-квадрат с одной степенью свободы). Делаем вывод, чтоданную последовательность можно считать случайной. Отметим, что для простоты была рассмотрена выборка объёмом 6, вто время, как рекомендуемый объём должен быть равен 5S/k.В таблице показано, как изменяются частоты и множество Aiпосле обработки каждого элемента выборки. Так, например, после обработки пятого элемента выборки частота попадания вAi = {1,4} была равна двум.Элемент выборки142143111222Ai{1,2}{М}{1,2}{1,2}{1,4}{.1,4}^41)111222001111000001011122В диссертационной работе описаны структуры данных, при использовании которых число операций, необходимое для тестирования выборки размера п, не превосходит O(nlog2n). Дляэффективной реализации статистических тестов использовалисьизмененные структуры хеш-таблицы и бинарного дерева поиска.Один из разделов первой главы посвящен статистическимтестам основанным на алгоритмах сжатия. Необходимо отметить, что идея проверки на случайность с помощью алгоритмовсжатия тесно связана с определением случайности и сложности. Например, А.Н. Колмогоров предложил измерять случайность последовательности неформально как длину программы,которая может воспроизвести эту последовательность. Такимобразом, случайность (или Колмогоровская сложность) конечной последовательности это тоже самое, что и кратчайшая еёзапись. Известно, что Колмогоровская сложность невычислима и следовательно не может непосредственно применяться длятестирования на случайность. С другой стороны, любой алгоритм неискажающего сжатия текстов может рассматриваться.как метод, оцениваюш;ий сверху Колмогоровскую сложность.Действительно, если рассмотреть бинарное слово ж, некоторыйметод сжатия ф и ф[х) код слова х то ясно, что \ф{х)\ не меньшеКолмогоровской сложности слова х. Поэтому идея использования методов сжатия для тестирования случайных последовательностей вполне обоснована.Определение 1. Методом сжатия данных (или кодом) ^ называется множество отображений (/?„, таких что (/?„ : Л"" —>{0,1}*, п = 1, 2,. . . для пары различных слов ж, у G Л" 'рп{х) фПеформально, это означает, что код (р может быть применендля сжатия сообн];ения произвольной длины п^ п > О из буквалфавита А и сообш;ение может быть разархивировано (декодировано), если метод сжатия известен.Вторая глава диссертации посвящена тестированию генераторов (псевдо)случайных чисел, которые используются на практике. Случайные числа П1ироко прр1меняются в численных методах, имр1тационном моделировании и полученные результатымогут суп];ественно зависеть от "качества" используемого генератора. Поэтому, нрежде чем использовать какой либо датчикслучайных чисел, исследователь должен проверить его с помощью всевозможных статистических тестов.В криптографии статистическая проверка генераторов также является одной из актуальных задач. В частности, для этихцелей Институтом стандартов и технологий США (NIST) былрекомендован ряд статистических тестов. Группа специалистовNIST выбрала 16 самых мощных тестов и реализовала их в виде удобной программы. Эта программа находится в свободномдоступе и каждый заинтересованный специалист может исиользовать её, чтобы проверить генератор (нсевдо)случайных чисел.В режиме R^ восьмибитовое слово уп "извлекается" из Хп поформуле( [256Х;г/ш* J, если Х„ т*.где т* = 256 [m/256j, а целое число [ 256 Хп/т,* J записано каквосьмибитовое слово.Было показано, что новые тесты суп],ественно лучше находятотклонения от случайности. В таблице 1 приведены результатытестирования порядковым тестом и тестами NIST, линейного12конгруэнтного генератора RANDU. Каждый метод применялсяк тестированию ста выборок и подсчитывались величины Qa,равные, по определению, количеству случаев, когда значениекритерия превышало квантиль порядка а распределения этогокритерия. (Так, для порядкового теста подсчитывалось количество случаев, когда значение х^ в (1.5) превышало квантильпорядка а распределения %^ с одной степенью свободы). В тесте1 и тесте 2 использовались выборки 10^ и 10^ бит соответственно. Из таблицы видно, что порядковый тест находит отклоненияот случайности суш;ественно лучше (все параметры тестов приведены в таблице).13Таблица 1: сравнение мощности тестов.МетодыПорядковыйFrequencyBlock FrequencyCumulative SumsRunsLongest Run of OnesRankDiscrete Fourier TransformNonperiodic Template MatchingsOverlapping Template MatchingsUniversal StatisticalApproximate EntropyRandom ExcursionsRandom Excursions VariantSerialLempel'-Ziv ComplexityLinear ComplexityQo.oiтест 1761212110200232тест 21002011001221722213Параметрытест 1 тест 2s = 18, r=2, \Ai\ = 2000M=10000m = l lm=13M=5000M=20000m=10m=10L=:7, Q=1280m=14m=8M=2500Например, один из рекомендованных NIST тестов был DFT(Discrete Fourier Transform). Алгоритм этого теста изначальнопостроен так, что позволяет находить отклонение от случайности в случае линейных конгруэнтных генераторов, по даже этоттест находит отклонения от случайности хуже чем порядковыйтест. Во втором тесте DFT отклопил гипотезу HQ ТОЛЬКО В ОДНОМ случае из ста, в то время как порядковый забраковал все100 выборок. Таким образом, мы видим, что мощность новоготеста сугцественно выше чем у тестов, предлагаемых NIST.14в главе 2 также нриведены результаты тестирования известных генераторов псевдослучайных чисел. Рассмотрены различные классы генераторов и даны практические указания к примененрхю: линейные конгруэнтные генераторы, мультипликативные генераторы (MRG), инверсионные генераторы (ICG), а также известные генераторы RC4, SEAL, ISAAK, VMPC, RC5, TEA,SNOW, Henkos, MT19937, TT800, A5.В третьей главе описывается новая статистическая атака наблоковые П1ифры.Большинство блоковых шифров могут быть описаны как функция, определенная на множестве всех двоичных слов длины{I + к) и принимаюш;ая значения в множестве двоичных словдлины /, где I - длина шифруемого слова (или блока) и длина зашифрованного слова, а к - длина (секретного) ключа. Бсовременных шифрах длина блока обычно 128 или 64 бита, адлина ключа у разных шифров (и разных режимов использования одного шифра) принимает значения от нескольких десятковбит до нескольких тысяч. Например, у шифра AES, победителяпроводимого в 1999-2001 г. в США конкурса на блоковый шифр21-ого века, длина блока I равна 128 бит, а длина ключа можетнринимать три значения -128, 196 и 256 бит. У других популярных шифров RC5 и RC6, предложенных Р.Ривестом (R. Rivest)длина блока может быть 32, 64 или 128 бит, а длина ключа вразных вариантах принимает значения от 64 до нескольких тысяч бит. Стоит отметить, что RC5 и RC6 имеют очень простоеописание и, по-видимому поэтому, являются одними из самыхпопулярных объектов криптоанализа в последние годы. В ра16ботах Б. Шнайера (В. Schneier), Р. Кнудсена (R. Knudsen), Т. Шимояма (T.Shimoyama) и др., описаны результаты криптоанализа шифров RC5 и RC6 и делается вывод об их высокойустойчивости ко всем описанным в литературе атакам.Процесс шифрования во многих, если не во всех, современных блоковых шифрах разбивается на последовательность сравнительно простых этапов, часто называемых раундами. В ходекаждого нового раунда проводится шифрование данных, полученных на предыдуп];ем этапе с так называемым ключом раунда. В RC5, RG6 и многих других шифрах количество раундов является параметром и часто криптоаналитики исследуют"стойкость" шифров как функцию числа раундов. Одна из целей такого анализа - нахождение числа раундов, гарантируюш,их высокую надежность шифра.В данной работе описывается новая атака на блоковые шифры данного типа, которая была названа обш;естатистической,и в качестве примера исследуется возможность ее применениядля криптоанализа шифра RC5. Приведенные экспериментальные данные позволяют сделать вывод о том, что эта атака может быть применена и что для некоторых режимов этого шифраее трудоемкость может быть суш;ественно меньше, чем у прямого перебора. Здесь стоит отметить, что хотя предлагаемая намиатака ранее не онисывалась и является новой, но исследование,статр1стических свойств блоковых шифров уже использовалосьв криптоанализе.Описываемый нами метод относится к классу атак с выбираемым шифруемым текстом (chosen ciphertexts attack). При ре17алР1зации этой атаки кринтоаналитик может подавать на входшифра любой текст, анализировать полученное зашифрованное сообп];ение, затем, базируясь на результатах этого анализа,подавать новое сообш;ение и т.д. Цель атаки - нахождение (секретного) ключа, причем при этом предполагается, что криптоаналитик знает все характеристики шифра, кроме этого ключа.Такие атаки представляют практический интерес и считается,что современные блоковые шифры должны быть стойки к ним.Рассмотрим шифры, в которых кодируемое битовое (двоичное) сообш;ение является блоком длины 1,1 > 1, и шифруетсяпри помош;и ключа К, являюш;егося словом из \К\ случайновыбранных бит. (Здесь и ниже \и\ длина и, если и слово, и мош;ность и, если и множество.)У большинства современных шифров суш;ествует этап инициализации, в ходе которого начальный ключ К преобразуетсяв так называемые ключи раундов ki,k2, • • • ,К, которые используются последовательно для шифрования на разных этапах.Схематично процесс шифрования для RC5, RC6 и многих других шифров можно представить как цепочку "элементарных"этапов (или раундов) шифрования.xi = Encri{xQ,ki), Х2 = Епсг2{х1, к2), ,Хг = ЕпсГг{хг-1, кг),(6)где хо исходное I— битовое слово, которое необходимо зашифровать, ЕпсГг— операция (функция) шифрования на i— ом этапе,ki - ключ, используемый на Г— ОМ этапе, Xi— I— битовое слово, являюш;ееся "выходом" i—ого этапа и "входом" (г -Ь 1)— ого,и, наконец, Xj.— результат шифрования. В разных шифрах эта18процедура осуществляется по разному, причем это зависит нетолько от шифра, но и от значений длин блока и ключа {к, I)и числа раундов (г), которые для многих шифров являютсяпараметрами. Например, для шифра RC5 длина блока можетпринимать значения 32, 64 или 128 бит, количество раундов может быть любым целым числом, а длина ключа должна бытькратна 8 и может принимать любое значение, начиная с 8 бит.Оценим трудоемкость атаки полного перебора. Для ее проведения достаточно иметь одно зашифрованное сообп];ение (двоичное слово), длина которого не меньше длины ключа. Затемнеобходимо пытаться дешифровать это зашифрованное сообп];ение, последовательно перебирая все возможные ключи в какомлибо порядке и сравнивая полученный результат с исходным,незашифрованным, текстом; совпадение означает, что неизвестный ключ найден. Обычно предполагается, что ключ принимаетлюбое значение из множества всех двоичных слов длины \К\ свероятностью 2"'-^', поэтому среднее значение числа перебира19емых ключей равно {\К\ + 1)/2.20Перейдем теперь к описанию предлагаемой статистическойатакр! на блоковые шифры, у которых кодирование и декодирование разбивается на последовательность раундов (3.1) и (3.2),начав с очень неформального предварительного рассмотрения.При использовании новых статистических тестов (стопка книг,порядковый и адаптивный) возникает проблема нехватки вычислительных мош;ностей. Компьютеры с одним процессоромне справляются с этой задачей поскольку, например, для проверки гипотезы Но при большом размере алфавита (5 велико)необходимо хранить v ^ чисел в памяти. У персональных ком22пьютеров есть ограничение на оперативную память до 2Гб иэтого может не хватить для тестирования стойких криптографических генераторов. Существует также проблема скоростивычислений, поэтому тесты были реализованы с использованием параллельных вычислений. Для реализации тестов иа многопроцессорных компьютерах были разработаны структуры данных и алгоритмы их взаимодействия. В Таблице 2 приведенырезультаты тестирования шифра RC5 на больших выборках, которые показывают, что отклонения от случайности фиксируются до 8 раунда.Таблица 2: Проверка гипотезы о случайности дляразличного числа раундов нри уровне значимости 0.01.раунд55.566.577.58длинаW228229231232232233237количествоключей302266663гипотеза о случайностиотвергнута301066552Приведены результаты реализации атаки для шифра RC5 с иснользованием параллельных вычислений. Для этого был разработан алгоритм атаки для многонроцессорного комньютераи использованы вычислительные мощности Сибирского суиеркомпьютерного центра ИВМиГ СО РАН.
