Dual EC DRBG

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Dual_EC_DRBG — алгоритм генерации псевдослучайных чисел, разработанный Агентством национальной безопасности США. Алгоритм основан на использовании эллиптических кривых. Это один из четырёх ГПСЧ, стандартизованных в NIST Special Publication 800-90 в 2006 году.[1]

Вскоре после публикации NIST, было высказано предположение, что данный ГПСЧ содержит бэкдор.[2][3]

Содержание

Безопасность [править]

Dual_EC_DRBG был добавлен в NIST SP 800-90, поскольку его работа основана на сложной проблеме теории чисел - Decision Diffie-Hellman problem (англ.)русск.. Он отличался от других трех алгоритмов в стандарте тем, что был медленнее них на три порядка. Однако, для криптографических применений безопасность ГПСЧ очень важна и допустимо использовать более медленные алгоритмы.

После публикации алгоритма Dual_EC_DRBG появилось несколько отчетов, анализирующих его уязвимости[4][5][6] [7]

По мнению Шнайера, он был добавлен в стандарт только благодаря поддержке со стороны NSA.[2]

Критика [править]

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

Dan Shumow и Niels Ferguson из Microsoft выступили в августе 2007 года на конференции CRYPTO 2007 и заявили, что один из недостатков алгоритма сводит его к решению единичной проблемы дискретного логарифмирования (на ЭК), и автор алгоритма, гипотетически, мог бы иметь решение этой проблемы. Они заметили, что в определении Dual EC DRBG не сказано о происхождении набора констант, определяющего эллиптическую кривую для алгоритма. Они показали, что для этого набора существует связанная с ними секретная константа, которая позволяет предсказывать вывод алгоритма после сбора всего 32 сгенерированных байт.[8] По оценке Шнайера это можно описать только как бэкдор ("черный ход"). [2][3]

Применение [править]

Алгоритм был включен в Windows Vista пактом обновлений SP1. [9][10] По умолчанию он выключен.[11]

Реализован в Windows 7[12] в модуле CNG.SYS и функции BCryptGenRandom.[13]

Также реализован в OpenSSL:[14]

Стандарт NIST SP 800-90 полностью одобрен по FIPS 140-2[15]

Интересные факты [править]

  • Вероятно, является наиболее распространенным теоретико-числовым генератором псевдослучайных чисел. [16]

Примечания [править]

  1. ↑ (2007-03) «Recommendations for Random Number Generation Using Deterministic Random Bit Generators (Revised)» (PDF) (National Institute of Standards and Technology). NIST SP 800-90.
  2. ↑ 1 2 3 Брюс Шнайер. Did NSA Put a Secret Backdoor in New Encryption Standard?, Wired News (15 ноября 2007).
  3. ↑ 1 2 Киви Берд, Неслучайные случайности // Компьютерра, 07 декабря 2007
  4. ↑ Kristian Gjøsteen. Comments on Dual-EC-DRBG/NIST SP 800-90
  5. ↑ Daniel R. L. Brown (2006). «Conjectured Security of the ANSI-NIST Elliptic Curve RNG».
  6. ↑ Daniel R. L. Brown and Kristian Gjøsteen. A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator, CRYPTO 2007, LNCS 4622, Springer, pp. 466-481. IACR ePrint version
  7. ↑ Berry Schoenmakers and Andrey Sidorenko. Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, IACR ePrint 2006/190.
  8. ↑ Dan Shumow, Niels Ferguson,On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng, CRYPTO 2007, august 2007
  9. ↑ В Windows Vista добавлен шпионский модуль? // Правда.Ру, 20.12.2007
  10. ↑ http://www.securitylab.ru/news/310128.php Windows Vista будет работать на спецслужбы США? 20 декабря, 2007
  11. ↑ Dual_EC_DRBG Added to Windows Vista, December 17, 2007
  12. ↑ DRBG Validation List // NIST: "24.. Windows 7 CNG algorithms .. Dual_EC_DRBG"
  13. ↑ Microsoft Windows 7 Kernel Mode Cryptographic Primitives Library (cng.sys) Security Policy Document // Microsoft, NIST, January 25, 2012
  14. ↑ http://www.openssl.org/docs/fips/SecurityPolicy-2.0.pdf "4. Modes of Operation and Cryptographic Functionality ... FIPS 140-2 Approved mode. Random Number Generation; ... Dual EC DRBG: P-256, P-384, P-521"
  15. ↑ Annex C: Approved Random Number Generators for FIPS PUB 140-2, Security Requirements for Cryptographic Modules, February 16, 2012
  16. ↑ Random number generation: An illustrated primer, February 21, 2012: "If you like standards, NIST also has a proposal called Dual-EC-DRBG. Dual-EC is particularly fascinating, for the following three reasons. First, it's built into Windows, which probably makes it the most widely deployed number-theoretic PRG in existence."


Замок Это заготовка статьи по криптографии. Вы можете помочь проекту, исправив и дополнив её.
Источник — «http://ru.wikipedia.org/w/index.php?title=Dual_EC_DRBG&oldid=53297789»