Messages in this thread | | | Date | Thu, 23 Sep 2004 19:43:40 -0400 | From | Jean-Luc Cooke <> | Subject | [PROPOSAL/PATCH] Fortuna PRNG in /dev/random |
| |
here we go ...
Team,
Here is a patch for the 2.6.8.1 Linux kernel which replaces the existing PRNG in random.c with the Fortuna PRNG designed by Ferguson and Schneier (Practical Cryptography). It is regarded in crypto circles as the current state-of-the-art in cryptographically secure PRNGs.
Warning: Ted Ts'o and I talked about this at great length in sci.crypt and in the end I failed on convince him that my patch was worth becoming main-line, and he failed to convince me that status-quo is acceptable considering a better solution exists.
I've made a page to capture my reasons and findings for this patch. http://jlcooke.ca/random/ Please review this link. As a minimum the first table comparing status-quo and Fortuna.
Changes in this patch (2 files): include/linux/sysctl.h + added a RANDOM_DERIVE_SEED enum for the new /proc/sys/kernel/random/derive_seed interface.
drivers/char/random.c + Kept all the event collection mechanisms, and interfaces. + Removed MD5-noPadding, SHA1-noPadding-endianIncorrect, halfMD4-noPadding (!?) and twoThirdsMD4-noPadding (!?) - Now uses Fortuna and the CryptoAPI (SHA-256, AES256) + Removed the one-of-a-kind (to my knowledge anyway) linear input mixing function - Now uses Fortuna and the CryptoAPI (SHA-256, AES256) + Removed the SHA1-feedback RNG output function - Input/Output now uses the Fortuna PRNG + Removed the "HASH+HASH++++" system of SynCookies - SynCookies now use block cipher CBC encryption + Removed the "HASH+++" system of TCPv4/v6 sequence number generation - Now uses a block cipher CTR system to generate 32bit random value + Removed the "HASH" system of IPv4/v6 ID number generation - Now uses a block cipher CTR system to generate 32bit random value + Removed entropy estimation - Fortuna doesn't need it, vanilla-/dev/random and other Yarrow-like PRNGs do to survive state compromise and other attacks. - /dev/random is synonymous with /dev/urandom - /proc/sys/kernel/random/entropy_avail is always the same as /proc/sys/kernel/random/pool_size so ssh, dm-crypt and other apps who block waiting for entropy don't seize up all together. + Added /proc/sys/kernel/random/derive_pool to save the pooling system's state. This is a good thing because Fortuna will avoid using the entire pooling system for output (this is a strength).
I expect much discussion on this. So let me lay out some facts: - I have not broken /dev/random. I wrote this patch because I think we can do better and Fortuna is the best there is right now. - Current /dev/random is difficult to analyze because it doesn't use standards compliant cryptographic primitives. - Current /dev/random is slower then my proposed patch (5x on output, 2x on input) - Current /dev/random's input mixing function is a linear function. This is bad in crypto-circles. Why? Linear functions are communitive, associative and sometimes distributive. Outputs from Linear function based PRNGs are very weak. + Note: Currently, output from /dev/random is feed-back into the input mixing function making linear attacks of the PRNG more complex. But I fear the combination of linear input mixing & knowing the feedback input is a bad combination. Fortuna eliminates this and other theoretical attacks. Read: http://groups.google.com/groups?lr=&ie=UTF-8&th=2d80024f677ccadc&seekm=BemdnYeJjt2qMc3cRVn-jw%40comcast.com - If need-be, I am prepared to take over maintainership of drivers/char/random.c + I don't want to push such a big change into Ted's lap, I am capable of taking over for him.
I look forward to hearing from all of you.
JLC
| |