Атака на ГПВЧ

Атака на генератор псевдовипадкових чисел — атака, спрямована на розкриття параметрів генератора псевдовипадкових чисел (ГПВЧ) з метою подальшого передбачення псевдовипадкових чисел.

Актуальність

Безпека криптографічних систем часто залежить від деяких даних, які повинні бути відомі лише авторизованим користувачам і які майже не можливо вгадати зловмисникові. Прикладами таких даних можуть бути - сеансові ключі, ініціалізуючі вектори, криптографічна сіль, унікальні параметри функції ЕЦП і тому подібне. Щоб досягти необхідного рівня непередбачуваності за умови частої генерації випадкових чисел, потрібно використовувати надійне джерело випадкових чисел. На жаль, велика кількість криптографічних додатків не володіють надійним джерелом випадкових послідовностей, таких як, наприклад, тепловий шум в електричних ланцюгах або точний час між парою спрацьовувань лічильника Гейгера. Замість цього доводиться використовувати генератори псевдовипадкових чисел (ГПВЧ). ГПВЧ отримує на вхід потік даних з джерела з низькою ентропією і намагається його перетворити в послідовність значень, що практично неможливо відрізнити від справжньої випадкової послідовності. Успішна атака на ГПВЧ може розкрити значну частину криптографічних системи незалежно від того, наскільки ретельно вони були спроектовані. Тим не менш, деякі системи використовують погано спроектовані ГПВЧ або роблять це таким чином, що зменшує складність атак. Більше того, потрібно лише одне успішне проникнення, щоб скомпрометувати всю систему.

Типи атак на ГПВЧ

В залежності від того, які дані ГПВЧ простіше відслідковувати (вихідні значення, вхідні значення або внутрішній стан), можуть бути реалізовані наступні типи атак.

Пряма криптоаналітична атака 

Якщо атакуючий здатний безпосередньо відстежувати вихідні дані ГПВЧ і дослідити закономірність їх появи, то це буде прямою криптоаналітичною атакою. Цей вид атаки поширюється на більшість алгоритмів, що використовують ГПВЧ. Однак якщо, наприклад, ГПВЧ використовується тільки для генерації ключа, як зроблено в Triple DES, то він не може бути вразливий до такого роду атак, так як вихідні значення ГПВЧ безпосередньо ніколи не видно.

Атаки, засновані на вхідних даних

Даний тип атак можливий у випадках, коли зловмисник може використовувати дані про вхідні сигнали ГПВЧ або контролювати їх. Атаки, засновані на вхідних даних, можуть бути розділені на атаки з відомими вхідними даними, атаки з відтворюваними вхідними даними і атаки на обрані вхідні дані.

Атаки з відомими вхідними даними практично здійснити в ситуаціях, коли деякі вхідні дані, передбачувані проектувальником системи як важко передбачувані, виявляються легко вгадуваним в деяких окремих випадках.

Атаки з відтворюваними вхідними даними можуть використовуватися в тих же ситуаціях, але вимагають менш складних систем злому і менш складного аналізу з боку атакуючого.

Атаки на обрані вхідні дані можуть бути практично реалізовані на системах, які використовують смарт-карти або токени. Також така атака може бути небезпечна для додатків, що використовують в якості вхідних сигналів ГПВЧ текстові повідомлення, паролі, що задаються користувачем, статистику мережі, час і т. д.

Атаки, засновані на розкритті внутрішнього стану

При проведенні такого типу атак зловмисник намагається використовувати раніше успішні атаки на ГПВЧ, що розкрили його внутрішній стан, з метою передбачення стану подальших або попередніх станів ГПВЧ, наскільки це можливо. Такого роду атаки можуть бути успішні в тому випадку, коли ГПВЧ починає свою роботу з відомого або передбачуваного стану. На практиці дуже складно визначити той факт, що внутрішній стан було скомпрометовано. Саме тому ГПВЧ повинні протидіяти компрометуванню внутрішнього стану. Можливі як мінімум 4 варіанти такої атаки:

Атака із зворотною прокруткою використовує розкритий стан ГПВЧ $S$ у момент часу $t_{0}$ з метою відновлення станів ГПВЧ і, відповідно, його виходів в попередні моменти часу.

Перманентне компрометування стану можливе для таких систем, у яких одного разу розкритий стан $S$ у момент часу $t_{0}$ робить всі попередні та наступні стани уразливими для подальших атак.

Атака ітеративним вгвдуванням використовує знання про стан $S$ у момент часу $t_{0}$ та проміжні виходи ГПВЧ, щоб дізнатися $S$ у момент часу $t_{0}+\Delta t$ коли входи, зібрані протягом цього періоду часу, є вгадуваними (але невідомими) для атакуючого.

Зустріч посередині є, по суті, поєднанням атаки ітеративним вгвдуванням і атаки з зворотньою прокруткою. Знання $S$ у моменти часу $t_{0}$ і $t_{0}+2\Delta t$ дозволяють зловмиснику відновити стан $S$ у моменти часу $t_{0}+\Delta t$, a так само у всьому часовому проміжку від $t_{0}$ до $t_{0}+2\Delta t$.

Приклади ненадійних систем

Ранні версії протоколу шифрування SSL компанії Netscape використовували псевдовипадкові числа, які створювалися ГПВЧ, джерелом ентропії якого виступали значення трьох змінних: час доби, ідентифікатор процесу і ідентифікатор батьківського процесу. Ці величини є передбачуваними і мають відносно низьку ентропію. Відповідно, дана версія SSL була визнана небезпечною. Повідомлення про проблему Netscape отримали від Філіпа Хелам-Бейкера в 1994 році, який тоді працював дослідником в CERN. Однак проблема не була вирішена аж до виробництва програмного продукту. Пізніше, в 1995 році, про проблеми знову заговорили Іан Голдберг і Девід А. Вагнер. Їм довелося застосувати об'єктні модулі зворотного інжинірингу, так як Netscape відмовилася розкрити деталі генерації випадкових чисел. ГПВЧ був виправлений в наступних випусках (версія 2 і більш пізні) зміною джерела ентропії на більш випадковий і з більш високим рівнем ентропії.

Компанія Microsoft використовує неопублікований алгоритм для генерації випадкових чисел в операційних системах Windows. Користувачеві цей алгоритм доступний через утиліту CryptGenRandom. У листопаді 2007 року Лео Дорредорф разом з співавторами з Хайфського університету та Єврейського університету в Єрусалимі опублікував статтю під назвою Cryptanalysis of the Random Number Generator of the Windows Operating System. У статті продемонстровано серйозні недоліки алгоритму, представленого Microsoft. Висновки наведені в статті були сформульовані в результаті вивчення дизасемблированного коду системи Windows 2000, але за заявами Microsoft, вони так само можуть відноситись і до Windows XP.

Національний інститут стандартів і технологій (США) в березні 2007 опублікував рекомендовані «детерміновані генератори псевдовипадкових чисел», які були стандартизовані в NIST Special Publication 800-90. Один з наведених ГПВЧ, Dual EC DRBG, запроваджений стандарт Агентством національної безпеки, заснований на еліптичній криптографії і містить певний набір рекомендованих констант. У серпні 2007 року Ден Шумів і Нільс Фергюсон з Microsoft показали, що константи можуть бути підібрані таким чином, що може виникнути бекдор в алгоритмі.

У травні 2008 року дослідник Лучано Белло опублікував роботу, що стверджувала - зміни, зроблені в 2006 році в ГПВЧ в пакеті openssl, що розповсюджуються разом з Debian Linux та іншими дистрибутивами, заснованими на Debian, значно зменшує ентропію генеруються значень, що робить ключі вразливими до атак. [1] [Архівовано 20 лютого 2014 у Wayback Machine.] [2] [Архівовано 14 липня 2014 у Wayback Machine.] Проблема була викликана змінами, зробленими одним з розробників Debian в коді openssl у відповідь на попередження компілятора про, на перший погляд, надмірний код. Дана уразливість була виправлена в той же день, як про неї стало відомо.

Способи захисту від атак на ГПВЧ

• Використовуйте хеш-функції, щоб приховати реальні вихідні значення ГПВЧ. Використовуйте результати хеш-функцій від вихідних значень ГПВЧ замість самих значень, щоб запобігти прямим криптоаналітичним атакам. Дана методика, хоч і не гарантує повної безпеки, робить систему більш надійною.
• Хэшуйте джерело ентропії з мітками часу, значеннями лічильника або іншими постійно змінними значеннями. Хешування джерела ентропії з яким постійно змінним значенням перед входом в ГПВЧ здатне захистити систему від атак, заснованих на вхідних даних.
• Періодично міняйте внутрішній стан ГПВЧ. Повністю міняйте внутрішній стан ГПВЧ час від часу. Це допоможе захиститися від атак, заснованих на розкритті внутрішнього стану, або, принаймні, зменшить шкоду, заподіяну успішною атакою.

Дивись також

• Генератор псевдовипадкових чисел
• CryptGenRandom

Література

• Randomness and the Netscape Browser [Архівовано 22 травня 2016 у Wayback Machine.], Ian Goldberg and David Wagner, Dr. Dobb's Journal, January 1996, pp66-70.
• Analysis of the Linux Random Number Generator [Архівовано 7 грудня 2017 у Wayback Machine.] Zvi Gutterman, Benny Pinkas and Tzachy Reinman, in IEEE S&P (Oakland Conference), May 2006, pp. 371-385.
• Randomness Requirements for Security. D. Eastlake, J. Schiller, S. Crocker, RFC 4086 (obsoletes RFC1750), 2006.
• Recommendation for Random Number Generation Using Deterministic Random Bit Generators, Elaine Barker and John Kelsey, NIST Special Publication 800-90. Revised March 2007