From DiskCryptor wiki
Jump to: navigation, search

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

В этой статье я расскажу о принципах работы и особенностях устройства генератора случайных чисел (ГСЧ), используемого в DiskCryptor.

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

Возможно создание односторонне стойкого ГСЧ, который позволит лицу, знающему некий секрет, восстановить все генерировавшиеся им ключи и скомпрометировать зашифрованные данные. Хороший пример такого случая — стандарт Dual_EC_DRBG, содержащий бекдор от АНБ и применяющийся в Windows, начиная с Vista SP1.

Цели создания и выполняемые задачи

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

  1. Выдача чисел, статистически неотличимых от случайных.
  2. Невозможность алгоритмического предсказания генерируемых или генерировшихся ранее последовательностей даже при наличии большого количества полученных ранее случайных чисел.
  3. Свойство 2 должно сохраняться в максимально возможном объеме даже при знании атакующим внутреннего состояния генератора.
  4. Необходимо обеспечить максимально возможный запас стойкости, многократно перекрывающий возможности атакующего.
  5. Простая и понятная для непрофессионала архитектура и принципы работы.

К ГСЧ для генерации больших объёмов случайных чисел предъявляются другие требования:

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

ГСЧ для генерации ключей

ГСЧ для генерации ключей, используемый в DiskCryptor, относится к ГСЧ накопительного типа с множественными источниками энтропии. ГСЧ этого типа накапливают малые значения энтропии в течение длительного времени, после чего способен выдать истинно случайную последовательность размером до 640 байт, после чего пойдут псевдослучайные последовательности, вплоть до нового накопления энтропии.

За основу конструкции ГСЧ взята хэш-функция SHA-512 и блочный шифр AES-256. Выбор именно этой функции обусловлен её простотой, хорошей производительностью и высокой надёжностью, хотя в данном случае к хэшу предъявляются менее жёсткие требования, чем, например, при использовании его для ЭЦП. Используемая хэш-функция должна обладать следующими свойствами:

  1. Статистически случайный выход при малослучайных входных данных.
  2. Зависимость каждого выходного бита хэша от всех входных бит. При изменении одного бита на входе должно меняться не менее половины выходных бит.
  3. Односторонность. Восстановление входных данных по хэш-значению должно быть невозможно. Это свойство очень желательно, но часть свойств ГСЧ сохраняется даже при его отсутствии.

Упрощённая блок-схема ГСЧ выглядит так:

Упрощённая блок-схема ГСЧ DiskCryptor

Накопление случайных чисел

Входные малослучайные данные хэшируются вместе с меткой времени и счётчиком обновлений случайных данных. Добавление 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генерированных случайных блоков и размера оставшейся части запрошенных данных и шифрования полученного хэша AES-256 ключом, полученным из ключевого пула. 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, разделяются на два типа: быстрые источники, работающие в режиме ядра и медленные, работающие в пользовательском приложении. Первые находятся вместе с ГСЧ внутри драйвера, вторые находятся в 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

Итак, мы видим, что в среднем мы получаем 39–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.

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

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

Список использованной литературы

  1. Peter Gutmann, "Software Generation of Practically Strong Random Numbers", 1998
  2. Elaine Barker, John Kelsey "NIST Special Publication 800-90", National Institute of Standards and Technology, March 2007
  3. John Kelsey, Bruce Schneier, David Wagner, Chris Hall, "Cryptanalytic Attacks on Pseudorandom Number Generators", Springer-Verlag London, UK, 1998
Language: English  • русский