Атака на ГПСЧ

Атака на генератор псевдослучайных чисел - атака, направленная на раскрытие параметров генератора псевдослучайных чисел (ГПСЧ) с целью дальнейшего предсказания псевдослучайных чисел.

Актуальность

Безопасность криптографических систем часто зависит от некоторых данных, которые должны быть известны лишь авторизованным пользователям, и которые должны быть трудно угадываемы для злоумышленника. Примерами таких данных могут быть сессионные ключи, инициализирующие вектора, соль, уникальные параметры в функциях ЭЦП и многие другие объекты. Чтобы достичь требуемого уровня непредсказуемости, при условии частой генерации случайных чисел, требуется надежный источник случайных чисел. К сожалению, многие криптографические приложения не обладают надежным источником случайных последовательностей значений, таких как, например, тепловой шум в электрических цепях или точное время между парой срабатываний счетчика Гейгера. Вместо этого приходится использовать генераторы псевдослучайных чисел (ГПСЧ). ГПСЧ получает на вход поток данных из источника с низкой энтропией и пытается его преобразовать в последовательность значений, практически неотличимую от настоящей случайной последовательности. Успешная атака на ГПСЧ может вскрыть многие криптографические системы независимо от того насколько тщательно они были спроектированы. Тем не менее некоторые системы используют плохо спроектированные ГПСЧ, или делают это таким образом, что уменьшает сложность атак. Более того, требуется лишь одно единственное успешное проникновение, чтобы скомпрометировать всю систему.

Типы атак на ГПСЧ

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

Прямая криптоаналитическая атака

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

Атаки, основанные на входных данных

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

Атаки с известными входными данными практически осуществимы в ситуациях, когда некоторые входные данные, предполагаемые проектировщиком системы как трудно предсказуемые, оказываются легко угадываемыми в некоторых частных случаях.

Атаки с воспроизводимыми входными данными могут использоваться в тех же ситуациях, но требуют менее сложных систем взлома и менее сложного анализа со стороны атакующего.

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

Атаки, основанные на вскрытии внутреннего состояния

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

Атака с обратной прокруткой использует вскрытое состояние ГПСЧ $S$ в момент времени $t_0$ с целью восстановления состояний ГПСЧ, а, соответственно, и его выходов в предыдущие моменты времени

Перманентное компрометирование состояния возможно для таких систем, в которых однажды раскрытое состояние $S$ в момент времени $t_0$ делает все предыдущие и последующие состояния уязвимыми для последующих атак

Атака итеративным угадыванием использует знание о состоянии $S$ в момент времени $t_0$, и промежуточные выходы ГПСЧ, чтобы узнать $S$ в момент времени $t_0 + \Delta t$, когда входы, собранные в течение этого периода времени, являются угадываемыми (но неизвестными) для атакующего.

Встреча по середине является по сути сочетанием атаки итеративным угадыванием и атаки с обратной прокруткой. Знание $S$ в моменты времени $t_0$ и $t_0 + 2\Delta t$ позволить злоумышленнику восстановить состояние $S$ в моменты времени $t_0 + \Delta t$, a так же во всем временном промежутке от $t_0$ до $t_0 + 2\Delta t$.

Примеры ненадежных систем

Ранние версии протокола шифрования SSL компании Netscape. Они использовали псевдослучайные числа, которые создавались ГПСЧ, источником энтропии которого выступали значения трех переменных: время суток, идентификатор процесса и идентификатор родительского процесса. Эти величины являются относительно предсказуемы, и имеют относительно низкую энтропию. Соответственно, данная версия SSL была признана небезопасной. Уведомление о проблеме Netscape получили от Филиппа Хэлам-Бэйкера в 1994 году, который тогда работал исследователем в Web команде CERN. Однако проблема не была решена вплоть до выпуска программного продукта. Позже, в 1995, о проблеме вновь заговорили Иан Голдберг и Дэвид А. Вагнер.^[1] Им пришлось подвергнуть объектные модули обратному инжинирингу, так как Netscape отказалась раскрыть детали генерации случайных чисел. ГПСЧ был исправлен в следующих выпусках (версия 2 и более поздние) изменением источника энтропии на более случайный и с более высоким уровнем энтропии.

Компания Microsoft использует неопубликованный алгоритм для генерации случайных чисел в операционных системах Windows. Пользователю этот алгоритм доступен через утилиту CryptGenRandom. В ноябре 2007, Лео Дорредорф вместе с соавторами из Хайфского университета и Еврейского университета в Иерусалиме опубликовал статью под названием Cryptanalysis of the Random Number Generator of the Windows Operating System^[2]. В статье продемонстрированы серьёзные недостатки алгоритма, представленного Microsoft. Выводы приведенные в статье были сформулированы в результате изучения дизасемблированного кода системы Windows 2000, но согласно заявлениям Microsoft, они так же могут относиться и к Windows XP.^[3]

Национальный институт стандартов и технологий (США) в марте 2007 опубликовал рекомендуемые "детерминированные генераторы псевдослучайных чисел", которые были стандартизованы в NIST Special Publication 800-90^[4]. Один из приведенных ГПСЧ, Dual EC DRBG, введенный в стандарт Агентством национальной безопасности^[5]. Dual EC DRBG основан на эллиптической криптографии и содержит определенный набор рекомендуемых констант. В августе 2007, Дэн Шумов и Нильс Фергесон из Microsoft показали, что константы могут быть подобраны таким образом, что может возникнуть бэкдор в алгоритме.^[6]

В мае 2008, исследователь Лучано Белло опубликовал свое открытие, в котором говорилось, что изменения сделанные в 2006 году в ГПСЧ в пакете openssl, распространяемым вместе с Debian Linux и остальными дистрибутивами, основанными на системе Debian, значительно уменьшает энтропию генерируемых значений, что делает ключи уязвимыми к атакам.[1] [2] Проблема была вызвана изменениями, сделанными одним из разработчиков Debian в коде openssl, в ответ на предупреждения от компилятора о, на первый взгляд, избыточном коде. Данная уязвимость в безопасности была устранена в тот же день, после того как о ней стало известно.^[7]

Способы защиты от атак на ГПСЧ

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

См. также

• Генератор псевдослучайных чисел

Примечания

1. ↑ Randomness and Netscape Browser
2. ↑ Cryptanalysis of the Random Number Generator of the Windows Operating System, Leo Dorrendorf
3. ↑ Microsoft confirms that XP contains random number generator bug
4. ↑ Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST Special Publication 800-90
5. ↑ Did NSA Put a Secret Backdoor in New Encryption Standard?
6. ↑ On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng
7. ↑ Debian OpenSSL Security Flaw

Литература

• Randomness and the Netscape Browser, Ian Goldberg and David Wagner, Dr. Dobb's Journal, January 1996, pp66–70.
• Cryptanalytic Attacks on Pseudorandom Number Generators, J. Kelsey, Bruce Schneier, David Wagner, and C. Hall, Fast Software Encryption, Fifth International Workshop Proceedings (March 1998), Springer-Verlag, 1998, pp. 168–188.
• Analysis of the Linux Random Number Generator Zvi Gutterman, Benny Pinkas and Tzachy Reinman, in IEEE S&P (Oakland Conference), May 2006, pp. 371–385.
• Randomness Requirements for Security. D. Eastlake, J. Schiller, S. Crocker, RFC 4086 (obsoletes RFC1750), 2006.
• Recommendation for Random Number Generation Using Deterministic Random Bit Generators, Elaine Barker and John Kelsey, NIST Special Publication 800-90. Revised March 2007