Views
Генератор случайных чисел накопительного типа
В этой статье я расскажу о принципах работы и особенностях устройства генератора случайных чисел (ГСЧ), используемого в DiskCryptor. ГСЧ - это критически важный элемент безопасности системы дискового шифрования, так как он генерирует ключи, которыми шифруются данные. Именно ГСЧ зачастую является слабым местом либо бекдором в различных проприетарных и сертифицированных органами системах шифрования, так как правильность реализации алгоритмов шифрования и методов хранения данных легко поддается проверке даже без наличия исходного кода, а ГСЧ гораздо труднее поддаётся проверке. Возможно создание односторонне стойкого ГСЧ, который позволит лицу, знающему некий секрет, восстановить все генерировавшиеся им ключи и скомпрометировать зашифрованные данные. Хороший пример такого случая - стандарт Dual_EC_DRBG, содержащий бекдор от NSA и применяющийся в Windows Vista.
Цели создания и выполняемые задачи
ГСЧ DiskCryptor предназначен для выполнения двух задач: генерации ключей шифрования и генерации больших объемов случайных данных для алгоритмов затирания диска. В первом случае необходимо обеспечить максимально возможный запас стойкости. К ГСЧ для генерации ключей шифрования предъявляются следующие требования:
- Выдача чисел, статистически неотличимых от случайных.
- Невозможность алгоритмического предсказания генерируемых или генерировшихся ранее последовательностей даже при наличии большого количества полученных ранее случайных чисел.
- Свойство 2 должно сохраняться в максимально возможном объеме даже при знании атакующим внутреннего состояния генератора.
- Необходимо обеспечить максимально возможный запас стойкости, многократно перекрывающий возможности атакующего.
- Простая и понятная для непрофессионала архитектура и принципы работы.
К ГСЧ для генерации больших объемов случайных чисел предъявляются другие требования:
- Выдача чисел, статистически неотличимых от случайных.
- Невозможность предсказания генерируемых последовательностей без знания внутреннего состояния генератора.
- Максимально высокая производительность.
ГСЧ для генерации ключей
ГСЧ для генерации ключей, используемый в DiskCryptor, относится к ГСЧ накопительного типа с множественными источниками энтропии. ГСЧ этого типа накапливают малые значения энтропии в течении длительного времени, после чего способен выдать истинно случайную последовательность размером до 640 байт, после чего пойдут псевдослучайные последовательности, вплоть до нового накопления энтропии.
За основу конструкции ГСЧ взята хэш-функция SHA-512 и блочный шифр AES-256. Выбор именно этой функции обусловлен ее простотой, хорошей производительностью и высокой надёжностью, хотя данном случае к хэшу предъявляются менее жёсткие требования, чем, например, при использовании его для ЭЦП. Используемая хэш-функция должна обладать следующими свойствами:
- Статистически случайный выход при малослучайных входных данных.
- Зависимость каждого выходного бита хэша от всех входных бит. При изменении одного бита на входе должно меняться не менее половины выходных бит.
- Односторонность. Восстановление входных данных по хэш-значению должно быть невозможно. Это свойство очень желательно, но часть свойств ГСЧ сохраняется даже при его отсутствии.
Упрощённая блок-схема ГСЧ выглядит так:
Накопление случайных чисел
Входные малослучайные данные (seed) хэшируются вместе с меткой времени (timestamp) и счётчиком обновлений случайных данных (reseed counter). Добавление timestamp и reseed counter предотвращает появление одинаковых значений хэша при одинаковом seed. Полученный хэш добавляется в пул случайных чисел путем сложения по модулю 28 с уже имеющимся содержимым пула, что создаёт зависимость содержимого пула от всех производившихся ранее добавлений случайных данных. Пул имеет длину 640 байт, что позволяет накапливать максимум 5120 бит энтропии. За одно добавление seed величина энтропии увеличивается максимум на 512 бит, размер хэша SHA-512, таким образом для полного заполнения пула требуется не менее 10 reseed. Помимо большого пула для накопления данных, в ГСЧ имеется второй, ключевой пул. Он имеет размер 256 бит и никогда не выводиться на выход даже косвенно, а используется как ключ для AES-256, которым шифруются выходные данные.
Перемешивание пула
Перемешивание пула - это операция, производимая с целью создать зависимость всех битов пула друг от друга. Цель перемешивания - создать зависимость каждого генерируемого бита от всего содержимого пула, но при этом не уменьшать максимальную энтропию, как бы произошло при хешировании всего пула в момент извлечения случайных чисел. Перемешивание обладает свойством односторонности, т.е. зная состояние пула после перемешивания, невозможно восстановить его предыдущее состояние. Это свойство напрямую опирается на соответствующее свойства SHA-512 хэша.
Перемешивание осуществляется с помощью mix function (функция rnd_pool_mix в исходном коде). В процессе перемешивания пул делиться на 10 частей по 64 байта в каждой, и к каждой части прибавляется значение SHA-512 хэша всего содержимого пула. Этот процесс можно представить как:
pool0 = pool0 + SHA(pool0 || pool1 ... pooln)
pool1 = pool1 + SHA(pool0 + SHA(pool0 || pool1 ... pooln) || pool1 ... pooln)
...
Перемешивание производится в трёх случаях: перед генерацией случайной последовательности байт, после генерации, и в случае если все содержимое пула было исчерпано в процессе генерации и извлечение данных пошло на второй круг. Первое перемешивание необходимо для создания зависимости выходных данных от всего содержимого пула, второе перемешивание защищает сгенерированные ключи от атакующего, имеющего возможность прочитать содержимое памяти после генерации (например с помощью cold boot атак), третье перемешивание позволяет использовать новую энтропию, добавляемую в пул в процессе генерации случайных чисел, а также создаёт дополнительную развязку между уже сгенерированными и следующими случайными числами.
Извлечение случайных чисел
Функция извлечения случайных чисел получает выходные данные генератора из его внутреннего состояния. Извлечение случайных чисел происходит путем взятия SHA-512 хэша от части пула, счетчика cгенерированных случайных блоков (getrand counter) и размера оставшейся части запрошенных данных (remaining length) и шифрования полученного хэша AES-256 ключом, полученным из ключевого пула (key pool). getrand counter и remaining length нужны для исключения возможности генерации двух одинаковых выходных блоков при одинаковом содержимом пула. Ситуация с одинаковым содержимым пула маловероятна по причине его перемешивания, но я считаю что дополнительная перестраховка не помешает. Процесс генерации можно представить так:
rand0 = SHA(pool0 || counter || length)
rand1 = SHA(pool1 || counter + 1 || length - 64)
...
randn = SHA(pooln || counter + n || length - 64*n)
В процессе извлечения каждых 512 бит данных дважды происходит сбор дополнительной энтропии, после достижения максимально возможного n (при размере пула в 640 байт он равен 10) происходит перемешивание пула, и следующие выдаваемые данные будут не истинно случайными, а частично псевдослучайными. Стойкость к компрометации этой конструкции при малых значениях эффективной энтропии (т.е. псевдослучайных чисел) опирается на общую стойкость SHA-512 и AES-256, что дает запас прочности даже в случае полного взлома одного из этих криптопримитивов. Исходный код извлечения чисел из пула вы можете посмотреть в функции rnd_get_bytes.
Источники энтропии
Источники энтропии - это элемент ГСЧ, важность которого трудно переоценить. Именно от них зависит эффективная энтропия, накапливаемая ГСЧ, и, следовательно, эффективная энтропия генерируемых ключей. Как бы ни был хорош алгоритм извлечения энтропии, плохой её источник способен поставить под угрозу безопасность ГСЧ. И наоборот - хороший источник случайности может в некоторых случаях вытянуть безопасность даже слабого алгоритма извлечения. К источникам энтропии следует подходить с гораздо большей паранойей, чем к алгоритму ГСЧ, т.к. стойкость этих источников практически недоказуема и может различаться на много порядков при различных предположениях о возможностях атакующего. Поэтому нужно следовать правилу "кашу маслом не испортишь", и использовать как можно больше разнообразных источников случайности. Добавление ещё одного источника понизить стойкость не может, но может в некоторых случаях её повысить, поэтому нужна избыточность, избыточность, и ещё раз избыточность.
Избыточность - это хорошо, но не стоит полагаться только на эмпирическую оценку её величины, ибо может оказаться, что атакующему доступно считывание большинства использованных источников энтропии, а оставшиеся недоступными он может подобрать или предсказать. Поэтому нужно иметь хотя-бы простейшее численное обоснование величины эффективной энтропии по отношению к атакующим, обладающим разными возможностями. Для начала определимся какими возможностями может обладать гипотетический атакующий. Самый простой вариант - атакующий не имеет никакого доступа к компьютеру в момент генерации случайных чисел, он не знает точного момента генерации и не имеет информации о состоянии системы на этот момент. Эта модель соответствует наиболее вероятному противнику, и в ней достигается максимально возможная безопасность всех источников энтропии. Один из вариантов расчета стойкости в дальнейшем будет даваться применительно к этой модели. Более сложный вариант - атакующий имеет частичный доступ к компьютеру и приблизительно (в пределах миллисекунд) знает время генерации случайных чисел, также он имеет доступ к части системной информации на этот момент. Практически такая модель соответствует возможностям атакующего в многопользовательской среде, когда он не имеет в ней административных привилегий. Расчёт стойкости для этой модели также будет приведён в дальнейшем, и именно этими числами следует руководствоваться при оценке стойкости "по минимуму". И, наконец, третий вариант - атакующий имеет полный доступ к атакуемой системе. Очевидно что в этом случае защититься невозможно, т.к. атакующий может контролировать и подменять любые источники энтропии, а также воздействовать непосредственно на внутреннее состояние ГСЧ, и даже подменять ГСЧ целиком на подконтрольный. Этот вариант соответствует атакующему, имеющему административные привилегии на атакуемой системе, от него нет и не может быть защиты. Поэтому ни в коем случае не генерируйте ключи и не работайте с конфиденциальными данными на системе подконтрольной кому-либо кроме вас, в противном случае ваша безопасность буквально висит на волоске.
Источники энтропии, используемые в ГСЧ DiskCryptor, разделяются на два типа: быстрые источники, работающие в режиме ядра (kernel mode) и медленные, работающие в пользовательском приложении (user mode). Первые находятся вместе с ГСЧ внутри драйвера, вторые находятся в dcapi.dll, и данные из них передаются драйверу периодически. Рассмотрим для начала набор функций ядра, используемых в качестве kernel-mode источников случайности. Основным их свойством является недоступность их прямого считывания атакующим, имеющим ограниченный доступ к системе, но часть их бит может быть предсказуемой, поэтому в нижеприведённой таблице для каждого источника указаны две оценки: минимальная и максимальная. Оценки справедливы при условии использования этих источников не чаще 10 раз в секунду, при более частом использовании эффективная энтропия каждого вызова уменьшается.
| Функция | Зависимость | Минимальная энтропия | Максимальная энтропия |
|---|---|---|---|
| PsGetCurrentProcess | От процесса вызывающего reseed | 0 | 2 |
| PsGetCurrentProcessId | От процесса вызывающего reseed | 0 | 2 |
| KeGetCurrentThread | От потока вызывающего reseed | 1 | 4 |
| PsGetCurrentThreadId | От потока вызывающего reseed | 0 | 2 |
| KeGetCurrentProcessorNumber | От номера текущего процессора | 0 | 2 |
| KeQueryInterruptTime | От всех прерываний в системе | 8 | 16 |
| KeQueryPriorityThread | От приоритета потока | 0 | 1 |
| KeQueryPerformanceCounter | RTC (real time clock) | 4 | 8 |
| __rdtsc | CPU timestamp counter | 16 | 24 |
| ExGetPreviousMode | Предыдущий режим исполнения потока | 0 | 1 |
| IoGetInitialStack | Начальный стек потока | 0 | 1 |
| IoGetTopLevelIrp | Последний IRP в очереди | 0 | 2 |
| MmQuerySystemSize | Размер системной памяти | 0 | ? |
| ExUuidCreate | PRNG ядра windows | 8 (?) | ? |
| RtlRandom | Предсказуемое значение, но может изменяться другими драйверами | 0 | ? |
| KeQueryTickCount | Число тактов таймера от загрузки системы | 2 | 4 |
| IoGetStackLimits | Границы стека для текущего потока | 0 | ? |
| Итого: | 39 | 75 |
Итак, мы видим, что в среднем мы получаем 35-75 случайных бит за одну reseed операцию. Этого мало если reseed производится однократно, поэтому DiskCryptor извлекает энтропию из быстрых функций в момент первой тысячи операций дискового I/O после старта системы. Даже если предположить что время выполнения I/O практически постоянно, то мы в минимуме будем иметь не менее 1 бита энтропии на reseed (потому что предсказание времени чтения данных с диска с точностью до наносекунды выглядит мягко говоря фантастикой), что в общей сумме составит не менее 1000 бит эффективной энтропии сразу после загрузки системы. В дальнейшем быстрый источник энтропии используется реже, а именно в момент некоторых не очень частых системных событий, и в момент генерации случайных чисел.
Помимо быстрых kernel-mode источников энтропии ГСЧ использует медленные user-mode источники. В качестве таких источником применяется ряд API функций, а также действия пользователя (движения мыши, нажатия клавиш). При старте программы в качестве источника энтропии однократно используется функция CryptoAPI CryptGenRandom, ГСЧ windows. Недавние исследования показали, что этот ГСЧ нестоек и в течении длительного времени выдает псевдослучайные числа, т.к. очень редко пополняет энтропию, поэтому его использование более одного раза не оправдано. Оценить его эффективную энтропию я затрудняюсь, но она явно должна быть не менее 32 бита, иначе ГСЧ бы обладал очень малым периодом, что выявляется с помощью простейших тестов. Движения мыши используются в качестве источника энтропии всё время работы программы. Это очень хороший источник случайности даже сам по себе, т.к. время между двумя сообщениями мыши велико по сравнению с частотой процессора, и из одного только этого времени можно уверено снимать 16 случайных бит за раз. Еще 2-3 случайных бита можно извлечь из координат курсора мыши и нажатий кнопок на ней. Нажатия клавиш в окне программы также используются ГСЧ, ему отправляется как время нажатия и отпускания, так и код клавиши. Это гарантирует, что даже в отсутствии других источников случайности эффективная энтропия генерируемых ключей не может быть меньше энтропии вашего пароля, т.к. он тоже используется в их генерации. Также важно то, что эти источники энтропии недоступны для считывания локальным атакующим с ограниченными правами, ведь если права атакующего достаточны для перехвата нажатий клавиатуры, то шифрование теряет всякий смысл.
Кроме однократных и постоянных источников описанных выше, в программе применяются периодические источники энтропии, информация из них собирается каждые 5 секунд в течении всего времени работы программы. Список используемых функций и приблизительная оценка количества получаемых от них случайных бит приведены в таблице ниже.
| Функция | Минимальная энтропия | Максимальная энтропия | Недоступно локальному атакующему |
|---|---|---|---|
| GetDesktopWindow | 0 | 1 | 0 |
| GetForegroundWindow | 2 | 4 | 2 |
| GetShellWindow | 0 | 1 | 0 |
| GetCapture | 0 | ? | ? |
| GetClipboardOwner | 0 | ? | ? |
| GetOpenClipboardWindow | 0 | ? | ? |
| GetCurrentProcessId | 0 | 1 | 0 |
| GetCurrentThreadId | 0 | 1 | 0 |
| GetFocus | 0 | 1 | ? |
| GetActiveWindow | 0 | ? | ? |
| GetKBCodePage | 0 | ? | ? |
| GetCursor | 0 | 2 | ? |
| GetLastActivePopup | 0 | ? | ? |
| GetProcessHeap | 0 | 2 | 0 |
| GetQueueStatus | 0 | 2 | 0 |
| GetInputState | 0 | ? | ? |
| GetMessageTime | 0 | ? | ? |
| GetOEMCP | 0 | ? | ? |
| GetCursorInfo | 8 | 16 | 8 |
| GetCaretPos | 0 | ? | ? |
| GetThreadTimes | 4 | 8 | 0 |
| GetProcessTimes | 4 | 8 | 0 |
| GetProcessMemoryInfo | 4 | 8 | 0 |
| QueryPerformanceCounter | 8 | 16 | 8 |
| GlobalMemoryStatusEx | 4 | 8 | 0 |
| EnumWindows | 128 | 256 | 128 |
| Итого: | 162 | 335 | 146 |
Итого мы имеем 146 бита гарантировано недоступных даже локальному атакующему. Не очень много, но уже лежит за пределами возможностей атак с помощью современной техники.
Быстрый ГПСЧ для генерации больших объемов случайных чисел
Вышеописанный ГСЧ предназначен для генерации малого количества случайных чисел с большим запасом стойкости. Но эта схема обладает очень низкой производительностью, поэтому она неприменима для генерации гигабайтных объемов случайных чисел, которые нужны для алгоритмов безопасной очистки секторов диска при шифровании. Для этой задачи DiskCryptor содержит генератор псевдослучайных чисел, он построен максимально просто, но тем не менее его стойкость полностью обусловлена стойкостью AES.
Источником энтропии в этой схеме является основной ГСЧ, с помощью которого генерируется случайный AES ключ при начальной инициализации генератора. Выработка псевдослучайных чисел производиться путем шифрования на этом ключе последовательно инкрементируемого 128 битного счетчика. Статистические характеристики выходных данных полностью обеспечиваются алгоритмом AES. По завершению работы генератора происходит уничтожение ключа, после чего становиться невозможно отличить полученые данные от случайных. Эта схема обладает простотой и достаточной для своего применения надежностью.
Список использованной литературы
| Software Generation of Practically Strong Random Numbers |
| NIST Special Publication 800-90 |
| Cryptanalytic Attacks on Pseudorandom Number Generators |