Журнал "Information Security/ Информационная безопасность" #4, 2019

Национальный институт стандартов и технологий США – (англ. The National Institute of Standards and Tech- nology, NIST). Официальная задача института – "продви- гать инновационную и инду- стриальную конкурентоспо- собность США путем разви- тия наук об измерениях, стан- дартизации и технологий с целью повышения экономи- ческой безопасности и улуч- шения качества жизни". Вме- сте с Американским нацио- нальным институтом стандар- тов (ANSI) участвует в разра- ботке стандартов и специфи- каций к программным реше- ниям, используемым как в государственном секторе США, так и имеющим ком- мерческое применение. https://ru.wikipedia.org Джон Келси – Дону Джонсону: "Знаете ли вы, откуда взялось Q в Dual_EC_DRBG?" Дон Джонсон – Джону Келси: "P = G.Q, по сути, открытый ключ для некото- рого случайного закрытого ключа. Кроме того, Q может быть получена как еще одна каноническая точка G, но АНБ отвергло эту идею и запретило мне это публично обсуждать…" процессом стандартизации генераторов случайных чисел. При этом изначальная версия стандарта ISO, за которую про- голосовало 19 стран из 24, не содержала генератора Dual EC. Было получено более 150 ком- ментариев, но большинство из них были незначительными исправлениями и пояснениями. Участники голосования выска- зывали те или иные замечания и уточнения к проекту стандар- та, комментируя его отдельные пункты и формулировки. Со стороны США не было конкрет- ных замечаний, был только общий комментарий "ко всему документу", в котором говори- лось, что текущая версия стан- дарта "не обладает достаточной глубиной" 1 . В качестве альтер- нативы ISO был предложен аме- риканский стандарт ANSI X9.82, как "более тщательно прорабо- танный" 2 . В результате США, по сути, навязали ISO свою вер- сию стандарта, включающую Dual EC, которая в итоге и была принята [7]. Параллельно с процессом продвижения Dual EC шел про- цесс его критики со стороны независимых экспертов. В авгу- сте 2007 г. на конференции CRYPTO-2007 сотрудники Mic- rosoft Дэн Шумов и Нильс Фер- гюсон продемонстрировали воз- можность существования лазей- ки в Dual EC [8]. В этом алго- ритме при генерации случайных чисел используются две точки эллиптической кривой: P и Q. С помощью точки P задается внутреннее состояние генера- тора, а точка Q используется для вычисления выхода гене- ратора. Если известна связь между точками P и Q (т.е. такое число d, что Q = d • P), то по нескольким известным значе- ниям выхода можно вычислить текущее внутреннее состояние генератора, а значит, можно предсказать все последующие генерируемые им числа 3 . В стандарте точки P и Q зада- ны. Поскольку задача дискрет- ного логарифмирования являет- ся вычислительно трудной, то найти такое d, что Q = dP, на данный момент невозможно. Но дело в том, что эти точки зада- ны авторами стандарта, а они могли изначально выбрать число d, а затем вычислить точку Q как dP. Подобное пред- положение подтверждается и следующей перепиской между Дж. Келси и Д. Джонсоном, которую приводят авторы статьи [18], посвященной исто- рии Dual EC (рис. 1). По сути, в ней говорится, что мы имеем дело с асимметричным SETUP- механизмом в структуре Dual EC, при этом Q играет роль открытого ключа SETUP-меха- низма, а d – роль секретного ключа [1]. Таким образом, наличие ука- занной скрытой лазейки в алго- ритме Dual EC в принципе воз- можно, хотя ни доказать, ни опровергнуть ничего нельзя. Из приведенной выше пере- писки видно еще одно немало- важное обстоятельство – роль АНБ в разработке и принятии стандарта Dual EC. Ни в одном из первоначальных материалов, посвященных нашему стандар- ту, не указан его автор или раз- работчик. Официальная публи- кация NIST, содержащая, наря- ду с другими генераторами псевдослучайных чисел, и алго- ритм Dual EC, имеет офици- альных авторов – Элейн Баркер (Elaine Barker) и Джон Келси (John Kelsey), оба сотрудники NIST. В то же время существуют многочисленные подтвержде- ния того, что ни Келси, ни Бар- кер не были разработчиками Dual EC, более того, они даже не чувствовали себя компетент- ными давать комментарии по поводу Dual EC, отсылая по этому поводу к сотрудникам АНБ, например, переписка между Э. Баркер и М. Кампанья (рис. 2), приведенная в [18]. Вскоре после конференции, в ноябре 2007 г., вышла раз- громная статья Брюса Шнайера [9], в которой он советовал ни при каких обстоятельствах не использовать генератор Dual EC, тем более что и в стандар- тах NIST, и в ISO есть альтер- нативы. Другой способ избежать воз- можной закладки в Dual EC – это выработать собственные точки P и Q и запускать генера- тор с этими новыми значения- ми. Формально NIST разрешил • 37 КРИПТОГРАФИЯ www.itsec.ru Рис. 1. Электронная переписка между Дж. Келси и Д. Джонсоном от 27.10.2004 [18] 1 We feel that this document is lacking sufficient depth in many areas and simply is not developed enough to be an ISO standard… [10]. 2 We do feel that ANSI X9.82 Random Bit Generation standardization work is much further developed and should be used as the basis for this ISO standard [10]. 3 Детально принцип работы генератора DUAL_EC_DRBG и механизм лазейки будет разобран в разделе 2.