Криптографически стойкий генератор псевдослучайных чисел
Криптографически стойкий генератор псевдослучайных чисел (англ. Cryptographically secure pseudorandom number generator, CSPRNG) — это генератор псевдослучайных чисел с определёнными свойствами, позволяющими использовать его в криптографии.
Многие прикладные задачи криптографии требуют случайных чисел, например:
- Генерация ключей
- Одноразовые случайные числа (англ. Nonces)
- Одноразовые шифроблокноты
- Соль в схемах цифровой подписи, например ECDSA
Задача
[править | править код]Требуемое «качество» случайности меняется от задачи к задаче. Например, генерация одного случайного числа в некоторых протоколах требует только уникальности, тогда как генерация мастер-ключа или одноразового шифроблокнота требует высокой энтропии. В идеале, генерация случайных чисел в КСГПСЧ использует высоконадёжный источник энтропии, которым может быть аппаратный генератор случайных чисел или ход непредсказуемых процессов в системе — хотя в обоих случаях возможны неожиданные уязвимости[1][2]. С точки зрения теории информации количество случайности — энтропия, которая может быть получена, равна энтропии, предоставляемой системой. Но зачастую в реальных ситуация требуется больше случайных чисел, чем можно получить при существующей энтропии. К тому же процедура получения случайности из самой системы требует достаточно много ресурсов (памяти и времени). В таких случаях, оправданно использование КСГПСЧ — это позволяет «растянуть» имеющуюся энтропию на большее число бит. Когда вся энтропия доступна до выполнения криптографического алгоритма, получается потоковый шифр[3]. Однако некоторые криптосистемы позволяют добавлять энтропию по мере работы, в таком случае алгоритм не является эквивалентом потокового шифра и не может использоваться в этом качестве. Таким образом, разработка потоковых шифров и КСГПСЧ тесно связаны.
Требования
[править | править код]Требования[4][5] к обычному генератору псевдослучайных чисел выполняются и криптографически стойким ГПСЧ, обратное неверно. Требования к КСГПСЧ можно разделить на две группы: во-первых, они должны проходить статистические тесты на случайность; а во-вторых, они должны сохранять непредсказуемость, даже если часть их исходного или текущего состояния становится известна криптоаналитику. А именно:
- КСГПСЧ должен удовлетворять «тесту на следующий бит». Смысл теста в следующем: не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать (k+1)-ый бит с вероятностью более 50 %. Эндрю Яо доказал в 1982 году, что генератор, прошедший «тест на следующий бит», пройдёт и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
- КСГПСЧ должен оставаться надёжным даже в случае, когда часть или все его состояния стали известны (или были корректно вычислены). Это значит, что не должно быть возможности получить случайную последовательность, созданную генератором, предшествующую получению этого знания криптоаналитиком. Кроме того, если во время работы используется дополнительная энтропия, попытка использовать знание о входных данных должна быть вычислительно невозможна.
- Пример
- Пусть генератор основывается на выводе битов двоичного представления числа π, начиная с какой-то неизвестной точки. Такой генератор, возможно, и пройдёт «тест на следующий бит», так как π, видимо, является случайной последовательностью (это было бы гарантированно, если доказать, что π является нормальным числом). Однако этот подход не является криптографически надёжным — если криптоаналитик определит, какой бит числа π используется в данный момент, он сможет вычислить и все предшествующие биты.
Большинство генераторов псевдослучайных чисел не подходит для использования в качестве КСГПСЧ по обоим критериям. Во-первых, несмотря на то, что многие ГПСЧ выдают последовательность, случайную с точки зрения разнообразных статистических тестов, они не надёжны по отношению к обратной разработке. Могут быть обнаружены специализированные, особым образом настроенные тесты, которые покажут, что случайные числа, получаемые из ГПСЧ не являются по настоящему случайными. Во-вторых, для большинства ГПСЧ возможно вычислить всю псевдослучайную последовательность, если их состояние скомпрометировано, что позволит криптоаналитику получить доступ не только к будущим сообщениям, но и ко всем предыдущим. КСГПСЧ разрабатываются с учётом сопротивляемости к различным видам криптоанализа.
Реализации
[править | править код]Рассмотрим три класса реализации КСГПСЧ:
- На основе криптографических алгоритмов
- На основе вычислительно сложных математических задач
- Специальные реализации
В последних часто используются дополнительные источники энтропии, поэтому, строго говоря, они не являются «чистыми» генераторами, так как их выход не полностью определяется исходным состоянием. Это позволяет дополнительно защититься от атак, направленных на определение исходного состояния.
Реализации на основе криптографических алгоритмов
[править | править код]- Безопасный блочный шифр можно преобразовать в КСГПСЧ, запустив его в режиме счетчика. Таким образом, выбрав случайный ключ, можно получать следующий случайный блок, применяя алгоритм к последовательным натуральным числам. Счет можно начинать с произвольного натурального числа. Очевидно, что периодом будет не больше, чем 2n для n-битного блочного шифра. Также очевидно, что безопасность такой схемы полностью зависит от секретности ключа.
- Криптографически стойкая хеш-функция также может быть преобразована в КСГПСЧ. В таком случае исходное значение счетчика должно оставаться в секрете. Однако, некоторые авторы предостерегают от такого использования хеш-функций[6].
- Большинство потоковых шифров работает на основе генерации псевдослучайного потока бит, которые некоторым образом комбинируется (почти всегда с помощью операции XOR) с битами открытого текста. Запуск такого шифра на последовательности натуральных чисел даст новую псевдослучайную последовательность, возможно, даже с более длинным периодом. Такой метод безопасен только если в самом потоковом шифре используется надёжный КСГПСЧ (что не всегда так). Опять же, начальное состояние счётчика должно оставаться секретным.
Реализации на основе математических задач
[править | править код]- Алгоритм Блюма — Блюма — Шуба имеет высокую криптостойкость, основанную на предполагаемой сложности факторизации целых чисел. Однако, этот алгоритм отличается очень медленной работой.
- Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) основан на задаче дискретного логарифма.
Специальные реализации
[править | править код]Существует целый ряд практически используемых ГПСЧ которые разрабатывались с учетом криптографической стойкости, например
- Алгоритм Ярроу (англ. Yarrow algorithm)[7] который пытается определить энтропию входных данных. Он используется в FreeBSD, OpenBSD и Mac OS X
- Алгоритм Fortuna (англ. Fortuna algorithm), наследник алгоритма Ярроу.
- Специальный файл ОС UNIX /dev/random, в частности, /dev/urandom, реализованный в Linux.
- Функция CryptGenRandom предоставленная в CryptoAPI компании Microsoft[8]
- ISAAC базируется на варианте RC4.
Примечания
[править | править код]- ↑ Zvi Gutterman. Open to Attack: Vulnerabilities of the Linux Random Number Generator (англ.). Дата обращения: 15 ноября 2010. Архивировано 27 февраля 2011 года.
- ↑ Stealthy Dopant-Level Hardware Trojans Архивная копия от 5 декабря 2013 на Wayback Machine (о потенциальном внедрении троянов в состав аппаратного генератора случайных чисел).
- ↑ Шнайер Б. 16 Генераторы псевдослучайных последовательностей и потоковые шифры // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
- ↑ Шнайер Б. 2.8 Генерация случайных и псевдослучайных последовательностей // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
- ↑ Peter Gutmann. Software Generation of Practically Strong Random Numbers (англ.) // Proceedings of the 7th USENIX Security Symposium : journal. — 1998. Архивировано 4 июля 2012 года.
- ↑ Adam Young, Moti Yung. Malicious Cryptography: Exposing Cryptovirology (англ.). — sect 3.2: John Wiley & Sons, 2004. — P. 416. — ISBN 978-0-7645-4975-5. Архивировано 27 мая 2009 года.
- ↑ Yarrow. Дата обращения: 15 ноября 2010. Архивировано 8 ноября 2012 года.
- ↑ Описание функции CryptoGenRandom на MSDN (англ.). Microsoft. Дата обращения: 15 ноября 2010. Архивировано 4 июля 2012 года.
Ссылки
[править | править код]- Юрий Лифшиц. Лекция 9: Псевдослучайные генераторы // Современные задачи криптографии. — Курс лекций. (недоступная ссылка)
- Cryptographic Random Numbers (англ.)
- Theory and Practice of Random Number Generation (англ.)
- Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analysis of the Linux Random Number Generator (англ.)
- A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (англ.) NIST SP 800-22