From DiskCryptor wiki
Jump to: navigation, search
(style, orfo, acronym)
 
Line 1: Line 1:
== Генератор случайных чисел накопительного типа ==
+
== Random number generator of an accumulative type ==
В этой статье я расскажу о принципах работы и особенностях устройства генератора случайных чисел (ГСЧ), используемого в DiskCryptor.
+
  
ГСЧ это критически важный элемент безопасности системы дискового шифрования, так как он генерирует ключи, которыми шифруются данные. Именно ГСЧ зачастую является слабым местом либо бекдором в различных проприетарных и сертифицированных органами системах шифрования, так как правильность реализации алгоритмов шифрования и методов хранения данных легко поддаётся проверке даже без наличия исходного кода, а ГСЧ гораздо труднее поддаётся проверке.
+
In this article I am going to tell about the operating principles and characteristic properties of random number generator (RNG) used in the DiskCryptor. RNG this is a critically important security element of a disk encryption system, as it generates the keys with which data is encrypted. And it is exactly the RNG that is often a weak spot or a backdoor in a different sorts of proprietary and government certified encryption systems, because precision of an encryption algorithm's implementation and the data storage methods can be easily examined even without having an access to the source code, but RNG, however, is much more difficult to analyze. It is possible to create a one-way strong RNG that will allow for a person, knowing a certain secret, to recover all the keys that were generated by it and to consequently compromise encrypted data. A good example of such case — the [http://en.wikipedia.org/wiki/Dual_EC_DRBG Dual_EC_DRBG] standard, which has NSA backdoor and is used in Windows Vista.
  
Возможно создание односторонне стойкого ГСЧ, который позволит лицу, знающему некий секрет, восстановить все генерировавшиеся им ключи и скомпрометировать зашифрованные данные. Хороший пример такого случая — стандарт [http://en.wikipedia.org/wiki/Dual_EC_DRBG Dual_EC_DRBG], содержащий бекдор от NSA и применяющийся в Windows Vista.
+
== The creation purposes and the objectives performed ==
  
== Цели создания и выполняемые задачи ==
+
The DiskCryptor's RNG purpose is to perform the following two objectives: generation of encryption keys and generation of a large volume of random data for disk wiping algorithms. For the first objective it is necessary to provide as big strength reserve as possible, and below are the key generation requirements that RNG has to meet:
ГСЧ DiskCryptor предназначен для выполнения двух задач: ''генерации ключей шифрования'' и ''генерации больших объёмов случайных данных'' для алгоритмов затирания диска. В первом случае необходимо обеспечить максимально возможный запас стойкости. К ГСЧ для генерации ключей шифрования предъявляются следующие требования:  
+
  
# Выдача чисел, статистически неотличимых от случайных.  
+
# Issue of numbers, statistically indistinguishable from random ones.
# Невозможность алгоритмического предсказания генерируемых или генерировшихся ранее последовательностей даже при наличии большого количества полученных ранее случайных чисел.  
+
# Impossibility of an algorithmic prediction of the sequences being generated or the ones generated earlier even with the availability of a large amount of random numbers made in the past.
# Свойство 2 должно сохраняться в максимально возможном объеме даже при знании атакующим внутреннего состояния генератора.  
+
# The requirement No.2 has to retain its maximum possible integrity state even when an attacker knows an internal state of the generator.
# Необходимо обеспечить максимально возможный запас стойкости, многократно перекрывающий возможности атакующего.  
+
# It is imperative to provide a maximum possible strength reserve that exceeds attacker's capabilities by manifold.
# Простая и понятная для непрофессионала архитектура и принципы работы.  
+
# Simple and clear, even for a non-professional, architecture and operating principles.
  
К ГСЧ для генерации больших объёмов случайных чисел предъявляются другие требования:  
+
For the second objective, when generating a large volume of random numbers, requirements for RNG differ:
  
# Выдача чисел, статистически неотличимых от случайных.  
+
# Issue of numbers, statistically indistinguishable from random ones.
# Невозможность предсказания генерируемых последовательностей без знания внутреннего состояния генератора.  
+
# Impossibility to predict sequences being generated without knowing an internal state of the generator.
# Максимально высокая производительность.
+
# Maximum possible performance.
  
== ГСЧ для генерации ключей ==
+
== RNG for key generation ==
ГСЧ для генерации ключей, используемый в DiskCryptor, относится к ГСЧ накопительного типа с множественными источниками энтропии. ГСЧ этого типа накапливают малые значения энтропии в течение длительного времени, после чего способен выдать истинно случайную последовательность размером до 640 байт, после чего пойдут псевдослучайные последовательности, вплоть до нового накопления энтропии.
+
  
За основу конструкции ГСЧ взята хэш-функция [http://ru.wikipedia.org/wiki/SHA-2 SHA-512] и блочный шифр [http://ru.wikipedia.org/wiki/Advanced_Encryption_Standard AES-256]. Выбор именно этой функции обусловлен её простотой, хорошей производительностью и высокой надёжностью, хотя в данном случае к хэшу предъявляются менее жёсткие требования, чем, например, при использовании его для [http://ru.wikipedia.org/wiki/Электронная_цифровая_подпись ЭЦП]. Используемая хэш-функция должна обладать следующими свойствами:
+
RNG for key generation that is used in the DiskCryptor, belongs to the accumulative RNG type with multiple sources of entropy. RNG of this type accumulates minor entropy values over a long period of time, following that it is capable of issuing a truly random sequence having size of up to 640 bytes, afterwards, pseudo-random sequences will follow up until a new accumulation of entropy.
  
# Статистически случайный выход при малослучайных входных данных.
+
As a basis for the RNG architecture, SHA-512 hash function and AES-256 block cipher are taken. The choice of this function is made because of its simplicity, good performance and high reliability, though less stringent requirements are set for hash in this case than, for example, when using it for the digital signatures. The hash function used, has to have the following properties:
# Зависимость каждого выходного бита хэша от всех входных бит. При изменении одного бита на входе должно меняться не менее половины выходных бит.
+
# Односторонность. Восстановление входных данных по хэш-значению должно быть невозможно. Это свойство очень желательно, но часть свойств ГСЧ сохраняется даже при его отсутствии.  
+
  
Упрощённая блок-схема ГСЧ выглядит так:
+
# Statistically random output on casually-random input data.
 +
# Dependence of each output bit of hash on all the input bits. On a change of one bit on an entry, no less than a half of output bits has to alter.
 +
# One-sidedness. Recovery of an entry data based on its hash value has to be impossible. This characteristic is very desirable, but a part of RNG properties are retained even without its presence.
  
[[File:DiskCryptor_RNG_01.png|center|Упрощённая блок-схема ГСЧ DiskCryptor]]
+
Simplified block scheme of RNG looks the following way:
  
== Накопление случайных чисел ==
+
[[File:DiskCryptor_RNG_01.png|center|DiskCryptor's simplified block scheme of RNG]]
Входные {{acronym|малослучайные данные|seed}} хэшируются вместе с {{acronym|меткой времени|timestamp}} и {{acronym|счётчиком обновлений случайных данных|reseed counter}}. Добавление timestamp и reseed counter предотвращает появление одинаковых значений хэша при одинаковом seed. Полученный хэш добавляется в пул случайных чисел путем сложения по модулю 28 с уже имеющимся содержимым пула, что создаёт зависимость содержимого пула от всех производившихся ранее добавлений случайных данных.
+
  
Пул имеет длину 640 байт, что позволяет накапливать максимум 5120 бит энтропии. За одно добавление seed величина энтропии увеличивается максимум на 512 бит, размер хэша SHA-512, таким образом для полного заполнения пула требуется не менее 10 reseed. Помимо большого пула для накопления данных, в ГСЧ имеется второй, ключевой пул. Он имеет размер 256 бит и никогда не выводится на выход даже косвенно, а используется как ключ для AES-256, которым шифруются выходные данные.
+
== Accumulation of random numbers ==
  
== Перемешивание пула ==
+
This is being done by hashing a seed together with a timestamp and a reseed counter. Adding both timestamp and reseed counter prevents generation of identical hash values on a same seed. The obtained hash is added to the random number pool by means of addition with respect to base 28 with existing content of the pool, and that creates a dependence of content of the pool on all random number additions made earlier. The pool has the size of 640 bytes, which allows for the accumulation of the maximum of 5120 bits of entropy. On one addition of a seed, the size of entropy increases by the maximum of 512 bits, therefore the SHA-512 hash size requires no less then 10 reseeds, for fully filling up the pool. In addition to having the big pool for data accumulation, RNG also has the second one, the keys pool. This pool has the size of 256 bits and it is never being outputted, even indirectly, but is used as a key for the AES-256, with which output data is encrypted.
Перемешивание пула — это операция, производимая с целью создать зависимость всех битов пула друг от друга. Цель перемешивания — создать зависимость каждого генерируемого бита от всего содержимого пула, но при этом не уменьшать максимальную энтропию, как бы произошло при хешировании всего пула в момент извлечения случайных чисел. Перемешивание обладает свойством односторонности, т.е. зная состояние пула после перемешивания, невозможно восстановить его предыдущее состояние. Это свойство напрямую опирается на соответствующее свойства SHA-512 хэша.  
+
  
Перемешивание осуществляется с помощью mix function (функция rnd_pool_mix в исходном коде). В процессе перемешивания пул делится на 10 частей по 64 байта в каждой, и к каждой части прибавляется значение SHA-512 хэша всего содержимого пула. Этот процесс можно представить как:
+
== Mixing up the pool ==
 +
 
 +
Mixing up the pool — this is the operation that is performed with the objective to make all the bits in the pool to become dependent on each other. The goal of mixing — is to create the reliance of each bit being generated, on all the content of the pool, but at the same time not to decrease the maximum entropy, as would have happened on hashing the whole pool at the moment of issuing random numbers. The mixing operation has a characteristic of being one-sided, meaning that, knowing a state of the pool after a mixing, it is impossible to restore its previous state. This characteristic is directly based on the corresponding properties of the SHA-512 hash.
 +
 
 +
Mixing is being done with the help of mix function (the rnd_pool_mix function in the source code). During the mixing process, the pool is being divided into 10 parts, each having the size of 64 bytes, and to each part, a value of SHA-512 hash of all the pool content is being added. This process can be presented as follows:
 
  pool<sub>0</sub> = pool<sub>0</sub> + SHA(pool<sub>0</sub> || pool<sub>1</sub> ... pool<sub>n</sub>)
 
  pool<sub>0</sub> = pool<sub>0</sub> + SHA(pool<sub>0</sub> || pool<sub>1</sub> ... pool<sub>n</sub>)
 
  pool<sub>1</sub> = pool<sub>1</sub> + SHA(pool<sub>0</sub> + SHA(pool<sub>0</sub> || pool<sub>1</sub> ... pool<sub>n</sub>) || pool<sub>1</sub> ... pool<sub>n</sub>)
 
  pool<sub>1</sub> = pool<sub>1</sub> + SHA(pool<sub>0</sub> + SHA(pool<sub>0</sub> || pool<sub>1</sub> ... pool<sub>n</sub>) || pool<sub>1</sub> ... pool<sub>n</sub>)
 
  ...
 
  ...
  
Перемешивание производится в трёх случаях: ''перед генерацией случайной последовательности байт'', ''после генерации'' и в случае, ''если всё содержимое пула было исчерпано в процессе генерации'' и извлечение данных пошло на второй круг. Первое перемешивание необходимо для создания зависимости выходных данных от всего содержимого пула, второе перемешивание защищает сгенерированные ключи от атакующего, имеющёго возможность прочитать содержимое памяти после генерации (например с помощью [http://citp.princeton.edu.nyud.net/pub/coldboot.pdf Cold Boot] атаки), третье перемешивание позволяет использовать новую энтропию, добавляемую в пул в процессе генерации случайных чисел, а также создаёт дополнительную развязку между уже сгенерированными и следующими случайными числами.
+
Mixing is performed in either of the following three cases: before generation of a random byte sequence, after it, and in the case when entire content of the pool has been expended in the process of generation, and issuing of data has gone to a second round. The first mixing is required for the creation of dependency of output data on all the pool content. The second mixing protects the generated keys from an attacker who has an opportunity to read the contents of memory after generation (for example with the [http://citp.princeton.edu.nyud.net/pub/coldboot.pdf Cold Boot] attack). The third mixing allows for the use of new entropy that is being added to the pool in the process of random number generation, and it also creates an additional remoteness between the already generated and the subsequent random numbers.
 +
 
 +
== Random numbers retrieval ==
  
== Извлечение случайных чисел ==
+
The random numbers retrieval function receives generator's output data from its internal state. Retrieval of random numbers is done by taking the SHA-512 hash from a part of the pool, random generated blocks counter (getrand counter), and a size of a remaining part of a requested data (remaining length), and encryption of an obtained hash with AES-256 key, received from the keys pool. Getrand counter and remaining length are needed to eliminate the possibility of generation of two identical output blocks on a same content of the pool. A situation having the same content in the pool is an unlikely one, due to its mixing, nevertheless, I believe that an additional safety measure would only be of a benefit. The generation process can be presented as follows:
Функция извлечения случайных чисел получает выходные данные генератора из его внутреннего состояния. Извлечение случайных чисел происходит путем взятия SHA-512 хэша от части пула, {{acronym|счетчика cгенерированных случайных блоков|getrand counter}} и {{acronym|размера оставшейся части запрошенных данных|remaining length}} и шифрования полученного хэша AES-256 ключом, полученным из {{acronym|ключевого пула|key pool}}. Getrand counter и remaining length нужны для исключения возможности генерации двух одинаковых выходных блоков при одинаковом содержимом пула. Ситуация с одинаковым содержимым пула маловероятна по причине его перемешивания, но я считаю что дополнительная перестраховка не помешает. Процесс генерации можно представить так:
+
 
  rand<sub>0</sub> = SHA(pool<sub>0</sub> || counter || length)
 
  rand<sub>0</sub> = SHA(pool<sub>0</sub> || counter || length)
 
  rand<sub>1</sub> = SHA(pool<sub>1</sub> || counter + 1 || length - 64)
 
  rand<sub>1</sub> = SHA(pool<sub>1</sub> || counter + 1 || length - 64)
Line 56: Line 56:
 
  rand<sub>n</sub> = SHA(pool<sub>n</sub> || counter + n || length - 64*n)
 
  rand<sub>n</sub> = SHA(pool<sub>n</sub> || counter + n || length - 64*n)
  
В процессе извлечения каждых 512 бит данных дважды происходит сбор дополнительной энтропии, после достижения максимально возможного n (при размере пула в 640 байт он равен 10) происходит перемешивание пула, и следующие выдаваемые данные будут не истинно случайными, а частично псевдослучайными. Стойкость к компрометации этой конструкции при малых значениях эффективной энтропии (т.е. псевдослучайных чисел) опирается на общую стойкость SHA-512 и AES-256, что дает запас прочности даже в случае полного взлома одного из этих криптопримитивов. Исходный код извлечения чисел из пула вы можете посмотреть в функции rnd_get_bytes.
+
In the process of retrieval of every 512 bits of data, twice, a gathering of additional entropy takes place. After reaching the maximum possible n (having the 640 bytes pool size, it equals 10), pool mixing takes place, and the subsequently issued data will not be truly random, but partially pseudorandom. The strength of this construction to withstand a risk of being compromised, having minor values of an effective entropy (that is, pseudorandom numbers), is based on the total strength of SHA-512 and AES-256, that gives a strength reserve even in a case of fully breaking of one of these cryptoprimitives. The source code for number retrieval from the pool, you can find in the function rnd_get_bytes.
  
== Источники энтропии ==
+
== Sources of entropy ==
Источники энтропии — это элемент ГСЧ, важность которого трудно переоценить. Именно от них зависит эффективная энтропия, накапливаемая ГСЧ, и, следовательно, эффективная энтропия генерируемых ключей. Как бы ни был хорош алгоритм извлечения энтропии, плохой её источник способен поставить под угрозу безопасность ГСЧ. И наоборот — хороший источник случайности может в некоторых случаях вытянуть безопасность даже слабого алгоритма извлечения. К источникам энтропии следует подходить с гораздо большей паранойей, чем к алгоритму ГСЧ, т.к. стойкость этих источников практически недоказуема и может различаться на много порядков при различных предположениях о возможностях атакующего. Поэтому нужно следовать правилу "кашу маслом не испортишь" и использовать как можно больше разнообразных источников случайности. Добавление ещё одного источника понизить стойкость не может, но может в некоторых случаях её повысить, поэтому нужна избыточность, избыточность, и ещё раз избыточность.
+
  
Избыточность это хорошо, но не стоит полагаться только на эмпирическую оценку её величины, ибо может оказаться, что атакующему доступно считывание большинства использованных источников энтропии, а оставшиеся недоступными он может подобрать или предсказать. Поэтому нужно иметь хотя бы простейшее численное обоснование величины эффективной энтропии по отношению к атакующим, обладающим разными возможностями. Для начала определимся какими возможностями может обладать гипотетический атакующий.
+
Sources of entropy, — is the RNG element, the importance of which is hard to overvalue. It is precisely these sources that are responsible for an effective entropy, which is accumulated by RNG, and consequently, an effective entropy of generated keys. Howsoever good the entropy retrieval algorithm might be, but a poor source of entropy can place the RNG security in jeopardy. And vice versa, — a good source of randomness, in some cases, may "stretch" the security of a weak retrieval algorithm. Sources of entropy should be approached to with a much greater paranoia, than the RNG algorithm, as the strength of these sources is practically non-provable and can vary by many magnitudes on different assumptions about an attacker's resources and potential. So therefore, it is prudent to follow the rule of "You can't spoil a good thing. Plenty is no plague." And thus, it is best to use as many different sources of randomness, as possible. Adding another additional source, will not lower the strength, but only might to increase it, in certain cases. Consequently, what is needed here, is — redundancy, more redundancy, and even more redundancy.
  
* Самый простой вариант — ''атакующий не имеет никакого доступа к компьютеру в момент генерации случайных чисел,'' он не знает точного момента генерации и не имеет информации о состоянии системы на этот момент. Эта модель соответствует наиболее вероятному противнику, и в ней достигается максимально возможная безопасность всех источников энтропии. Один из вариантов расчёта стойкости в дальнейшем будет даваться применительно к этой модели.
+
Having redundancy, — is a very good thing, but one should not rely on an empirical value of its size, as it just may happen, that an attacker may be able to read the majority of entropy sources used, and the remaining inaccessible sources he may be capable to pick up or predict. Therefore, there is the need to have at least a simplest numerical basis for an effective size of entropy in relation to an attacker, who has various capabilities. For the start, we should define what kind of leverage a hypothetical attacker may have.
* Более сложный вариант — ''атакующий имеет частичный доступ к компьютеру и приблизительно (в пределах миллисекунд) знает время генерации случайных чисел,'' также он имеет доступ к части системной информации на этот момент. Практически такая модель соответствует возможностям атакующего в многопользовательской среде, когда он не имеет в ней административных привилегий. Расчёт стойкости для этой модели также будет приведён в дальнейшем, и именно этими числами следует руководствоваться при оценке стойкости "по минимуму".
+
* The simplest version, is when an ''attacker has absolutely no access to a computer in a moment of random number generation'', he also does not know the exact moment of generation, nor has an information about the state of a system on that moment either. This model corresponds to the most likely kind of an attacker, and this model has the maximum possible safety of all the sources of entropy. Later on, one of the versions of strength calculation will be given with regard to this model.
* И, наконец, третий вариант — ''атакующий имеет полный доступ к атакуемой системе''. Очевидно, что в этом случае защититься невозможно, т.к. атакующий может контролировать и подменять любые источники энтропии, а также воздействовать непосредственно на внутреннее состояние ГСЧ, и даже подменять ГСЧ целиком на подконтрольный. Этот вариант соответствует атакующему, имеющему административные привилегии на атакуемой системе, от него нет и не может быть защиты. Поэтому ни в коем случае не генерируйте ключи и не работайте с конфиденциальными данными на системе подконтрольной кому-либо кроме вас, в противном случае ваша безопасность буквально висит на волоске.  
+
* A more complicated version, is when an ''attacker has a partial access to a computer and knows an approximate (within the milliseconds range) time of random number generation'', and when he also has the access to a part of system information on that moment. Practically, this model corresponds to a potential that an attacker may have in a multi-user environment, when he has no administrative privileges in there. Later on, strength calculation for this model will also be presented, and exactly these kind of numbers should be taken as a basis for giving an assessment for having a minimum acceptable strength.
 +
* And finally the third version, — when an ''attacker has a full access to a system''. It is obvious, that it is impossible to be protected in such a case, as an attacker can take control of and to replace any sources of entropy, and also can have a direct influence upon internal state of the RNG, or to replace the RNG completely with his own one. This version corresponds to a kind of an attacker, which has administrative privileges on a system that he is attacking, and there is no, nor there can be a defense from him. Therefore, under no circumstances you must generate keys or work with a confidential data on a system that can be controlled by someone other than you. Otherwise, your security is literally hairbreadth to none.
  
Источники энтропии, используемые в ГСЧ DiskCryptor, разделяются на два типа: ''быстрые источники,'' работающие в {{acronym|режиме ядра|kernel mode}} и ''медленные,'' работающие в {{acronym|пользовательском приложении|user mode}}. Первые находятся вместе с ГСЧ внутри драйвера, вторые находятся в dcapi.dll, и данные из них периодически передаются драйверу. Рассмотрим для начала набор функций ядра, используемых в качестве kernel-mode источников случайности. Основным их свойством является недоступность их прямого считывания атакующим, имеющим ограниченный доступ к системе, но часть их бит может быть предсказуемой, поэтому в нижеприведённой таблице для каждого источника указаны две оценки: минимальная и максимальная. Оценки справедливы при условии использования этих источников не чаще 10 раз в секунду, при более частом использовании эффективная энтропия каждого вызова уменьшается.
+
The sources of entropy that are used in the DiskCryptor's RNG are separated into two types: fast sources, working in the kernel-mode, and slow sources, working in the user-mode. The first ones a residing together with the RNG inside the driver, and the second ones reside in the dcapi.dll, and the data from them is periodically transmitted to the driver. First, let us examine a set of functions of the kernel, used as a kernel-mode sources of randomness. Their main property is inaccessibility of their direct reading by an attacker that has a limited access to a system, but a portion of their bits may be predictable, and so in the table that is presented below there are two values for each source: minimum and maximum. The values are true on a condition that the use of these sources is no frequent than 10 times per second, on a more numerous use an effective entropy of each call decreases.
  
 
{| class="wikitable" border=1 width="100%"
 
{| class="wikitable" border=1 width="100%"
! Функция
+
! Function !! Dependency !! Minimum entropy !! Maximum entropy
! Зависимость
+
! Минимальная энтропия
+
! Максимальная энтропия
+
 
|-
 
|-
 
| PsGetCurrentProcess
 
| PsGetCurrentProcess
| От процесса вызывающего reseed
+
| On the process invoking reseed
 
| 0
 
| 0
 
| 2
 
| 2
 
|-
 
|-
 
| PsGetCurrentProcessId
 
| PsGetCurrentProcessId
| От процесса вызывающего reseed
+
| On the process invoking reseed
 
| 0
 
| 0
 
| 2
 
| 2
 
|-
 
|-
 
| KeGetCurrentThread
 
| KeGetCurrentThread
| От потока вызывающего reseed
+
| On the thread invoking reseed
 
| 1
 
| 1
 
| 4
 
| 4
 
|-
 
|-
 
| PsGetCurrentThreadId
 
| PsGetCurrentThreadId
| От потока вызывающего reseed
+
| On the thread invoking reseed
 
| 0
 
| 0
 
| 2
 
| 2
 
|-
 
|-
 
| KeGetCurrentProcessorNumber
 
| KeGetCurrentProcessorNumber
| От номера текущего процессора
+
| On the number of current processor
 
| 0
 
| 0
 
| 2
 
| 2
 
|-
 
|-
 
| KeQueryInterruptTime
 
| KeQueryInterruptTime
| От всех прерываний в системе
+
| On all interrupts in the system
 
| 8
 
| 8
 
| 16
 
| 16
|-  
+
|-
 
| KeQueryPriorityThread
 
| KeQueryPriorityThread
| От приоритета потока
+
| On the thread priority
 
| 0
 
| 0
 
| 1
 
| 1
 
|-
 
|-
 
| KeQueryPerformanceCounter
 
| KeQueryPerformanceCounter
| RTC (real time clock)
+
| RTC (Real Time Clock)
 
| 4
 
| 4
 
| 8
 
| 8
Line 121: Line 118:
 
|-
 
|-
 
| ExGetPreviousMode
 
| ExGetPreviousMode
| Предыдущий режим исполнения потока
+
| Previous mode of the thread execution
 
| 0
 
| 0
 
| 1
 
| 1
 
|-
 
|-
 
| IoGetInitialStack
 
| IoGetInitialStack
| Начальный стек потока
+
| Initial stack of the thread
 
| 0
 
| 0
 
| 1
 
| 1
 
|-
 
|-
 
| IoGetTopLevelIrp
 
| IoGetTopLevelIrp
| Последний IRP в очереди
+
| Last IRP (Input/output Request Packet) in the queue
 
| 0
 
| 0
 
| 2
 
| 2
 
|-
 
|-
 
| MmQuerySystemSize
 
| MmQuerySystemSize
| Размер системной памяти
+
| Size of the system memory
 
| 0
 
| 0
 
| ?
 
| ?
 
|-
 
|-
 
| ExUuidCreate
 
| ExUuidCreate
| PRNG ядра windows
+
| PRNG of the Windows kernel
 
| 8 (?)
 
| 8 (?)
 
| ?
 
| ?
 
|-
 
|-
 
| RtlRandom
 
| RtlRandom
| Предсказуемое значение, но может изменяться другими драйверами
+
| Predictable value, but may be altered by other drivers
 
| 0
 
| 0
 
| ?
 
| ?
 
|-
 
|-
 
| KeQueryTickCount
 
| KeQueryTickCount
| Число тактов таймера от загрузки системы
+
| Number of ticks of the counter from the moment of system's boot
 
| 2
 
| 2
 
| 4
 
| 4
 
|-
 
|-
 
| IoGetStackLimits
 
| IoGetStackLimits
| Границы стека для текущего потока
+
| Stack limits for the current thread
 
| 0
 
| 0
 
| ?
 
| ?
 
|-
 
|-
! Итого:
+
! Total:
|  
+
|
 
| 39
 
| 39
 
| 75
 
| 75
 
|}
 
|}
  
Итак, мы видим, что в среднем мы получаем 39–75 случайных бит за одну reseed операцию. Этого мало если reseed производится однократно, поэтому DiskCryptor извлекает энтропию из быстрых функций в момент первой тысячи операций дискового I/O после старта системы. Даже если предположить что время выполнения I/O практически постоянно, то мы в минимуме будем иметь не менее 1 бита энтропии на reseed (потому что предсказание времени чтения данных с диска с точностью до наносекунды выглядит мягко говоря фантастикой), что в общей сумме составит не менее 1000 бит эффективной энтропии сразу после загрузки системы. В дальнейшем быстрый источник энтропии используется реже, а именно в момент некоторых не очень частых системных событий, и в момент генерации случайных чисел.  
+
Thus, we can see that on an average we get 39–75 random bits on one reseed operation. This is not enough if reseed is carried out once, therefore DiskCryptor retrieves entropy from fast functions in the moment of a first thousand disk I/O operations after the system's start. Even if we are to assume that the time of I/O operations execution is practically constant, then on the minimum we would have no less than 1 bit of entropy per reseed (because predicting the time of reading data from a disk with the nanosecond precision looks like a fiction), that in total would amount to no less than 1000 bits of effective entropy right after the system's boot. Subsequently, the fast source of entropy is being used less, and namely in the moment of some not very frequent system events, and in the moment of random number generation.
  
Помимо быстрых kernel-mode источников энтропии ГСЧ использует медленные user-mode источники. В качестве таких источников применяется ряд API функций, а также действия пользователя (движения мыши, нажатия клавиш). При старте программы в качестве источника энтропии однократно используется функция CryptoAPI CryptGenRandom, ГСЧ windows. Недавние исследования показали, что этот ГСЧ нестоек и в течение длительного времени выдает псевдослучайные числа, т.к. очень редко пополняет энтропию, поэтому его использование более одного раза не оправдано. Оценить его эффективную энтропию я затрудняюсь, но она явно должна быть не менее 32 бита, иначе ГСЧ бы обладал очень малым периодом, что выявляется с помощью простейших тестов. Движения мыши используются в качестве источника энтропии всё время работы программы. Это очень хороший источник случайности даже сам по себе, т.к. время между двумя сообщениями мыши велико по сравнению с частотой процессора, и из одного только этого времени можно уверено снимать 16 случайных бит за раз. Ещё 2–3 случайных бита можно извлечь из координат курсора мыши и нажатий кнопок на ней. Нажатия клавиш в окне программы также используются ГСЧ, ему отправляется как время нажатия и отпускания, так и код клавиши. Это гарантирует, что даже в отсутствии других источников случайности эффективная энтропия генерируемых ключей не может быть меньше энтропии вашего пароля, т.к. он тоже используется в их генерации. Также важно то, что эти источники энтропии недоступны для считывания локальным атакующим с ограниченными правами, ведь если права атакующего достаточны для перехвата нажатий клавиатуры, то шифрование теряет всякий смысл.  
+
Besides using fast kernel-mode entropy sources, RNG also uses slow user-mode sources. Several API functions and also user actions (mouse movement, pressing of keys) are used as user-mode sources. At the start of the program, Windows's RNG CryptoAPI CryptGenRandom function is used once, as the source of entropy. Recent studies show that this RNG is weak and in a protracted period of time it issues pseudorandom numbers, as it rarely replenishes entropy, and thus using it more than once is not justified. It is difficult for me to name the value of its effective entropy, but apparently it has to be no less than 32 bits, otherwise RNG would have had a very short period, which can be discovered with a simplest of tests. Mouse movements are used as the source of entropy the whole time the program is working. This is a very good source of entropy even on its own accord, as the time between the two mouse communications is wide in comparison with CPU clocks, and even from this time alone it is possible to confidently gather 16 random bits at a time. Extra 2–3 random bits can be taken off from mouse cursor coordinates and presses of mouse keys. Keyboard keys presses in the program's window are also used by RNG, and both the time of press and release, as well as the key's code are sent to it. This guarantees, that even in the absence of other sources of randomness, the effective entropy of the keys being generated, cannot be less than the entropy of your password, as the password is also used in key generation. It is also important, that these sources of entropy are inaccessible for reading by a local attacker with limited privileges, since if attacker's privileges are high enough to intercept keyboard presses, then encryption loses all its meaning.
  
Кроме однократных и постоянных источников описанных выше, в программе применяются периодические источники энтропии, информация из них собирается каждые 5 секунд в течение всего времени работы программы. Список используемых функций и приблизительная оценка количества получаемых от них случайных бит приведены в таблице ниже.
+
In addition to one-time and persistent sources of entropy described above, the program also uses recurrent entropy sources, information from which is collected every 5 seconds as long as the program works. The list of functions used, and approximate value of amount of random bits receive from them, is presented in the table below.
  
{| class="wikitable" border=1 width="100%"
+
{| class="wikitable" border=1
! Функция
+
! Function !! Minimum entropy !! Maximum entropy !! Inaccessible to local attacker
! Минимальная энтропия
+
! Максимальная энтропия
+
! Недоступно локальному атакующему
+
 
|-
 
|-
 
| GetDesktopWindow
 
| GetDesktopWindow
Line 182: Line 176:
 
| 1
 
| 1
 
| 0
 
| 0
|-  
+
|-
 
| GetForegroundWindow
 
| GetForegroundWindow
 
| 2
 
| 2
Line 207: Line 201:
 
| ?
 
| ?
 
| ?
 
| ?
|-  
+
|-
 
| GetCurrentProcessId
 
| GetCurrentProcessId
 
| 0
 
| 0
Line 247: Line 241:
 
| 2
 
| 2
 
| 0
 
| 0
|-  
+
|-
 
| GetQueueStatus
 
| GetQueueStatus
 
| 0
 
| 0
Line 303: Line 297:
 
| 0
 
| 0
 
|-
 
|-
| EnumWindows  
+
| EnumWindows
 
| 128
 
| 128
 
| 256
 
| 256
 
| 128
 
| 128
 
|-
 
|-
! Итого:
+
! Total:
 
| 162
 
| 162
 
| 335
 
| 335
Line 314: Line 308:
 
|}
 
|}
  
Итого мы имеем 146 бит гарантировано недоступных даже локальному атакующему. Не очень много, но уже лежит за пределами возможностей атак с помощью современной техники.
+
In total we have 146 bits, that are guaranteed to be inaccessible even to a local attacker. That is not too much, but nevertheless, already lies beyond the capabilities of attackers having modern day technology.
 +
 
 +
== Fast PRNG for generation of large volume of random numbers ==
 +
 
 +
The aforementioned RNG is designed to generate small amount of random numbers with a large strength reserve. This scheme's efficiency, however, is quite low and therefore it is unsuited for generation of gigabytes of random numbers that are needed for the algorithms to securely wipe disk sectors on encryption. For this purpose DiskCryptor has the pseudorandom number generator that is built with the utmost simplicity, but nonetheless its durability is based on the strength of the AES.
  
== Быстрый ГПСЧ для генерации больших объёмов случайных чисел ==
+
[[File:DiskCryptor_RNG_02.png|center|DiskCryptor's pseudorandom number generator]]
Вышеописанный ГСЧ предназначен для генерации малого количества случайных чисел с большим запасом стойкости. Но эта схема обладает очень низкой производительностью, поэтому она неприменима для генерации гигабайтных объёмов случайных чисел, которые нужны для алгоритмов безопасной очистки секторов диска при шифровании. Для этой задачи DiskCryptor содержит генератор псевдослучайных чисел, он построен максимально просто, но тем не менее его стойкость полностью обусловлена стойкостью AES.
+
  
[[File:DiskCryptor_RNG_02.png|center|Генератор псевдослучайных чисел в DiskCryptor]]
+
Here in this scheme, the main RNG is used as the source of entropy, and with its help a random AES key is generated on the first initialization of the generator. Output of pseudorandom numbers is done by the process of encryption, using this key, of sequentially incrementing 128 bit counter. Statistical characteristics of output data are fully ensured by the AES algorithm. On the completion of generator's work, the key is destroyed, and it becomes impossible to distinguish an obtained data from a random data. This scheme has the property of being simple and sufficiently safe for its purpose.
  
Источником энтропии в этой схеме является основной ГСЧ, с помощью которого генерируется случайный AES ключ при начальной инициализации генератора. Выработка псевдослучайных чисел производится путем шифрования на этом ключе последовательно инкрементируемого 128 битного счетчика. Статистические характеристики выходных данных полностью обеспечиваются алгоритмом AES. По завершению работы генератора происходит уничтожение ключа, после чего становится невозможно отличить полученые данные от случайных. Эта схема обладает простотой и достаточной для своего применения надёжностью.
+
== List of publications used ==
  
== Список использованной литературы ==
 
 
# Peter Gutmann, "[http://www.cs.auckland.ac.nz/~pgut001/pubs/usenix98.pdf Software Generation of Practically Strong Random Numbers]", 1998
 
# Peter Gutmann, "[http://www.cs.auckland.ac.nz/~pgut001/pubs/usenix98.pdf Software Generation of Practically Strong Random Numbers]", 1998
 
# Elaine Barker, John Kelsey "[http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf NIST Special Publication 800-90]", National Institute of Standards and Technology, Март 2007
 
# Elaine Barker, John Kelsey "[http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf NIST Special Publication 800-90]", National Institute of Standards and Technology, Март 2007

Revision as of 07:10, 28 October 2013

Random number generator of an accumulative type

In this article I am going to tell about the operating principles and characteristic properties of random number generator (RNG) used in the DiskCryptor. RNG — this is a critically important security element of a disk encryption system, as it generates the keys with which data is encrypted. And it is exactly the RNG that is often a weak spot or a backdoor in a different sorts of proprietary and government certified encryption systems, because precision of an encryption algorithm's implementation and the data storage methods can be easily examined even without having an access to the source code, but RNG, however, is much more difficult to analyze. It is possible to create a one-way strong RNG that will allow for a person, knowing a certain secret, to recover all the keys that were generated by it and to consequently compromise encrypted data. A good example of such case — the Dual_EC_DRBG standard, which has NSA backdoor and is used in Windows Vista.

The creation purposes and the objectives performed

The DiskCryptor's RNG purpose is to perform the following two objectives: generation of encryption keys and generation of a large volume of random data for disk wiping algorithms. For the first objective it is necessary to provide as big strength reserve as possible, and below are the key generation requirements that RNG has to meet:

  1. Issue of numbers, statistically indistinguishable from random ones.
  2. Impossibility of an algorithmic prediction of the sequences being generated or the ones generated earlier even with the availability of a large amount of random numbers made in the past.
  3. The requirement No.2 has to retain its maximum possible integrity state even when an attacker knows an internal state of the generator.
  4. It is imperative to provide a maximum possible strength reserve that exceeds attacker's capabilities by manifold.
  5. Simple and clear, even for a non-professional, architecture and operating principles.

For the second objective, when generating a large volume of random numbers, requirements for RNG differ:

  1. Issue of numbers, statistically indistinguishable from random ones.
  2. Impossibility to predict sequences being generated without knowing an internal state of the generator.
  3. Maximum possible performance.

RNG for key generation

RNG for key generation that is used in the DiskCryptor, belongs to the accumulative RNG type with multiple sources of entropy. RNG of this type accumulates minor entropy values over a long period of time, following that it is capable of issuing a truly random sequence having size of up to 640 bytes, afterwards, pseudo-random sequences will follow up until a new accumulation of entropy.

As a basis for the RNG architecture, SHA-512 hash function and AES-256 block cipher are taken. The choice of this function is made because of its simplicity, good performance and high reliability, though less stringent requirements are set for hash in this case than, for example, when using it for the digital signatures. The hash function used, has to have the following properties:

  1. Statistically random output on casually-random input data.
  2. Dependence of each output bit of hash on all the input bits. On a change of one bit on an entry, no less than a half of output bits has to alter.
  3. One-sidedness. Recovery of an entry data based on its hash value has to be impossible. This characteristic is very desirable, but a part of RNG properties are retained even without its presence.

Simplified block scheme of RNG looks the following way:

DiskCryptor's simplified block scheme of RNG

Accumulation of random numbers

This is being done by hashing a seed together with a timestamp and a reseed counter. Adding both timestamp and reseed counter prevents generation of identical hash values on a same seed. The obtained hash is added to the random number pool by means of addition with respect to base 28 with existing content of the pool, and that creates a dependence of content of the pool on all random number additions made earlier. The pool has the size of 640 bytes, which allows for the accumulation of the maximum of 5120 bits of entropy. On one addition of a seed, the size of entropy increases by the maximum of 512 bits, therefore the SHA-512 hash size requires no less then 10 reseeds, for fully filling up the pool. In addition to having the big pool for data accumulation, RNG also has the second one, the keys pool. This pool has the size of 256 bits and it is never being outputted, even indirectly, but is used as a key for the AES-256, with which output data is encrypted.

Mixing up the pool

Mixing up the pool — this is the operation that is performed with the objective to make all the bits in the pool to become dependent on each other. The goal of mixing — is to create the reliance of each bit being generated, on all the content of the pool, but at the same time not to decrease the maximum entropy, as would have happened on hashing the whole pool at the moment of issuing random numbers. The mixing operation has a characteristic of being one-sided, meaning that, knowing a state of the pool after a mixing, it is impossible to restore its previous state. This characteristic is directly based on the corresponding properties of the SHA-512 hash.

Mixing is being done with the help of mix function (the rnd_pool_mix function in the source code). During the mixing process, the pool is being divided into 10 parts, each having the size of 64 bytes, and to each part, a value of SHA-512 hash of all the pool content is being added. This process can be presented as follows:

pool0 = pool0 + SHA(pool0 || pool1 ... pooln)
pool1 = pool1 + SHA(pool0 + SHA(pool0 || pool1 ... pooln) || pool1 ... pooln)
...

Mixing is performed in either of the following three cases: before generation of a random byte sequence, after it, and in the case when entire content of the pool has been expended in the process of generation, and issuing of data has gone to a second round. The first mixing is required for the creation of dependency of output data on all the pool content. The second mixing protects the generated keys from an attacker who has an opportunity to read the contents of memory after generation (for example with the Cold Boot attack). The third mixing allows for the use of new entropy that is being added to the pool in the process of random number generation, and it also creates an additional remoteness between the already generated and the subsequent random numbers.

Random numbers retrieval

The random numbers retrieval function receives generator's output data from its internal state. Retrieval of random numbers is done by taking the SHA-512 hash from a part of the pool, random generated blocks counter (getrand counter), and a size of a remaining part of a requested data (remaining length), and encryption of an obtained hash with AES-256 key, received from the keys pool. Getrand counter and remaining length are needed to eliminate the possibility of generation of two identical output blocks on a same content of the pool. A situation having the same content in the pool is an unlikely one, due to its mixing, nevertheless, I believe that an additional safety measure would only be of a benefit. The generation process can be presented as follows:

rand0 = SHA(pool0 || counter || length)
rand1 = SHA(pool1 || counter + 1 || length - 64)
...
randn = SHA(pooln || counter + n || length - 64*n)

In the process of retrieval of every 512 bits of data, twice, a gathering of additional entropy takes place. After reaching the maximum possible n (having the 640 bytes pool size, it equals 10), pool mixing takes place, and the subsequently issued data will not be truly random, but partially pseudorandom. The strength of this construction to withstand a risk of being compromised, having minor values of an effective entropy (that is, pseudorandom numbers), is based on the total strength of SHA-512 and AES-256, that gives a strength reserve even in a case of fully breaking of one of these cryptoprimitives. The source code for number retrieval from the pool, you can find in the function rnd_get_bytes.

Sources of entropy

Sources of entropy, — is the RNG element, the importance of which is hard to overvalue. It is precisely these sources that are responsible for an effective entropy, which is accumulated by RNG, and consequently, an effective entropy of generated keys. Howsoever good the entropy retrieval algorithm might be, but a poor source of entropy can place the RNG security in jeopardy. And vice versa, — a good source of randomness, in some cases, may "stretch" the security of a weak retrieval algorithm. Sources of entropy should be approached to with a much greater paranoia, than the RNG algorithm, as the strength of these sources is practically non-provable and can vary by many magnitudes on different assumptions about an attacker's resources and potential. So therefore, it is prudent to follow the rule of "You can't spoil a good thing. Plenty is no plague." And thus, it is best to use as many different sources of randomness, as possible. Adding another additional source, will not lower the strength, but only might to increase it, in certain cases. Consequently, what is needed here, is — redundancy, more redundancy, and even more redundancy.

Having redundancy, — is a very good thing, but one should not rely on an empirical value of its size, as it just may happen, that an attacker may be able to read the majority of entropy sources used, and the remaining inaccessible sources he may be capable to pick up or predict. Therefore, there is the need to have at least a simplest numerical basis for an effective size of entropy in relation to an attacker, who has various capabilities. For the start, we should define what kind of leverage a hypothetical attacker may have.

  • The simplest version, — is when an attacker has absolutely no access to a computer in a moment of random number generation, he also does not know the exact moment of generation, nor has an information about the state of a system on that moment either. This model corresponds to the most likely kind of an attacker, and this model has the maximum possible safety of all the sources of entropy. Later on, one of the versions of strength calculation will be given with regard to this model.
  • A more complicated version, — is when an attacker has a partial access to a computer and knows an approximate (within the milliseconds range) time of random number generation, and when he also has the access to a part of system information on that moment. Practically, this model corresponds to a potential that an attacker may have in a multi-user environment, when he has no administrative privileges in there. Later on, strength calculation for this model will also be presented, and exactly these kind of numbers should be taken as a basis for giving an assessment for having a minimum acceptable strength.
  • And finally the third version, — when an attacker has a full access to a system. It is obvious, that it is impossible to be protected in such a case, as an attacker can take control of and to replace any sources of entropy, and also can have a direct influence upon internal state of the RNG, or to replace the RNG completely with his own one. This version corresponds to a kind of an attacker, which has administrative privileges on a system that he is attacking, and there is no, nor there can be a defense from him. Therefore, under no circumstances you must generate keys or work with a confidential data on a system that can be controlled by someone other than you. Otherwise, your security is literally hairbreadth to none.

The sources of entropy that are used in the DiskCryptor's RNG are separated into two types: fast sources, working in the kernel-mode, and slow sources, working in the user-mode. The first ones a residing together with the RNG inside the driver, and the second ones reside in the dcapi.dll, and the data from them is periodically transmitted to the driver. First, let us examine a set of functions of the kernel, used as a kernel-mode sources of randomness. Their main property is inaccessibility of their direct reading by an attacker that has a limited access to a system, but a portion of their bits may be predictable, and so in the table that is presented below there are two values for each source: minimum and maximum. The values are true on a condition that the use of these sources is no frequent than 10 times per second, on a more numerous use an effective entropy of each call decreases.

Function Dependency Minimum entropy Maximum entropy
PsGetCurrentProcess On the process invoking reseed 0 2
PsGetCurrentProcessId On the process invoking reseed 0 2
KeGetCurrentThread On the thread invoking reseed 1 4
PsGetCurrentThreadId On the thread invoking reseed 0 2
KeGetCurrentProcessorNumber On the number of current processor 0 2
KeQueryInterruptTime On all interrupts in the system 8 16
KeQueryPriorityThread On the thread priority 0 1
KeQueryPerformanceCounter RTC (Real Time Clock) 4 8
__rdtsc CPU timestamp counter 16 24
ExGetPreviousMode Previous mode of the thread execution 0 1
IoGetInitialStack Initial stack of the thread 0 1
IoGetTopLevelIrp Last IRP (Input/output Request Packet) in the queue 0 2
MmQuerySystemSize Size of the system memory 0  ?
ExUuidCreate PRNG of the Windows kernel 8 (?)  ?
RtlRandom Predictable value, but may be altered by other drivers 0  ?
KeQueryTickCount Number of ticks of the counter from the moment of system's boot 2 4
IoGetStackLimits Stack limits for the current thread 0  ?
Total: 39 75

Thus, we can see that on an average we get 39–75 random bits on one reseed operation. This is not enough if reseed is carried out once, therefore DiskCryptor retrieves entropy from fast functions in the moment of a first thousand disk I/O operations after the system's start. Even if we are to assume that the time of I/O operations execution is practically constant, then on the minimum we would have no less than 1 bit of entropy per reseed (because predicting the time of reading data from a disk with the nanosecond precision looks like a fiction), that in total would amount to no less than 1000 bits of effective entropy right after the system's boot. Subsequently, the fast source of entropy is being used less, and namely in the moment of some not very frequent system events, and in the moment of random number generation.

Besides using fast kernel-mode entropy sources, RNG also uses slow user-mode sources. Several API functions and also user actions (mouse movement, pressing of keys) are used as user-mode sources. At the start of the program, Windows's RNG CryptoAPI CryptGenRandom function is used once, as the source of entropy. Recent studies show that this RNG is weak and in a protracted period of time it issues pseudorandom numbers, as it rarely replenishes entropy, and thus using it more than once is not justified. It is difficult for me to name the value of its effective entropy, but apparently it has to be no less than 32 bits, otherwise RNG would have had a very short period, which can be discovered with a simplest of tests. Mouse movements are used as the source of entropy the whole time the program is working. This is a very good source of entropy even on its own accord, as the time between the two mouse communications is wide in comparison with CPU clocks, and even from this time alone it is possible to confidently gather 16 random bits at a time. Extra 2–3 random bits can be taken off from mouse cursor coordinates and presses of mouse keys. Keyboard keys presses in the program's window are also used by RNG, and both the time of press and release, as well as the key's code are sent to it. This guarantees, that even in the absence of other sources of randomness, the effective entropy of the keys being generated, cannot be less than the entropy of your password, as the password is also used in key generation. It is also important, that these sources of entropy are inaccessible for reading by a local attacker with limited privileges, since if attacker's privileges are high enough to intercept keyboard presses, then encryption loses all its meaning.

In addition to one-time and persistent sources of entropy described above, the program also uses recurrent entropy sources, information from which is collected every 5 seconds as long as the program works. The list of functions used, and approximate value of amount of random bits receive from them, is presented in the table below.

Function Minimum entropy Maximum entropy Inaccessible to local attacker
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
Total: 162 335 146

In total we have 146 bits, that are guaranteed to be inaccessible even to a local attacker. That is not too much, but nevertheless, already lies beyond the capabilities of attackers having modern day technology.

Fast PRNG for generation of large volume of random numbers

The aforementioned RNG is designed to generate small amount of random numbers with a large strength reserve. This scheme's efficiency, however, is quite low and therefore it is unsuited for generation of gigabytes of random numbers that are needed for the algorithms to securely wipe disk sectors on encryption. For this purpose DiskCryptor has the pseudorandom number generator that is built with the utmost simplicity, but nonetheless its durability is based on the strength of the AES.

DiskCryptor's pseudorandom number generator

Here in this scheme, the main RNG is used as the source of entropy, and with its help a random AES key is generated on the first initialization of the generator. Output of pseudorandom numbers is done by the process of encryption, using this key, of sequentially incrementing 128 bit counter. Statistical characteristics of output data are fully ensured by the AES algorithm. On the completion of generator's work, the key is destroyed, and it becomes impossible to distinguish an obtained data from a random data. This scheme has the property of being simple and sufficiently safe for its purpose.

List of publications used

  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, Март 2007
  3. John Kelsey, Bruce Schneier, David Wagner, Chris Hall, "Cryptanalytic Attacks on Pseudorandom Number Generators", Springer-Verlag London, UK, 1998
Language: English  • русский