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]. Одна з областей застосування - криптографічні системи для генерації ключів. Алгоритм заснований на використанні еліптичних кривих.

Алгоритм

[ред. | ред. код]
схема Dual_EC_DRBG

У стандарті 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 байт. Всі майбутні вихідні дані генератора випадкових чисел можуть бути легко пораховані, поки зовнішній джерело ентропії не перезавантажить генератор з новим значенням t0 . Наприклад, використання цього генератора робить небезпечним SSL / TLS, оскільки встановлення SSL-з'єднання включає в себе відправлення випадково згенерованого кількості у відкритому вигляді. Бекдор полягає в тому, що при використанні констант P і Q стандарту, АНБ знає таке e, e * Q = P.[12] Таким чином, e є секретним ключем, імовірно відомим АНБ, а передбачуваний бекдор є клієнтографічним прихованим бекдором.[13]

Бекдор

[ред. | ред. код]

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

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

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

e * A = s0 * e * Q = s0 * P [3]

Виходячи з цього, є можливість порахувати s1 = φ ( x ( e * A) ), а потім і r1, потім і наступні s2,...,sn і r2,...,rn. Для цього потрібно лише повним перебором знайти 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]

Примітки

[ред. | ред. код]
  1. ↑ Recommendations for Random Number Generation Using Deterministic Random Bit Generators (Revised) (PDF). — National Institute of Standards and Technology, 2007. — 1 березня. — NIST SP 800-90. Архівовано з джерела 26 вересня 2007.
  2. ↑ а б NIST Special Publication 800-90 (PDF). Архів оригіналу (PDF) за 28 листопада 2016. Процитовано 25 квітня 2018.
  3. ↑ а б в г Dual_Ec_Drbg backdoor: a proof of concept at Aris' Blog - Computers, ssh and rock'n roll (англ.). blog.0xbadc0de.be. Архів оригіналу за 3 вересня 2018. Процитовано 21 грудня 2017.
  4. ↑ Daniel R. L. Brown, Kristian Gjøsteen. A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator : [арх. 4 березня 2018] : .mw-parser-output .masklink-text-color{color:#252525;text-decoration:inherit;text-decoration-color:#252525}@media screen{html.skin-theme-clientpref-night .mw-parser-output .masklink-text-color{color:#dadad6;text-decoration-color:#dadad6}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .masklink-text-color{color:#dadad6;text-decoration-color:#dadad6}}англ.] // Advances in Cryptology - CRYPTO 2007. — Springer, Berlin, Heidelberg, 2007-08-19. — С. 466–481. — ISBN 9783540741428, 9783540741435. — DOI:10.1007/978-3-540-74143-5_26.
  5. ↑ Berry Schoenmakers, Andrey Sidorenko. Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator : [арх. 15 грудня 2017]. — 2006. — № 190.
  6. ↑ The Many Flaws of Dual_EC_DRBG. A Few Thoughts on Cryptographic Engineering (амер.). 18 вересня 2013. Архів оригіналу за 20 серпня 2016. Процитовано 14 грудня 2017.
  7. ↑ а б в A few more notes on NSA random number generators. A Few Thoughts on Cryptographic Engineering (амер.). 28 грудня 2013. Архів оригіналу за 24 червня 2018. Процитовано 14 грудня 2017.
  8. ↑ Dual EC in X9.82 and SP 800-90 (PDF). Архів оригіналу (PDF) за 15 грудня 2017. Процитовано 25 квітня 2018.
  9. ↑ 'Flaw in Dual EC DRBG (no, not that one)' - MARC. marc.info. Архів оригіналу за 16 жовтня 2014. Процитовано 14 грудня 2017.
  10. ↑ Ball, James (6 вересня 2013). Revealed: how US and UK spy agencies defeat internet privacy and security. The Guardian (брит.). 0261-3077. Архів оригіналу за 25 квітня 2018. Процитовано 14 грудня 2017.
  11. ↑ а б [Cfrg] Dual_EC_DRBG ... [was RE: Requesting removal of CFRG co-chair]. www.ietf.org. Архів оригіналу за 18 серпня 2016. Процитовано 14 грудня 2017.
  12. ↑ On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng (PDF). Архів оригіналу (PDF) за 26 лютого 2014. Процитовано 25 квітня 2018.
  13. ↑ Dual_Ec_Drbg backdoor: a proof of concept at Aris' Blog - Computers, ssh and rock'n roll (англ.). blog.0xbadc0de.be. Архів оригіналу за 3 вересня 2018. Процитовано 14 грудня 2017.
  14. ↑ Espacenet -Bibliographic data (англ.). worldwide.espacenet.com. Архів оригіналу за 16 листопада 2018. Процитовано 14 грудня 2017.
  15. ↑ Matthew D. Green. Архів оригіналу за 3 травня 2018. Процитовано 25 квітня 2018.
  16. ↑ Matthew Green (амер.). A Few Thoughts on Cryptographic Engineering. Архів оригіналу за 29 січня 2018. Процитовано 21 грудня 2017.
  17. ↑ Hopefully the last post I’ll ever write on Dual EC DRBG. A Few Thoughts on Cryptographic Engineering (амер.). 14 січня 2015. Архів оригіналу за 24 березня 2018. Процитовано 14 грудня 2017.
  18. ↑ а б Dual EC in X9.82 and SP 800-90 (PDF). Архів оригіналу (PDF) за 15 грудня 2017. Процитовано 25 квітня 2018.
  19. ↑ а б 'Flaw in Dual EC DRBG (no, not that one)' - MARC. marc.info. Архів оригіналу за 16 жовтня 2014. Процитовано 15 грудня 2017.
  20. ↑ The Many Flaws of Dual_EC_DRBG. A Few Thoughts on Cryptographic Engineering (амер.). 18 вересня 2013. Архів оригіналу за 20 серпня 2016. Процитовано 15 грудня 2017.
  21. ↑ A few more notes on NSA random number generators. A Few Thoughts on Cryptographic Engineering (амер.). 28 грудня 2013. Архів оригіналу за 24 червня 2018. Процитовано 15 грудня 2017.
  22. ↑ Six Cryptographers Whose Work on Dual EC DRBG Were Deemed Without Merit by RSA Chief Art Coviello. jeffreycarr.blogspot.ru. Архів оригіналу за 15 грудня 2017. Процитовано 15 грудня 2017.
  23. ↑ Ball, James (6 вересня 2013). Revealed: how US and UK spy agencies defeat internet privacy and security. The Guardian (брит.). 0261-3077. Архів оригіналу за 25 квітня 2018. Процитовано 15 грудня 2017.
  24. ↑ а б Exclusive: Secret contract tied NSA and security industry pioneer. Reuters. Fri Dec 20 22:07:30 UTC 2013. Архів оригіналу за 5 травня 2018. Процитовано 15 грудня 2017.
  25. ↑ We don’t enable backdoors in our crypto products, RSA tells customers. Ars Technica (амер.). Архів оригіналу за 12 серпня 2018. Процитовано 15 грудня 2017.
  26. ↑ Did NSA Put a Secret Backdoor in New Encryption Standard?. WIRED (амер.). Архів оригіналу за 23 листопада 2015. Процитовано 15 грудня 2017.
  27. ↑ Dual_EC_DRBG Added to Windows Vista - Schneier on Security. www.schneier.com. Архів оригіналу за 10 червня 2018. Процитовано 15 грудня 2017.
  28. ↑ CNG Algorithm Identifiers (Windows) (англ.). msdn.microsoft.com. Архів оригіналу за 15 грудня 2017. Процитовано 15 грудня 2017.
  29. ↑ SUPPLEMENTAL ITL BULLETIN FOR SEPTEMBER 2013 (PDF). Архів оригіналу (PDF) за 26 травня 2018. Процитовано 25 квітня 2018.
  30. ↑ Perlroth, Nicole. Government Announces Steps to Restore Confidence on Encryption Standards. Bits Blog (англ.). Архів оригіналу за 25 березня 2018. Процитовано 15 грудня 2017.
  31. ↑ Can You Trust NIST?. IEEE Spectrum: Technology, Engineering, and Science News (англ.). Архів оригіналу за 1 лютого 2016. Процитовано 15 грудня 2017.
  32. ↑ Stop using NSA-influenced code in our products, RSA tells customers. Ars Technica (амер.). Архів оригіналу за 25 березня 2018. Процитовано 15 грудня 2017.
  33. ↑ RSA warns developers not to use RSA products. A Few Thoughts on Cryptographic Engineering (амер.). 20 вересня 2013. Архів оригіналу за 24 квітня 2018. Процитовано 15 грудня 2017.
  34. ↑ This page has been removed | News. The Guardian (брит.). 0261-3077. Архів оригіналу за 13 лютого 2021. Процитовано 15 грудня 2017.

Посилання

[ред. | ред. код]
Отримано з https://uk.wikipedia.org/wiki/Dual_EC_DRBG