Dual EC DRBG

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

Dual_EC_DRBG (от англ. Dual Elliptic Curve Deterministic Random Bit Generator) — алгоритм генерации псевдослучайных чисел, разработанный Агентством национальной безопасности США, один из четырёх криптографически стойких генераторов, стандартизованных NIST как «Special Publication 800-90» (NIST SP 800-90A (англ.)русск.) в 2006 году[1]. Предполагалось его применение в том числе в криптографических системах для генерации ключей. Алгоритм основан на использовании эллиптических кривых.

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

В сентябре 2013 года в прессе появилась разоблачающая публикация Эдварда Сноудена на тему внедрения бэкдоров в стандарты шифрования[4], в которой явно указывалось на некий стандарт NIST 2006 года[5]. Спустя несколько дней NIST вернул на публичное обсуждение и рецензирование стандарт SP 800-90, описывающий алгоритм Dual EC DRBG[6] и призвал прекратить использование алгоритма Dual EC DRBG в том виде, как он был определен в оригинальном стандарте.[7]

20 декабря 2013 года стало известно о факте взятки, выданной АНБ США известной компании RSA Security (англ.) (в настоящий момент — подразделение EMC)[8][9]. В обмен на крупную сумму денег, компания RSA обязывалась использовать генератор Dual_EC_DRBG как предпочтительный и по умолчанию в своих криптографических библиотеках семейства RSA bsafe.

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

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

Вскоре после публикации алгоритма Dual_EC_DRBG появилось несколько отчетов, анализирующих его уязвимости[11][12][13][14].

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

Критика[править | править вики-текст]

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

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

В декабре 2013 года был представлен концептуальный демонстратор бэкдора (использовались измененные константы, для которых имеется соответствующий набор секретных констант)[16][17].

Применение[править | править вики-текст]

Алгоритм вошел в состав ОС Windows начиная с версии Windows Vista с пакетом обновлений SP1.[18][19]

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

Также реализован в OpenSSL,[22] однако из-за программной ошибки никогда не использовался[23][24].

Стандарт NIST SP 800-90 полностью одобрен по FIPS 140-2[25]. Для сертификации программных реализаций по FIPS 140-2 в них в обязательном порядке должны использоваться параметры, заданные в стандарте NIST.[24]

Некоторые продукты компании RSA Security (укр.)русск. используют Dual EC DRBG по умолчанию с 2004 года,[26][27] в частности, библиотеки семейства RSA BSAFE: Crypto-J и Crypto-C, SSL-C, SSL-J, Cert-C, Cert-J, а также решения RSA Data Protection Manager (DPM). Лишь осенью 2013 года компания призвала пользователей не пользоваться алгоритмом.[28][29][30] В декабре 2013 года Рейтер сообщило, что АНБ тайно заплатила компании RSA 10 миллионов долларов, чтобы та использовала Dual EC DRBG по умолчанию[31][32].

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

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

Примечания[править | править вики-текст]

  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). Архивировано из первоисточника 19 сентября 2012.
  3. 1 2 Киви Берд, Неслучайные случайности // Компьютерра, 07 декабря 2007
  4. James Ball, Julian Borger, Glenn Greenwald. Revealed: how US and UK spy agencies defeat internet privacy and security, The Guardian (5 сентября 2013). «security experts have long suspected that the NSA has been introducing weaknesses into security standards, a fact confirmed for the first time by another secret document. It shows the agency worked covertly to get its own version of a draft security standard issued by the US National Institute of Standards and Technology approved for worldwide use in 2006.».
  5. Government Announces Steps to Restore Confidence on Encryption Standards // The New-York Times, 2013-09-10: «The Times reported that as part of its efforts, the N.S.A. had inserted a back door into a 2006 standard adopted by N.I.S.T. and later by the International Organization for Standardization»
  6. NIST. DRAFT SP 800-90 Series: Random Bit Generators (9 сентября 2013). «In light of recent reports, NIST is reopening the public comment period for Special Publication 800-90A and draft Special Publications 800-90B and 800-90C. NIST is interested in public review and comment to ensure that the recommendations are accurate and provide the strongest cryptographic recommendations possible.».
  7. RSA Tells Its Developer Customers: Stop Using NSA-Linked Algorithm // Wired, 2013-09-19: о документе Supplemental ITL Bulletin for September 2013: «NIST strongly recommends that, pending … the re-issuance of SP 800-90A, the Dual_EC_DRBG, as specified in the January 2012 version of SP 800-90A, no longer be used.» (копия)
  8. Joseph Menn. Exclusive: Secret contract tied NSA and security industry pioneer, Reuters (20.12.2013). «the U.S. National Security Agency arranged a secret $10 million contract with RSA, one of the most influential firms in the computer security industry».
  9. Security firm RSA took millions from NSA: report The National Security Agency paid $10 million to the security firm RSA to implement intentionally flawed encryption, according to a new report.  (англ.), CNet (December 20, 2013). Проверено 22 декабря 2013. «"Now we know that RSA was bribed," said security expert Bruce Schneier,».
  10. 1 2 Bruce Schneier. The Strange Story of Dual_EC_DRBG (англ.) (November 15, 2007). Проверено 4 января 2014.
  11. Kristian Gjøsteen. Comments on Dual-EC-DRBG/NIST SP 800-90
  12. Daniel R. L. Brown (2006). «Conjectured Security of the ANSI-NIST Elliptic Curve RNG».
  13. 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
  14. Berry Schoenmakers and Andrey Sidorenko. Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, IACR ePrint 2006/190.
  15. Dan Shumow, Niels Ferguson, On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng, CRYPTO 2007, august 2007
  16. Dual_EC_DRBG backdoor: a proof of concept (31/12/13). Проверено 4 января 2014.
  17. Опубликован прототип бэкдора в генераторе псевдослучайных чисел Dual_EC_DRBG, входившем в стандарт NIST // Opennet.ru 01.01.2014
  18. В Windows Vista добавлен шпионский модуль? // Правда. Ру, 20.12.2007
  19. http://www.securitylab.ru/news/310128.php Windows Vista будет работать на спецслужбы США? 20 декабря, 2007
  20. DRBG Validation List // NIST: «24.. Windows 7 CNG algorithms .. Dual_EC_DRBG»
  21. Microsoft Windows 7 Kernel Mode Cryptographic Primitives Library (cng.sys) Security Policy Document // Microsoft, NIST, January 25, 2012
  22. 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»
  23. Worried OpenSSL uses NSA-tainted crypto? This BUG has got your back. Discovered software blunder disabled distrusted random number generator  (англ.), The Register (20th December 2013). Проверено 21 декабря 2013.
  24. 1 2 Steve Marquess. Flaw in Dual EC DRBG (no, not that one) (англ.). OpenSSL Foundation (19 December 2013). — «if you want to be FIPS 140-2 compliant you MUST use the compromised points.»  Проверено 21 декабря 2013.
  25. Annex C: Approved Random Number Generators for FIPS PUB 140-2, Security Requirements for Cryptographic Modules, February 16, 2012
  26. RSA, The Security Division of EMC. RSA Response to Media Claims Regarding NSA Relationship (англ.). EMC (December 22, 2013). Проверено 23 декабря 2013.
  27. Competitiveness impacts from BSAFE & Dual_EC_DRBG? (Jan 2, 2014). — «RSA decided to use it as the default PRNG for the BSAFE tookit [edit 1/2/14: according to their statement on the topic, this was in 2004].»  Проверено 4 января 2014.
  28. RSA Tells Its Developer Customers: Stop Using NSA-Linked Algorithm // Wired, 2013-09-19: «The currently released and supported versions of the BSAFE libraries (including Crypto-J 6.1.x and Crypto-C ME 4.0.x) and of the RSA DPM clients and servers use Dual EC DRBG as the default PRNG»
  29. Stop using NSA-influenced code in our products, RSA tells customers. Firm «strongly recommends» customers stop using RNG reported to contain NSA backdoor. // Ars Technica
  30. АНБ перечислило $10 млн RSA для принятия стандарта на уязвимый ГСЧ // Хакер, 23.12.2013
  31. Report: NSA paid RSA to make flawed crypto algorithm the default The NSA apparently paid RSA $10M to use Dual EC random number generator.  (англ.), ARSTechnica (Dec 20, 2013). Проверено 21 декабря 2013.
  32. Exclusive: Secret contract tied NSA and security industry pioneer  (англ.), Reuters (Dec 20, 2013). Проверено 21 декабря 2013.
  33. 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.»

Ссылки[править | править вики-текст]