Skip to contentSkip to conversation

Fortuna PRNG in /dev/random

PROPOSAL/PATCH Jean-Luc Cooke 6 participants 15 messages Sep 23, 2004 – Sep 27, 2004 1 message not in the archive

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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

include/linux/sysctl.h +2 -1
diff -uNr linux-2.6.8.1-orig/include/linux/sysctl.h linux-2.6.8.1-fortuna/include/linux/sysctl.h
@@ -198,7 +198,8 @@
 	RANDOM_READ_THRESH=3,
 	RANDOM_WRITE_THRESH=4,
 	RANDOM_BOOT_ID=5,
-	RANDOM_UUID=6
+	RANDOM_UUID=6,
+	RANDOM_DERIVE_SEED=7
 };
 
 /* /proc/sys/kernel/pty */
drivers/char/random.c +656 -1389

2,496 lines not on this page · raw message

maintainer
#1 lore raw
Quoted 10 lines · Jean-Luc Cooke

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 taken a quick look at your patch, and here are some problems with it.

0. Code style issues

Take a look at /usr/src/linux/Documentation/CodingStyle, and follow it, please. In particular, pay attention to wrapping text (particularly comment blocks) at 80 characters, max, and lose the C++-style comments, please. Maintaining a good common comment convention is good, too.

1. Don't leave out-of-date comments behind.

Your patch makes significant changes, but you haven't updated the comments to reflect all of your changes. For example, the comments for secure TCP sequence number generation are no longer correct. The comments about the twisted GFSR document the original scheme, not the Fortuna generator. If you're going to remove the code, remove the comments too, or the resulting mess will be confusing and not very maintainable.

2. The kernel will break if CONFIG_CRYPTO is false

The /dev/random driver is designed to be present in the system no matter what. This was a design decision that was made long ago, to simplify user space applications that could count on /dev/random being present. This is a philosophical divide; your belief (as you put it on your web site) seems to be: "If you want secure random numbers but don't want crypto, then you don't want secure random numbers." The problem is that someone may not want (or need) encryption algorithms in the *kernel*, but they may still want secure random numbers in *userspace*.

In any case, your patch is broken, since the kernel will simply fail to build if CONFIG_CRYPTO is turned off. And simply making the compilation of /dev/random conditional on CONFIG_CRYPTO isn't good enough, since there are other portions of the kernel that assume that random.c will be present. (For example, irqaction for providing entropy input, and the TCP stack depends on it for secquence numbers.)

3. The TCP sequence numbers are broken

The requirements on secure sequence number is far more than just "needs to be random-ish, but incresing [sic]". Read RFC 1948:

The choice of initial sequence numbers for a connection is not random. Rather, it must be chosen so as to minimize the probability of old stale packets being accepted by new incarnations of the same connection [RFC 1185].

The increasing bit is also not guaranteed, since tmp[0] isn't masked off. Not that it would really matter if it did; with only 8 bits worth of COUNT_BITS, every 256 TCP connections you will wrap, and expose that connection to the risk that stale packets being accepted.

I'm also a bit concerned about how much time AES takes over the cut-down MD4, as this may affect networking benchmarks. (And we don't need super-strength crypto here.)

As far as the Fortuna generator being "better", it really represents a philosophical divide between what I call Crypto academics" and "Crypto engineers". I won't go into that whole debate here, except to note that the current /dev/random was designed with close consultation with Colin Plumb, who wrote the random number generator found in PGP, and indeed /dev/random is very close to that used in PGP. In discussions on sci.crypt, there were those who argued on both side of this issue, with such notables as Peter Gutmann lining up against Jean-Luc.

Quoted 3 lines

+ Removed entropy estimation
- Fortuna doesn't need it, vanilla-/dev/random and other Yarrow-like PRNGs do to survive state compromise and other attacks.

Entropy estimation is a useful concept in that it attempts to limit possible attacks caused by weaknesses in the crypto algorithms (such what happened at this year's Crypto's conference, where MD4, MD5, HAVAL, and SHA-0 were all weakened). The designed used by PGP and /dev/random both limit the amount of reliance placed in the crypto algorithms, where as Fortuna and Yarrow both assume that crypto primitives are 100% strong. This is again a philosophical divide; given that we have access to unpredicitability based on hardware timings, we should limit the dependence on crypto algorithsm and to design a system that is closer to "true randomness" as possible.

Quoted 3 lines

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

This is a red herring. /dev/random is not a linear function based PRNG. We use a linear function for mixing, yes, but we do use SHA-1 as part of the output stage. And based on how we use SHA-1, even if arbitrary collisions can be found in SHA-1 (as has been found in SHA-0) this wouldn't cause a failure of /dev/random's security --- this is part of the design philosophy of trying to avoid relying over much on the security of the crypto primitives, as much as possible.

- Ted

#2 lore raw
Quoted 6 lines · Theodore Ts'o

I've taken a quick look at your patch, and here are some problems with it.

0. Code style issues

Take a look at /usr/src/linux/Documentation/CodingStyle, ...

Will-do. My bad.

Quoted 9 lines

1. Don't leave out-of-date comments behind.

Your patch makes significant changes, but you haven't updated the comments to reflect all of your changes. ...

2. The kernel will break if CONFIG_CRYPTO is false matter what. This was a design decision that was made long ago, to simplify user space applications that could count on /dev/random ...

My naive point of view tells me either this design decision from days of yore was not thought out properly (blasphemy!), or the cryptoapi needs to be in kernel.

A compromise would be to have a primitive PRNG in random.c is no CONFIG_CRYRPTO is present to keep things working.

Quoted 1 line

3. The TCP sequence numbers are broken

I see. I'll make the change. Thank you.

Quoted 8 lines

As far as the Fortuna generator being "better", it really represents a philosophical divide between what I call Crypto academics" and "Crypto engineers". I won't go into that whole debate here, except to note that the current /dev/random was designed with close consultation with Colin Plumb, who wrote the random number generator found in PGP, and indeed /dev/random is very close to that used in PGP. In discussions on sci.crypt, there were those who argued on both side of this issue, with such notables as Peter Gutmann lining up against Jean-Luc.

Agreed. This is why I've been dreading in posting the patch here. The current /dev/random is good, possibly the best OS-level RNG out there right now. Ted, if I've never said it before or ever again, you've done a great job. But my first impressions when I dove in were:
- gah! Why did someone go through so much trouble to make this hard to analyse?
- humm, why not use the cryptoapi if we want random data?
- why do linux users want information secure random numbers? Wouldn't crypto-secure random numbers be what they really want?
+ this, I've learned, is not something you can argue well against. It's a matter of taste ... like Brittany Spears.

I wanted something more structured running on my machines so I re-wrote random.c to use Fortuna, no entropy estimators, and uses the cryptoapi.

For the record, I believe David Wagner saw the case for replacing the PRNG with Fortuna holding water. Even removing the entropy estimator. But coneeded that some people will want /dev/random to block, so let them eat cake.

Quoted 4 lines
Quoted 3 lines

+ Removed entropy estimation
- Fortuna doesn't need it, vanilla-/dev/random and other Yarrow-like PRNGs do to survive state compromise and other attacks.

Quoted 10 lines

Entropy estimation is a useful concept in that it attempts to limit possible attacks caused by weaknesses in the crypto algorithms (such what happened at this year's Crypto's conference, where MD4, MD5, HAVAL, and SHA-0 were all weakened). The designed used by PGP and /dev/random both limit the amount of reliance placed in the crypto algorithms, where as Fortuna and Yarrow both assume that crypto primitives are 100% strong. This is again a philosophical divide; given that we have access to unpredicitability based on hardware timings, we should limit the dependence on crypto algorithsm and to design a system that is closer to "true randomness" as possible.

What if I told the SHA-1 implementation in random.c right now is weaker than those hashs in terms of collisions? The lack of padding in the implementation is the cause. HASH("a\0\0\0\0...") == HASH("a") There are billions of other examples.

The academic vs. engineer analogy works the other way as well. Fortuna's security can be directly reduced to the security of the underlying algorithms. This is a good thing. If the security of all applications were reduced in the same way, the world would be a safer place (political discussions not withstanding).

Vanilla random.c depends on SHA-1 be to be resistant to 1-st pre-image attacks. Fortuna depends on this as well with SHA-256 (or whatever other hash you put in there). The "folding over with XOR" method you use to make random.c stronger can work against you as well. It comes down to "I've changed SHA-1 to make it stronger". The logic question
becomes: "Then why doesn't everyone use it?"

JLC

maintainer
#3 lore raw
Quoted 8 lines · Jean-Luc Cooke
Quoted 3 lines · Theodore Ts'o

2. The kernel will break if CONFIG_CRYPTO is false matter what. This was a design decision that was made long ago, to simplify user space applications that could count on /dev/random ...

My naive point of view tells me either this design decision from days of yore was not thought out properly (blasphemy!), or the cryptoapi needs to be in kernel.

There is some historical issues here --- namely, back in the early 1990's crypto still had significant export control issues, so we didn't want to put any crypto code into the core kernel. So we didn't have *any* encryption algorithms in the kernel at all. As to whether or not cryptoapi needs to be mandatory in the kernel, the question is aside from /dev/random, do most people need to have crypto in the kernel? If they're not using ipsec, or crypto loop devices, etc., they might not want to have the crypto api in their kernel unconditionally.

That aside, it's been demonstrated through a lot of experience, to the point of it being a principle of software engineering, that optional interfaces significantly complicate the users of that interface. In order to encourage applications to use /dev/random, we wanted to make it something that people could guarantee would be there. Random numbers are important!

Quoted 2 lines

A compromise would be to have a primitive PRNG in random.c is no CONFIG_CRYRPTO is present to keep things working.

Now *that*'s an extremely ill-considered idea. It means that an application can without any warning, can have its strong source of random numbers replaced with a weak random number generator. It should be blatently obvious why this is a specatularily bad, horrific idea.

Quoted 2 lines

- why do linux users want information secure random numbers? Wouldn't crypto-secure random numbers be what they really want?

If they only want crypto-secure random numbers, they can do it in userspace. Information secure random numbers is something the kernel can provide, because it has low-level access to entrpoy sources. So why not try to do the best possible job?

This by the way your complaint that /dev/random is "too slow" is a complete red herring. When do you need more than 6 megs of random numbers per second? And if the application just needs crypto-secure random numbers, then the application can just extract 32 bytes or so of randomness from /dev/random, and then do the CRNG in userspace, at which point it will be even faster, since the data won't have to copied from kernel to userspace.

Quoted 8 lines

The design used by PGP and

Quoted 6 lines

/dev/random both limit the amount of reliance placed in the crypto algorithms, where as Fortuna and Yarrow both assume that crypto primitives are 100% strong. This is again a philosophical divide; given that we have access to unpredicitability based on hardware timings, we should limit the dependence on crypto algorithsm and to design a system that is closer to "true randomness" as possible.

Quoted 4 lines

What if I told the SHA-1 implementation in random.c right now is weaker than those hashs in terms of collisions? The lack of padding in the implementation is the cause. HASH("a\0\0\0\0...") == HASH("a") There are billions of other examples.

This is another red herring. First of all, we're not using the hash as a MAC, or in any way where we would care about collisions. Secondly, all of the places where we take a hash, we are always doing it 16 bytes at a time, which is SHA's block size, so that there's no need for any padding. And although you didn't complain about it, that's also why we don't need to mix in the length in the padding; extension attacks just simply aren't an issue, since the way we are using the hash, that just simply an issue as far as the strength of /dev/random.

Quoted 3 lines

Vanilla random.c depends on SHA-1 be to be resistant to 1-st pre-image attacks. Fortuna depends on this as well with SHA-256 (or whatever other hash you put in there).

Incorrect, vanilla random.c does *not* depend on SHA-1's resistance to 1st pre-image attacks. In other words, even if you did have an oracle which given a SHA-1 hash will give you a string which hashes to that value, /dev/random's security properties would not be affected. Just because you have *a* string which hashes to that value, that won't help you find the contents of the pool.

That's my whole point. We have not changed SHA-1 to make it stronger; we simply have carefully designed /dev/random to minimize its reliance on crypto primitives, since we have so much entropy available to us from the hardware. Fortuna, in contrast, has the property that if its cryptoprimitives are broken, you might as well go home.

- Ted

#4 lore raw

If I submitted a patch that gave users the choice of swapping my Fortuna for the current /dev/random, would you be cool with that then?

Our discussions on the matter always seem to move to areas where we can never agree.

Quoted 8 lines · Theodore Ts'o
Quoted 2 lines

A compromise would be to have a primitive PRNG in random.c is no CONFIG_CRYRPTO is present to keep things working.

Now *that*'s an extremely ill-considered idea. It means that an application can without any warning, can have its strong source of random numbers replaced with a weak random number generator. It should be blatently obvious why this is a specatularily bad, horrific idea.

Easy fix - use CryptoAPI in our PRNGs and make it standard in the kernel. :)

You can see we're going in circles.

Quoted 4 lines

If they only want crypto-secure random numbers, they can do it in userspace. Information secure random numbers is something the kernel can provide, because it has low-level access to entrpoy sources. So why not try to do the best possible job?

Sure. I hate Brittney Spears, but I will not deny people the choice.

Quoted 7 lines

This by the way your complaint that /dev/random is "too slow" is a complete red herring. When do you need more than 6 megs of random numbers per second? And if the application just needs crypto-secure random numbers, then the application can just extract 32 bytes or so of randomness from /dev/random, and then do the CRNG in userspace, at which point it will be even faster, since the data won't have to copied from kernel to userspace.

I never complained that it was too slow. I've just noticed that when ever a patch is submitted there are only 3 reasons to accept it:
- does it do something we havn't done before?
- does it do something faster / smaller?
- is it in someway better then what's there now?

I did my best to alliviate #2. #3 I've decided I'll never be able to convince enough people for an all-out replacement. I'd be happy with a configuration choice.

Quoted 5 lines
Quoted 4 lines

What if I told the SHA-1 implementation in random.c right now is weaker than those hashs in terms of collisions? The lack of padding in the implementation is the cause. HASH("a\0\0\0\0...") == HASH("a") There are billions of other examples.

Quoted 9 lines

This is another red herring. First of all, we're not using the hash as a MAC, or in any way where we would care about collisions. Secondly, all of the places where we take a hash, we are always doing it 16 bytes at a time, which is SHA's block size, so that there's no need for any padding. And although you didn't complain about it, that's also why we don't need to mix in the length in the padding; extension attacks just simply aren't an issue, since the way we are using the hash, that just simply an issue as far as the strength of /dev/random.

Woh there. Didn't you just say "see, these hashes are weakened. That's bad". Now I just demonstrated the same thing with your SHA1 implementation and you throw that "red-herring" phrase out again?

Point of history when breaking a hash:
- first a method for collisions is found
- then comes 2nd pre-image
- then comes complete inversion

MD4 case and point. Any how. I've given up trying to sell a replacement. Can users have an option to switch?

JLC

#5 lore raw
Quoted 2 lines · Jean-Luc Cooke

If I submitted a patch that gave users the choice of swapping my Fortuna for the current /dev/random, would you be cool with that then?

I would certainly appreciate this option, given that my customers often have very different ideas of what they need. I don't see how it hurts the kernel to have a choice for /dev/random.

Signature · 3 lines
Scott Robert Ladd
site: http://www.coyotegulch.com
blog: http://chaoticcoyote.blogspot.com
maintainer
#6 lore raw
In reply to Jean-Luc Cooke
Quoted 6 lines · Jean-Luc Cooke
Quoted 4 lines

If they only want crypto-secure random numbers, they can do it in userspace. Information secure random numbers is something the kernel can provide, because it has low-level access to entrpoy sources. So why not try to do the best possible job?

Sure. I hate Brittney Spears, but I will not deny people the choice.

The principle of avoiding kernel bloat means that if it doesn't have to be done in the kernel, it should be done in userspace. If all you're providing is an CRNG, the question then is why should it be done in kernel, when it could be done just as easily in userspace, and using /dev/random as its input?

Quoted 10 lines
Quoted 9 lines

This is another red herring. First of all, we're not using the hash as a MAC, or in any way where we would care about collisions. Secondly, all of the places where we take a hash, we are always doing it 16 bytes at a time, which is SHA's block size, so that there's no need for any padding. And although you didn't complain about it, that's also why we don't need to mix in the length in the padding; extension attacks just simply aren't an issue, since the way we are using the hash, that just simply an issue as far as the strength of /dev/random.

Quoted 3 lines

Woh there. Didn't you just say "see, these hashes are weakened. That's bad". Now I just demonstrated the same thing with your SHA1 implementation and you throw that "red-herring" phrase out again?

No, what I'm saying is that crypto primitives can get weakened; this is a fact of life. SHA-0, MD4, MD5, etc. are now useless as general purpose cryptographic hashes. Fortuna makes the assumptions that crypto primitives will never break, as it relies on them so heavily. I have a problem with this, since I remember ten years ago when people were as confident in MD5 as you appear to be in SHA-256 today.

Crypto academics are fond of talking about how you can "prove" that Fortuna is secure. But that proof handwaves around the fact that we have no capability of proving whether SHA-1, or SHA-256, is truly secure.

In contrast, /dev/random doesn't have this dependence, which (a) is a good thing, and (b) why it doesn't bother with the SHA finalization step. It's simply not necessary.

- Ted

#7 lore raw
Quoted 10 lines · Theodore Ts'o
Quoted 3 lines

Woh there. Didn't you just say "see, these hashes are weakened. That's bad". Now I just demonstrated the same thing with your SHA1 implementation and you throw that "red-herring" phrase out again?

No, what I'm saying is that crypto primitives can get weakened; this is a fact of life. SHA-0, MD4, MD5, etc. are now useless as general purpose cryptographic hashes. Fortuna makes the assumptions that crypto primitives will never break, as it relies on them so heavily. I have a problem with this, since I remember ten years ago when people were as confident in MD5 as you appear to be in SHA-256 today.

http://eprint.iacr.org/2004/207.pdf

SHA-256 showing indications of weakness. Fortuna's algorithms can be replaced at compile-time. I may even consider doing them at run-time.

Quoted 4 lines

Crypto academics are fond of talking about how you can "prove" that Fortuna is secure. But that proof handwaves around the fact that we have no capability of proving whether SHA-1, or SHA-256, is truly secure.

Our issues are that we are *both* handwaving.

JLC

#8 lore raw
In reply to Theodore Ts'o
Quoted 6 lines · Theodore Ts'o

have *any* encryption algorithms in the kernel at all. As to whether or not cryptoapi needs to be mandatory in the kernel, the question is aside from /dev/random, do most people need to have crypto in the kernel? If they're not using ipsec, or crypto loop devices, etc., they might not want to have the crypto api in their kernel unconditionally.

As far as I know embedded folk do not want the crypto API to be mandatory, although I think Matt Mackall wanted to try and make something work (perhaps a subset just for /dev/random use).

- James

Signature · 2 lines
James Morris
<[email protected]>
#9 lore raw
Quoted 9 lines · James Morris
Quoted 6 lines · Theodore Ts'o

have *any* encryption algorithms in the kernel at all. As to whether or not cryptoapi needs to be mandatory in the kernel, the question is aside from /dev/random, do most people need to have crypto in the kernel? If they're not using ipsec, or crypto loop devices, etc., they might not want to have the crypto api in their kernel unconditionally.

Quoted 3 lines

As far as I know embedded folk do not want the crypto API to be mandatory, although I think Matt Mackall wanted to try and make something work (perhaps a subset just for /dev/random use).

I want to move a couple critical hash algorithms into lib/ as has been done with the CRC code. Then cryptoapi and /dev/random and a couple other things (htree comes to mind) could share code without inflicting the cryptoapi overhead and context limitations on everyone.

(currently about 4k messages behind on lkml, sorry for not chiming in sooner)

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#10 lore raw
In reply to James Morris
Quoted 9 lines · James Morris
Quoted 6 lines · Theodore Ts'o

have *any* encryption algorithms in the kernel at all. As to whether or not cryptoapi needs to be mandatory in the kernel, the question is aside from /dev/random, do most people need to have crypto in the kernel? If they're not using ipsec, or crypto loop devices, etc., they might not want to have the crypto api in their kernel unconditionally.

Quoted 3 lines

As far as I know embedded folk do not want the crypto API to be mandatory, although I think Matt Mackall wanted to try and make something work (perhaps a subset just for /dev/random use).

/dev/random used to be a source of high latencies, but Ingo's patches fix this. There was not a lot of CPU overhead but the latency was was a problem for serious audio use. But, audio is a unique set of requirements, it's somewhere between desktop and embedded and hard-RT.

This could certainly be a problem for the embedded folks due to space or CPU concerns, but the latency problem seems to be solved.

Lee

#11 lore raw
In reply to Theodore Ts'o
Quoted 3 lines · Theodore Ts'o

I'm also a bit concerned about how much time AES takes over the cut-down MD4, as this may affect networking benchmarks. (And we don't need super-strength crypto here.)

Oh,

openssl speed md4 aes shows:

type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
md4              10708.72k    38240.96k   111170.47k   215872.85k 296828.93k
aes-128 cbc      32121.81k    32678.31k    33119.49k    33221.29k 33210.59k
aes-192 cbc      27915.92k    27868.52k    28418.08k    28677.12k 28721.15k
aes-256 cbc      24599.57k    25142.38k    25381.80k    25474.88k 25392.46k

Since we're using small blocks.

Attached is the patch with the problems Ted pointed out.

JLC

include/linux/sysctl.h +2 -1
diff -uNr linux-2.6.8.1-orig/include/linux/sysctl.h linux-2.6.8.1-fortuna/include/linux/sysctl.h
@@ -198,7 +198,8 @@
 	RANDOM_READ_THRESH=3,
 	RANDOM_WRITE_THRESH=4,
 	RANDOM_BOOT_ID=5,
-	RANDOM_UUID=6
+	RANDOM_UUID=6,
+	RANDOM_DERIVE_SEED=7
 };
 
 /* /proc/sys/kernel/pty */
drivers/char/random.c +706 -1617

2,800 lines not on this page · raw message

maintainer
#12 lore raw
In reply to Jean-Luc Cooke

I recently posted the following article on sci.crypt, which has a more detailed analysis of the design of JLC's proposed patch to random.c

- Ted

From: [email protected] (Theodore Y. Ts'o)
Subject: Re: new /dev/random
Newsgroups: sci.crypt
Date: 27 Sep 2004 00:05:32 -0400
Organization: Massachusetts Institute of Technology

Quoted 1 line · Paul Rubin

Huh? JLC's patch *is* Fortuna.

Actually, it isn't Fortuna. But more on that in a moment....

Quoted 5 lines

However, IMO, JLC's patch (Fortuna)
should not go into the kernel in its present form, and the kernel maintainers should reject it. It should not be a configuration option. It has too much potential of screwing the user, until the entropy accounting is restored.

The problem is that Fortuna's design isn't really particularly compatible with entropy accounting. Each pool only contains 256 bits, and by definition, the pool can not possibly store more entropy than that. Once you extract 256 bits, you have to wait a second before you can drain whatever entropy might be in pool #1, then two seconds before you can drain whatever entropy might be in pool #2, then four seconds before you can drain whataver might be in pool #3, and so on. This means that even if all of the pools are completely filled, in order to extract 2048 bits of entropy (for an long-term RSA key pair, for example), this would require waiting for a little over 4 minutes (255 seconds, to be precise). To extract 4096 bits of entropy, we would have to wait 18 hours, 12 minutes, and 15 seconds (65535 seconds).

Indeed, one of the complaints that I have about the whole Fortuna design is that from the entropy perspective, 25% of the entropy is stashed away in pools that will never be used for over six *months*, with 50% of the pools never getting used until after 18 hours or more. Of course in that time, those pools will get filled, refilled and overfilled, many times over, uselessly wasting entropy. Entropy is a precious resource; it should not be so thoughtlessly squandered.

.... but of course, waiting over 18 hours to before sufficient amounts of entropy cascades through the pool structure in order to generate a 4096-bit RSA key isn't a problem with JLC's patch, because it doesn't implement the 2^k second delay for each pool, as specified by the Fortuna design. Instead, it reseeds at every call to extract_entropy, and every 2^k reseeds, it uses a particular pool. But in order to provide resistance to the state-extension attack --- which is the only justification for replacing /dev/random's current algorithm with Fortuna, and Fortuna's raison de etre --- you have to wait until a pool has a sufficient amount of entropy in order to provide for a catastrophic reseeding. Because the rate at which the pools are drawn down is dependent on the extraction rate, not based on a time basis, or based on some estimate of the amount of entropy collected in each of the pools, JLC's proposed patch is vulnerable to state extension attack. In other words, the proposed patch doesn't even do what it sets out to do!!

P.S. Despite the fact that JLC's patch is vulnerable to the state extension attack, because it does not faithfully implement the Fortuna design, it still squanders entropy. In fact, because under normal operations, reads to /dev/random are happen even less frequently than once a second, over 50% of the collected entropy could be stored for **years** before it is ever used, with the net result that the high-level entropy pools will get overfilled, and the entropy wasted. This is despite the fact that in the attack scenario, the attacker can still force the high-order pools to be used before sufficient entropy can be stored. So with respect to these two defects, it is the worst of both worlds.

P.P.S. Despite the fact that JLC's patch defines a #define RANDOM_RESEED_INTERVAL, which might lead one to believe that it is using a time-based cascading, in fact, that #define is never used in his patch. Despite the fact that a certain party has been seen whining about "obfuscated" code being hard being "rude", I won't go down that particular path. Nevertheless, the JLC's patch, with a profusion of unsued #define's, and dead code from the original /dev/random that is incompletely removed, has obfuscation not from the subtle design standpoint, but from the sloppy coding perspective, which IMHO is far worse (although of course, this can be corrected).
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Theodore Ts'o http://web.mit.edu/user/tytso/www/
Everybody's playing the game, but nobody's rules are the same!

A message that is not in the archive (sent off-list or not yet received): [email protected]

maintainer
#14 lore raw
Quoted 3 lines · Jean-Luc Cooke

I'll read over this once I finish re-writing my patch to use your entropy estimation.

While you're at it, please re-read RFC 793 and RFC 1185. You still don't have TCP sequence generation done right. The global counter is being increased for every TCP connection, and with only eight bits, it can wrap very frequently. Encrypting the source/destination address/port tuple and using that as an offset to the global clock, and then only bumping the counter when you rekey would be much more in the spirit of RFC 1185, and would result in sequence numbers much less likely to cause stale packets to get mistakenly accepted.

I'm still a bit concerned about whether doing AES is going to be a speed issue. Your comparisons against MD4 using openssl don't really prove much, because (a) the original code used a cut-down MD4, and (b) the openssl benchmark does a large number of encryptions and nothing else, so all of the AES key schedule and tables will be in cache.

The only real way to settle this would be to ask Jamal and some of the other networking hackers to repeat their benchmarks and see if the AES encryption for every TCP SYN is a problem or not. CPU's have gotten faster (but then again so have networks, and memory has *not* gotten much faster), so only a real benchmark will tell us for sure.

- Ted

#15 lore raw

Thanks.

My re-writing wilol appear as more like an editorial revision than a re-write.

I will certainly talk to Jamal et al. Thanks

JLC

Quoted 27 lines · Theodore Ts'o
Quoted 3 lines · Jean-Luc Cooke

I'll read over this once I finish re-writing my patch to use your entropy estimation.

While you're at it, please re-read RFC 793 and RFC 1185. You still don't have TCP sequence generation done right. The global counter is being increased for every TCP connection, and with only eight bits, it can wrap very frequently. Encrypting the source/destination address/port tuple and using that as an offset to the global clock, and then only bumping the counter when you rekey would be much more in the spirit of RFC 1185, and would result in sequence numbers much less likely to cause stale packets to get mistakenly accepted.

I'm still a bit concerned about whether doing AES is going to be a speed issue. Your comparisons against MD4 using openssl don't really prove much, because (a) the original code used a cut-down MD4, and (b) the openssl benchmark does a large number of encryptions and nothing else, so all of the AES key schedule and tables will be in cache.

The only real way to settle this would be to ask Jamal and some of the other networking hackers to repeat their benchmarks and see if the AES encryption for every TCP SYN is a problem or not. CPU's have gotten faster (but then again so have networks, and memory has *not* gotten much faster), so only a real benchmark will tell us for sure.

- Ted