Генератор случайных чисел

Для генерирования мастер-ключа шифрования, вторичного ключа (режим XTS), соли и ключевых файлов в VeraCrypt используется генератор случайных чисел (RNG). Он создаёт в ОЗУ (оперативной памяти компьютера) пул из случайных значений. Этот пул размером 320 байт заполняется данными, получаемыми из следующих источников:

• перемещения мыши
• нажатия клавиш
• Mac OS X и Linux: значения, генерируемые встроенным RNG (оба – /dev/random и /dev/urandom)
• только Microsoft Windows: Windows CryptoAPI (регулярно собираются с интервалом 500 мс)
• только Microsoft Windows: статистика сетевого интерфейса (NETAPI32)
• только Microsoft Windows: различные дескрипторы Win32, переменные времени и счётчики (регулярно собираются с интервалом 500 мс)

Прежде чем значение, полученное из любого вышеуказанного источника, будет записано в пул, оно разделяется на отдельные байты (например, 32-битовое число делится на четыре байта). Затем эти байты индивидуально записываются в пул операцией сложения по модулю 2⁸ (не заменяя старые значения в пуле) в позиции указателя пула. После записи байта позиция указателя пула перемещается на один байт вперёд. Когда указатель достигает конца пула, его позиция устанавливается в начало пула. После записи в пул каждого шестнадцатого байта, ко всему пулу автоматически применяется функция перемешивания (см. ниже).

Функция перемешивания пула

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

Описание функции перемешивания пула:

1. Пусть R это пул случайных значений
2. Пусть H это выбранная пользователем функция хеширования (SHA-512, BLAKE2S-256 или Whirlpool)
3. l = байтовый размер вывода функции хеширования H (то есть если H – BLAKE2S-256, то l = 20; если H – SHA-512, то l = 64)
4. z = байтовый размер пула случайных значений R (320 байт)
5. q = z / l – 1 (например, если H – Whirlpool, то q = 4)
6. R это поделённые на l байт блоки B₀...B_q

   Для 0 ≤ i ≤ q (то есть для каждого блока B) выполняются следующие шаги:

   1. M = H (B₀ || B₁ || ... || B_q) [то есть пул случайных значений хешируется с помощью хеш-функции H, что даёт хеш M]
   2. B_i = B_i ^ M
7. R = B₀ || B₁ || ... || B_q

Например, если q = 1, то пул случайных значений будет перемешан следующим образом:

1. (B₀ || B₁) = R
2. B₀ = B₀ ^ H(B₀ || B₁)
3. B₁ = B₁ ^ H(B₀ || B₁)
4. R = B₀ || B₁

Создаваемые значения

Содержимое пула RNG никогда прямо не экспортируется (даже когда VeraCrypt даёт RNG инструкцию сгенерировать и экспортировать значение). Таким образом, даже если неприятель завладеет созданным RNG значением, это ему никак не поможет в определении или предсказании (с помощью полученного значения) любых других значений, созданных RNG в течение сеанса (определить содержимое пула, основываясь на сгенерированном RNG значении, невозможно).

Генератор случайных чисел обеспечивает это, выполняя следующие шаги всякий раз, когда VeraCrypt даёт указание сгенерировать и экспортировать значение:

1. Данные, полученные из перечисленных выше источников, добавляются в пул, как описано выше.
2. Запрошенное число байт копируется из пула в выходной буфер (копирование начинается с позиции указателя пула; по достижении конца пула копирование продолжается с начала пула; если запрошенное число байт больше размера пула, значение не генерируется и возвращается ошибка).
3. Состояние каждого бита в пуле инвертируется (то есть 0 становится 1, а 1 становится 0).
4. Данные, полученные из какого-либо перечисленного выше источника, добавляются в пул, как описано выше.
5. Содержимое пула трансформируется с помощью функции перемешивания пула.
   Примечание. Эта функция использует криптографически стойкую одностороннюю хеш-функцию, выбираемую пользователем (подробности см. выше в разделе Функция перемешивания пула).
6. Преобразованное содержимое пула подвергается операции XOR в выходной буфер следующим образом:
   1. Указатель записи в выходном буфере устанавливается в 0 (первый байт буфера).
   2. Байт в позиции курсора пула считывается из пула и подвергается операции XOR с байтом в выходном буфере в позиции курсора записи выходного буфера.
   3. Позиция указателя пула смещается вперёд на один байт. По достижении конца пула позиция указателя устанавливается в 0 (первый байт пула).
   4. Позиция указателя записи выходного буфера перемещается вперёд на один байт.
   5. Шаги b–d повторяются для каждого остающегося байта в выходном буфере (чья длина равна запрошенному числу байт).
   6. Содержимое выходного буфера, являющееся окончательным значением, сгенерированным RNG, экспортируется.

Первоисточники

Дизайн и реализация генератора случайных чисел основаны на следующих работах:

• Software Generation of Practically Strong Random Numbers, автор Peter Gutmann [10]
• Cryptographic Random Numbers, автор Carl Ellison [11]

 

Следующий раздел >>