16.11 // Backdoor в генераторе псевдослучайных чисел NIST
Брюс Шнайер сообщает, что новый официальный стандарт по генераторам случайных чисел, предложенный NIST (NIST Special Publication 800-90), содержит уязвимость, которую можно расценивать как backdoor.
Дело в том, что одна из четырех конструкций ГСЧ, содержащихся в стандарте, а именно Dual_EC_DRBG на основе эллиптических кривых, использует некоторые предопределенные константы (метод получения которых нигде не указан). В свою очередь, эти константы соотносятся с неким секретным неизвестным набором чисел. Как показали на минувшей конференции CRYPTO-2007 Дэн Шумоу (Dan Shumow) и Нильс Фергюсон (Niels Ferguson), зная этот набор, можно полностью скомпрометировать полученные ключи. Самое интересное то, что функция эта целиком и полностью детище NSA.
Насколько реальна эта уязвимость? Зная этот секретный набор чисел, достаточно проследить всего 32 байта генератора случайных чисел (или, другими словами, всего одну сессию TLS), чтобы полностью реконструировать выход генератора и взломать ключ.
Следует уточнить, что вопросы и подозрения вызывает только медленная конструкция Dual_EC_DRBG, основанная на EC. Остальные ГСЧ, приведённые в NIST Special Publication 800-90 (а именно, построенные на хэш-функции, HMAC и блочном шифре), не подвержены уязвимости.
Источники: www.schneier.com, www.wired.com, www.linux.org.ru
комментариев: 1060 документов: 16 редакций: 32
Заметка на wired.com
Блог Шнайера
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 9796 документов: 488 редакций: 5664
Но существует, например, генератор Блюм-Блюм-Шуб (BBS), очень медленный, но стойкость которого доказуемо сводится к проблеме RSA. Было бы заманчиво создать нечто подобное, хотя бы чуть более быстрое. Это и сделали авторы генератора, используя проблему дискретного логарифма, а для относительного ускорения вычислений, выполняя операции на эллиптических кривых, вероятнее всего заодно и изящно встроив туда закладку или возможность её осуществления. Этот алгоритм позиционируется, как единственный, чья стойкость основана на трудных проблемах теории чисел, что должно было внушить большее к нему доверие. Хотя он давал плохие статистические результаты (не имеющие практического значения, но тем не менее статистические отклонения были выявлены, чем уже сразу вызвал подозрения).
Почему Шнайер обратил внимание на этот факт только сейчас, хотя конференция прошла летом? Потому что появилось сообщение об уязвимости в генераторе псевдослучайных чисел ОС Windows, который был реализован вообще не по стандарту (так же как и генератор Linux, который тоже содержит уязвимости). Шнайер хочет привлечь внимание к тому, что и открытые стандарты небезопасны, если авторы не предоставляют доказательств отсутствия лазеек, которые проще всего встроить в константы. Также ему хотелось бы узнать кто из работников NIST мог протащить решение от NSA.
В самом документе NIST приводятся имена консультантов от NSA (Mike Boyle, Paul Timmel, Debby Wallner), но не указано, что они разработали именно этот из четырёх генераторов, так что на это могли обратить внимание только те, кто следил за историей принятия документа. Теоретические работы, на основе которых создан этот генератор по ссылкам NIST написаны другими авторами (Nicholas Gurel, E. E. Mahassni, I. Shparlinski), есть также ссылки на предыдущие стандарты NIST по эллиптической криптографии, создаваемые по патентованным NSA алгоритмам (но об этом тоже ещё надо откуда-то узнать).
Документ NIST 800-90 выпустили Elaine Barker и John Kelsey. Именно они отвечали собственно за криптографический контент. Имена остальных авторов – это просто перечисление чиновников из NIST. Джон Келси – известный криптограф, совместно со Шнайером один из создателей блочного шифра Twofish.
"Раскрыли заговор" криптографы Dan Shumov и Niels Fergusson, являющиеся сотрудниками компании Microsoft. Нильс Фергюссон тоже известный криптограф, например по книге, выпущенной совместно со Шнайером. Они уклоняются от прямого заявления о закладке. Они только объективно расматривают вопрос о её лёгкой возможности осуществления в данном алгоритме.
Почему тогда в Windows плохой ГПСЧ? ГПСЧ Windows был написан до появления Фергюссона в компании Microsoft, кроме того, возможно, что Нильс реально там вообще ни на что не влияет, как это часто бывает со специалистами в крупных компаниях.
Введение в стандарт начинается со стандартного предупреждения, о том, что все стандарты и инструкции NIST могут быть предназначены только для адекватного обеспечения безопасности при минимальных требованиях и не могут быть использованы в системах национальной безопасности, что выделено в самом документе жирным цветом.
После попытки осмыслить все эти факты из которых ничего конкретного выйти не может и которые можно толковать как угодно, кроме того, что тут что-то подозрительно, приходит
в голову другая цитата, из киношного Мюллера, который всех "водил под колпаком":
комментариев: 9796 документов: 488 редакций: 5664
BSD это тоже касается?
Я где-то слышал, что в BSD /dev/random много качественнее, или это всё байки?
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 371 документов: 19 редакций: 20
Зря вы так категорично. Я был уже на 4м курсе института технической специальности, когда мне объясняли сокурсники, работающие в области коммуникаций, принцип асимметричного крипто. И чётко помню, что мне объяснли подряд раза 3 аттаку "человек посередине", потом я ещё подумал сам, и только потом понял... почему "мэллори" принципиально неизбежен в этой схеме... а следовательно либо сеть доверия либо сверка отпечатков по доверяемому каналу.
А что вы хотите от простых смертных?!
Это всё на самом деле не просто... просто когда знаешь :) С меня, вот, реферат по теме QKD (распределение квантового ключа) трясут, страниц на 15 обзор, а я во всём этом нуль немотря ни на познания в области quantum ни в области crypto. В этой ситуации ощущаю себя новчиком в области крипто, потому понимаю как другим, кто впервые со этим сталкивается...
Поидее нужно было бы ввеси общеобразовательный курс по теме "защита информации", и лучше – ещё в школе, где бы объяснялось как сохранить свою "самость" (от слова "сам") в этом мире :)
комментариев: 11558 документов: 1036 редакций: 4118
Эм, мы тут о бедных студентах или о гигантской корпорации с миллиардными оборотами?