Aris Adamantiadis, исследователь безопасности из Бельгии, развивающий проект libssh, опубликовал рабочий прототип приложения, подтверждающего теорию о возможном наличии бэкдора в алгоритме генерации псевдослучайных чисел Dual EC DRBG, до недавних пор входящим в стандарт NIST SP 800-90 и использованном по умолчанию в продуктах Bsafe и RSA Data Protection Manager от компании RSA.

Алгоритм Dual EC DRBG, описывающий способ генерации псевдослучайных чисел на основе методов криптографии по эллиптическим кривым, был разработан и продвинут в состав стандарта Агентством национальной безопасности США (АНБ). Теоретические опасения о возможных проблемах в Dual_EC_DRBG были опубликованы ещё в 2007 году, но всерьёз они насторожили общественность лишь в сентябре 2013 года, после публикации Эдвардом Сноуденом материалов, свидетельствующих о работе АНБ по внедрению бэкдора, кардинально упрощающего предсказание генерируемых через Dual_EC_DRBG последовательностей.

После появления этих сведений компания RSA и Национальный институт стандартов и технологий США (NIST) выпустили рекомендации не использовать Dual_EC_DRBG. В декабре появились новые материалы, указывающие на заключение секретного контракта между АНБ и RSA, размером в 10 млн долларов, подразумевающего применение Dual_EC_DRBG в качестве алгоритма по умолчанию в Bsafe.

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

Aris Adamantiadis сумел успешно продемонстрировать возможность предсказывать выдаваемые на выходе значения, используя лишь одну изменённую константу в Dual_EC_DRBG. Весь код и инструкции, позволяющие повторить эксперимент, опубликованы на GitHub. Параметры генерации констант, указанных в стандарте NIST, остаются известны только АНБ. При этом данные константы обязательны для использования в неизменном виде при прохождении сертификатции по FIPS 140-2.

   aris@kalix86:~/dualec$ ./dual_ec_drbg_poc
   s at start of generate:
   E9B8FBCFCDC7BCB091D14A41A95AD68966AC18879ECC27519403B34231916485
   [omitted: many output from openssl]
   y coordinate at end of mul:
   0663BC78276A258D2F422BE407F881AA51B8D2D82ECE31481DB69DFBC6C4D010
   r in generate is:
   96E8EBC0D507C39F3B5ED8C96E789CC3E6861E1DDFB9D4170D3D5FF68E242437
   Random bits written:
   000000000000000000000000000000000000000000000000000000000000
   y coordinate at end of mul:
   5F49D75753F59EA996774DD75E17D730051F93F6C4EB65951DED75A8FCD5D429
   s in generate:
   C64EAF10729061418EB280CCB288AD9D14707E005655FDD2277FC76EC173125E
   [omitted: many output from openssl]
   PRNG output:  ebc0d507c39f3b5ed8c96e789cc3e6861e1ddfb9d4170d3d5ff68e242437449e
   Found a match !
   A_x:  96e8ebc0d507c39f3b5ed8c96e789cc3e6861e1ddfb9d4170d3d5ff68e242437
   A_y: 0663bc78276a258d2f422be407f881aa51b8d2d82ece31481db69dfbc6c4d010
   prediction: a3cbc223507c197ec2598e6cff61cab0d63a89a68ccffcb7097c09d3
   Reviewed 65502 valid points (candidates for A)
   PRNG output: a3cbc223507c197ec2598e6cff61cab0d63a89a68ccffcb7097c09d3