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

Статья посвящена обзору криптографически стойких генераторов псевдослучайных чисел (CSPRNG), ключевого элемента в обеспечении безопасности криптографических систем. Рассматриваются различные виды криптографически стойких генераторов псевдослучайных чисел, проведено их сравнение и анализ их уязвимостей.

Введение

Генераторы случайных чисел играют значительную роль в различных областях информационной технологии и науки. Вот несколько потенциальных областей применения:

1. Шифрование. Генераторы случайных чисел используются для формирования криптографически стойких ключей, которые применяются в различных шифровальных алгоритмах. Ключи, сгенерированные с использованием высококачественных случайных чисел, служат основой для безопасного обмена информацией и шифрования данных.

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

3. Моделирование событий. В научных исследованиях генераторы случайных чисел применяются для моделирования случайных процессов и симуляции различных событий и явлений, в том числе случайных входных данных.

4. Игры. Случайные числа задействованы в играх для генерации различных рандомизированных игровых элементов.

5. Статистика. В статистических и экспериментальных исследованиях случайные числа используются для формирования случайных выборок, что упрощает проведение анализов.

6. Рандомизация. Некоторые алгоритмы внедряют случайные числа для придания элемента случайности и предотвращения предсказуемости их поведения.

7. Криптографически стойкие генераторы (CSPRNG). В криптографии CSPRNG применяются для создания последовательностей псевдослучайных чисел с высокой стойкостью к криптоанализу. Эти генераторы играют ключевую роль в обеспечении безопасности криптографических систем и будут подробно рассмотрены в данной статье.

Общее использование случайных чисел обеспечивает разнообразие и непредсказуемость в различных контекстах, что является ключевым фактором в обеспечении безопасности, эффективности и надежности различных приложений и систем.

Генераторы случайных чисел [1] разделяются на две основные категории: истинные генераторы случайных чисел (TRNG) и псевдослучайные генераторы чисел (PRNG). TRNG создают случайные числа, опираясь на физические источники, к примеру, шум от тепловых, атмосферных или радиоактивных явлений. С другой стороны, PRNG генерируют числа детерминированно на основе начального значения, которое должно быть трудно предсказуемым и безопасным. Если кто-либо извне получает доступ к нему или может влиять на его генерацию, то он может предсказать вывод PRNG, что будет являться нарушением безопасности. Следовательно, разработка криптографически стойких PRNG остается актуальной задачей.

Псевдослучайный генератор чисел [2] – это функция, которая принимает короткое случайное начальное значение и выдает более длинную последовательность бит, которая кажется случайной. Криптографически стойкий генератор [3] псевдослучайных чисел (CSPRNG) обладает свойствами стойкости к криптоанализу и является важным средством в обеспечении безопасности криптографических систем, таких как шифрование данных, создание ключей и другие приложения, где требуется случайность с высоким уровнем безопасности. Для обеспечения криптографической безопасности вывод PRNG должен быть вычислительно неотличим от случайной строки. Это означает, что при наличии короткого префикса последовательности должно быть вычислительно невозможно предсказать оставшуюся часть последовательности без знания начального значения.

Таким образом, основные требования к CSPRNG включают [4]:

1. CSPRNG должен быть стойким к различным видам атак, таким как атаки на основе предсказания, статистические атаки и другие методы криптоанализа.

2. Период, в течение которого генератор не повторяет свою последовательность, должен быть как можно больше, чтобы предотвратить возможность атак перебора.

3. Эффективность алгоритма, а именно большая скорость его работы и малые затраты памяти.

Критерий, по которому можно оценить, является ли криптографически стойкий генератор псевдослучайных чисел надежным, [5] – по k бит случайной последовательности никаким полиноминальным по времени и памяти алгоритмам нельзя предсказать, какой будет следующий бит с вероятностью больше, чем в 50%. Если же числа последовательности должны находиться в диапазоне [0, n − 1], то должно быть недопустимо предсказать это число с вероятностью немного лучше, чем 1 / n.

Перейдем к классификации. На практике используются следующие методы [6] генерации случайных чисел:

1. Физические генераторы. Эти генераторы основаны на взаимодействии с внешними устройствами или предметами, и не зависят от операций, выполняемых самим компьютером. Они не задействуют дополнительные вычислительные ресурсы компьютера. Примерами являются монета («орел» и «решка») или игральные кости.

2. Табличные генераторы. В этих генераторах последовательность случайных чисел берется из заранее заполненной таблицы, что дает быстрый доступ к уже сгенерированным значениям. Однако, такие генераторы могут занимать достаточно памяти компьютера из-за того, что полученные значения помещаются в таблицу и сохраняются, а также они не обладают надежностью при повторных использованиях таблицы.

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

Каждый из этих методов имеет свои преимущества и недостатки в зависимости от конкретного применения. Выбор метода может зависеть от требований к безопасности, производительности, объема доступной памяти и других факторов.

Далее будут представлены алгоритмические генераторы. Рассмотрим, какие виды генераторов псевдослучайных чисел существуют, а также оценим их криптографическую стойкость.

Генераторы, основанные на регистре сдвига с обратной связью (LFSR)

Регистр сдвига с линейной обратной связью (LFSR) [7, 8] – это регистр сдвига, входной бит которого является линейной функцией его предыдущего состояния. Таким образом, это регистр сдвига, значение входного бита которого задается «исключающим или» (xor) некоторых уже имеющихся битов. Входными данными генератора являются начальное значение LFSR, а также принцип генерации входного бита, который также может быть представлен характеристическим полиномом в поле Галуа GF(2^m). В связи с тем, что работа регистра детерминирована, последовательность значений, генерируемых регистром, полностью определяется его текущим (или предыдущим) состоянием. Также, поскольку регистр имеет конечное число возможных состояний, в конечном итоге он должен войти в повторяющийся цикл. Однако, LFSR с правильно выбранной функцией обратной связи может генерировать последовательность битов, которая будет выглядеть случайной и имеет очень длинный период.

Таким образом, с точки зрения криптографии, такой генератор абсолютно не является стойким. Период псевдослучайной последовательности чисел, созданной подобным генератором, равен 2^m и является конечным, более того, зная характеристический полином, соответствующий регистру сдвига, можно с легкостью восстановить псевдослучайную последовательность чисел.

Линейный конгруэнтный генератор

Линейный конгруэнтный генератор [9] – это псевдослучайный генератор, который генерирует последовательность чисел в соответствии со следующей линейной формулой:

x_n = (ax_{n - 1} ​+ b) mod n,

где x_n​ представляет состояние генератора, а a, b и n – его параметры. Последовательность {x_n} является выходом генератора. Его максимальный возможный период равен 2ⁿ − 1. Также, часто в качестве n выбирают степени двойки, что позволяет избежать операции взятия по модулю.

Такой генератор прост в реализации. Следовательно, его можно рассматривать как хорошего кандидата для генерации псевдослучайных последовательностей. Однако есть важный недостаток, последовательность является предсказуемой. Имея фрагмент последовательности, легко восстановить все остальное, даже если неизвестны точные значения a, b и n. Таким образом, использование данного генератора в криптографических целях не является надежным.

Таким образом, два рассмотренных выше генератора последовательностей псевдослучайных чисел не являются достаточно криптографически стойкими.

Комбинированные генераторы

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

Во-первых, можно использовать рассмотренные ранее генераторы, основанные на линейных зависимостях, применяя нелинейные правила к их выходам. Во-вторых, является возможным соединить генераторы последовательно, то есть вход одного генератора является выходом другого. В-третьих, можно проводить синхронизацию генераторов, чтобы выход одного тем или иным образом зависел от выхода другого. Иначе говоря, можно комбинировать различные регистры сдвига с линейной обратной связью и линейные конгруэнтные генераторы, тем самым образуя из них более комплексный генератор. Тогда период получившейся в результате последовательности псевдослучайных чисел будет гораздо больше. В таком случае комбинированные генераторы будут более криптографически стойкими, чем генераторы, являющиеся их компонентами.

Примером комбинированного генератора является алгоритм A5/1 [10, 11], который состоит из трех генераторов, основанных на регистре сдвига с обратной связью. Также можно комбинировать не только генераторы, основанные на линейных зависимостях, но и любые иные генераторы псевдослучайных последовательностей чисел.

Генераторы, использующие блочные шифры в режиме счетчика (CTR)

Данные генераторы используют блочные шифры [12] для образования последовательности псевдослучайных чисел на выходе. Блочный шифр преобразует n-битную входную строку (блок) в n-битную выходную строку, используя секретный ключ некоторого фиксированного размера. Примерами блочных шифров являются DES и AES, они отличаются размерами ключа и блока, для DES 56 и 64 бит соответственно, для AES 128/192/256 и 128 бит соответственно.

Режим счетчика, или CTR – это реализация блочного шифрования на основе счетчика в криптографии. Каждый раз, когда значение, инициированное счетчиком, шифруется и передается в качестве входных данных XOR с исходным текстом, который приводит к блоку зашифрованных данных. Режим CTR не зависит от использования обратной связи и, таким образом, может быть реализован параллельно в этом режиме. Он генерирует следующий блок ключевого потока путем шифрования последовательных значений. Этот счетчик может быть любого назначения или функции, генерирующей последовательность, которая гарантированно не будет вызываться в течение длительного времени. Однако, счетчик с прибавлением единицы является самым распространенным. Также, начальные значения для генератора, основанном на CTR, должны не повторяться, чтобы последовательность на выходе действительно была псевдослучайной. Тем не менее, период псевдослучайной последовательности чисел будет не превышать 2ⁿ. Надежность генератора полностью зависит только от ключа, что делает его криптографически стойким, однако, все еще существует периодичность псевдослучайной последовательности.

Генераторы на основе хэширования

Подобные генераторы задействуют хэширование для преобразования начального значения в последовательность чисел. Благодаря хэш-функциям результирующая последовательность является псевдослучайной. Далее приведено определение хэш-функции. Криптографическая хэш-функция – это функция, которая принимает входные данные переменной длины для возврата выходных данных фиксированной длины, называемых хэш-значением, или просто “хэшем”. Их использование в криптографии, тем более в генераторах псевдослучайных последовательностей, обусловлено сложностью их расшифровки.

Криптографические хэш-функции должны обладать некоторыми свойствами [13]:

1. Необратимость, или односторонняя функция. Хорошее хэш-значение должно затруднять восстановление исходного пароля по выходным данным или по хэшу.

2. Диффузионный, или лавинообразный эффект. Изменение всего одного бита исходных входных данных должно привести к изменению половины битов их хэша. Другими словами, при незначительном изменении входа вывод должен измениться значительно и непредсказуемо.

3. Детерминизм. Заданные входные данные всегда должен генерировать одно и то же хэш-значение.

4. Устойчивость к коллизиям. Должно быть сложно найти два разных входных данных, которые имеют одинаковое хэш-значение. Здесь стоит отметить разницу между просто хэш-функциями и криптографическими. Криптографические хэш-функции предназначены для защиты от коллизий, в то время как хэш-функции созданы для ускорения решения.

5. Непредсказуемость. Значение хэша не должно быть предсказуемым по входным данным.

Преимуществом использования криптографических хэш-функций является то, что криптографические хэш-функции принимают что-то на вход и преобразуют их в хэш-значения, расшифровка которых затрачивает время, ресурсы и прочее.

Рассмотрим недостатки криптографических хэш-функций [14]. Несмотря на то, что криптографические хэши могут замедлить работу злоумышленников, но в конечном итоге, особенно при условии простоты хэшей, они не смогут обеспечить полноценную безопасность. Более того, при наличии хорошего оборудования, хэш-значения могут быть быстро расшифрованы. К тому же, хорошие алгоритмы хэширования разработаны так, чтобы быть устойчивыми к коллизиям, но полностью устранить коллизии невозможно. Доказано, что хэш-функции MD5 и SHA-1 содержат известные коллизии, например, выдают одно и то же значение хэша из разных учетных данных.

Еще одной уязвимостью криптографических хэш-функций являются радужные таблицы. [15] Это оптимизированные таблицы поиска, которые можно использовать для обратного проектирования односторонних хэш-функций. Радужная таблица – это предварительно вычисленный набор строк открытого текста и соответствующих им хэшей. Большие радужные таблицы находятся в открытом доступе, и могут быть использованы злоумышленниками для расшифровки хэшей.

Одной из рекомендуемых к использованию криптографических хэш-функций является VSH (Very Smooth Hash function) [16]. Она надежная, обладает стойкостью к коллизиям, по сложности алгоритма сравнима с разложением числа на множители, что является основой другого генератора, а именно Blum Blum Shub (BBS). К сожалению, использование многих других хэш-функций затруднено в связи с наличием в них уязвимостей.

Далее приводится краткое описание хэш-функции VSH [17]:

Пусть p₁ = 2, p₂ = 3, p₃ = 5, . . . - последовательность простых чисел. Пусть n – модуль, а k – длина блока, является наибольшим целым числом, таким, что

Пусть m – l-битовое сообщение, подлежащее хэшированию, состоящее из битов m₁, . . . , m_l, и выполняется l < 2^k. Алгоритм вычисления хэша m:

1. Пусть x₀ = 1.

2. Пусть L = [ l / k ] (количество блоков). Пусть m_i = 0 для l < i ≤ Lk.

3. Пусть

где l_i ∈ {0, 1} – двоичное представление сообщения длины l и m_Lk+i = l_i для 1 ≤ i ≤ k .

4. Для j = 0, 1, . . . , L последовательно вычисляется

5. Возвращается x_L+1.

В генераторах, основанных на хэшировании, криптографические хэш-функции используются по аналогии с генераторами, использующими блочные шифры в режиме счетчика. Также выбирается начальное значение, а затем к нему применяется итеративно хэширование. Главными недостатками этого типа генераторов являются две вещи. Во-первых, имея начальное значение и тип используемой криптографической функции, возможно восстановить всю псевдослучайную последовательность, а во-вторых, нельзя забывать про существующие недостатки хэш-функций, рассмотренные ранее.

Генераторы на основе математических алгоритмов

В основе данных генераторов лежат нетривиальные математические алгоритмы. Такие генераторы используют комплексные вычислительные задачи для гарантирования собственной стойкости. Примером является генератор последовательности псевдослучайных чисел Blum Blum Shub (BBS) [18]. Он используется в качестве генератора псевдослучайных чисел и был создан Ленор Блюм, Мануэлем Блюмом и Майклом Шубом в 1968 году. Blum–Blum–Shub (BBS) является одним из наиболее эффективных известных генераторов псевдослучайных чисел, который безопасен в предположении, что разложение на множители больших чисел неразрешимо, иначе говоря, невозможна целочисленная факторизация. Этот генератор использует модульную арифметику и работает следующим образом. Blum Blum Shub [19] основан на формуле x_{n + 1} = x_n² (mod M), где x₀ – начальное случайное значение. Значение M равно pq, где p и q – простые числа. Оба значения p и q должны быть равны 3 по модулю 4: p = q = 3 (mod 4), они называются целыми числами Блюма. Для каждой итерации берется младший значащий бит x_{n + 1}. Безопасность метода связана со сложностью разложения M на множители. Это медленный, но один из самых надежных и криптографически стойких известных генераторов случайных чисел. Данный генератор не используется для шифрования, но может быть использован при генерации ключей.

Генераторы, предложенные NIST

Напоследок оценим криптографическую стойкость генераторов псевдослучайных последовательностей чисел, предложенных к использованию национальным институтом стандартов и технологий (NIST), а именно – ANSI X9.31 и Dual EC DRBG.

ANSI X9.31 [20] генератор использует блочный шифр. Спецификация NIST [21] предлагает две реализации с использованием алгоритмов 3DES или AES. 3DES был разработан как более надежная альтернатива из-за небольшой длины ключа DES. В 3DES алгоритм DES выполняется трижды с тремя ключами. Однако, он считается безопасным только в том случае, если используются три отдельных ключа. Рассмотрим принцип работы генератора на примере AES. Пусть K – 128-битный секретный ключ AES, который зарезервирован только для генерации псевдослучайных чисел. EK обозначает шифрование AES под ключом K, V – это 128-разрядное начальное значение, а DT – 128-разрядный вектор. I – это промежуточное значение, а символ ⊕ является оператором исключающего или (XOR). Псевдослучайный выходной сигнал R генерируется на каждой итерации следующим образом:

1. I = EK(DT),

2. R = EK(I ⊕ V),

3. V = EK(R ⊕ I).

Надежность данного генератора зависит исключительно от секретного ключа. Так была выявлена уязвимость DUHK (Don't Use Hard-coded Keys) [22]. Она заключается в том, что если используется генератор случайных чисел X9.31 и секретный ключ, используемый генератором, жестко запрограммирован в реализации генератора, то злоумышленники могут узнать ключ и восстановить псевдослучайную последовательность чисел.

Детерминированный генератор случайных битов с двойной эллиптической кривой, или Dual EC DRBG [23] – это алгоритм, стандартизированный NIST и представленный как криптографически защищенный генератор случайных чисел. Из-за широко распространенных подозрений о намеренном ослаблении алгоритма, он был официально отозван в качестве стандарта в 2014 году. Данный генератор работает на основе эллиптической кривой. Его надежность основана на неразрешимости задачи дискретного логарифма.

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

Далее приведено краткое описание того, как работает генератор. Эллиптическая кривая, как и две точки P и Q, которые принадлежат кривой, заданы изначально. Пусть s1 – существующее состояние. Вычисляется s1·P, и результат присваивается промежуточному значению r. Далее вычисляется r·P, это будет s2 – следующее значение внутреннего состояния. Затем вычисляется r·Q, фиксированное количество младших битов из результата добавляется в псевдослучайную последовательность. Внутреннее состояние обновляется до значения s2. Следовательно, для того, чтобы восстановить псевдослучайную последовательность чисел, нужно получить r·P, но для этого необходимо решить задачу дискретного логарифма на эллиптической кривой.

Предположим, что существует некоторое e такое, что P = e·Q. Если это так, то теоретически становится возможным вычислить e·(r·Q) = r·(e·Q) = r·P и, таким образом, найти внутреннее состояние генератора. Однако это не является проблемой, потому что найти e практически невозможно из-за неразрешимости задачи дискретного логарифма.

Проблема данного генератора заключается в том, что неизвестно, как именно были изначально выбраны P и Q. Вполне возможно, что было выбрано случайное значение для e, а затем исходя из него были сгенерированы P и Q. Если это так, следовательно, существует возможность предсказать следующее число в последовательности. P и Q должны быть выбраны случайным образом, но в этом случае это не будет выполняться. Таким образом, это ослабляет генератор и дает бэкдор-информацию о нем тем, кто знает значение e.

На данный момент оба генератора не считаются криптографически стойкими [24] из-за выявленных проблем.

Заключение

Таким образом, были изучены различные генераторы псевдослучайных последовательностей чисел, а также проанализирована их криптографическая стойкость. Было выяснено, что генераторы, основанные на линейных зависимостях, такие как генераторы, основанные на регистре сдвига с обратной связью, или линейные конгруэнтные генераторы, не обладают данным свойством. Однако, с помощью использования комбинированных генераторов является возможным повысить надежность. Наиболее криптографически стойкими являются генераторы Blum Blum Shub (BBS), а также генератор на основе хэш-функции VSH (Very Smooth Hash function).

Список литературы:

1. Генераторы псевдослучайных чисел. Слеповичев И.И.. Учебное пособие

2. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, AndrewRukhin, JuanSoto, JamesNechvatal, Miles Smid, Elaine Barker, Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, James Dray, San Vo, April 2010

3. Design and implementation of a novel cryptographically secure pseudorandom number generator, Juan Di Mauro, Eduardo Salazar, Hugo D. Scolnik, Journal of Cryptographic Engineering (2022) 12:255–265

4. URL: https://science-engineering.ru/ru/article/view?id=1321 (дата обращения: 07.12.2023).

5. Обзорная экскурсия в криптографически стойкие генераторы псевдослучайных чисел https://habr.com/ru/articles/595905/

6. Лекции курса «Моделирование систем», Мухин Олег Игоревич, Пермский национальный исследовательский политехнический университет

7. Pseudorandom Number Generation using LFSR, Arpit Bhayani, Feb 2022

8. Implementation of Random Number Generator Using LFSR for High Secured Multi Purpose Applications, M.Sahithi, B.MuraliKrishna, M.Jyothi, K.Purnima, A.Jhansi Rani, N.Naga Sudha, (IJCSIT) International Journal of Computer Science and Information Technologies, Vol. 3 (1), 2012, 3287-3290

9. Encyclopedia of Cryptography and Security, Caroline Fontaine, Oct 2006, pp 350

10. Габидулин Э. М., Кшевецкий А. С., Колыбельников А.И. Защита информации: учебное пособие — М.: МФТИ, 2019

11. ЗАЩИЩЕННАЯ СВЯЗЬ В СТАНДАРТЕ GSM, Ю. Б. Нечаев, Б. Н. Воронков, Е. С. Долбилова, А. В. Дудченко, Воронежский государственный университет

12. Design, Implementation, and Analysis of a Block Cipher Based on a Secure Chaotic Generator, Fethi Dridi, Safwan El Assad, Wajih El Hadj Youssef, Mohsen Machhout, Sep 2022

13. What are cryptographic hash functions? Synopsys Editorial Team Dec 10, 2015

14. https://www.sciencedirect.com/topics/computer-science/cryptographic-hash-algorithm

15. https://www.geeksforgeeks.org/understanding-rainbow-table-attack/

16. VSH, an Efficient and Provable Collision-Resistant Hash Function, Scott Contini, Arjen K. Lenstra & Ron Steinfeld, Annual International Conference on the Theory and Applications of Cryptographic Techniques

17. Security of VSH in the Real World, Markku-Juhani O. Saarinen, Information Security Group Royal Holloway, University of London Egham, Surrey TW20 0EX, UK.

18. Encyclopedia of Cryptography and Security, Henk C. A. Tilborg, Oct 2006, pp 50-51

19. Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator, Pascal Junod, August 1999

20. Generating Random and Pseudorandom Sequences in Mobile Devices, Jan Krhovjak, Vashek Matyas, Jiri Zizkovsky, Faculty of Informatics, Masaryk University, Brno, Czech Republic

21. Keller, S.S.: NIST-recommended random number generator based on ANSI X9.31 Appendix A.2.4 using the 3-key triple DES and AES algorithms. NIST (2005)

22. https://duhkattack.com/

23. https://www.vokke.com.au/blog/2021/01/15/failure-of-the-dual-elliptic-curve-prng/

24. https://csrc.nist.gov/pubs/sp/800/131/a/r1/final