Обзорная экскурсия в криптографически стойкие генераторы псевдослучайных чисел16.12.2021 08:01

image-loader.svg

0.Вступление

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

Для получения этих самых случайных чисел используются так называемые генераторы псевдослучайных чисел (ГПСЧ) — алгоритмы, на основе двоичной последовательности длины k порождающие последовательность длины l >> k, элементы которой слабо зависят друг от друга и подчиняются заданному распределению (обычно равномерному). Входное значение называется инициализационным вектором, а выход — псевдослучайной последовательностью бит. Генераторы должны удовлетворять следующим требованиям:

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

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

  3. Воспроизводимость — возможность заново воспроизвести ранее сгенерированную последовательность чисел любое число раз.

  4. Портируемость — одинаковое функционирование на различном оборудовании и операционных системах.

  5. Быстрота получения Xn+i элемента последовательности при задании Xn элемента для любой величины i  (для разделения последовательности на несколько потоков)

Несмотря на то, что существует большое число удовлетворяющих этим требованиям ГПСЧ, лишь малая их часть является криптографически стойкими, то есть удовлетворяющими статистическим тестам на случайность и специальным требованиям:

1.Требования к криптографически стойким ГПСЧ (КСГПСЧ)

  1. Тест на следующий бит — не должно существовать полиномиального алгоритма, который, зная первые k бит случайной последовательности, сможет предсказать k + 1 бит с вероятность большей 50%.
    Генератор, прошедший «тест на следующий бит», пройдёт и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.

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

Например, если генератор основывается на выводе двоичного представления числа π с какой-то неизвестной точки, он не является криптографически устойчивым — при определении текущего бита числа π аналитик может вычислить и все предшествующие биты.

2.Виды генераторов случайных чисел

Генераторы случайных чисел по способу получения чисел делятся на:

  1. Аппаратные

  2. Табличные

  3. Алгоритмические

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

Аппаратные генераторы (истинно) случайных последовательностей — устройство, использующее для создания случайных чисел замеры параметров некоторых физических процессов. Как правило, аппаратный генератор случайных чисел состоит из источника энтропии и устройства, преобразующего значения, полученные с источника энтропии, в нужный формат. Разработка генераторов, использующих источники энтропии, генерирующих не коррелированные и статистически независимые числа — достаточно сложная задача. Источниками энтропии, могут быть, например, временные задержки между моментами излучения частиц в процессе радиоактивного распада, тепловые шумы при работе полупроводникового диода или резистора, частотные отклонения свободно работающего генератора частот, фотоэффект. Для большинства криптографических приложений такой ГПСЧ не должен быть предметом изучения и воздействий криптоаналитиков.

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

3.Алгоритмические генераторы

Из-за дороговизны аппаратных генераторов случайных чисел в большинстве случаев, в качестве источника энтропии используются ресурсы вычислительной машины, на которой выполняется программа генерации ПСЧ. В персональных компьютерах используются быстрые (по сравнению с аппаратными) источники энтропии, такие как шум звуковой карты, счетчик тактов процессора, измерение реакции пользователя (движение мышки или нажатие клавиш, их используют, например, PGP и Yarrow), или взаимодействие между потоками, как, например, Java SecureRandom.

Рассмотрим 3 класса реализации КСГПСЧ:

  1. Методы на основе криптографических алгоритмов.

  2. Методы на основе односторонних функций (математически сложных задач).

  3. Специальные реализации.

3.1.Криптографические алгоритмы

В данном случае генерация может осуществляться одним из следующих способов:

  1. Применением безопасного блочного шифра в режиме счетчика (гаммирования) к некоторому случайному ключу.

  2. Применением криптографически стойкой хэш-функции к исходному секретному случайному числу.

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

3.1.1.Безопасный блочный шифр

Рассмотрим подробнее данный способ генерации. Блочный шифр — разновидность шифра, основными особенностями которого являются шифрование исходного текста блоками (например, по n-бит),   содержимое каждого из которых никак не влияет на результат шифрования других блоков.  Формально его можно представить в виде функции E, которая на вход получает блок данных M размером n бит и ключ K размером k бит и на выходе отдает блок шифротекста C размером n бит:

Ek (M) = E (K, M) : {0, 1}k x {0, 1}n ↦ {0, 1}n

Для любого ключа K,  EK является биективной функцией на множестве n-битных блоков, то есть всегда существует обратная функция Ek-1, однозначно и корректно отображающая шифротекст в исходное сообщение.

Примеры безопасных блочных шифров

  • Des — (Data Encryption Standard) — алгоритм, разработанный фирмой IBM и утверждённый правительством США в 1977 году как федеральный стандарт (FIPS 46–3). DES имеет размер блока 64 бит и ключ 56 бит. Впоследствии 64-битные блоки стали общепринятыми при построении шифра. Длина ключа зависела от нескольких факторов, в том числе от правительственных ограничений, и в результате стала очевидным недостатком алгоритма — её оказалось недостаточно, чтобы противостоять атакам полным перебором. Существует улучшенная версия алгоритма, называемая Triple DES или 3DES. Скорость алгоритма снизилась трижды, но система оказалась значительно более устойчива к полному перебору за счёт утроенной длины ключа (168 бит и 112 секретных бит). Опционально можно выбрать удвоенный ключ (112 бит и 80 секретных бит). По состоянию на 2011 год трехключевая система сохраняет свою безопасность, однако двуключевая версия с 80-битным уровнем безопасности больше не удовлетворяет современным требованиям

  • AES (Advanced Encryption Standard) — алгоритм, заменивший собой шифр DES в качестве федерального стандарта США.  Размер блока составляет 128 бит и размер ключа 128, 192 и 256 бит, несмотря на то, что размер блока может быть определён любым числом бит, кратным 32, с минимальным значением 128 бит. Максимальный размер блока равен 256 бит, при этом размер ключа не имеет теоретического предела. Поддержка данного шифра введена компанией Intel в семейство процессоров x86

  • ГОСТ 28147–89 — российский стандарт шифрования, введенный в 1990 году, также является стандартом СНГ. Шифр основан на 32-раундовой сети Фейстеля c 256-битным ключом. Вопрос о безопасности ГОСТа остается открытым.

Режим счетчика блочного шифра (CTR mode) — предполагает возврат на вход соответствующего алгоритма блочного шифрования значения некоторого счётчика, накопленного с момента старта. Режим делает из блочного шифра потоковый, то есть генерирует последовательность, к которой применяется операция XOR с текстом сообщения. Исходный текст и блок зашифрованного текста имеют один и тот же размер блока, как и основной шифр (например,  DES или AES). Режим CTR предусматривает следующие операции:

Шифрование:

C_i=P_i⊕E_k (T_i );i=1,2,…,m

Расшифрование:

P_i=C_i⊕E_k (T_i );i=1,2,…,m

Где i — номер блока, Ci — зашифрованный текст, Pi — блок сообщения, Ek — алгоритм шифрования (например, AES), Ti — значение счетчика для i-го блока. Значения счетчика должны быть уникальны для каждого блока шифруемого текста. Это осуществляется в 2 этапа.

Во-первых,  значения счётчика для шифрования блоков в пределах одного сообщения получаются из начального значения счётчика использованием функции приращения. Чтобы обеспечивать случайность, величина приращения может зависеть от номера блока. Стандартная функция приращения может быть применена как ко всему блоку счётчика, так и к его части. Пусть значение счётчика представляет блок из b битов, а функцию приращения мы применяем к m младшим разрядам:

L_{i+1}=(L_i+1)\ mod\ 2^mT_i=M_i | L_{i+1}

Где | — функция конкатенации; Li —  младшие m битов; Mi — старшие (b-m) битов. Уникальность значений счетчика обеспечивается для всех блоков сообщения при условии, что n ≤ 2m, где n — количество блоков, на которое разбивается сообщение.

Во-вторых, начальные значения счётчика для каждого сообщения выбираются таким образом, чтобы обеспечить уникальность всех используемых значений счётчика. Этого можно достичь разными способами. Например, если сообщения шифруются последовательно, то в качестве начального значения счётчика для данного сообщения можно использовать результат применения функции приращения к последнему значению счётчика предыдущего сообщения. При этом если функция приращения использует m битов, общее количество блоков открытого текста не должно превышать 2m.  Другой подход предлагает разбить двоичное представление счётчика на две части. Старшие разряды назначаются одноразовым номером сообщения, а к оставшимся будет применяться функция приращения.

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

3.1.2.Криптографически стойкая хэш-функция

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

  • Сопротивление поиску первого прообраза:
    При наличии хеша h должно быть трудно найти какое-либо сообщение m такое, что h = hash (m), Это свойство связано с понятием односторонней функции. Функции, у которых отсутствует это свойство, уязвимы для атак нахождения первого прообраза.

  • Сопротивление поиску второго прообраза:
    При наличии сообщения m1, должно быть трудно найти другое сообщение m2 (не равное m1) такое, что hash (m1) = hash (m2). Это свойство иногда называют слабым сопротивлением поиску коллизий. Функции, у которых отсутствует это свойство, уязвимы для атак поиска второго прообраза.

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

  • Стойкость к удлинению прообраза:
    Если сообщение неизвестно, но известны его длина и хеш-код от него, то должно быть сложно подобрать сообщение, которое, будучи дописанным к оригинальному, даст какую-нибудь известную хеш-функцию. Другими словами, не должно иметься возможности злоумышленнику что-то менять путём дополнения в сообщении, получая известный выход. Это можно сформулировать по-другому: хеш-функция не должна быть хорошо «дополняема».

Примеры безопасных хэш-функций

  • VSH (Very Smooth Hash function) — доказуемо безопасная и устойчивая к коллизиям функция, опирающаяся на сложность нахождения нетривиальных квадратных корней по модулю составного числа n (что является настолько же сложным, насколько разложение n на множители).

  • MD4 и MD5 — в данный момент не рекомендуются для применения в реальных приложениях из-за найденных уязвимостей.

  • SHA-1, SHA-2, SHA-3, SHA-256
    SHA-1 и SHA-2 не рекомендуется использовать из-за найденных уязвимостей.
    SHA-3 — алгоритм, основанный на принципе криптографической губки. Утвержден и опубликован в качестве Федерального стандарта обработки информации в США.
    SHA-256 — алгоритм, используемый в алгоритмах хеширования биткоина и других криптовалют. Выходной хеш составляет в длину 256 бит, соответствующую энтропию можно определить, как множество значение от 1 до 2256 — это огромное число значений, что делает взлом  расшифровку крайне трудоемким процессом, опирающимся на последовательный перебор.

  • Стрибог — криптографический алгоритм вычисления хеш-функции с размером блока входных данных 512 бит и размером хеш-кода 256 или 512 бит. Описан в ГОСТ 34.11–2018.

Использование в криптостойком ГПСЧ

Использование хэш-функции для генерации КСПСЧ подобно использованию блочного шифра для этой же цели. Выбрав некоторое инициализирующее натуральное число S1, мы последовательно применяем преобразование Si+1 = H (Si). Алгоритм может быть модифицирован, но главная его уязвимость останется — безопасность полностью зависит от инициализирующего значения. Узнав инициализирующее значение и алгоритм ГПСЧ, злоумышленник может построить всю последовательность ПСЧ.

3.1.3.Потоковый шифр

Большинство потоковых шифров работают на основе генерации псевдослучайного потока бит, которые некоторым образом комбинируется (почти всегда с помощью операции XOR) с битами открытого текста. Запуск такого шифра на последовательности натуральных чисел даст новую псевдослучайную последовательность, возможно, даже с более длинным периодом. Такой метод безопасен только при использовании надёжного КСГПСЧ в самом потоковом шифре (что не всегда так). Начальное состояние счетчика должно оставаться секретным и в этом случае.

Примеры используемых в КСПГСЧ потоковых шифров

В качестве примера можно привести RC4 — потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах SSL и TLS, алгоритмах обеспечения безопасности беспроводных сетей WEP и WPA). Его достоинствами являются высокая скорость работы и переменный размер ключа.

3.2.Алгоритмы на основе математических задач

Алгоритмы ГПСЧ на основе сложных математических задач используют сложность решения некоторых задач для получения псевдослучайных чисел, защищенных от криптоанализа.  Примерами таких алгоритмов являются алгоритм Блюма-Блюма-Шуба, в основе которого лежит использование квадратичных остатков по модулю n, алгоритм Блюма-Микали, основанный на задаче дискретного логарифмирования. Рассмотрим один из них подробнее.

Алгоритм Блюма-Блюма-Шуба

Описание алгоритма:
Входные данные — длина последовательности l.
Выходные данные — последовательность псевдослучайных бит z1, z2, …, zl
Ход алгоритма:

  1. Сгенерировать два простых числа p и q, сравнимых с 3 по модулю 4. Их произведение n = pq является целым числом Блюма

  2. Найти случайное целое число X, взаимно простое с n

  3. X0 = X2 mod n

  4. for i = 1 to l:
                Xi = Xi-12 mod n
                zi  = Xi mod 2

  5. return Z =

Интересным достоинством этого генератора является то, что для получения i-го бита bi при известных p и q достаточно воспользоваться формулой

b_i=x_0^{(2^{i} mod(λ(n)))} mod 2

Где λ — функция Кармайкла: в данном случае λ (n) = λ (pq) = НОК (p — 1, q — 1)

Это дает данному ГПСЧ преимущества при работе с массивами данных с произвольной точкой доступа. Безопасность алгоритма основана на сложности разложения числа n на множители, которая делает этот генератор безопасным как для предсказания следующего бита последовательности, так и для определения предыдущего бита.

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

3.3.Специальные реализации

Существует целый ряд практически используемых ГПСЧ которые разрабатывались с учетом криптографической стойкости, например:

  • Алгоритм Ярроу (Yarrow) который пытается определить энтропию входных данных. Он используется в FreeBSD,  OpenBSD и Mac OS X

  • Алгоритм Fortuna, наследник алгоритма Ярроу

  • Специальный файл ОС UNIX /dev/random, в частности, /dev/urandom, реализованный в Linux

  • Функция CryptGenRandom,  предоставленная в CryptoAPI компании Microsoft

Рассмотрим подробнее один из них.

Алгоритм Ярроу

Разработчики алгоритма опирались на следующие ключевые принципы:

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

  2. Простота — любой программист без особых знаний в криптографии должен суметь его безопасно использовать

  3. Оптимизация — алгоритм должен использовать уже существующие блоки команд там, где это возможно

Структура алгоритма

image-loader.svg

Алгоритм состоит из 4-х главных частей:

  • Накопитель энтропии. Собирает выборки из источников энтропии и помещает их в два пула

  • Механизм усложнения. Периодически усложняет ключ генератора, используя энтропию из пулов

  • Механизм генерации. Генерирует выходные сигналы ГПСЧ из ключа

  • Механизм управления усложнением. Определяет время выполнения усложнения

Накопление энтропии — это процесс, при котором ГПСЧ получает новое неугадываемое внутреннее состояние. В данном алгоритме энтропия накапливается в двух пулах  быстром и медленном. В данном контексте под пулом понимается хранилище инициализированных и готовых к использованию битов. Быстрый пул обеспечивает частые усложнения ключа. Это гарантирует, что компрометация ключа имеет невысокую продолжительность. Медленный пул обеспечивает редкие, но существенные усложнения ключа. Это необходимо для того, чтобы гарантировать получение безопасного усложнения даже в тех случаях, когда оценки энтропии сильно завышены. Входные выборки попеременно посылаются в быстрый и медленный пулы

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

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

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

Механизм генерации дает на выходе последовательность псевдослучайных чисел. Она должна быть такой, чтобы злоумышленник, не знающий ключа генератора, не смог отличить её от случайной последовательности бит.

Механизм генерации должен обладать следующими свойствами:

  • стойкость к криптографическим атакам

  • производительность

  • способность генерировать очень длинную последовательность сигналов без усложнения

  • стойкость к атакам перебором с возвратом после компрометации ключа

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

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

Ярроу-160

Одной из реализаций алгоритма Ярроу является Ярроу-160.Основная идея — использование односторонней хэш-функции (SHA-1) и блочного шифра Triple DES в режиме счетчика.

4.Заключение

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

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

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

  2. J Kelsey, B Schneier, N Ferguson «Yarrow-160: Notes on the design and analysis of the yarrow cryptographic pseudorandom number generator», Sixth Annual Workshop on Selected Areas in Cryptography, Springer Verlag, August 1999. https://doi.org/10.1007/3–540–46513–8_2

  3. V Pareek, Ankur, Divyanjali  «An Overview of Cryptographically Secure Pseudorandom Number generators and BBS» International Journal of Computer Applications® (IJCA) (0975 — 8887), 2014

  4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си — М.: Триумф, 2002.

© Habrahabr.ru