v2.1.9: - Removed from -mm tree. :( - Locks are cleaner (or at least inline with random.c from 2.6.12.1!) - secure_ip_id() is used as a generic random u32 generator. For early boot this is not possible. So it returns crap. But at least it doesn't crash. "Early" being before floppy drivers, IPSec, SELinux load! v2.1.8: - Included into -mm tree - jlcooke will now focus on keeping it stable in this tree, support for older kernels ends. - added get_random_int() and secure_tcpv6_port_ephemeral() v2.1.7: - Ported to 2.6.11.4 (works up to 2.6.12-rc1) v2.1.6: - Sami Farin pointed out RANDOM_MAX_BLOCK_SIZE was used for __u32[]'s and u8[]'s, fixed. - Sami also found TCP sequence numbers weren't very secure. Typo in code fixed. - Sami found crypto_cipher_encrypt() uses nbytes and not numscatterlists. Fixed. v2.1.5: - random-fortuna.c is no longer #include'd from random.c, the drivers/char/Makefile takes care of this now thanks to Chris Han v2.1.4: - Fixed flaw where some situations, /dev/random would not block. v2.1.3: - Added a seperate round-robin index for use inputs. Avoids a super-cleaver user from forcing all system (unknown) random events from being fed into, say, pool-31. - Added a "can only extract RANDOM_MAX_EXTRACT_SIZE bytes at a time" to extract_entropy() v2.1.2: - Ts'o's (I love writing that!) recommendation to force reseeds to be at least 0.1 ms apart. v2.1.1: - Re-worked to keep the blocking /dev/random. Yes I finally gave in to what everyone's been telling me. - Entropy accounting is *only* done on events going into pool-0 since it's used for every reseed. Those who expect /dev/random to only output data when the system is confident it has info-theoretic entropy to justify this output, this is the only sensible method to count entropy. v2.0: - Initial version
Standard /dev/random | Fortuna Patch | |
---|---|---|
Cryptographic routines | Endian incorrect and missing padding to SHA1 Missing padding to MD5 as well "halfMD4" and "twothirdsMD4" missing padding as well |
Linux Kernel CryptoAPI |
Input mixing function | Linear hash of maintainer's design | Cryptographic Hash (SHA-256) |
Output PRNG function | SHA1* hash of entire pool fed to input mixing function | Block cipher in CTR mode (AES256), reseeded from pooling system once length(pool-0)>=256 and it has been at least 0.1 sec since the last reseed. Pool-j is used once every 2j reseeds. |
Kernel Size | 1,926,528 linux-2.6.8.1 no config changes |
1,934,281 linux-2.6.8.1 CryptoAPI, AES, SHA256 and Fortuna |
Output Performance (link) | 6,389,367 bytes/sec | 33,190,071 bytes/sec |
Input Performance (link) | 10,587,763 bytes/sec | 22,188,424 bytes/sec |
Basic High Level Design | A two pool Yarrow-like design using a linear mixing function and entropy estimation. The PRNG in red |
Fortuna as described in Practical Cryptography (Ferguson, Schneier). Other: Wiki, CodeProject, FreeDictionary, Citadel SW, GoogleGroups Linear PRNGs. The PRNG in red, and Cooke's changes in blue |
External Dependencies | Almost none | The Kernel Cryptographic API |
TCP SynCookie | cookie = f(sec1,sec2, srcAddr, dstAddr, srcPort, dstPort, count) f(...) = SHA1*(sec1,srcAddr,srcPort,dstaddr,dstPort,sec1) + sseq + (count * 224) + ((SHA1*(sec2,srcAddr,srcPort,dstaddr,dstPort,count,sec2)+data) % 224) |
---|---|
cookie = f(sec1,sec2, srcAddr, dstAddr, srcPort, dstPort, count) f(...) = AES256-CBC encrypt PT = {(count<<24)|(data&0x00ffffff), 0, 0, 0} IV = {saddr, daddr, (sport<<16)|dport, sseq} CT = PT ^ ENCRYPT(Key=join(sec1,sec2), IV) f(...) = CT[0] |
|
TCP-IPv4 Sequence Number | H = halfMD4Compress*({dstAddr, srcAddr, (srcPort<<16)|dstPort, secret[11]}, secret[0..47]) seq# = H[1] + count + usec + (1,000,000 * sec) |
seq# = Encrypt(secret, {(sport<<16)|dport,daddr,saddr}) |
|
TCP-IPv6 Sequence Number | H = twoThirdsMD4Compress*(dstAddr, {srcAddr, (srcPort<<16)|dstPort, secret[0..27]}) seq# = H[1] + count + usec + (1,000,000 * sec) |
seq# = CT2[0] CT1 = CBCEncrypt(Key, daddr XOR IV) CT2 = CBCEncrypt(Key, saddr XOR CT1) |
|
Secure IPv4 ID | H = halfMD4Compress*( {dstAddr, secret[9], secret[10], secret[11}, secret[0..47] ) id# = H[1] |
id# = Encrypt(secret, {daddr,0,0,0}) |
|
Secure IPv6 ID | H = halfMD4Compress*( dstAddr, secret[0..47] ) id# = H[1] |
id# = Encrypt(secret, daddr) |
|
Saving the RNG state | dd if=/dev/urandom of=/var/run/random-seed bs=2048 count=1 |
dd if=/dev/urandom of=/var/run/random-seed bs=2048 count=1 |
A TRNG is a True Random Number Generator. The output is not based on anything an attacker can base an attack on (examples include a transistor in avalanche mode, a high resolution Geiger counter, etc). TRNGs are prone to failure and it is sometimes difficult detect when they do fail. They also have a bias in their output which must be removed before use in things like generating cryptographic keys.
A PRNG is a Pseudo-Random Number Generator. The never ending output is computed from a seed value.
A CSRNG is a Cryptographically Strong Random Number Generator. In simplest terms it is a PRNG which evolves its seed over time by adding events which are either hard to predict and/or observe by an outside attacker. Since typically at least one source of a CSRNG is exposed to an attacker (network traffic causes interrupts, etc) it is also important that access to one event source not compromise the CSRNG. A CSRNG is what most Linux users want in a OS level RNG so I will address the requirements of a CSRNG.
A CSRNG has the following requirements:
Information about system events from several sources are mixed together in an ever-evolving pool of random data. When random data is required by the OS or a user, the entire pool is taken as a seed into a PRNG and the output is passed to the requestor. There is a secondary pool within the Linux RNG in an attempt to meet the needs of a CSRNG (above). There is also a entropy accounting heuristic in place to estimate how much entropy is in the system. This is used to stop (or block) the output from the character device /dev/random until it is believed that sufficient randomness exists for your uses.
There are two ways to get random data from the Linux RNG, /dev/random and /dev/urandom:
Let us explore deeper into how this RNG operates.
When you perform a "dd if=/dev/urandom of=rnd.out count=1 bs=1024", a single 1024 byte block is extracted from the PRNG and placed into the file "rnd.out".
Changing the block size to 2048: "dd if=/dev/urandom of=rnd.out count=1 bs=2048", a single 2048 byte block is extracted from the PRNG and placed into the file "rnd.out".
Changing the block count to 2: "dd if=/dev/urandom of=rnd.out count=2 bs=1024", two 1024 byte blocks are extracted from the PRNG and placed into the file "rnd.out" (2048 bytes in size).
There are two (2) 4096-bit pools used: primary_pool and secondary_pool.
When new data is added, it is added to one of the pools using a linear transformation of unique design.
Each pool is fed new data in round-robin fashion.
Data is given and taken from a pool in the following way (HASH_FUNCTION is typically SHA-1):
$fh = fopen("vanilla_pseudocode.html", "rb"); print fread($fh, 32*1024); fclose($fh); ?> |
A summary of the discussion (paraphrased by myself):
With the following additions:
- crw-r--r-- 1 root root /dev/random
- crw-r--r-- 1 root root /dev/urandom
- -r--r--r-- 1 root root /proc/sys/kernel/random/boot_id
- -r--r--r-- 1 root root /proc/sys/kernel/random/entropy_avail
- -rw-r--r-- 1 root root /proc/sys/kernel/random/poolsize
- -rw-r--r-- 1 root root /proc/sys/kernel/random/read_wakeup_threshold
- -r--r--r-- 1 root root /proc/sys/kernel/random/uuid
- -rw-r--r-- 1 root root /proc/sys/kernel/random/write_wakeup_threshold
The differences in behaviour:
- -r--r--r-- 1 root root /proc/sys/kernel/random/cipher_algo
- -r--r--r-- 1 root root /proc/sys/kernel/random/digest_algo
There are thirty-two (32) 512-bit pools used: r.pool[0] r.pool[1] .. r.pool[31]
When new data is added, it is added to one of the pools using a cryptographic hash.
Each pool is fed new data in round-robin fashion.
Output is generated using AES128 in CTR mode.
The key used for the output cipher is updated every 0.1 seconds.
The key is updated by hashing the old key and one or more of the 32 pools.
The ith pool is used once every 2i key updates (pools are numbers 0 to 31).