ГЕНЕРАТОРЫ  СЛУЧАЙНЫХ  ЧИСЕЛ

Малышев  Максим  Вадимович

студент  3  курса,  кафедра  АТ  ПНИПУ,  РФ,  г.  Пермь

Е-mail:  ckdeliverance@gmail.ru

Как  известно,  ключ  —  одна  из  важнейших  частей  криптографии,  ни  один  процесс  шифрования  или  дешифрования  не  обходится  без  ключа.  Некоторые  ключи  присылаются  от  доверенного  источника,  например,  сервера  криптографических  ключей,  большинство  —  создаются  с  помощью  генератора  случайных  чисел.  При  этом  генерация  качественной  случайной  последовательности  является  неотъемлемой  и  самой  важной  частью  многих  криптографических  операций.  Для  создания  криптостойкого  ключа  с  помощью  генератора  необходимо  учитывать  множество  факторов,  таких  как  длина  ключа,  его  энтропия,  использование  истинно  случайных  и  псевдослучайных  чисел,  а  также  предусматривать  возможные  атаки  на  генератор.  Эти  моменты  делают  вопрос  исследования  и  создания  безопасного  генератора  случайных  чисел  довольно  важной  темой  в  области  криптографии.

Мера  случайности  называется  энтропией  —  мерой  неопределённости  источника  сообщения,  определяемой  вероятностями  появления  тех  или  иных  символов  при  их  передаче.  В  наборе  символов  из  n  битов  энтропия  m  —  число  битов,  в  значении  которых  нельзя  быть  уверенным.  Это  значит,  что  чем  больше  энтропия  в  генерируемой  последовательности,  тем  эта  последовательность  устойчивей  к  взлому.  Полностью  случайная  последовательность  называется  истинно  случайным  числом  и  определить  её  злоумышленник  может  только  перебором.

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

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

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

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

При  проведении  атак,  основанных  на  вскрытии  внутреннего  состояния,  злоумышленник  пытается  использовать  ранее  успешные  атаки  на  генератор  случайных  последовательностей,  вскрывшие  его  внутреннее  состояние,  с  целью  предсказания  состояния  дальнейших  или  предыдущих  состояний.  Такого  рода  атаки  могут  быть  успешны  в  том  случае,  когда  генератор  начинает  свою  работу  с  известного  или  предсказуемого  состояния.  На  практике  очень  сложно  определить  тот  факт,  что  внутреннее  состояние  было  скомпрометировано,  поэтому  противодействие  этим  атакам  имеет  особый  приоритет.  В  таких  атаках  используется  состояние  генератора  S  в  момент  времени  t₀,  в  зависимости  от  собранных  данных  и  уязвимости  генератора  злоумышленник  может  восстановить  предыдущие  состояния,  угадать  с  помощью  промежуточных  выходов  будущее  состояние  или  вычислить  данные  из  середины  временного  отрезка  с  помощью  крайних  значений.  Худшим  исходом  является  полное  компроментирование  генератора,  когда  однажды  раскрытое  S  создает  угрозу  нахождения  всех  прошлых  и  будущих  состояний  генератора. 

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

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

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

В-третьих,  необходимо  удовлетворять  «тесту  на  следующий  бит».  Смысл  теста  в  следующем:  не  должно  существовать  полиномиального  алгоритма,  способного  при  знании  первых  k  битов  случайной  последовательности  предсказать  (k+1)-ый  бит  с  вероятностью  более  50  %. 

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

В-пятых,  внутреннее  состояние  генератора  должно  периодически  полностью  меняться.  Это  поможет  защититься  от  атак,  основанных  на  вскрытии  внутреннего  состояния,  или,  по  крайней  мере,  уменьшит  урон,  нанесённый  успешной  атакой.

Примеры  успешных  генераторов:

·     ГПСЧ  стандарта  ANSI  X9.17  —  используется  в  PGP,  работает  на  тройном  DES,  энтропия  -  текущие  дата  и  время;

·     Fortuna  Брюса  Шнайера  —  гибкая  настройка  источников  энтропии;

·     Функция  CryptGenRandom  в  Microsoft  CryptoAPI  —  встроена  в  Windows,  является  стандартным  генератором  подобного  рода  для  среды  разработки  под  Win32:

·     Специальный  файл  ОС  UNIX  /dev/random,  в  частности,  /dev/urandom.  Есть  во  всех  Unix,  надёжный  источник  энтропии.

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

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

Список  литературы:

1. Атака  на  ГПСЧ  //  Википедия  —  свободная  энциклопедия.  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  https://ru.wikipedia.org/wiki/Атака_на_ГПСЧ  (дата  обращения:  12.05.2015).
2. Фергюсон  Н.,  Шнайер  Б.  [Ferguson  N.,  Schneier  B.]  Практическая  криптография:  пер.  с  англ.  М.:  Вильямс,  2005.