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

В компьютерной безопасности криптобиблиотеки широко используются от базовых уровней, таких как алгоритмы защиты паролем, до защищенных или зашифрованных каналов связи или методов шифрования данных. Понимание слабости алгоритмов важно для выбора правильной криптографической конфигурации при разработке программного обеспечения или создании сетевой системы. В асимметричной криптографии, также известной как криптография с открытым ключом, используются открытый и закрытый ключи для шифрования и расшифровки данных. Ключи — это просто большие числа, которые были соединены вместе, но не идентичны (асимметричны). Эти большие числа генерируются случайным образом вычислительной машиной или специальным устройством, некоторые из них являются простыми числами (пример: P & Q в RSA), другие случайные числа используются для генерации сеансового ключа, поэтому случайность является наиболее важной для обеспечения достоверности система.

В этой статье мы анализируем три популярные арифметики для генерации случайности: LCG, CTR-DRGB и HRNG.

«Глупый» RNG-подобный

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

var timestamp = new Date().getTime().toString();
console.log(timestamp.slice(9,13))

Представьте себе, есть лотерейный автомат, который использует этот метод случайности для генерации 4-значных счастливых номеров, игроки покупают 4-значный номер, затем нажимают красную кнопку на автомате, если автомат остановится на выбранном номере, игрок получит приз. . Теперь, как злоумышленник, мы пытаемся получить лотерейный номер на удачу в каждом временном интервале (частоте дискретизации). В частности, я куплю 40 билетов не для выигрыша, а просто для записи 40 значений, которые были сгенерированы вышеуказанной машиной случайностей, а затем попытаюсь увидеть закономерность этих чисел методом статистического анализа:

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

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

(Программа JavaScript prng_ssp.js)

var rand=function(n) {
[...Array(n).keys()].forEach(i  => { 
    var moment_i = new  Date()
    var timestamp = moment_i.getTime().toString()
    console.log(timestamp.slice(9,13))
 })
}
rand(10)

Это приведет всего к 3 числам с приращением каждой миллисекунды: (x1) 6816, (x7) 6817, (x2) 6818. Сравнивая две ситуации: одна сгенерирована на основе человеческого фактора, другая сгенерирована вычислительной программой, которая является детерминированной, мы можем увидеть разные группы значений с определенной характеристикой.

Вывод:

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

Генератор псевдослучайных чисел (PRNG)

Теперь мы немного изучим наиболее распространенный PRNG, который является linear congruential generator, который использует повторение этого уравнения:

X(n+ 1) = [ aX(n) + b] мод м.

В то время как:

  • a, b и m — это большие целые числа, выбранные алгоритмом
  • X(n) — предыдущее случайное число, сгенерированное на последнем шаге.
  • X(n+1) — это ожидаемое случайное число, которое запрашивается для создания

Y = a*X + b — это усиливающее уравнение, которое дает результат, когда Y больше, чем X, плюс смещение, равное b. По модулю результат с m является действием сокращения выпуска.

Give T0 — это первая метка времени, в которой уравнение используется как seed number, и это секрет, a=8543785353454, b=795683477236463256 и m=1/Tn — вариантная база на основе текущего значения метки времени, которое может быть отправлено как master entropy source, оно может генерировать 10 случайных чисел подпоследовательности следующим образом. :

X0 = (8543785353454*T0 + 795683477236463256) % 1/T0
X1 = (8543785353454*X0 + 795683477236463256) % 1/T1
Xn = (8543785353454*Xn-1 + 795683477236463256) % 1/Tn

(Вывод программы Javascript prng_lcg.js)

VM621:20  3262865913765157
VM621:20  7324337203842918
VM621:20  4391091005089619
VM621:20  6249451093214968
VM621:20  3623421945882500
VM621:20  4531038569870347
VM621:20  1353719860753889
VM621:20  1456133755530897
VM621:20  6788199706312740
VM621:20  1933777729152979

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

Если мы игнорируем магию математической функции, просто сосредоточимся на главном факторе, который может повлиять на результат: это значение timestamp. Это означает, что если мы знаем начальное значение: начальную временную метку и уравнение, мы можем обратиться из программы PRNG, то мы можем пересчитать все возможности вариантов случайности в конкретный запланированный момент. Важная обязанность математики состоит в том, чтобы усложнить обращение начального значения из собранных выходных данных.

Это явление напоминает мне о серии фильмов 12 обезьян:

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

Вывод:

1- LCG — это просто математическая функция, которая увеличивает поток битов случайности и сложность вероятности коллизии из master entropy source. Люди говорят, что его можно сломать с помощью взлома ГСЧ.

2 — Если previous random number и master entropy source предсказуемы, PRNG можно сломать.

PRNG с использованием детерминированного генератора случайных байтов в режиме счетчика (CTR-DRBG)

(Подробный алгоритм CTR-DRBG и анализ безопасности см. в Анализ стандарта NIST SP 800–90A стр. 6,7)

В этой области мы изучаем использование CTR-DRBG в конкретном микропроцессоре, это серия ESP32 от Espressif Systems, которая используется для генерации ключа RSA, ключа AES mbedtls библиотеки, которая является основным компонентом безопасности ESP32.

Упрощенный алгоритм CTR_DRBG для mbedtssl:

(mbedtls_ctr_drbg_random_with_add)

Основной цикл проходит вокруг функции mbedtls_aes_crypt_ecb. Это похоже на математическую функцию Xn+1 = (a*Xn + b) mod m, которая усиливает входные биты и делает поток выходных битов очень трудным для предсказания. Применение ECB с матрицей s-box может увеличить скорость вычислений, сохраняя при этом их безопасность.

Мы заметили условие require_to_reseed и функцию_34, которые являются ключевым фактором, влияющим на алгоритм CTR_DRBG. Когда требуется повторное заполнение и как функция заполнения обеспечивает рабочее состояние повторного заполнения?

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

new_working_state = CTR_DRBG_Reseed(working_state, entropy_input)

require_to_reseed основывается на двух условиях:

  • reseed_counter › 10000
  • предсказание_сопротивление установлено

В то время как reseed_counter увеличивается каждый раз, когда запрашивается ГСЧ для ускорения вычислений, prediction_resistance устанавливается вызывающим приложением, когда ему необходимо принудительно перевести его в новое состояние повторного заполнения.

Каков размер ключа, используемого в AES? В mbedtls используется 256 бит:

  • MBEDTLS_CTR_DRBG_KEYSIZE = 32
  • MBEDTLS_CTR_DRBG_KEYBITS = MBEDTLS_CTR_DRBG_KEYSIZE * 8

Еще раз, мы можем видеть, что алгоритм CTR_DRBG описан в виде следующей диаграммы:

Зная, что система ESP32 использует радиочастотный шум, захваченный интерфейсом WiFi/Bluetooth, для генерации источника энтропии, который, как они сказали, рассматривается как TRNG (генератор истинных случайных чисел). После некоторых дискуссий об использовании РЧ-шума в качестве TRNG эксперты говорят, что это «глупое» мышление, когда они рассматривают РЧ-шум в определенном месте как источник случайности. У кого-то достаточно мощности и ресурсов, чтобы излучать активный радиочастотный шум в окружающую среду, целевая система будет рассматривать его как доверенный шум, и он будет нарушен.

Вывод:

1 — CTR_DRBG — это просто еще одна функция шифрования, которая увеличивает случайность битового потока и сложность возможности коллизии, используя master entropy source и его предыдущее состояние. Всякий раз, когда AES-256 все еще не ломается, он не ломается.

2. Если previous working state и master entropy source предсказуемы, CTR_DRBG можно сломать.

Аппаратный генератор случайных чисел

В частности, аппаратное обеспечение open cores использует systemc_rng модуль в качестве HRNG, он использует комбинацию двух методов PRNG на аппаратном уровне реализации (см. systemc_rng/trunk/verilog/rng.v:

  • Сдвиговый регистр с линейной обратной связью: 43 бита
  • Сдвиговый регистр клеточного автомата: 37 бит

Процедура генерации HRNG состоит из двух шагов: load seed и generate:

load_seed[31:0] = seed_i[31:0];
number_o[31:0] = (LFSR_reg [31:0]^CASR_reg[31:0]);

В то время как:

  • Модуль LFSR_reg использует метод Галуа LFSR с битами обратной связи: 40, 19, 0.
  • Модуль CASR_reg использует локальную функцию перехода с правильным битом: 28.

Блок алгоритма HRNG описывается следующей схемой:

LFSR используется как линейная функция для преобразования исходного входного источника в 32-битное арифметическое число, хранящееся в регистре компьютера, тогда как CASR преобразует исходный ввод нелинейным способом. В сочетании с естественным источником энтропии (известным как источник осциллятора) HRGN станет настоящей случайностью.

Вывод:

1 — HRNG использует естественный источник энтропии в качестве случайного начального числа.
2 — Выбор natural entropy source является наиболее важным из HRNG.
3 — Компрометация естественного источника энтропии поставит под угрозу случайность.



Отправлять письма онлайн с помощью коммутатора
Хотите отправлять физическую почту без каких-либо проблем? Сделайте Switch бесплатно сегодня и получите 10 долларов на свой счет…a.switchmail.com



Резюме

Скорость HRNG сильно зависит от собранного источника, обычно замедляется из-за одного аппаратного ресурса и не может быть многопоточной операцией. PRNG работает быстро благодаря вычислительному программному обеспечению с использованием нескольких потоков, нескольких процессов, которые могут доставляться многим приложениям одновременно. PRNG можно сломать, если его master entropy source генерация использует только программное обеспечение. TRNG эффективен, быстр и безопасен, когда он состоит из HRND и PRNG с тщательным natural entropy source дизайном.

Концепция системы TRNG для использования криптографии:

Используя внутреннюю систему на источнике энтропии чипа, можно безопасно не подвергаться влиянию какой-либо внешней мощности, которая может подать в систему поддельный случайный источник. Не рекомендуется самостоятельно создавать систему TRNG и использовать без требований безопасности и методов оценки, таких как RFC-4086, AIS-20/31 или TRNG-IP-76 (EIP-76). Он также должен соответствовать стандарту безопасности криптографических модулей FIPS 140-2, прежде чем применять его к вашей критической системе.

Библиография