fortuna-random-2.6.12.1.patch (version 2.1.8 - Ottawa, Ontario, Canada)
- Applies cleanly to 2.6.12.1 and 2.6.12.2
- Instructions:
- cd linux-2.6.12.2; patch -p1 < ../fortuna-random-2.6.12.1.patch
- make menuconfig
Under "Cryptographic Options" enable: Cryptographic API and Fortuna CSRNG.
Change Log:
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
|
| TCP-IPv4 Sequence Number |
H = halfMD4Compress*({dstAddr, srcAddr, (srcPort<<16)|dstPort, secret}, secret[0..47])
seq# = H + 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 + count + usec + (1,000,000 * sec)
|
seq# = CT2
CT1 = CBCEncrypt(Key, daddr XOR IV)
CT2 = CBCEncrypt(Key, saddr XOR CT1)
|
| Secure IPv4 ID |
H = halfMD4Compress*( {dstAddr, secret, secret, secret[11}, secret[0..47] )
id# = H
|
id# = Encrypt(secret, {daddr,0,0,0})
|
| Secure IPv6 ID |
H = halfMD4Compress*( dstAddr, secret[0..47] )
id# = H
|
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
|
Acknowledgments
Greg Rose
Contents:
- What is /dev/random?
- Description of the current PRNG in Linux's /dev/random and /dev/urandom
- Cooke's thoughts on the current Linux PRNG
- Description of the PRNG in the Fortuna PRNG Patch
0. What is /dev/random?
Linux has a OS level Random Number Generator (RNG). RNGs come in two broad categories: TRNG and PRNG.
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:
- It is difficult to determine the output (or any expected patterns in the output) without complete knowledge of the current and past system
- Previous output is difficult to determine without complete knowledge of the current and past system at the past time in question
- Future output is difficult to determine without complete knowledge of the current and past system at the future time in question
It is important to point out that input and output behaviour are not specified in these requirements - they are not necessarily relevant to the construction of a CSRNG. Hash algorithms, block ciphers, event sources, programming language, and other details are not necessarily relevant either. A CSRNG should possess the following in an open environment:
- Clear description of how it operates (well documented source code explaining the algorithm)
- Design which lends itself to easy analysis (use of operations with known properties)
- Security statement (Assuming Z the difficulty of attack Y is M, the RNG will recover from attack X in N operations/seconds/inputs/etc)
1. Description of the current PRNG in Linux's /dev/random and /dev/urandom
From these requirements /dev/random was created. Let us examine how /dev/random operates.
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:
- /dev/random will only output data if an internal measure of entropy exceeds a certain value.
This measure also has a maximum, no matter how much more system events are mixed into the pool, the value will never exceed this maximum.
- /dev/urandom will take the pool and use it as a seed for a PRNG.
Every read from /dev/urandom remixes the output back in to the pool.
/dev/urandom will never wait for the entropy count to reach a certain value.
Other parts of the Linux OS that use the data from the RNG are:
- TCPv4/v6 sequence numbers
- TCPv4/v6 SYNcookies
- IPSec
- dm-crypt
- et cetra
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):
System events currently collected are:
- IRQ interrupt numbers plus 0x100 (?!?) and time of their occurrence.
- Disk major and minor versions numbers plus 0x100 (!?!) and time of their occurrence.
- Keyboard input scancode and time of their occurrence.
Data is only entered if the present scancode is not equal to the previous scancode.
- Mouse movements and time of their occurrence.
2. Cooke's thoughts on the current Linux PRNG
It must first be mentioned that my views are not shared with many people including the original author of the Linux PRNG. For more on this, I refer you to this UseNet discussion on sci.crypt, and this last thread on the Linux Kernel Mailing List.
A summary of the discussion (paraphrased by myself):
- Several professional cryptographers agreed that the need for secure information theoretic random numbers is likely fictitious.
- As a consequence of this, the design decision of having /dev/random stop outputting data until more entropy is observed by the system is no longer needed.
- Several users of Linux in the discussion (some times emphatically) disagree with this notion.
- Several professional cryptographers attempted to explain to the group the commonly held opinion among cryptographers that designing an entropy estimation and accounting heuristic for a generic system (not a specific entropy source) is next to impossible.
- A a consequence of this, the design decision of having /dev/random stop outputting data until more entropy is observed by the system is likely vulnerable to attack.
- Cooke stated that the every existence of entropy estimation might allow an attacker to observe the level of activity on the system. Such as keyboard stroke timings, mouse movement timings, etc.
- Cooke was pretty much alone in holding this point of view.
- However, a few people did concede that if this theoretical attack could be eliminated, then changes should be done.
- In the end, it will be left up to the system admin whether to rmnod /dev/random and mknod /dev/random c 1 9 to remove this blocking if they see fit to do so.
The primary goal of the Fortuna PRNG patch was to replace the existing PRNG
After the reader reviews the 2.6 Linux vanilla PRNG in drivers/char/random.c file, they will note the following:
- It is not a trivial exercise to analyze the current PRNG.
- random.c has its own independent implementations of SHA-1, MD5 and two crippled versions of MD4 (halfMD4 and twothridsMD4 ... what is 2/3 of 16?).
It should use the Linux Crypto API. Use of properly implemented and tested cryptographic primitives lends to ease of analysis. (disclaimer: Cooke has contributed to the Crypto API).
- The implementations for all the hash functions are incomplete (They do not add the bit-length field and padding bits).
This may not be critical, but implementing cryptographic primitives which do not pass test vectors is highly undesirable since it only impedes cryptanalysis.
- The input transformation in add_entropy_words() is entirely linear.
Effectively, the input "hash function" for the vanilla Linux PRNG is linear.
This is undesirable, it has been demonstrated that linear hash functions are insecure.
state1 holds a linear relationship to state2 in: state2 = f(state1+x) = f(state1) + f(x)
Is this critical? Likely not, the mixing of the RNG output back into the input mixing function alleviates much of this.
Improvements the Fortuna PRNG Patch gives you
- All interfaces remain.
- 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
With the following additions:
- -r--r--r-- 1 root root /proc/sys/kernel/random/cipher_algo
- -r--r--r-- 1 root root /proc/sys/kernel/random/digest_algo
The differences in behaviour:
- None other than performance.
- All transformations in the PRNG are cryptographic primitives from the Linux Crypto API.
Thus, the Crypto API must be built into the kernel (not as a module).
- Dramatic performance increases as found by thomass from irc.freenode.net#crypto
- A Fortuna re-seeding occurs before every block is read from either /dev/random or /dev/urandom.
But only if the amount of data fed into pool-0 is greater then the digests block size and in /dev/urandom's case it has been at least 0.1 seconds since the last reseed.
- Use of a PRNG designed by a known cryptographer Niels Ferguson which is state-of-the-art.
- resilience against all known PRNG attacks (backtracking, future secrecy, state compromise, state extension, direct cryptanalysis of transformation primitives, etc)
- Two small changes were made to the design presented by Ferguson:
- Output for the ith pool is fed back into itself, there-by carrying forward up to 256 bits of entropy into the next transformation for each of the 32 pools.
- Input of random events is no longer a round-robin method but rather random based on the AES128 key to prevent control of event sources by a malicious attacker.
- A PRNG which does not depend on any entropy estimation for secure operation.
There-by eliminating the need for a potentially compromising element of the PRNG.
- A simpler design than the existing PRNG to ease future analysis of the PRNG.
3. Description of the CSRNG in the Fortuna patch
The Fortuna CSRNG requires a block cipher and a message digest function.
Fortuna is a provable CSRNG if there is a minimal rate of entropy entering the system and the cryptographic primitives meet the following requirements:
- Block cipher:
- Knowing only the plaintext-ciphertext pairs, it is not possible to determine the key faster than brute force
- Knowing only the first N-1 plaintext-ciphertext pairs, it is not possible to determine the N-th ciphertext block without the key
- The statistical distribution of output symbols is indistinguishable from white noise
- Message digest or hash function:
- From the output you can not controllably determine the input (1st pre-image resistance)
- Being able to alter some of the input you can not manipulate the output (2nd pre-image resistance)
For this patch, I used "#define" macro definitions to chose AES256 and SHA-256 as the block cipher and message digest function. My discussion does not justify this choice.
There are thirty-two (32) 512-bit pools used: r.pool r.pool .. r.pool
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).
