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

Для обеспечения криптографической стойкости системы мало использовать достаточно большие ключи, необходимо иметь криптостойкий генератор случайных чисел. Используя только программную часть невозможно построить генератор случайных чисел, программная реализация будет представлять собойгенератор псевдослучайных чисел. Для построения криптографически-стойкого ГСЧ необходимо использовать источники энтропии.

3.6.1 Источники энтропии. Существует множество процессов, которые ведут себя случайным образом. Например, младшие биты данных, полученных с АЦП-преобразователя будут всегда содержать фактически случайные значения. В данном проекте мы воспользуемся этим и будем считать АЦП – одним из источников энтропии. По прерыванию окончания АЦП-преобразования программа будет брать число, полученное в результате преобразования и преобразовывать его в один бит энтропии. Так же, если подключить на один вход микроконтроллера источник прямоугольных (вообще, не обязательно прямоугольных) импульсов, работающий на частоте, превышающей частоту микроконтроллера, то чтение состояния этого вывода в произвольные моменты времени будет эквивалентно чтению случайного значения, однако мы не будем надеятся на истинную случайность этих данных и состояние этого вывода будет складываться по модулю два с одним битом энтропии, полученным с АЦП-преобразователя.

Таким образом, каждый раз, когда происходит прерывание АЦП, мы получаем один бит энтропии. Было бы очень неплохо добавить дополнительные источники энтропии, и это не сложно, однако в данной курсовой работе этот вопрос опускается.

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

Генератор псевдослучайных чисел. Истинно случайные числа будут использоваться нами только для того, чтобы получить начальное число, подающееся на вход генератора псевдослучайных чисел. После того как у нас появится начальное число, генератор сможет произвести на свет любое нужное количество случайных (а точнее, псевдослучайных) чисел. При необходимости мы можем прибавлять истинно случайные числа к начальному числу генератора псевдослучайных чисел. Это гарантирует, что выходные данные последнего никогда не станут полностью предсказуемыми, даже если злоумышленник каким-либо образом узнает начальное число.

Существует теоретическое мнение, что истинно случайные числа лучше, чем псевдослучайные. Для некоторых криптографических протоколов можно доказать, что при использовании истинно случайных чисел определенные типы атак становятся невозможными. Такой протокол называется безусловно защищенным (unconditionally secure). Если же использовать генератор псевдослучайных чисел, протокол будет безопасным только при условии, что злоумышленник не сможет взломать этот генератор случайных чисел.

Такой протокол называется защищенным по вычислениям (computationally secure). Это различие, однако, не совсем обоснованно. Все криптографические протоколы почти всегда основаны на вычислительных приближениях. Устранение такого приближения для одного конкретного типа атак не принесет существенного улучшения. Более того, генерация истинно случайных чисел, необходимых для обеспечения безусловной защищенности, настолько сложна, что попытка использовать такие числа может только ухудшить безопасность системы.

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

3.6.3 Программный пул. Пул – программный блок памяти, осуществляющий накопление случайных данных перед их использованием в генераторе псевдо случайных чисел.

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

3.6.4 RC4. RC4 – потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах SSL и TLS, алгоритме безопасности беспроводных сетей WEP).

Алгоритм RC4, как и любой потоковый шифр, строится на основе параметризованного ключом генератора псевдослучайных битов с равномерным распределением. Длина ключа составляет от 40 до 2048 бит.

Основные преимущества шифра – высокая скорость работы и переменный размер ключа. RC4 довольно уязвим, если используются не случайные или связанные ключи, один ключевой поток используется дважды. Эти факторы, а также способ использования могут сделать криптосистему небезопасной.

Внутреннее состояние RC4 представляется в виде массива размером 2ⁿ и двух счётчиков. Массив известен как S-блок, и далее будет обозначаться как S. Он всегда содержит перестановку 2ⁿ возможных значений слова. Два счётчика обозначены через i и j.

Инициализация RC4 состоит из двух частей: инициализация S-блока и генерация псевдослучайного слова K.

Ядро алгоритма поточных шифров состоит из генератора гаммы, который выдаёт ключевой поток (гамму). Функция генерирует последовательность битов (k_i), которая затем объединяется с открытым текстом (m_i) посредством суммирования по модулю два. Так получается шифрограмма (c_i).

Однако в данном проекте RC4 будет использоваться не как потоковый шифр, а как генератор псевдослучайной последовательности. Гамма, выдаваемая алгоритмом непосредственно является этой последовательностью. Любой криптографический шифр будь то блочный или поточный обязан иметь такую гамму, чтобы каждый следующий бит невозможно было предсказать и на самом деле между ГПСЧ и поточным шифров нет никакой разницы, оба эти понятия взаимозаменяемы. Мы лишь немного модифицируем алгоритм RC4, чтобы ускорить его работу и интегрируем его в нашу систему, добавив функцию перемешиванияrc4update.

Устройство постоянной памяти. Как уже упоминалось выше генератору псевдослучайных чисел необходимо иметь устройство постоянной памяти для хранения своего состояния между запусками системы. В данной системе в качестве такого устройства будет использоваться встроенная память eeprom микроконтроллера AtMega8.

Так как память такого типа имеет ограниченное число циклов перезаписи, мы не должны сохранять состояние ГПСЧ слишком часто, поэтому встаёт вопрос. Когда мы должны сохранять состояние? В течении работы всей системы нет необходимости в сохранении состояния. Необходимость возникает после того, как система заканчивает свою работу, поэтому модуль генератора случайных чисел должен уметь узнавать когда главный модуль заканчивает свою работу. Поэтому в протокол связи модулей было введено дополнительное условие. Если главный модуль отправляет на генератор число 2, генератор случайных чисел считает это кодом завершения и останавливает свою работу. Число 2 задано в коде в виде изменяемой константы, поэтому при необходимости его можно заменить на другое число.

Это работает должным образом по одной простой причине. Главный модуль никогда не запрашивает у генератора блок случайных чисел меньше, чем 32, за подобные запросы отвечает функция crandom из модуля main.c, данная функция будет рассмотрена позже. То есть номера запросов от нуля до 31 являются зарезервированными для служебных команд, таких, как например выключение микроконтроллера. Так как выбранный микроконтроллер поддерживает интерфейс SPI, в проектируемую систему был добавлен модуль часов реального времени, что позволяет инициировать внутреннее состояние генератора случайных чисел в зависимости от времени, когда он был запущен. Так при отказе в работе источников энтропии, генератор продолжит генерацию случайных данных, так как основан на достаточно надёжном генератор псевдо случайных чисел, который при каждом запуске системы будет генерировать различные случайные данные, инициализируя своё состояние, основываясь на часах реального времени.