[lkml]   [2004]   [Sep]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
Subject[PROPOSAL/PATCH] Fortuna PRNG in /dev/random
here we go ...


Here is a patch for the 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.
Please review this link. As a minimum the first table comparing status-quo
and Fortuna.

Changes in this patch (2 files):
+ added a RANDOM_DERIVE_SEED enum for the new
/proc/sys/kernel/random/derive_seed interface.

+ 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
- 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:
- 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.

 \ /
  Last update: 2005-03-22 14:06    [W:0.062 / U:0.348 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site