Криптографічно стійкий генератор псевдовипадкових чисел

Криптографічно стійкий генератор псевдовипадкових чисел — генератор псевдовипадкових чисел, який задовільняє додатковим умовам. Зокрема, він має генерувати такі послідовності, які не здатен відрізнити від повністю випадкових послідовностей жоден ефективний алгоритм за поліноміальний час. Іншими словами, жоден статистичний тест не буде здатен відрізнити отриману послідовність псевдовипадкових чисел від насправді випадкової послідовності.

Таким чином, генерована послідовність:

• повинна мати якнайбільш можливий період;
• не повинна мати прихованих періодів;
• повинна мати різномірний спектр.

Опис

Безпека деяких алгоритмів шифрування залежить від стійкості генератора випадкових чисел завдяки якому формується ключ або послідовність біт. Шифри з досконалою стійкістю потребують повністю випадкового ключа такої ж довжини, як і вихідний ключ. Проте у більшості випадків, насправді випадкові послідовності біт необхідної довжини не доступні. Тому були розроблені методи отримання псевдовипадкових послідовностей. Такі послідовності можуть справляти враження випадкових, але отримані вони в результаті роботи детермінованого алгоритму. Такі алгоритми називають генераторами псевдовипадкових чисел. Отримавши порівняно невеликий випадковий вхідний рядок (так зване випадкове початкове значення — англ. seed), такі алгоритми здатні обчислити доволі довгі псевдовипадкові послідовності.

Звичайні генератори псевдовипадкових послідовностей можуть обчислювати послідовності з якісними статистичними показниками. Отримані послідовності можуть бути придатними для використання в методах Монте-Карло, але непридатними для використання в криптографічних алгоритмах. Наприклад, таємні параметри генераторів псевдовипадкових послідовностей на основі лінійного конгруентного методу або на основі регістра зсуву з лінійним зворотнім зв'язком можуть бути відтворені з доволі невеликої кількості згенерованих ними елементів послідовності. Таким чином, стає можливим відтворити всю згенеровану ними послідовність.

Серед відомих методів побудови криптографічно стійких генераторів псевдовипадкових послідовностей важливу роль відіграють генератори на основі односторонніх підстановок.

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

Властивості

Оскільки генератори псевдовипадкових чисел є детермінованими алгоритмами, тому буть-хто здатен обчислити елементи генерованої послідовності для заданого початкового значення (англ. seed). А оскільки, зазвичай, алгоритми таких генераторів загально відомі, особливі зусилля мають бути скеровані на те, що б втаємничити їхні початкові значення та унеможливити їхнє обчислення на основі згенерованої послідовності. Крім того, саме початкове значення бажано зробити випадковим та непередбачуваним.

Властивості генераторів псевдовипадкових чисел оцінюють з використанням низки кількісних показників, основними з яких є:

• період ${\displaystyle l}$ (довжина) послідовності псевдовипадкових чисел;
• основа алфавіту ${\displaystyle m}$;
• ймовірність перекриття в просторі або в часі двох сегментів ${\displaystyle Y_{r}}$ та ${\displaystyle Y_{\mu }}$, тобто в різних абонентів або в одного абонента протягом часу, так, що ${\displaystyle Y_{r}=Y_{\mu }}$;
• структурна скритність (еквівалентна складність) ${\displaystyle S_{e}}$ послідовності ${\displaystyle Y}$;
• кількість (ентропія ${\displaystyle N_{k}(H_{k})}$ джерела) ключів для випадку, коли генератор випадкових чисел використовують як джерело ключів;
• відстань рівнозначності ${\displaystyle l_{0}}$ конкретної послідовності ${\displaystyle Y_{\nu }}$;
• безпечний час генератора випадкових чисел ${\displaystyle t_{b}}$;
• складність ${\displaystyle I_{y}}$ формування послідовності ${\displaystyle Y}$;
• довжина параметрів зворотного зв'язку;
• властивості випадковості, рівноймовірності, незалежності та однорідності.

За всіма названими показниками до генератора послідовностей псевдовипадкових чисел висувають низку вимог. Так, період повторення ${\displaystyle l_{n}\geq l_{z}}$, тобто повинен бути не менше заданого, можливість змінної основи алфавіту ${\displaystyle m}$, ймовірність перекриття ${\displaystyle P_{n}<P_{z}}$ менше допустимої, структурна скритність ${\displaystyle S\geq S_{g}}$, ентропія джерела ключів ${\displaystyle H\geq H_{g}}$, відстань рівнозначності ${\displaystyle l_{0}>l_{g}}$, безпечний час ${\displaystyle t_{b}<t_{g}}$, тобто не менш допустимих. Крім того, реалізації ${\displaystyle Y}$ i повинна задовольняти вимогам випадковості, рівноймовірності, незалежності та однозначності.

Крім того, до генераторів псевдовипадкових послідовностей можуть бути висунуті вимоги прямої стійкості (англ. forward unpredictability): попри знання всіх попередніх чисел послідовності наступні числа мають бути непередбачуваними якщо не відоме початкове значення генератора. Зворотна стійкість вимагає унеможливити обчислення початкового значення на основі будь-якої кількості згенерованих чисел послідовності. Кореляція між початковим значенням та згенерованою послідовністю має бути неочевидною, а кожен наступний елемент має справляти враження реалізації випадкової події з імовірністю ½.

Стандарти

Загальним підходом до генерування ключів, ключової інформації та параметрів є стандартизація методів, механізмів і практичних (конкретних) алгоритмів їх генерування.

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

Базовими міжнародними стандартами, що стандартизують алгоритми генерації послідовностей випадкових чисел є:

• міжнародний стандарт ISO/IEC 18031 «Information technology — Random number generation», який визначає алгоритми генерації псевдовипадкових і випадкових чисел, а також визначає статистичні тести перевірки генераторів;
• міжнародний стандарт ISO/IEC 18032 «Information technology — Prime number generation», який визначає методи генерації простих чисел і методи тестування чисел на простоту;
• національний стандарт ДСТУ ISO/IEC19790 «Інформаційна технологія — Методи захисту — Вимоги щодо захисту для криптографічних модулів».

Додаткові вимоги до алгоритмів та реалізацій методів і засобів генерації та тестування послідовностей випадкових чисел визначені національними та промисловими стандартами США: FIPS 140-3, ANSI X9.17, ANSI X9.31, ANSI X9.44 та ін., а також рекомендаціями NIST — NIST SP 800-22 і рекомендаціями органу зі стандартизації Німеччини — AIS-20, AIS-31 та інші.

Одним із важливих та необхідних напрямків досліджень при створенні ефективних генераторів випадкових чисел та генераторів псевдовипадкових чисел є розробка методів та засобів оцінки статистичних властивостей випадкових послідовностей. Статистичні показники та побудовані на їх основі критеріїв оцінки є інструментом перевірки правильності технічних рішень щодо побудови генераторів випадкових чисел. Дослідження статистичних властивостей здійснюються у рамках методики статистичних випробувань на основі статистичних тестів.

Найбільш прийнятними (з точки зору практичного використання) методиками тестування є методики NIST STS, FIPS PUB 140-1, AIS 20 та AIS 31.

Приклади

ANSI X9.17

Генератор псевдовипадкових послідовностей визначений у стандарті ANSI X9.17 (Financial Institution Key Management (wholesale)) пройшов сертифікацію та прийнятий як стандарт FIPS. На вході він отримує TDEA (варіант ключів 2) набір ключів k та випадкове початкове число розміром 64 біт s. Для обчислення наступного псевдовипадкового числа послідовності він:

• Бере поточний час D з найбільшою доступною точністю (мілісекунди, тощо).
• Обчислює проміжне значення t = TDEA_k(D)
• Обчислює псевдовипадкове число x = TDEA_k(s ⊕ t), де ⊕ позначає побітову операцію виключної диз'юнкції.
• Оновлює значення початкового числа s = TDEA_k(x ⊕ t)

Вади реалізацій

DUHK

Попри відповідність алгоритму формальним вимогам стандартів його реалізації можуть мати вади. Так, в жовтні 2017 року група дослідників оприлюднила доповідь про виявлену ними ваду у деяких апаратних реалізаціях генераторів псевдовипадкових чисел. Зокрема, йдеться про уразливість в реалізації генератора псевдовипадкових чисел ANSI X9.31 Random Number Generator (RNG), коли в пристрої виробником закодовано одне єдине початкове значення генератора замість використання випадкового числа обчисленого іншим генератором випадкових чисел.

Генератори ANSI X9.31 мають доволі широке використання в пристроях для генерації ключів шифрування VPN, SSL/TLS, IPsec, тощо.

Також дослідники розробили алгоритм атаки на знайдену ними вразливість. Алгоритм отримав назву DUHK (англ. Don't Use Hard-coded Keys) та дозволяє зловмиснику відтворити зашифровані дані аж до встановлення сеансового ключа.

Дослідникам вдалось встановити 12 продуктів, які успішно пройшли сертифікацію , але в яких присутня дана вада. Зокрема, вразливість була виявлена в популярній системі v4 версії 4.3.17.

Примітки

1. Hans Delfs, Helmut Knebl (2007). 8.1 Computationally Perfect Pseudorandom Bit Generators. Introduction to Cryptography. Information Security and Cryptography (вид. 2-ге). Springer. ISBN .
2. Олег Ігорович Гарасимчук, Володимир Миколайович Максимович. Генератори псевдовипадкових чисел, їх застосування, класифікація, основні методи побудови і оцінка якості // Захист інформації. — 2003. — Т. 5, вип. 16. — DOI:10.18372/2410-7840.5.4270. з джерела 2 червня 2018. Процитовано 6 листопада 2017.
3. 1.1.2 Unpredictability. (PDF) (Звіт). Special Publication (вид. Revision 1a). NIST. квітень 2010. NIST 800-22. Архів оригіналу (PDF) за 18 листопада 2017. Процитовано 7 листопада 2017.
4. О. А. Замула, Д. О. Семченко, Ю. В. Землянко. Аналіз і обґрунтування критеріїв і показників ефективності криптографічних генераторів псевдовипадкових чисел // Системи обробки інформації. — 2014. — Вип. 120. — С. 131-136. з джерела 8 листопада 2017. Процитовано 8 листопада 2017.
5. Handbook of Applied Cryptography [ 16 лютого 2012 у Wayback Machine.], , , and , CRC Press, 1996, Chapter 5 Pseudorandom Bits and Sequences [ 8 лютого 2012 у Wayback Machine.] (PDF)
6. Catalin Cimpanu (24 жовтня 2017). . Bleeping Computer. Архів оригіналу за 25 жовтня 2017. Процитовано 7 листопада 2017.
7. Shaanan Cohney, Nadia Heninger, and Matthew D. Green. Practical state recovery attacks against legacy RNG implementations. з джерела 5 листопада 2017. Процитовано 7 листопада 2017.

Література

• Jan Krhovják, Abstract Analysis, demands, and properties of pseudorandom number generators [ 16 листопада 2017 у Wayback Machine.]

Див. також

• Генерація випадкових чисел

Посилання

• (PDF) (Звіт). Special Publication (вид. Revision 1a). NIST. квітень 2010. NIST 800-22. Архів оригіналу (PDF) за 18 листопада 2017. Процитовано 7 листопада 2017.
• RFC 4086 Randomness Requirements for Security (2005)
• Random Bit Generation [ 14 листопада 2017 у Wayback Machine.] на сайті NIST