Криптографічна ненадійність алгоритму Dual_EC_DRBG

09/10/2014

Командою CERT-UA проведено вивчення доступної інформації щодо криптографічної ненадійності алгоритму Dual_EC_DRBG. Ця стаття не претендує на серйозну наукову працю. Проте, нам хотілося б звернути увагу українських фахівців із криптографії на ситуацію у цій галузі, що склалася в світі. Жорстка конкуренція провідних країн світу при створенні та впровадженні нових криптоалгоритмів, а також їх програмних і апартних реалізацій, стосується і нашої країни. Актуальну інформацію щодо криптографічного захисту інформації в Україні можливо отримати на сайті Держспецзв’язку.   

Об’єктом вивчення команди CERT-UA став криптографічний алгоритм, що описаний стандартом Dual Elliptic Curve Deterministic Random Bit Generator (NIST SP 800-90А), розроблений Агентством національної безпеки США та стандартизований у 2007 році Національним інститутом стандартів і технології США (далі — Dual_EC_DRBG). Ми звернули на нього увагу, отримавши повідомлення правоохоронних органів України та засобів масової інформації про криптографічну ненадійність цього алгоритму.  Отже, метою вивчення було надання аналітичних та практичних підтверджень того, що Dual_EC_DRBG є криптографічно не надійним.

 

Нез’ясована  історія  однієї константи

 

Dual_EC_DRBG було анонсовано Агентством національної безпеки США у 2005 році. Спеціалісти відзначали його недостатній опис з технічного боку.

Так, 21 серпня 2007 року фахівці Microsoft Ден Шумов та Нільс Фергюсон на конференції CRYPTO 2007 доповіли про можливий бекдор   у цьому алгоритмі. Вони з’ясували, що один з недоліків алгоритму Dual_EC_DRBG зводить його до одного окремого випадку рішення задачі дискретного логарифмування на еліптичних кривих. Дослідники припустили, що автори алгоритму мали змогу приховати рішення цієї задачі. Зокрема, вони помітили відсутність у описовій частині стандарту інформації про походження набору констант, який визначає еліптичну криву для алгоритму. Вони також довели, що для цього набору існує секретна константа, яка дозволяє точно передбачати наступний результат після збору всього 32 згенерованих алгоритмом байт.

Проте, після відповідної пропозиції Агентством національної безпеки США, у 2011 році алгоритм був прийнятий NIST у якості стандарту, який використовується у десятках програмних продуктів.

На цілеспрямований намір у організації такої криптографічної слабкості вказують ще деякі деталі.

Так, за інформацією, оприлюдненою у ЗМІ з посиланням на Едварда Сноудена, згідно з програмою американських спецслужб Bullrun у криптоалгоритми вбудовувались неявні вразливості, які дозволяли б скомпрометувати криптографічний захист, що їх використовує. А  за оцінкою всесвітньо відомого криптографа Брюса Шнайєра, оприлюдненою у 2007 році, цю можливість можливо було описати тільки, як бекдор.

 

Windows, OpenSSL та інші

 

Втім, алгоритм Dual_EC_DRBG є одним з найпоширеніших теоретико-числових генераторів випадкових чисел. Як вже згадувалося, він використовується, зокрема, у наступних продуктах:

  • операційна система Windows, починаючи з версії Windows Vista з пакетом оновлень SP1;
  • операційна система Windows 7 в модулі CNG.SYS і функції BCryptGenRandom;
  • операційні системи Windows 8, Windows RT, Windows Server 2012, Surface Windows RT, Surface Windows 8 Pro, та у різних версіях Windows Phone 8 Cryptography Next Generation (CNG) Version 6.2.9200 (у вигляді програмної бібліотеки The Microsoft Windows Cryptographic Primitives Library, яка надає розробникам можливість суміності при використанні FIPS 140-2 Level 1);
  • реалізований в OpenSSL;
  • у деяких продуктах компанії RSA використовується за замовчанням, зокрема, у бібліотеках BSAFE Crypto-J та Crypto-C ME, а також у рішеннях RSA (підрозділу захисту інформації EMC): Data Protection Manager та у програмному забезпеченні RSA BSAFE Crypto-C Micro Edition (ME). Компанія RSA закликала користувачів не користуватись алгоритмом;
  • у модулі CiscoSSL FIPS Object Module;
  • у криптобібліотеці Blackberry для операційної системи BlackBerry версії 10 та компонентів BlackBerry Enterprise Service 10. Також реалізовано у бібліотеці The BlackBerry Algorithm Library for Secure Work Space, яка використовується BlackBerry Cryptographic Library для  BlackBerry Secure Work Space (BBSWS). BBSWS потрібна при організації захищеної взаємодії та управління пристроїв під управлінням iOS та Android, коли використовується у поєднанні з рішеннями мобільного управління від BlackBerry®;
  • програмний криптомодуль Security Builder® FIPS Core, який потрібен для побудови взаємодії з програмними продуктами, написаними на мові програмування C для FIPS 140-2 та Suite B security. Також може бути використаний модулями Certicom PKI, IPSec та SSL.
  • криптографічний модуль The Juniper Networks Pulse Cryptographic Module;
  • криптомодулі The Mocana Cryptographic Loadable Kernel Module (версії ПЗ 5.5fi та 5.4F) ;
  • SafeNet Software Cryptographic Library Version 1.0;
  • CryptoComply Server Engine Version 2.1;
  • Panzura Cryptographic Module Version 4.2;
  • програмно-апаратний модуль Datacryptor DUAL_EC_DRBG версії 1.8 (Firmware), який використовується у виробах криптозахисту Datacryptor® 2000 та Datacryptor® Advanced Performance.

Всі ці продукти, та багато інших, потенційно скомпрометовані.

 

Цікаві досліди CERT-UA

 

Отже, спочатку ми добряче розібралися із самим алгоритмом, та з запропонованою Шумовим та Фергюсоном методикою атаки на нього.

Потім ми вивчили, та максимально засвоїли кілька теоретичних статей з цього приводу. Зокрема,  працю Берри Шонмейкерса та Андрія Сидоренко з Ейдховенського університету щодо вісутності достатнього обгрунтування надійності генератора псевдовипадкових послідовностей за допомогою еліптичних кривих, опубліковану у 2006 році, а також аналіз безпечності Dual_EC_DRBG, проведений у 2007 році Даніелем Брауном з компанії Certicom Research, та Крістіаном Гйостином з Норвезького університету природничих та технічних наук.

Після цього ми перейшли до практичного етапу. Так, для тестування атаки на реалізацію алгоритму Dual_EC_DRBG у OpenSSL під Linux ми обрали методику, опубліковану бельгійським програмістом прибалтійського походження Арісом Адамантіадісом. Зкомпілювавши запропонований ним вихідний код, ми здійснили його збірку та виконання.  Підбір зазделегідь невідомого початкового параметру за наявною псевдовипадковою послідовністю, згенерованою по алгоритму Dual_EC_DRBG, зайняв приблизно 10 секунд часу. Скриншоти експерименту наведено нижче:

3

4

Додаткову перевірку можна здійснити шляхом аналізу доступних для загального перегляду зразків вихідних кодів криптобібліотек, що реалізують алгоритм Dual_EC_DRBG. З огляду на обмеженість часу, необхідного для повторення тесту, його результат буде викладено на веб-сайті cert.gov.ua. Також наведені та альтернативні тести пропонується виконати власними силами науковим установам та закладам, які є профільними з криптографічного  захисту інформації.

 

Замість післямови

 

Отже, за наявною інформацією та результатами тестування CERT-UA вважає алгоритм Dual_EC_DRBG таким, що має ознаки криптографічно ненадійного.  Ми пропонуємо визнати його непридатним для використання у критичних з точки зору захисту інформації сферах.

З огляду на широке застосування алгоритму Dual_EC_DRBG ми пропонуємо профільним установам і організаціям у галузі криптозахисту провести власний аналіз наданих позитивних експертних висновків на програмні та апаратні засоби КЗІ в Україні на предмет підтримки цього алгоритму. У разі наявності підтримки такого алгоритму пропонується проводити повторну експертизу цих засобів КЗІ без підтримки цього алгоритму (за можливості). У разі відстуності можливості проведення такої перевірки з вищенаведеними умовами, пропонується експертні висновки скасувати.

 

Обговорення результатів перевірки алгоритму Dual_EC_DRBG та пропозицій пропонується CERT-UA у вигляді електронного листування, а також шляхом обговорення у соціальних мережах. Наші контакти — до ваших послуг!