Dual EC DRBG

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

У стандарті NIST SP 800-90A, в описі алгоритму використовуються 2 функції:^{[2] [3]}

• φ(a) - функція, що перетворює ціле число в бінарну послідовність
• x(A) - функція, що повертає x-координату точки A

Хід роботи:

1) Задається випадкове значення t = randomseed()

2) У циклі виконуються операції:

1. Обчислюється значення s = φ ( x ( t * P ) )
2. Обчислюється значення r = φ ( x ( s * Q ) )
3. Обрізаються старші 2 байти r
4. Отримання 30 байтів r
5. t = s

Безпеку Dual_EC_DRBG засновано на складній проблемі теорії чисел — проблема Діффі-Гелмана. Це було заявленою причиною включення до NIST SP 800-90.^[2] Проте виробники генератора не опублікували математичного доказу безпеки генератора, і після публікації проекту NIST було показано, що Dual_EC_DRBG не є безпечним через те, що на виході отримується велика кількість бітів за раунд.^[4][5] Якщо використовувати точки еліптичної кривої, що задано у стандарті, то через завелику кількість бітів на виході створюється можливість бекдору, що дає можливість зловмиснику зламати генератор повним перебором. Цю проблему не було виправлено в остаточно опублікованому стандарті, залишивши Dual_EC_DRBG небезпечним.^[6]

У багатьох інших стандартах константи, які повинні бути довільними, вибираються принципом Nothing sleeve up my number. У Dual_EC_DRBG виробники не вказали як задаються константи - точки еліптичної кривої P і Q. Оскільки комітет про стандартизацію був обізнаний про можливий бэкдор, до стандарту було включено спосіб отримання своїх констант P і Q.^[7][8] Але точне формулювання в стандарті було написане так, що використання P і Q, наданих у стандарті, потрібне для проходження перевірки FIPS 140-2, тому в OpenSSL були реалізовані саме ці константи, незважаючи на обізнаність про бэкдор і бажання використовувати більш надійні параметри.^[9] New York Times пізніше написала, що АНБ працювала під час процесу стандартизації так, щоб у кінцевому підсумку стати єдиним редактором стандарту.^[10]

Через деякий час, Деніел Браун і Крістіан Гьєстін [Архівовано 8 березня 2018 у Wayback Machine.] опублікували доказ безпеки Dual_EC_DRBG, в якому було показано, що сформовані точки еліптичної кривої будуть відрізняються від випадкових, якщо  :

1. на виході буде менша кількість біт за раунд
2. точки P і Q будуть незалежні
3. наступні три проблеми будуть належати класу NP:
   • проблема Діффі-Гелмана
   • проблема дискретного логарифмування
   • проблема усіченої точки

Dual_EC_DRBG є досить повільним генератором в порівнянні з альтернативними генераторами, включеними в той же стандарт, однак ці альтернативи не мають доказів безпеки.^[11] Деніел Браун стверджує, що, завдяки доведення безпеки, генератор можна використовувати, незважаючи на швидкість його роботи, при умові, що використані надійні параметри.^[11]

Передбачуваний бекдор дозволяє зловмисникові визначити внутрішній стан генератора випадкових чисел після перегляду виходу одного раунду розміром 30 байт. Всі майбутні вихідні дані генератора випадкових чисел можуть бути легко пораховані, поки зовнішній джерело ентропії не перезавантажить генератор з новим значенням t₀ . Наприклад, використання цього генератора робить небезпечним SSL / TLS, оскільки встановлення SSL-з'єднання включає в себе відправлення випадково згенерованого кількості у відкритому вигляді. Бекдор полягає в тому, що при використанні констант P і Q стандарту, АНБ знає таке e, e * Q = P.^[12] Таким чином, e є секретним ключем, імовірно відомим АНБ, а передбачуваний бекдор є клієнтографічним прихованим бекдором.^[13]

Перший висновок 30 байт r₀ - це x - координата точки без початкових 16 біт. Для кожної кривої, заданої в стандарті, написані значення X нуля і однієї або двох точок на кривій. Таким чином, потрібно повністю перебрати не більше 17 біт для відновлення вихідної точки A.^[3]

1. Відома точка A, а отже і відомо твір s₀ * Q дорівнює A
2. Відомий секретний ключ e, який задає співвідношення P = e * Q

То домножив кожну сторону рівняння s₀ * Q = A на e виходить:

e * A = s₀ * e * Q = s₀ * P ^[3]

Виходячи з цього, є можливість порахувати s₁ = φ ( x ( e * A) ), а потім і r₁, потім і наступні s₂,...,s_n і r₂,...,r_n. Для цього потрібно лише повним перебором знайти A, помножити отримане A e, потім помножити отримане значення Q і вивести значення координати x отриманої точки без перших двох байт.^[3]

АНБ вперше представила Dual_EC_DRBG в ANSI X9.82 DRBG на початку 2000-х років, включаючи параметри, що забезпечують бекдор, і в проекті стандарту ANSI був опублікований Dual_EC_DRBG. Так само він був доданий в стандарт ISO 18031.^[7] Принаймні два учасники комісії за стандартами і рекомендаціями ANSI X9F1, Деніел Браун і Скотт Ванстон з Certicom,^[7]були обізнані про точний механізм і обставин, при яких можливий бекдор, так як в січні 2005 року вони подали заявку на патент ^[14], в якому було описано, як вставити або запобігти бекдор в Dual_EC_DRBG. Пізніше було підтверджено, що дана "пастка" ідентична бэкдору генератора. У 2014 році Метью Грін, криптограф і професор університету Джона Хопкінса,^[15][16]критикував комітет, за те що не був прибраний цей заздалегідь відомий бекдор.^[17] У патенті були описані 2 умови існування цього бекдор:

1) Вибрано Q.

Генератор випадкових чисел еліптичної кривої уникає escrow keys, вибираючи випадково точку Q. Навмисне використання escrow keys може забезпечити резервне копіювання. Зв'язок між P і Q використовується в якості escrow key і зберігається в захищеній області. Адміністратор реєструє вихід генератора і відновлює випадкове число за допомогою escrow key.

2) Не скорочений вихід генератора

Усічення виходу генератора - це альтернативний спосіб запобігання атаки за допомогою escrow key. Усічення виходу приблизно на половину забезпечить те, що вихід значень R, пов'язаних з одним виходом r, не піддаватиметься пошуку. Наприклад, для 160-бітної групи еліптичних кривих число потенційних точок R в списку становить близько 280, і пошук буде таким же складним, як завдання дискретного логарифмування. Недолік цього методу в тому, що ефективність генератора зменшується вдвічі, так як удвічі скорочується його вихід

За словами Джона Келсі, одного з авторів NIST SP 800-90A, варіант вибору достовірного випадкового Q був доданий в стандарт в відповідь на бекдор^[18], але таким чином, що перевірку FIPS 140-2 генератор проходив би тільки з використанням Q від АНБ.^[19] Не було зрозуміло, чому стандарт не вказував принцип вибору точки як Nothing sleeve up my number, або чому стандарт не скорочував вихід генератора, який запобігав би атаку з допомогою escrow key.

Порівняно з попереднім генератором EC PRG усічення виходу було реалізовано в Dual_EC_DRBG, який виводив від 1/2 до 2/3 від результату раунду EC PRG.^[20] Таке скорочення виходу, все одно залишало вихід генератора передбачуваним і непридатним як криптографічно стійкого генератора псевдовипадкових чисел. У стандарті зазначено, що реалізації повинні використовувати малий max_outlen, але при цьому дозволяє використовувати його тільки кратним 8 бітам. У додатку C стандарту сказано, що висновок меншої кількості біт, зробить вихід менш рівномірно розподіленим, але доказ безпеки від Брауна покладається на те, що значення показника max_outlen значно менше.

Комісія зі стандартів та рекомендацій ANSI X9F1, в якій обговорювався бекдор, також включала в себе співробітників з RSA Security.^[21] У 2004 році, RSA Security впровадила реалізацію Dual_EC_DRBG, в якій містився бекдор, в RSA BSAFE як результат секретної угоди з АНБ. В 2013 році, після того, як New York Times повідомила, що Dual_EC_DRBG містила бекдор, в RSA Security заявили, що не знали про бэкдоре при укладанні угоди з АНБ, після чого попросили користувачів переключити генератор. На конференції RSA 2014 року виконавчий голова RSA Security Art Coviello пояснив, що компанія зазнавала збитків від шифрування і вирішила перестати ним займатися, і замість цього стала довіряти стандартам і організаціям за твердженнями стандартів, таких як NIST.^[22]

Попередній варіант NIST SP 800-90A, включаючи Dual_EC_DRBG, був опублікований в грудні 2005 року. Остаточний варіант був опублікований в червні 2006 року. Документи, показані Сноуденом, були інтерпретовані як припущення, що в Dual_EC_DRBG реалізований бекдор від АНБ, посилаючись на прагнення АНБ бути єдиним редактором стандарту.^[23] Раннє використання Dual_EC_DRBG в RSA Security було висунуто АНБ як аргумент для включення генератора в NIST SP 800-90A.^[24] RSA Security згодом сказала, що прийняття Dual_EC_DRBG в NIST було причиною для його використання.^[25]

Потенційний бекдор не публікувався за межами комісії по стандартизації. Тільки після презентації Дана Шумова^[en] і Нільса Фергюсона в 2007 році бекдор став широко відомий. Їм було доручено реалізувати Dual_EC_DRBG для Microsoft. Крім того, Фергюсон обговорив можливий бекдор у 2005 році на нараді X9.^[18] Брюс Шнайер написав у статті Wired 2007 року про те, що недоліки Dual_EC_DRGB настільки очевидні, що ніхто не стане його використовувати.^[26]

В OpenSSL реалізовані всі частини NIST SP 800-90A, включаючи Dual_EC_DRBD, незважаючи на його сумнівну репутацію. При цьому творці OpenSSL зазначили, що вони прагнуть зробити OpenSSL повним і тому реалізують навіть небезпечні алгоритми. OpenSSL не використовував Dual_EC_DRBG за замовчуванням, і в 2013 році було виявлено, що реалізація OpenSSL Dual_EC_DRBG не працює і ніхто не міг її використовувати.^[19]

Брюс Шнайер повідомив в грудні 2007 року, що Microsoft додала підтримку Dual_EC_DRBG в Windows Vista, хоча вона не включена, і Шнайер попередив про потенційний бекдор.^[27] Windows 10 і більш пізні версії будуть замінювати виклики Dual_EC_DRBG на виклики генератора на основі AES.^[28]

9 вересня 2013 року, за інформацією отриманою від Сноудена, а також через доповідь New York Times про бекдор у Dual_EC_DRBG, NIST оголосив, що перевидає SP 800-90A і відкриває SP 800-90B/C для громадського обговорення. Зараз NIST «настійно рекомендує» не використовувати Dual_EC_DRBG.^[29][30] Публікація бекдор в стандарті прийнятому стало для NIST серйозним конфузом.^[31]

RSA Security зберегла Dual_EC_DRBG як генератор за замовчуванням в BSAFE навіть після того, як бекдор став широко відомий. Після широко поширився занепокоєння з приводу бекдор була зроблена спроба знайти програмне забезпечення, яке використовувало Dual_EC_DRBG, серед якого виділявся BSAFE. В 2013 році, начальник служби безпеки RSA Сем Каррі надав сайту Ars Technica обґрунтування вибору помилкового стандарту Dual_EC_DRBG за замовчуванням порівняно з альтернативними генераторами.^[32] Технічна частина заяви широко критикувалася криптографами.^[33] 20 грудня 2013 року агентство Reuters повідомило, що RSA прийняв секретний платіж в розмірі 10 мільйонів доларів від АНБ, щоб встановити Dual_EC_DRBG за замовчуванням в двох продуктах шифрування.^[24][34]

• The Many Flaws of Dual_EC_DRBG [Архівовано 20 серпня 2016 у Wayback Machine.] // Matthew Green (Johns Hopkins University), September 18, 2013