Содержание к диссертации
Введение
1. Типы генераторов последовательностей и их характеристики 9
1.1 Типы генераторов последовательностей 9
1.2 Характеристики генераторов псевдослучайных последовательностей . 14
1.3 Выводы по главе 21
2. Построение модели генератора ПСП и его исследование 22
2.1 Описание исследуемого генератора ПСП 22
2.2 Построение модели генератора 30
2.2.1 Распределение последовательностей 31
2.2.2 Автокорреляционная функция 34
2.2.3 Исследование влияния ключа генератора на ПСП 36
2.2.4 Исследование периода повторения ПСП 38
2.3 Выводы по главе 43
3. Исследование возможности модифицирования генератора ПСП 44
3.1 Изменение функционального преобразования/ 44
3.1.1 Изменение функционального преобразования с сохранением однозначности 45
3.1.2 Изменение функционального преобразования без сохранения однозначности 50
3.1.3 Исследование влияния нелинейности генератора на его
характеристики 52
3.1.4 Выводы по исследованию изменения таблицы функционального преобразования. 56
3.2 Изменение длины ключа и способа заполнения РГ2 56
3.3 Исследование усложненных алгоритмов использования генератора...61
3.3.1 Каскадное последовательное соединение двух генераторов 61
3.3.2 Режим автогенератора 65
3.3.3 Выводы по исследованию усложненных алгоритмов генерации 67
3.4 Выводы по главе 68
4. Практическое применение генераторов ПСП 70
4.1 Способы применения генераторов псевдослучайной последовательности для защиты информации 70
4.2 Пример практического использования генератора ПСП 73
4.2.1 Постановка задачи 73
4.2.2. Принцип разработки плагинов Outpost 74
4.2.3 Описание алгоритмов работы плагина 82
4.2.4 Результаты работы плагина 93
4.2.5 Исследование влияния разработанного модуля на скорость передачи данных 100
4.3 Выводы по главе 103
Заключение 105
Библиографический список 107
Приложение
- Характеристики генераторов псевдослучайных последовательностей
- Исследование влияния ключа генератора на ПСП
- Изменение функционального преобразования без сохранения однозначности
- Исследование влияния разработанного модуля на скорость передачи данных
Введение к работе
В современном мире одной из главных основ жизнедеятельности человека является информация, часть которой является конфиденциальной, а потому наиболее ценной для отдельного человека или организации, и всегда найдутся люди, желающие завладеть этой информацией в корыстных целях или просто из любопытства. Сейчас существует множество способов защитить свою информацию, но и не меньше способов взлома стоит на вооружении у хакеров.
Особенно уязвимым местом для нарушения информационной безопасности являются сети передачи данных, так как нельзя гарантировать сохранность данных при проходе их через публичные среды (Интернет, телефонные линии, радиоканал). Поэтому информация, передаваемая по различным сетям передачи данных, особенно нуждается в защите.
Для решения задач защиты информации часто используются генераторы псевдослучайных последовательностей (ПСП):
генерация гаммирующих последовательностей;
формирование контрольных кодов (контрольных сумм, имитоприставок);
формирования случайных запросов в криптографических протоколах выработки общего секретного ключа, разделения секрета, подбрасывания монеты, привязки к биту, аутентификации, электронной подписи;
внесения неопределенности в работу защищаемых аппаратно-программных средств;
внесения неопределенности в работу средств защиты;
формирования ключевой информации.
Необходимы способы исследования характеристик генераторов ПСП и сравнения между собой различных генераторов. Работа с оригинальными
алгоритмами генерации требует значительных временных затрат на вычисления, поэтому необходимы построения моделей генераторов, позволяющие увеличить скорость расчетов. Также требуются количественные критерии, по которым можно было бы сравнить несколько генераторов ПСП.
В направлении исследований в области защиты информации работали многие зарубежные и отечественные ученые: В. С. Барсуков [5, 6, 7], В. А. Герасименко [13, 14], П. Д. Зегжда [39], Д. П. Зегжда [38], В. Жельников [36], А. В. Мельников [57], М. А. Иванов [41], С. П. Расторгуев [65], В. М. Фомичев [77, 78, 79], А.А. Малюк [14, 55, 56], К. Шеннон [84], Р. Л. Ривест [104, 105], А. Шамир [105, 106], Л. Эйдльман [105], Б. Шнайер [107, 85] и другие.
Научные школы в этой области существуют в Москве, Санкт-Петербурге, Томске, Новосибирске, Красноярске, Таганроге, Воронеже, Пензе, Екатеринбурге.
Целью работы является разработка принципов построения моделей генераторов псевдослучайных последовательностей и анализ с их помощью применимости генераторов в области защиты данных и усиления секретности.
Для достижения поставленной цели потребовалось решить следующие задачи.
Сравнение различных типов генераторов последовательностей, определения их пригодности для использования в области защиты информации.
Анализ характеристик генераторов ПСП, выбор наиболее важных характеристик для оценки пригодности генератора, а также количественных оценок характеристик для возможности сравнения различных генераторов по ним.
Построение модели генератора псевдослучайной последовательности, доказательство ее адекватности исходному алгоритму генерации путем исследования ее характеристик.
Исследование способов модифицирования оригинального генератора ПСП с целью увеличения его секретности, анализ характеристик модифицированных генераторов.
Исследование характеристик усложненных алгоритмов генерации, основанных на эталонном его образце, с целью увеличения секретности генератора и улучшения показателей.
Экспериментальная реализация методов защиты передаваемых данных с помощью генераторов ПСП, исследование влияния маскирования данных на скорость передачи.
Методы исследования. Исследования проведены с использованием теории конечных полей, алгебры множеств, булевых алгебр, теории подобия, математического моделирования, математической статистики.
Научная новизна.
Предложена новая модель генераторов псевдослучайных последовательностей, применимая также к другим блочным алгоритмам.
Впервые проведены исследования возможности модифицирования исходного алгоритма генерации с целью усиления его криптостойкости.
Проведены исследования усложненных алгоритмов генерации с целью улучшения показателей и секретности генератора.
Экспериментально исследовано влияние шифрования передаваемых данных на скорость передачи для алгоритма шифрования с помощью генератора ПСП.
Практическая полезность работы.
1. Предложен способ моделирования генераторов псевдослучайных последовательностей и других блочных алгоритмов для исследования их
характеристик, обеспечивающий высокую скорость генерации всех возможных значений последовательности.
На основе результатов моделирования выработаны рекомендации по применению генераторов ПСП, разработчикам указаны «узкие места» исследуемого алгоритма.
Выработаны рекомендации по ограничениям и условиям использования модифицированных генераторов псевдослучайных последовательностей, позволившие обеспечить максимальную криптостойность алгоритмов генерации.
Программный модуль, разработанный для проведения экспериментальных исследований, используется для шифрования передаваемых данных в локальной сети ОАО «Сибирьтелеком», регионального филиала «Электросвязь Омской области».
Материалы исследований используются при изучении дисциплин «Математические основы теории систем» и «Информационная безопасность и защита информации» в ОмГУПС.
Основные положения работы докладывались на 9 конференциях, по теме диссертации опубликовано 6 статей, в том числе 3 статьи без соавторов, всего 15 работ.
Работа состоит из введения, четырёх глав, списка использованных источников из 107 наименований, 3 приложений. Основной текст изложен на 132 страницах, содержит 6 таблиц, 48 рисунков.
Основные положения, выносимые на защиту.
Проведен анализ различных типов генераторов последовательностей, их характеристик и применимости в области защиты информации, выбраны наиболее важные характеристики.
Выполнено построение модели генератора псевдослучайной последовательности, анализ ее адекватности оригинальному алгоритму генератора, на основании которой выработаны рекомендации по ограничениям в применении генератора.
На разработанной модели проведены исследования модифицированных и усложненных генераторов псевдослучайных последовательностей с увеличенной секретностью, на основании которых выработаны условия и ограничения применения модифицированных и усложненных генераторов ПСП.
Разработан программный модуль и проведено экспериментальное исследование одного из способов применения генератора ПСП — шифрование передаваемых данных по локальной вычислительной сети.
Характеристики генераторов псевдослучайных последовательностей
Многообразие критериев оценки псевдослучайных последовательностей, используемых при шифровании, чрезвычайно велико. Каждый из подходов к анализу шифрующих последовательностей можно отнести к одной из двух групп [77].
Первая группа связана с поиском закономерностей, позволяющих воспроизвести шифрующую последовательность по относительно небольшому отрезку. При этом основные требования сводятся к тому, чтобы в псевдослучайной последовательности отсутствовали относительно простые межзнаковые зависимости — зависимости, по которым можно было бы предсказать следующее значение последовательности или ее части.
Вторая группа критериев связана с оценкой статистических свойств последовательности: имеется ли в исследуемой последовательности какой-либо, частотный дисбаланс, позволяющий аналитику предположить значение следующей части последовательности, с вероятностью большей, чем при случайном выборе. При этом основные требования к шифрующей последовательности сводятся к тому, чтобы псевдослучайная последовательность обладала теми же статистическими свойствами, что и случайная последовательность.
Лишь для некоторых частных классов последовательностей удается аналитически доказать некоторые важные свойства. Для обоснования многих других свойств используются статистические тесты. При системном подходе для анализа последовательностей используются известные тесты и разрабатываются новые тесты с учетом особенностей анализируемого объекта. Если в ходе анализа в некотором классе последовательностей обнаруживается новое уязвимое место, то разрабатывается новый тест, который пополняет используемый набор известных тестов.
Существуют конкретные оценки для статистических проверок качества генераторов псевдослучайной последовательности [41, 77]: 1. Гистограмма распределения.
Гистограмма позволяет определить равномерность распределения символов в тестируемой последовательности, а также оценить частоту появления конкретного символа. Данный тест незаменим при проверке последовательности на «случайность», а также при исследовании генераторов с произвольным законом распределения символов. Для того чтобы последовательность удовлетворяла свойствам случайности, необходимо, чтобы в ней присутствовали все символы, при этом разброс частот появления символов стремился к нулю. Рассматриваемый тест может принести пользу также в тех случаях, когда оценивается качество последовательности с законом распределения, отличным от равномерного, либо последовательности, в которой некоторые символы вообще отсутствуют. 2. Автокорреляционная функция.
Для всего множества сгенерированных значений последовательности рассчитывается автокорреляционная функция [47]: где А І — /-oe значение ПСП в таблице сгенерированных значений; / — расстояние между сравниваемыми элементами, N— количество значений в этой таблице, М— среднее значение последовательности.
Генератор, удовлетворяющий требованиям безопасности должен иметь автокорреляционную функцию, близкую к символу Кронекера — равную 1 при у = 0, и нулю при остальных значениях. . Период повторения генератора.
Данный тест определяет периоды повторения генератора — через сколько циклов генерации будет получена последовательность, совпадающая с первым ее значением. Так как при одинаковых начальных установках получаемые последовательности совпадают, дальнейшая генерация приведет к зацикливанию получаемых последовательностей.
Удовлетворяющим требованиям безопасности считается генератор, период повторения которого не меньше половины количества всех возможных значений получаемой последовательности [82]: где Т— период повторения генератора; N— длина получаемой последовательности в битах. 4. Распределение на плоскости. Тест позволяет оценивать равномерность и независимость распределения символов в исследуемой последовательности. Для построения графической зависимости на поле размером 256 х 256 наносятся точки с координатами {Qh Qi+\), где Qt — г-й баш последовательности, i = \,m-\, т — длина последовательности. Далее анализируется полученная картина. В случае некачественной последовательности точки распределены неравномерно, либо наблюдается некий узор. Для последовательностей большой длины (порядка 700 Кб и выше) положительным результатом считается график, представляющий собой черный квадрат. 5. Байтовая автокорреляционная функция Тест проверяет взаимонезависимость байтов изучаемой последовательности на основе анализа всплесков корреляции. Для расчета автокорреляционной функции последовательность нормируется. Пусть [ 7-.. 1 0J — двоичная запись элемента последовательности длиной т, ,-=(0,1), j = 1,7. Тогда нормированное значение этого элемента вычисляется как После этого вычисляются всплески корреляции Нетрудно заметить, что при т = 0 и т = m значение F(x) = 1. Во всех остальных случаях для качественной ПСП значения F(x) должны стремиться к нулю.
Исследование влияния ключа генератора на ПСП
Для анализа генератора может быть использована теория конечных автоматов, согласно которой ключ генератора является входом конечного автомата, а полученные при этом ключе последовательности — его выходом [10, 15]. Генератор считается пригодным для использования в области защиты данных, если при изменении одного бита в ключе генератора количество изменившихся битов в полученных последовательностях близко к половине длины всей выходной последовательности (количества бит во всех сгенерированных с данным ключом последовательностях).
Для исследования влияния изменения ключа генератора на получаемые последовательности было проведено изменение одного бита ключа генератора — первый байт ключа установили равным 2438 вместо 2428: (х,6,..., х,) = (243, 13, 342, 236, 321, 272, 107, 165, 214, 167, 161, 73, 3, 170,34,147)8. При этом количество изменившихся битов во всех полученных с измененным ключом последовательностях должно быть не меньше половины общего количества битов в этих последовательностях. После генерации ПСП для всех начальных установок — от 0 до 65535 было проведено побитовое сложение по модулю 2 (побитовое исключающее ИЛИ — XOR) всех получившихся последовательностей с соответствующими последовательностями, полученными при предыдущем значении ключа (пп. 2.2.1 и 2.2.2). После этого было посчитано количество единиц в двоичном представлении результата сложения (вычислен суммарный вес [90]).
Как видно из расчета, количество изменившихся битов примерно равно половине общего числа битов, что говорит о сильной зависимости генерируемых ПСП от ключа генератора.
Для исследования зависимости периода повторения от начальной установки генератора последовательно в качестве исходного значения генератора ПСП подставлялись числа от 0 до 65535 (216-1) и генерировались ПС числа до тех пор, пока полученное число не равнялось устанавливаемому исходному значению. Внутренних зацикливаний (повторения уже сгенерированного числа) быть не может, так как данная система (генератор) является однозначной, как было показано выше. В таблицу записывались начальная установка генератора и период повторения (количество сгенерированных чисел до совпадения полученного и начального числа). Затем полученная таблица для наглядности сортировалась по периоду повторения.
Максимальное значение периода повторения — 34367 (больше половины максимального значения ПСП) — было получено при 34367 начальных установках. Остальные начальные установки дали меньший результат, причем для некоторых из них период повторения получился равен 1 (число на выходе генератора ПСП не меняется и всё время равно числу на входе, сколько циклов генерации мы бы не сделали). В таблице 4 представлены первые 30 строк из сортированной таблицы. Зависимость между периодом повторения и количеством начальных установок, приводящих к этому периоду, приведена в таблице 5: Вывод о существовании какой-либо функциональной зависимости между периодом повторения и начальной установкой генератора сделать затруднительно, так как алгоритм генератора является нелинейным. Как видно из таблицы 5, число начальных установок равняется длине периода повторения, к которому они приводят, то есть все множество возможных значений разбивается на некоторое число циклов — циклически повторяющихся значений, которые получаются при генерации последовательностей подряд — без смены начальной установки. Следовательно, можно упростить определение начальных установок, приводящих к малому периоду повторения — при получении одной такой установки достаточно сгенерировать подряд такое число последовательностей, которое равно полученному периоду повторения. Полученные при этом значения последовательности также будут являться «плохими» начальными установками, так как они являются элементами одного цикла. Можно утверждать, что изменение длины последовательности не могло так сильно повлиять на период повторения и оригинальный генератор обладает тем же недостатком, что и модель — при некоторых (различных для различных значений других устанавливаемых параметров генератора) значениях начальной установки генератора период повторения меньше половины всех возможных значении ПСП. Предложенная автором модель генератора является адекватной оригинальному алгоритму генератора, так как она обладает свойствами оригинального генератора ПСП (если он является отраслевым стандартом, то он должен обладать свойствами генератора, подходящего для применения в области защиты информации): 1) равномерным распределением последовательностей; 2) автокорреляционной функцией близкой к символу Кронекера; 3) сильной зависимостью полученных ПСП от ключа генератора. Следовательно, модель генератора может быть использована для дальнейших исследований алгоритма этого генератора. Период повторения модели при некоторых (различных для различных значений других устанавливаемых параметров генератора) значениях начальной установки генератора меньше половины всех возможных значений сгенерированной последовательности. Однако это отражает недостаток исходного алгоритма генератора, а не модели. Исходя из всего вышеприведенного, можно сделать вывод, что исследуемый генератор ПСП может быть использован в качестве генератора гаммы для защиты передаваемых данных, но с проверкой периода повторения для данной начальной установки генератора. Разработчикам устройств и программ, реализующих данный алгоритм можно порекомендовать составлять таблицы допустимых начальных установок генератора с отбрасыванием начальных установок, приводящих к вырожденным циклам.
Изменение функционального преобразования без сохранения однозначности
Исследована другая модификация таблицы функционального преобразования — без сохранения ее однозначности. В исходной таблице был инвертирован один бит: число 2g было заменено на число 3g. Таким образом, получилась таблица, в которой число 3 присутствует 2 раза, а число 2 — ни разу. Далее было проведено исследование распределения последовательностей, сгенерированных модифицированным таким образом генератором. На рисунке 19 представлена полученная гистограмма распределения. Как видно, нарушилась однозначность алгоритма генератора — некоторые значения выходной последовательности встречаются 8 раз, а некоторые — ни разу. Это является недопустимым, так как становится возможна статистическая атака нарушителем на полученные последовательности [85]. Нарушение равномерности распределения сгенерированных последовательностей является недопустимым для генератора используемого для защиты информации, поэтому можно сделать вывод, что такой модификацией таблицы функционального преобразования пользоваться нельзя. Дальнейшее исследование модифицированного таким способом генератора является нецелесообразным. Генератор, используемый для защиты информации, должен быть существенно нелинейным (глава 1).
Для проверки влияния нелинейности на характеристики генератора было проведено следующее исследование -из оригинального алгоритма был исключен нелинейный элемент — функциональное преобразование/ Далее по методике, описанной выше, были получены распределение последовательностей и автокорреляционная функция. Гистограмма полученного распределения представлена на рисунке 25. Z = 1.6668, что в 3 раза больше значения для немодифицированного генератора. Это подтверждает то, что нелинейность влияет на взаимозависимость между сгенерированными последовательностями. Для подтверждения этого был исследован случай, когда ключ генератора содержит только 0. Для этого значения ключа были посчитаны автокорреляционные функции для генераторов с отсутствующим функциональным преобразованием и с исходным немодифицированным функциональным преобразованием. Автокорреляционная функция для генератора без функционального преобразования/с ключом, равным 0, представлена на рисунке 23. Как видно из графика и значения показателя Zk , при нелинейном алгоритме даже при нулевом ключе генератора сгенерированные последовательности практически некоррелированны. Все вышеприведенное подтверждает необходимость нелинейности алгоритма генератора ПСП для сохранения его характеристик, требуемых для использования его при защите информации. Из всего вышеизложенного можно сделать вывод, что таблицу функционального преобразования / можно использовать в качестве дополнительной секретной информации алгоритма генератора только при обязательном выполнении следующих условий: 1) сохранение однозначности таблицы — одному значению входного байта соответствует одно значение выходного байта и наоборот; 2) таблица не может быть единственной ключевой информацией генератора — изменение таблицы должно происходить совместно с изменением основного ключа генератора JC; 3) сохранение нелинейности функционального преобразования. При соблюдении этих условий модифицированный генератор сохраняет свойства генератора, необходимые для использования в алгоритмах защиты информации.
Исследование влияния разработанного модуля на скорость передачи данных
В информационной безопасности практическое применение генераторов псевдослучайных последовательностей очень широко [36,41,77]. Можно предложить следующие способы применения генератора псевдослучайной последовательности: 1. Шифрование сообщений, передаваемых между двумя абонентами. У двух объектов, обменивающихся информацией, есть заданный алгоритм генератора ПСП и начальные данные для него. При установлении связи на обоих объектах запускается этот алгоритм и передаваемые данные гаммируются полученным N-ым псевдослучайным числом. О значении числа N (номере ПСП) можно договариваться заранее или передавать его по открытому каналу. Сам алгоритм генератора (его функциональные таблицы) и начальные данные для него должны передаваться по секретному каналу связи или устанавливаться заранее (например, жёстко прошиваться в приемо-передающей аппаратуре) [57]. Так как каждый сеанс связи проходит с использованием новой гаммы, а нарушитель не знает начальных установок генератора, то даже зная номер используемого псевдослучайного числа и алгоритм генератора ПСП, он не может получить открытый текст. Гаммирование характеризуется более высокой скоростью работы, чем другие более сложные алгоритмы шифрования (как асимметричные, так и симметричные), однако гораздо меньшей степенью криптостойкости при использовании одной и той же несменяемой гаммы. Этот недостаток и исправляется генератором ПСП, который служит для частой регулярной смены гаммирующей последовательности. При повышенных требованиях к защите информации полученную ПСП можно использовать в более сложных функциональных преобразованиях открытого текста. 2.
Организация виртуальных защищенных сетей. При использовании информационных технологий часто возникает необходимость связи двух компьютеров (сетей, оборудования и так далее) на больших расстояниях. Но при большом удалении связываемых объектов невозможно и дорого обеспечить безопасный канал связи, тогда как открытых каналов связи предостаточно (Интернет, телефонные линии, радиоканалы). Таким образом, необходимо обеспечить конфиденциальную передачу сетевых пакетов в открытой информационной среде. Одним из решений данной проблемы являются так называемые частные (защищенные) виртуальные сети (VPN — Virtual Private Network) [9, 37]. При этом между двумя узлами VPN образуется виртуальный защищенный канал связи. Физически этот канал является частью общедоступной информационной среды (например, Интернета), но все сетевые пакеты (IP-пакеты в случае с Интернетом), передаваемые между этими узлами, шифруются определенным алгоритмом с известным обоим узлам ключом. Этим алгоритмом может быть простое гаммирование с последовательностью, полученной с помощью двух синхронизируемых генераторов ПСП. При этом ДР-адреса при каждом сеансе связи также выбираются из доступного диапазона с помощью генератора. Данный способ применения является расширенным вариантом способа, описанного выше. 3. Генерация последовательностей для использования в более сложных алгоритмах шифрования. Во многих алгоритмах шифрования кроме ключа шифра используется дополнительная цифровая последовательность. В качестве этой последовательности вместо постоянной величины можно использовать результат работы генератора ПСП, что усиливает алгоритм шифрования. 4. Генерация ключей пользователей. В любой системе, нуждающейся в регулярной смене паролей (ключей) пользователей возможно введение так называемого Центра Управления Ключами (ЦУК). На нем по запросу происходит формирование ключа пользователя. Эта схема позволяет исключить использование коротких и «плохих» ключей пользователями. Кроме того, полученный от ЦУК ключ может быть использован в качестве начальной установки индивидуального генератора пользователя.
Это позволяет еще больше усилить секретность системы, а также разграничить ответственности ЦУК и конкретного пользователя. При использовании генераторов ПСП для шифрования данных основной проблемой является их синхронизация на удаленных объектах. Начальная установка и ключ могут задаваться заранее, прошиваться жестко или передаваться по закрытому каналу. Однако номер используемой последовательности или сигнал о переходе на следующую последовательность необходимо передавать по тому же каналу, что и зашифрованные данные. При этом необходимо исключать ошибки сбоя синхронизации, могущие привести к тому, что генераторы на разных устройствах будут выдавать разные последовательности. Это соответственно приведет к некорректной расшифровке данных. Можно предложить следующие способы синхронизации генераторов при использовании их для шифрования передаваемых данных: 1) по отдельному каналу или отдельным соединением по основному каналу передавать сигналы о номере используемой последовательности или сигналы о переходе на следующую последовательность.
Данный способ, однако, требует разработки специального протокола обмена, компенсирующего возможные задержки этих передаваемых сигналов. 2) синхронизация по существующему или дополнительно введенному полю пакета передаваемых данных. Этот способ более прост, но или требует вмешательство в структуру пакета, что недопустимо для уже существующих протоколов данных (например, TCP/IP), или требует разработки дополнительных алгоритмов для определения соответствия значения существующего поля пакета и номера используемой последовательности (именно этот способ был использован в практической реализации).
