Атака на ГПСЧ

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

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

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

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

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

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

Если атакующий способен напрямую отслеживать выходные данные ГПСЧ и исследовать закономерность их появления, то это является прямой криптоаналитической атакой. Этот вид атаки распространяется на большинство алгоритмов, использующие ГПСЧ. Однако если, например, ГПСЧ используется исключительно для генерации ключа, как сделано в 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 году, который тогда работал исследователем в CERN. Однако проблема не была решена вплоть до выпуска программного продукта. Позже, в 1995 году, о проблеме вновь заговорили Иан Голдберг и Дэвид А. Вагнер. Им пришлось подвергнуть объектные модули обратному инжинирингу, так как Netscape отказалась раскрыть детали генерации случайных чисел. ГПСЧ был исправлен в следующих выпусках (версия 2 и более поздние) изменением источника энтропии на более случайный и с более высоким уровнем энтропии.

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

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

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

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

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

См. также

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

Литература

• Randomness and the Netscape Browser, Ian Goldberg and David Wagner, Dr. Dobb’s Journal, January 1996, pp66-70.
• Kelsey J., Schneier B., Wagner D. A., Hall C. Cryptanalytic Attacks on Pseudorandom Number Generators (англ.) // Fast Software Encryption: 5th International Workshop, FSE’ 98 Paris, France, March 23–25, 1998 Proceedings / S. Vaudenay — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 1998. — P. 168—188. — (Lecture Notes in Computer Science; Vol. 1372) — ISBN 978-3-540-64265-7 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-69710-1_12
• 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