VeraCrypt
aboutsummaryrefslogtreecommitdiff
path: root/doc/html/Random Number Generator.html
blob: bbe1785850b5632030e37996cd2005ffce10ee5e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>VeraCrypt - Free Open source disk encryption with strong security for the Paranoid</title>
<meta name="description" content="VeraCrypt is free open-source disk encryption software for Windows, Mac OS X and Linux. In case an attacker forces you to reveal the password, VeraCrypt provides plausible deniability. In contrast to file encryption, data encryption performed by VeraCrypt is real-time (on-the-fly), automatic, transparent, needs very little memory, and does not involve temporary unencrypted files."/>
<meta name="keywords" content="encryption, security"/>
<link href="styles.css" rel="stylesheet" type="text/css" />
</head>
<body>

<div>
<a href="https://www.veracrypt.fr/en/Home.html"><img src="VeraCrypt128x128.png" alt="VeraCrypt"/></a>
</div>

<div id="menu">
	<ul>
	  <li><a href="Home.html">Home</a></li>
	  <li><a href="/code/">Source Code</a></li>
	  <li><a href="Downloads.html">Downloads</a></li>
	  <li><a class="active" href="Documentation.html">Documentation</a></li>
	  <li><a href="Donation.html">Donate</a></li>
	  <li><a href="https://sourceforge.net/p/veracrypt/discussion/" target="_blank">Forums</a></li>
	</ul>
</div>

<div>
<p>
<a href="Documentation.html">Documentation</a>
<img src="arrow_right.gif" alt=">>" style="margin-top: 5px">
<a href="Technical%20Details.html">Technical Details</a>
<img src="arrow_right.gif" alt=">>" style="margin-top: 5px">
<a href="Random%20Number%20Generator.html">Random Number Generator</a>
</p></div>

<div class="wikidoc">
<h1>Random Number Generator</h1>
<p>The VeraCrypt random number generator (RNG) is used to generate the master encryption key, the secondary key (XTS mode), salt, and keyfiles. It creates a pool of random values in RAM (memory). The pool, which is 320 bytes long, is filled with data from the
 following sources:</p>
<ul>
<li>Mouse movements </li><li>Keystrokes </li><li><em>Mac OS X and Linux</em>: Values generated by the built-in RNG (both <em>/dev/random</em> and<em>/dev/urandom</em>)
</li><li><em>MS Windows only</em>: MS Windows CryptoAPI (collected regularly at 500-ms interval)
</li><li><em>MS Windows only</em>: Network interface statistics (NETAPI32) </li><li><em>MS Windows only</em>: Various Win32 handles, time variables, and counters (collected regularly at 500-ms interval)
</li></ul>
<p>Before a value obtained from any of the above-mentioned sources is written to the pool, it is divided into individual bytes (e.g., a 32-bit number is divided into four bytes). These bytes are then individually written to the pool with the modulo 2<sup>8</sup>
 addition operation (not by replacing the old values in the pool) at the position of the pool cursor. After a byte is written, the pool cursor position is advanced by one byte. When the cursor reaches the end of the pool, its position is set to the beginning
 of the pool. After every 16<sup>th</sup> byte written to the pool, the pool mixing function is automatically applied to the entire pool (see below).</p>
<h2>Pool Mixing Function</h2>
<p>The purpose of this function is to perform diffusion [2]. Diffusion spreads the influence of individual &ldquo;raw&rdquo; input bits over as much of the pool state as possible, which also hides statistical relationships. After every 16<sup>th</sup> byte
 written to the pool, this function is applied to the entire pool.</p>
<p>Description of the pool mixing function:</p>
<ol>
<li>Let <em>R</em> be the randomness pool. </li><li>Let <em>H</em> be the hash function selected by the user (SHA-512, RIPEMD-160, or Whirlpool).
</li><li><em>l</em> = byte size of the output of the hash function <em>H</em> (i.e., if
<em>H</em> is RIPEMD-160, then <em>l</em> = 20; if <em>H</em> is SHA-512, <em>l</em> = 64)
</li><li><em>z</em> = byte size of the randomness pool <em>R </em>(320 bytes) </li><li><em>q</em> = <em>z</em> / <em>l</em> &ndash; 1 (e.g., if <em>H</em> is Whirlpool, then
<em>q</em> = 4) </li><li>Ris divided intol-byte blocksB0...Bq.
<p>For 0 &le; i &le; q (i.e., for each block B) the following steps are performed:</p>
<ol type="a">
<li><em>M = H</em> (<em>B</em>0 || <em>B</em>1 || ... || <em>B</em>q) [i.e., the randomness pool is hashed using the hash function H, which produces a hash M]
</li><li>Bi = Bi ^ M </li></ol>
</li><li><em>R = B</em>0 || <em>B</em>1 || ... || <em>B</em>q </li></ol>
<p>For example, if <em>q</em> = 1, the randomness pool would be mixed as follows:</p>
<ol>
<li>(<em>B</em>0 || <em>B</em>1) = <em>R</em> </li><li><em>B</em>0 = <em>B</em>0 ^ <em>H</em>(<em>B</em>0 || <em>B</em>1) </li><li><em>B</em>1 = <em>B</em>1 ^ <em>H</em>(<em>B</em>0 || <em>B</em>1) </li><li><em>R</em> = <em>B</em>0 || <em>B</em>1 </li></ol>
<h2>Generated Values</h2>
<p>The content of the RNG pool is never directly exported (even when VeraCrypt instructs the RNG to generate and export a value). Thus, even if the attacker obtains a value generated by the RNG, it is infeasible for him to determine or predict (using the obtained
 value) any other values generated by the RNG during the session (it is infeasible to determine the content of the pool from a value generated by the RNG).</p>
<p>The RNG ensures this by performing the following steps whenever VeraCrypt instructs it to generate and export a value:</p>
<ol>
<li>Data obtained from the sources listed above is added to the pool as described above.
</li><li>The requested number of bytes is copied from the pool to the output buffer (the copying starts from the position of the pool cursor; when the end of the pool is reached, the copying continues from the beginning of the pool; if the requested number of bytes
 is greater than the size of the pool, no value is generated and an error is returned).
</li><li>The state of each bit in the pool is inverted (i.e., 0 is changed to 1, and 1 is changed to 0).
</li><li>Data obtained from some of the sources listed above is added to the pool as described above.
</li><li>The content of the pool is transformed using the pool mixing function. Note: The function uses a cryptographically secure one-way hash function selected by the user (for more information, see the section
<em>Pool Mixing Function</em> above). </li><li>The transformed content of the pool is XORed into the output buffer as follows:
<ol type="a">
<li>The output buffer write cursor is set to 0 (the first byte of the buffer). </li><li>The byte at the position of the pool cursor is read from the pool and XORed into the byte in the output buffer at the position of the output buffer write cursor.
</li><li>The pool cursor position is advanced by one byte. If the end of the pool is reached, the cursor position is set to 0 (the first byte of the pool).
</li><li>The position of the output buffer write cursor is advanced by one byte. </li><li>Steps b&ndash;d are repeated for each remaining byte of the output buffer (whose length is equal to the requested number of bytes).
</li><li>The content of the output buffer, which is the final value generated by the RNG, is exported.
</li></ol>
</li></ol>
<h2>Design Origins</h2>
<p>The design and implementation of the random number generator are based on the following works:</p>
<ul>
<li>Software Generation of Practically Strong Random Numbers by Peter Gutmann [10]
</li><li>Cryptographic Random Numbers by Carl Ellison [11] </li></ul>
<p>&nbsp;</p>
<p><a href="Keyfiles.html" style="text-align:left; color:#0080c0; text-decoration:none; font-weight:bold.html">Next Section &gt;&gt;</a></p>
</div><div class="ClearBoth"></div></body></html>