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

'''Криптографічно стійкий генератор псевдовипадкових чисел'''&nbsp;— [[генератор псевдовипадкових чисел]], який задовільняє додатковим умовам. Зокрема, він має генерувати такі послідовності, які не здатен відрізнити від повністю випадкових послідовностей жоден ефективний [[алгоритм]] за [[Клас складності P|поліноміальний час]]. Іншими словами, жоден статистичний тест не буде здатен відрізнити отриману послідовність псевдовипадкових чисел від насправді випадкової послідовності<ref name="itc.8.1">{{cite book | chapter = 8.1 Computationally Perfect Pseudorandom Bit Generators | title = Introduction to Cryptography | edition = 2-ге | author = Hans Delfs, Helmut Knebl | publisher = Springer | isbn = 978-3-540-49243-6 | year = 2007 | series = Information Security and Cryptography}}</ref>.

Таким чином, генерована послідовність:<ref>{{cite article
 | 1 = 
 | volume = 5
 | number = 3
 | issue = 16
 | year = 2003
 | doi = 10.18372/2410-7840.5.4270
 | title = Генератори псевдовипадкових чисел, їх застосування, класифікація, основні методи побудови і оцінка якості
 | author = Олег Ігорович Гарасимчук, Володимир Миколайович Максимович
 | journal = Захист інформації
 | url = http://jrnl.nau.edu.ua/index.php/ZI/article/view/4270
 | accessdate = 6 листопада 2017
 | archivedate = 2 червня 2018
 | archiveurl = https://web.archive.org/web/20180602014840/http://jrnl.nau.edu.ua/index.php/ZI/article/view/4270
 }}</ref>
* повинна мати якнайбільш можливий період;
* не повинна мати прихованих періодів;
* повинна мати різномірний спектр.

== Опис ==

Безпека деяких алгоритмів шифрування залежить від стійкості генератора випадкових чисел завдяки якому формується ключ або послідовність біт. Шифри з досконалою стійкістю потребують повністю випадкового ключа такої ж довжини, як і вихідний ключ. Проте у більшості випадків, насправді випадкові послідовності біт необхідної довжини не доступні. Тому були розроблені методи отримання псевдовипадкових послідовностей. Такі послідовності можуть справляти враження випадкових, але отримані вони в результаті роботи детермінованого алгоритму. Такі алгоритми називають генераторами псевдовипадкових чисел. Отримавши порівняно невеликий випадковий вхідний рядок (так зване [[випадкове початкове значення]]&nbsp;— {{lang-en|seed}}), такі алгоритми здатні обчислити доволі довгі псевдовипадкові послідовності<ref name="itc.8.1"/>.

Звичайні генератори псевдовипадкових послідовностей можуть обчислювати послідовності з якісними статистичними показниками. Отримані послідовності можуть бути придатними для використання в [[Метод Монте-Карло|методах Монте-Карло]], але непридатними для використання в криптографічних алгоритмах. Наприклад, таємні параметри генераторів псевдовипадкових послідовностей на основі лінійного конгруентного методу або на основі [[Регістр зсуву з лінійним зворотним зв'язком|регістра зсуву з лінійним зворотнім зв'язком]] можуть бути відтворені з доволі невеликої кількості згенерованих ними елементів послідовності. Таким чином, стає можливим відтворити всю згенеровану ними послідовність<ref name="itc.8.1"/>.

Серед відомих методів побудови криптографічно стійких генераторів псевдовипадкових послідовностей важливу роль відіграють генератори на основі [[Одностороння функція|односторонніх підстановок]]<ref name="itc.8.1"/>.

Слід зазначити, що навіть найкращий генератор псевдовипадкових послідовностей потребує [[генератор випадкових чисел|джерело дійсно випадкових чисел]] для отримання початкового значення<ref name="itc.8.1"/>.

== Властивості ==

Оскільки генератори псевдовипадкових чисел є детермінованими алгоритмами, тому буть-хто здатен обчислити елементи генерованої послідовності для заданого [[випадкове початкове значення|початкового значення]] ({{lang-en|seed}}). А оскільки, зазвичай, алгоритми таких генераторів загально відомі, особливі зусилля мають бути скеровані на те, що б втаємничити їхні початкові значення та унеможливити їхнє обчислення на основі згенерованої послідовності. Крім того, саме початкове значення бажано зробити випадковим та непередбачуваним<ref name="nist_1.1.2"/>.

Властивості генераторів псевдовипадкових чисел оцінюють з використанням низки кількісних показників, основними з яких є:<ref name="hups.11573"/>
* період <math>l</math> (довжина) послідовності псевдовипадкових чисел;
* основа алфавіту <math>m</math>;
* ймовірність перекриття в просторі або в часі двох сегментів <math>Y_r</math> та <math>Y_\mu</math>, тобто в різних абонентів або в одного абонента протягом часу, так, що <math>Y_r = Y_\mu</math>;
* структурна скритність (еквівалентна складність) <math>S_e</math> послідовності <math>Y</math>;
* кількість ([[Інформаційна ентропія|ентропія]] <math>N_k(H_k)</math> джерела) ключів для випадку, коли генератор випадкових чисел використовують як джерело ключів;
* відстань рівнозначності <math>l_0</math> конкретної послідовності <math>Y_\nu</math>;
* безпечний час генератора випадкових чисел <math>t_b</math>;
* складність <math>I_y</math> формування послідовності <math>Y</math>;
* довжина параметрів зворотного зв'язку;
* властивості випадковості, рівноймовірності, незалежності та однорідності.

За всіма названими показниками до генератора послідовностей псевдовипадкових чисел висувають низку вимог. Так, період повторення <math>l_n \ge l_z</math>, тобто повинен бути не менше заданого, можливість змінної основи алфавіту <math>m</math>, ймовірність перекриття <math>P_n < P_z</math> менше допустимої, структурна скритність <math>S \ge S_g</math>, ентропія джерела ключів <math>H \ge H_g</math>, відстань рівнозначності <math>l_0 > l_g</math>, безпечний час <math>t_b < t_g</math>, тобто не менш допустимих. Крім того, реалізації <math>Y</math> i повинна задовольняти вимогам випадковості, рівноймовірності, незалежності та однозначності<ref name="hups.11573"/>.

Крім того, до генераторів псевдовипадкових послідовностей можуть бути висунуті вимоги прямої стійкості ({{lang-en|forward unpredictability}}): попри знання всіх попередніх чисел послідовності наступні числа мають бути непередбачуваними якщо не відоме початкове значення генератора. Зворотна стійкість вимагає унеможливити обчислення початкового значення на основі будь-якої кількості згенерованих чисел послідовності. [[Кореляція]] між початковим значенням та згенерованою послідовністю має бути неочевидною, а кожен наступний елемент має справляти враження реалізації [[випадкова подія|випадкової події]] з імовірністю ½<ref name="nist_1.1.2">{{cite report | title = A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications | publisher = NIST | series = Special Publication | chapter = 1.1.2 Unpredictability | id = NIST 800-22 | date = квітень 2010 | edition = Revision 1a | url = http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf | accessdate = 7 листопада 2017 | archive-date = 18 листопада 2017 | archive-url = https://web.archive.org/web/20171118085526/http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf }}</ref>.

== Стандарти ==
Загальним підходом до генерування ключів, ключової інформації та параметрів є стандартизація методів, механізмів і практичних (конкретних) алгоритмів їх генерування<ref name="hups.11573"/>.

Нині розроблені та прийняті регіональні і міжнародні стандарти, у яких визначені вимоги, методи, механізми та алгоритми реалізації генераторів. Оскільки при застосуванні засобів криптографічного захисту інформації необхідністю є відновлення ключів та ключової інформації у просторі й часі, у зазначених стандартах розглянуті лише детерміновані генератори випадкових бітів<ref name="hups.11573"/>.

Базовими міжнародними стандартами, що стандартизують алгоритми генерації послідовностей випадкових чисел є:<ref name="hups.11573"/>

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

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

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

Найбільш прийнятними (з точки зору практичного використання) методиками тестування є методики NIST STS, FIPS PUB 140-1, AIS 20 та AIS 31<ref name="hups.11573">{{cite article
 | title = Аналіз і обґрунтування критеріїв і показників ефективності криптографічних генераторів псевдовипадкових чисел
 | author = О. А. Замула, Д. О. Семченко, Ю. В. Землянко
 | journal = Системи обробки інформації
 | year = 2014
 | number = 4
 | issue = 120
 | pages = 131-136
 | url = http://www.hups.mil.gov.ua/periodic-app/article/11573
 | accessdate = 8 листопада 2017
 | archivedate = 8 листопада 2017
 | archiveurl = https://web.archive.org/web/20171108210418/http://www.hups.mil.gov.ua/periodic-app/article/11573
 }}</ref>.

== Приклади ==

; ANSI X9.17

Генератор псевдовипадкових послідовностей визначений у стандарті [[American National Standards Institute|ANSI]] X9.17 (''Financial Institution Key Management (wholesale)'') пройшов сертифікацію та прийнятий як стандарт [[Federal Information Processing Standard|FIPS]]. На вході він отримує [[Triple DES|TDEA]] ([[Triple DES|варіант ключів 2]]) набір ключів ''k'' та випадкове початкове число розміром 64 біт ''s''.<ref>[http://www.cacr.math.uwaterloo.ca/hac Handbook of Applied Cryptography] {{Webarchive|url=https://web.archive.org/web/20120216084232/http://www.cacr.math.uwaterloo.ca/hac/|date=16 лютого 2012}}, [[Alfred Menezes]], [[Paul van Oorschot]], and [[Scott Vanstone]], CRC Press, 1996, [http://www.cacr.math.uwaterloo.ca/hac/about/chap5.pdf Chapter 5 Pseudorandom Bits and Sequences] {{Webarchive|url=https://web.archive.org/web/20120208074532/http://www.cacr.math.uwaterloo.ca/hac/about/chap5.pdf|date=8 лютого 2012}} (PDF)</ref> Для обчислення наступного псевдовипадкового числа послідовності він:
* Бере поточний час ''D'' з найбільшою доступною точністю (мілісекунди, тощо).
* Обчислює проміжне значення ''t'' = TDEA<sub>''k''</sub>(''D'')
* Обчислює псевдовипадкове число ''x'' = TDEA<sub>''k''</sub>(''s'' ⊕ ''t''), де ⊕ позначає побітову операцію [[Виключна диз'юнкція|виключної диз'юнкції]].
* Оновлює значення початкового числа ''s'' = TDEA<sub>''k''</sub>(''x'' ⊕ ''t'')

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

=== DUHK ===

Попри відповідність алгоритму формальним вимогам стандартів його реалізації можуть мати [[Баг|вади]]. Так, в жовтні 2017 року група дослідників оприлюднила доповідь про виявлену ними ваду у деяких апаратних реалізаціях генераторів псевдовипадкових чисел. Зокрема, йдеться про [[Уразливість (інформаційні технології)|уразливість]] в реалізації генератора псевдовипадкових чисел ANSI X9.31 Random Number Generator (RNG), коли в пристрої виробником закодовано одне єдине [[Випадкове початкове значення|початкове значення генератора]] замість використання випадкового числа обчисленого іншим генератором випадкових чисел<ref name="bc.24-10-2017">{{cite web | url = https://www.bleepingcomputer.com/news/security/duhk-crypto-attack-recovers-encryption-keys-exposes-vpn-connections-more/ | title = DUHK Crypto Attack Recovers Encryption Keys, Exposes VPN Connections, More | author = Catalin Cimpanu | date = 24 жовтня 2017 | publisher = Bleeping Computer | accessdate = 7 листопада 2017 | archive-date = 25 жовтня 2017 | archive-url = https://web.archive.org/web/20171025175631/https://www.bleepingcomputer.com/news/security/duhk-crypto-attack-recovers-encryption-keys-exposes-vpn-connections-more/ }}</ref>.

Генератори ANSI X9.31 мають доволі широке використання в пристроях для генерації ключів шифрування [[VPN]], [[SSL]]/[[TLS]], [[IPsec]], тощо<ref name="bc.24-10-2017"/><ref name="duhk.paper">{{cite paper | title = Practical state recovery attacks against legacy RNG implementations | author = Shaanan Cohney, Nadia Heninger, and Matthew D. Green | url = https://duhkattack.com/paper.pdf | accessdate = 7 листопада 2017 | archivedate = 5 листопада 2017 | archiveurl = https://web.archive.org/web/20171105133321/https://duhkattack.com/paper.pdf }}</ref>.

Також дослідники розробили алгоритм атаки на знайдену ними вразливість. Алгоритм отримав назву DUHK ({{lang-en|Don't Use Hard-coded Keys}}) та дозволяє зловмиснику відтворити зашифровані дані аж до встановлення сеансового ключа<ref name="bc.24-10-2017"/>.

Дослідникам вдалось встановити 12 продуктів, які успішно пройшли сертифікацію [[FIPS 140|FIPS 140-2]], але в яких присутня дана вада<ref name="bc.24-10-2017"/>. Зокрема, вразливість була виявлена в популярній системі [[FortiOS]] v4 версії 4.3.17<ref name="duhk.paper"/>.

== Примітки ==
{{reflist|2}}

== Література ==
* Jan Krhovják, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.84.2279 Abstract Analysis, demands, and properties of pseudorandom number generators] {{Webarchive|url=https://web.archive.org/web/20171116031049/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.84.2279 |date=16 листопада 2017 }}

== Див. також ==

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

== Посилання ==

* {{cite report | title = A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications | publisher = NIST | series = Special Publication | id = NIST 800-22 | date = квітень 2010 | edition = Revision 1a | url = http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf | accessdate = 7 листопада 2017 | archive-date = 18 листопада 2017 | archive-url = https://web.archive.org/web/20171118085526/http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf }}
* RFC 4086 Randomness Requirements for Security (2005)
* [https://csrc.nist.gov/projects/random-bit-generation Random Bit Generation] {{Webarchive|url=https://web.archive.org/web/20171114040356/https://csrc.nist.gov/projects/random-bit-generation |date=14 листопада 2017 }} на сайті NIST


{{-}}{{Crypto-stub}}
{{Крипто навігація}}
{{ВП-портали|Програмування|Математика}}

[[Категорія:Генератори псевдовипадкових чисел]]