Fortuna PRNG in /dev/random
Subsystems (4)
Fortuna is an attempt to avoid the need for entropy estimation. It doesn't do a perfect job. And I don't think it's received enough review to be "regarded as the state of the art".
Entropy estimation is very difficult, but not doing it leads to problems.
Bruce Schneier's "catastrophic reseeding" ideas have some merit. If, for some reason, the state of your RNG pool has been captured, then adding one bit of seed material doesn't hurt an attacker who can look at the output and brute-force that bit.
Thus, once you've lost security, you never regain it. If you save up, say, 128 bits of seed material and add it all at once, your attacker can't brute-force it.
/dev/random tries to solve this my never letting anyone see more output than there is seed material input. So regardless of the initial state of the pool, an attacker can never get enough output to compute a unique solution to the seed material question. (See "unicity distance".)
However, this requires knowing the entropy content of the input, which is a hard thing to measure.
The while issue of catastrophic reseeding applies to output-larger-than-key generators like something like /dev/urandom (that uses cryptographic
Here's an example of how Fortuna's design fails.
Suppose we have a source which produces 32-bit samples, which are guaranteed to contain 1 bit of new entropy per sample. We should be able to feed that into Fortuna and have a good RNG, right? Wrong.
Suppose that each time you sample the source, it adds one bit to a 32-bit shift register, and gives you the result. So sample[0] shares 31 bits with sample[1], 30 bits with sample[2], etc.
Now, suppose that we add samples to 32 buckets in round-robin order, and dump bucket[i] into the pool every round 2^i rounds. Further, assume that our attacker can query the pool's output and brute-force 32 bits of seed material. In the following, "+=" is some cryptographic mixing primitive, not literal addition.
Pool: Initial state known to attacker (e.g. empty)
Buckets: Initial state known to attacker (e.g. empty) bucket[0] += sample[0]; pool += bucket[0]
-> attacker can query the pool and brute-force compute sample[0].
bucket[1] += sample[1] (= sample[0] << 1 | sample[32] >> 31) bucket[2] += sample[2] (= sample[0] << 2 | sample[32] >> 30)
...
bucket[31] += sample[31] (= sample[0] << 31 | sample[32] >> 1) bucket[0] += sample[32]; pool += bucket[0]
-> attacker can query the pool and brute-force compute sample[32]. -> Attacker now knows sample[1] through sample[31] -> Attacker now knows bucket[1] through bucket[31.
Note that the attacker now knows the value of sample[1] through sample[31] and thus the state of all the buckets, and can continue tracking the pool's state indefinitely:
bucket[1] += sample[33]; pool += bucket[1]
-> attacker can query the pool and brute-force compute sample[33].
etc.
This shift register behaviour should be obvious, but suppose that sample[i] is put through an encryption (known to the attacker) before being presented. You can't tell that you're being fed cooked data, but the attack works just the same.
Now, this is, admittedly, a highly contrived example, but it shows that Fortuna does not completely achieve its stated design goal of achieving catastrophic reseeding after having received some contant times the necessary entropy as seed material. Its round-robin structure makes it vulnerable to serial correlations in the input seed material. If they're bad enough, its security can be completely destroyed. What *are* the requirements for it to be secure? I don't know.
All I know is that it hasn't been analyzed well enough to be a panacea.
(The other thing I don't care for is the limited size of the entropy pools. I like the "big pool" approach. Yes, 256 bits is enough if everything works okay, but why take chances? But that's a philosophical/style/gut feel argument more than a really technical one.)
I confess I haven't dug into the /dev/{,u}random code lately. The various problems with low-latency random numbers needed by the IP stack suggest that perhaps a faster PRNG would be useful in-kernel. If so, there may be a justification for an in-kernel PRNG fast enough to use for disk overwriting or the like. (As people persist in using /dev/urandom for, even though it's explicitly not designed for that.)
"linux",
The Fortuna patch I've submitted tried to achieve this "more than 256 bits per pool" by carrying forward the digest output to the next pool. Stock Fortuna does not carry forward digest output form previous iterations.
reseed:
reseedCount++;
for (i=0..31) {
if (2^i is a factor of reseedCount) {
hash_final(pool[i], dgst);
hash_init(pool[i]);
hash_update(pool[i], dgst); // my addition
...
} }
...
Considering each pool has 256 bits of digest output, and there are 32 pools, this gives about 8192 bits for the pool size. Far greater then current design. If you extremely pessimistically consider the probability of drawing pool j is 1/2 that of {j-1}, then it's a 512bit RNG.
But I'd like talk to your attack for a second. I'd argue that it is valid for the current /dev/random and Yarrow with entropy estimators as well.
I agree that if the state is known by an active attacker, then a trickle of entropy into Fortuna compared to the output gathered by an attacker would make for an argument that "Fortuna doesn't have it right." And no matter what PRNG engine you but between the attack and the random sources, there is no solution other than accurate entropy measurement (*not* estimation).
However, this places the security of the system in the hands of the entropy estimator. If it is too liberal, we have the nearly the same situation with Fortuna. As much as I rely on Ted's work everyday for the smooth running of my machine, I can't concede to the notion that Ted got it right.
Fortuna, I'd argue reduces the attack on the PRNG to that of the base crypto primitives, the randomness of the events and the rate at which data is output by /dev/random. This holds true for the current /dev/random except:
1) crypto primitives are do not pass test vectors, and the input mixing function is linear.
2) The randomness of the events can only be estimated, their true randomness requires analysis of the hardware device itself... not Feasible considering all the possible IRQ sources, mice, and hard disks that Linux drives.
3) Following on (2) above, the output rate of /dev/random is directly related to the estimated randomness.
If you have ideas on how to make a PRNG that can more closely tie output rate to input events and survive state compromise attacks (backtracking, forward secrecy, etc) then please drop anonymity and contact me at my email address. Perhaps a collaboration is possible.
Cheers,
JLC
Quoted 97 lines · On Fri, Sep 24, 2004 at 12:59:38AM -0000, [email protected] wrote:
Fortuna is an attempt to avoid the need for entropy estimation. It doesn't do a perfect job. And I don't think it's received enough review to be "regarded as the state of the art".
Entropy estimation is very difficult, but not doing it leads to problems.
Bruce Schneier's "catastrophic reseeding" ideas have some merit. If, for some reason, the state of your RNG pool has been captured, then adding one bit of seed material doesn't hurt an attacker who can look at the output and brute-force that bit.
Thus, once you've lost security, you never regain it. If you save up, say, 128 bits of seed material and add it all at once, your attacker can't brute-force it.
/dev/randomtries to solve this my never letting anyone see more output than there is seed material input. So regardless of the initial state of the pool, an attacker can never get enough output to compute a unique solution to the seed material question. (See "unicity distance".)However, this requires knowing the entropy content of the input, which is a hard thing to measure.
The while issue of catastrophic reseeding applies to output-larger-than-key generators like something like
/dev/urandom(that uses cryptographicHere's an example of how Fortuna's design fails.
Suppose we have a source which produces 32-bit samples, which are guaranteed to contain 1 bit of new entropy per sample. We should be able to feed that into Fortuna and have a good RNG, right? Wrong.
Suppose that each time you sample the source, it adds one bit to a 32-bit shift register, and gives you the result. So sample[0] shares 31 bits with sample[1], 30 bits with sample[2], etc.
Now, suppose that we add samples to 32 buckets in round-robin order, and dump bucket[i] into the pool every round 2^i rounds. Further, assume that our attacker can query the pool's output and brute-force 32 bits of seed material. In the following, "+=" is some cryptographic mixing primitive, not literal addition.
Pool: Initial state known to attacker (e.g. empty)
Buckets: Initial state known to attacker (e.g. empty) bucket[0] += sample[0]; pool += bucket[0]-> attacker can query the pool and brute-force compute sample[0].bucket[1] += sample[1] (= sample[0] << 1 | sample[32] >> 31) bucket[2] += sample[2] (= sample[0] << 2 | sample[32] >> 30)
...
bucket[31] += sample[31] (= sample[0] << 31 | sample[32] >> 1) bucket[0] += sample[32]; pool += bucket[0]-> attacker can query the pool and brute-force compute sample[32]. -> Attacker now knows sample[1] through sample[31] -> Attacker now knows bucket[1] through bucket[31.Note that the attacker now knows the value of sample[1] through sample[31] and thus the state of all the buckets, and can continue tracking the pool's state indefinitely:
bucket[1] += sample[33]; pool += bucket[1]
-> attacker can query the pool and brute-force compute sample[33].etc.
This shift register behaviour should be obvious, but suppose that sample[i] is put through an encryption (known to the attacker) before being presented. You can't tell that you're being fed cooked data, but the attack works just the same.
Now, this is, admittedly, a highly contrived example, but it shows that Fortuna does not completely achieve its stated design goal of achieving catastrophic reseeding after having received some contant times the necessary entropy as seed material. Its round-robin structure makes it vulnerable to serial correlations in the input seed material. If they're bad enough, its security can be completely destroyed. What *are* the requirements for it to be secure? I don't know.
All I know is that it hasn't been analyzed well enough to be a panacea.
(The other thing I don't care for is the limited size of the entropy pools. I like the "big pool" approach. Yes, 256 bits is enough if everything works okay, but why take chances? But that's a philosophical/style/gut feel argument more than a really technical one.)
I confess I haven't dug into the
/dev/{,u}randomcode lately. The various problems with low-latency random numbers needed by the IP stack suggest that perhaps a faster PRNG would be useful in-kernel. If so, there may be a justification for an in-kernel PRNG fast enough to use for disk overwriting or the like. (As people persist in using/dev/urandomfor, even though it's explicitly not designed for that.)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
BTW, you write:
Quoted 2 lines
It is regarded in crypto circles as the current state-of-the-art in cryptographically secure PRNGs.
The question this brings to mind is:
It is? Can you point me to a single third-party paper on the subject?
There's nothing in the IACR preprint archive. Nor citeseer,
The big difference between when /dev/random was designed and today:
- USB is a broadcast bus, and a lot (timing, at least) can be sniffed by a small dongle. Wireless keyboards and mice are popular. That sort of user data probably shouldn't be trusted any more. (No harm mixing it in, just in case it is good, but accord it zero weight.)
- Clock speeds are a *lot* higher (> 1 GHz) and the timestamp counter is almost universally available. Even an attacker with multiple antennas pointed at the computer is going to have a hard time figuring out on which tick of the clock an interrupt arrived even if they can see it.
Thus, the least-significant bits of the TSC are useful entropy on *every* interrupt, timer included.
For a fun exercise, install a kernel hack to capture the TSC on every timer interrupt. Run it for a while on an idle system (processor in the halt state, waiting for interrupts on a cycle-by-cycle basis).
Take the resultant points, subtract the best-fit line, and throw out any outliers caused by delayed interrupts.
Now do some statistical analysis of the residue. How much entropy do you have from the timer interrupt? Does it look random? How many lsbits can you take and still pass Marsaglia's DIEHARD suite? Do any patterns show up in an FFT?
Quoted 4 lines
What if I told the SHA-1 implementation in
random.cright 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.
EXCUSE me? You're a little unclear, so I don't want to be attacking strawmen of my own devising, but are you claiming the failure to do Merkle-Damgaard padding in the output mixing operation of /dev/random is a WEAKNESS?
If true, this is a level of cluelessness incompatible with being trusted to design decent crypto.
The entire purpose of Merkle-Damgaard padding (also know as Merkle-Damgaard strengthening) is to include the length in the data hashed, to make hashing variable-sized messages as secure as fixed-size messages. If what you are hashing is, by design, always fixed-length, this is completely unnecessary.
If I were designing a protocol for message interchange, I might add the padding anyway, just to use pre-existing primitives easily, but for a 100% internal use like a PRNG, let's see... I can reduce code size AND implementation complexity AND run time without ANY security consequences, and there are no interoperability issues...
I could argue it's a design flaw to *include* the padding.
Quoted 6 lines · On Fri, Sep 24, 2004 at 09:42:30PM -0000, [email protected] wrote:
Quoted 4 lines
What if I told the SHA-1 implementation in
random.cright 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.EXCUSE me?
...
Quoted 1 line
I could argue it's a design flaw to *include* the padding.
I was trying to point out a flaw in Ted's logic. He said "we've recently discoverd these hashs are weak because we found collsions. Current /dev/random doesn't care about this."
I certainly wasn't saying padding was a requirment. But I was trying to point out that the SHA-1 implementaion crrently in /dev/random by design is collision vulnerable. Collision resistance isn't a requirment for it's purposes obviously.
Guess my pointing this out is a lost cause.
JLC
Theodore Ts'o
maintainerQuoted 9 lines · Jean-Luc Cooke
I was trying to point out a flaw in Ted's logic. He said "we've recently discoverd these hashs are weak because we found collsions. Current
/dev/randomdoesn't care about this."I certainly wasn't saying padding was a requirment. But I was trying to point out that the SHA-1 implementaion crrently in
/dev/randomby design is collision vulnerable. Collision resistance isn't a requirment for it's purposes obviously.
You still haven't shown the flaw in the logic. My point is that an over-reliance on crypto primitives is dangerous, especially given recent developments. Fortuna relies on the crypto primitives much more than /dev/random does. Ergo, if you consider weaknesses in crypto primitives to be a potential problem, then it might be reasonable to take a somewhat more jaundiced view towards Fortuna compared with other alternatives.
Whether or not /dev/random performs the SHA finalization step (which adds the padding and the length to the hash) is completely and totally irrelevant to this particular line of reasoning.
And actually, not doing the padding does not make the crypto hash vulnerable to collisions, as you claim. This is because in /dev/random, we are always using the full block size of the crypto hash. It is true that it is vulernable to extension attacks, but that's irrelevant to this particular usage of the SHA-1 round function. Whether or not we should trust the design of something as critical to the security of security applications as /dev/random to someone who fails to grasp the difference between these two rather basic issues is something I will leave to the others on LKML.
- Ted
Quoted 7 lines · Theodore Ts'o
You still haven't shown the flaw in the logic. My point is that an over-reliance on crypto primitives is dangerous, especially given recent developments. Fortuna relies on the crypto primitives much more than
/dev/randomdoes. Ergo, if you consider weaknesses in crypto primitives to be a potential problem, then it might be reasonable to take a somewhat more jaundiced view towards Fortuna compared with other alternatives.
Correct me if I'm wrong here.
You claimed that the collision techniques found for the UFN design hashs (sha0, md5, md5, haval, ripemd) demonstrated the need to not rely on hash algorithms for a RNG. Right?
And I showed that the SHA-1 in random.c now can produce collisions. So, if your argument against the fallen UFN hashs above (SHA-1 is a UFN hash also btw. We can probably expect more annoucments from the crypto community in early 2005) should it not apply to SHA-1 in random.c?
Or did I misunderstand you? Were you just mentioning the weakened algorithms as a "what if they were more serious discoveries? Wouldn't be be nice if we didn't rely on them?" ?
The decision to place trust in a entropy estimation scheme vs. a crypto algorithm we have different views on. I can live with that.
Quoted 3 lines
Whether or not
/dev/randomperforms the SHA finalization step (which adds the padding and the length to the hash) is completely and totally irrelevant to this particular line of reasoning.
I "completly and totally" agree. I'm pointing out that no added padding makes me, the new guy reading your code, work harder to decide if it's a weakness. You shouldn't do that to people if you can avoid it. Just like you shouldn't obfuscate code, even if it doesn't "weaken" its implementation. It's just rude. Take the performance penalty to avoid scaring people away from a very important peice of the kernel.
Quoted 4 lines
... Whether or not we should trust the design of something as critical to the security of security applications as
/dev/randomto someone who fails to grasp the difference between these two rather basic issues is something I will leave to the others on LKML.
... biting my toung ... so hard it bleeds ...
The quantitaive aspects of the two RNGs in question are not being discussed. It's the qualitative aspects we do not see eye to eye on. So I will no longer suggest replacing the status-quo. I'd like to submit a patch to let users chose at compile-time under Cryptographic options weither to drop in Fortuna.
Ted, can we leave it at this?
JLC
Theodore Ts'o
maintainerQuoted 9 lines · Jean-Luc Cooke
Quoted 7 lines · Theodore Ts'o
You still haven't shown the flaw in the logic. My point is that an over-reliance on crypto primitives is dangerous, especially given recent developments. Fortuna relies on the crypto primitives much more than
/dev/randomdoes. Ergo, if you consider weaknesses in crypto primitives to be a potential problem, then it might be reasonable to take a somewhat more jaundiced view towards Fortuna compared with other alternatives.
Quoted 5 lines
Correct me if I'm wrong here.
You claimed that the collision techniques found for the UFN design hashs (sha0, md5, md5, haval, ripemd) demonstrated the need to not rely on hash algorithms for a RNG. Right?
For Fortuna, correct. This is why I believe /dev/random's current design to be superior.
Quoted 4 lines
And I showed that the SHA-1 in
random.cnow can produce collisions. So, if your argument against the fallen UFN hashs above (SHA-1 is a UFN hash also btw. We can probably expect more annoucments from the crypto community in early 2005) should it not apply to SHA-1 inrandom.c?
(1) Your method of "producing collisions" assumed that /dev/random was of the form HASH("a\0\0\0...") == HASH("a) --- i.e., you were kvetching about the lack of padding. But we've already agreed that the padding argument isn't applicable for /dev/random, since it only hashes block-sizes at the same time. (2) Even if there were real collisions demonstrated in SHA-1's cryptographic core at some point in the future, it wouldn't harm the security of the algorithm, since /dev/random doesn't depend on SHA-1 being resistant against collisions. (Similarly, HMAC-MD5 is still safe for now since it also is designed such that the ability to find collisions do not harm its security. It's a matter of how you use the cryptographic primitives.)
Quoted 3 lines
Or did I misunderstand you? Were you just mentioning the weakened algorithms as a "what if they were more serious discoveries? Wouldn't be be nice if we didn't rely on them?" ?
That's correct. It is my contention that Fortuna is brittle in this regard, especially in comparison to /dev/random current design.
And you still haven't pointed out the logic flaw in any argument but your own.
- Ted
Quoted 9 lines
Quoted 3 lines
This, I do not recall. I must have missed it. Will you please show me two inputs that, when fed to the SHA-1 in
random.c, will produce identical output?SHA-1 without padding, sure.
hash("a")=hash("a\0")=hash("a\0\0")= ...hash("b")=hash("b\0")=hash("b\0\0")= ...hash("c")=hash("c\0")=hash("c\0\0")= ...
And how do I hash one byte with SHA-1 *without padding*? The only hashing code I can find in random.c works 64 bytes at a time. What are the other 63 bytes?
(I agree that that *naive* padding leads to collisions, but random.c doesn't do ANY padding.)
Quoted 3 lines
I see. And in the -mm examples, is the code easily readable for other os-MemMgt types? If no, then I guess
random.cis not the exception and I apologize.
The Linux core -mm code is a fairly legendary piece of Heavy Wizardry. To paraphrase, "do not meddle in the affairs of /usr/src/linux/mm/, for it is subtle and quick to anger." There *are* people who understand it, and it *is* designed (not a decaying pile of old hacks that *nobody* understands how it works like some software), but it's also a remarkably steep learning curve. A basic overview isn't so hard to acquire, but the locking rules have subtle details. There are places where someone very good noticed that a given lock doesn't have to be taken on a fast path if you avoid doing certain things anywhere else that you'd think would be legal.
And so if someone tries to add code to do the "obvious" thing, the lock-free fast path develops a race condition. And we all know what fun race conditions are to debug.
Fortunately, some people see this as a challenge and Linux is blessed with some extremely skilled VM hackers. And some of them even write and publish books on the subject. But while a working VM system can be clear, making it go fast leads to a certain amount of tension with the clarity goal.
Quoted 3 lines
And the ring-buffer system which delays the expensive mixing stages untill a a sort interrupt does a great job (current and my fortuna-patch). Difference being, fortuna-patch appears to be 2x faster.
Ooh, cool! Must play with to steal the speed benefits. Thank you!
Quoted 6 lines · On Mon, Sep 27, 2004 at 12:50:33AM -0000, [email protected] wrote:
Quoted 5 lines
SHA-1 without padding, sure.
hash("a")=hash("a\0")=hash("a\0\0")= ...hash("b")=hash("b\0")=hash("b\0\0")= ...hash("c")=hash("c\0")=hash("c\0\0")= ...
Quoted 6 lines
And how do I hash one byte with SHA-1 *without padding*? The only hashing code I can find in
random.cworks 64 bytes at a time. What are the other 63 bytes?(I agree that that *naive* padding leads to collisions, but
random.cdoesn't do ANY padding.)
And I guess it is my fault to assume "no padding" is naive padding.
Quoted 14 lines
Quoted 3 lines
I see. And in the -mm examples, is the code easily readable for other os-MemMgt types? If no, then I guess
random.cis not the exception and I apologize.The Linux core -mm code is a fairly legendary piece of Heavy Wizardry. To paraphrase, "do not meddle in the affairs of
/usr/src/linux/mm/, for it is subtle and quick to anger." There *are* people who understand it, and it *is* designed (not a decaying pile of old hacks that *nobody* understands how it works like some software), but it's also a remarkably steep learning curve. A basic overview isn't so hard to acquire, but the locking rules have subtle details. There are places where someone very good noticed that a given lock doesn't have to be taken on a fast path if you avoid doing certain things anywhere else that you'd think would be legal.
Quoted 8 lines
And so if someone tries to add code to do the "obvious" thing, the lock-free fast path develops a race condition. And we all know what fun race conditions are to debug.
Fortunately, some people see this as a challenge and Linux is blessed with some extremely skilled VM hackers. And some of them even write and publish books on the subject. But while a working VM system can be clear, making it go fast leads to a certain amount of tension with the clarity goal.
Freightning ... but informative thank you.
Quoted 5 lines
Quoted 3 lines
And the ring-buffer system which delays the expensive mixing stages untill a a sort interrupt does a great job (current and my fortuna-patch). Difference being, fortuna-patch appears to be 2x faster.
Ooh, cool! Must play with to steal the speed benefits. Thank you!
I'll have a patch for a "enable in crypto options" and "blocking with entropy estimation" random-fortuna.c patch this week. My fiance is out of town and there should be time to hack one up.
JLC
Theodore Ts'o
maintainerQuoted 5 lines · On Mon, Sep 27, 2004 at 12:50:33AM -0000, [email protected] wrote:
Quoted 3 lines
And the ring-buffer system which delays the expensive mixing stages untill a a sort interrupt does a great job (current and my fortuna-patch). Difference being, fortuna-patch appears to be 2x faster.
Ooh, cool! Must play with to steal the speed benefits. Thank you!
The speed benefits come from the fact that /dev/random is currently using a large pool to store entropy, and so we end up taking cache line misses as we access the memory. Worse yet, the cache lines are scattered across the memory (due to the how the LFSR works), and we're using/updating information from the pool 32 bits at a time. In contrast, in JLC's patch, each pool only has enough space for 256 bits of entropy (assuming the use of SHA-256), and said 256 bits are stored packed next to each other, so it can fetch the entire pool in one or two cache lines.
This is somewhat fundamental to the philosophical question of whether you store a large amount of entropy, taking advantage of the fact that the kernel has easy access to hardware-generated entropy, or use tiny pools and put a greater faith in crypto primitives.
So the bottom line is that while Fortuna's input mixing uses more CPU (ALU) resources, /dev/random is slower because of memory latency issue. On processors with Hyperthreading / SMT enabled (which seems to be the trend across all architectures --- PowerPC, AMD64, Intel, etc.), the memory latency usage may be less important, since other tasks will be able to use the other (virtual) half of the CPU while the entropy mixing is waiting on the memory access to complete. On the other hand, it does mean that we're chewing up a slightly greater amount of memory bandwidth during the entropy mixing process. Whether or not any of this is actually measurable during real-life mixing is an interesting and non-obvious question.
- Ted
Quoted 11 lines · Theodore Ts'o
Quoted 5 lines · On Mon, Sep 27, 2004 at 12:50:33AM -0000, [email protected] wrote:
Quoted 3 lines
And the ring-buffer system which delays the expensive mixing stages untill a a sort interrupt does a great job (current and my fortuna-patch). Difference being, fortuna-patch appears to be 2x faster.
Ooh, cool! Must play with to steal the speed benefits. Thank you!
This is somewhat fundamental to the philosophical question of whether you store a large amount of entropy, taking advantage of the fact that the kernel has easy access to hardware-generated entropy, or use tiny pools and put a greater faith in crypto primitives.
Tiny in that at most you can only pull out 256bits of entropy from one pool, you are correct. SHA-256 buffers 64 bytes at time. The transform requires 512 bytes for its mixing. The mixing of the 512 byte W[] array is done serially.
random_state->pool is POOLBYTES in size. Which is poolwords*4, which is DEFAULT'd to 512 bytes. The "5 tap" LFSR reaches all over that 512byte memory for its mixing.
If page sizes get big enough and we page-align the pool[] member, the standard RNG will get faster.
JLC
Quoted 3 lines
You claimed that the collision techniques found for the UFN design hashs (sha0, md5, md5, haval, ripemd) demonstrated the need to not rely on hash algorithms for a RNG. Right?
I'm putting words into Ted's mouth, but it seemed clear to me he said it was good not to rely *entirely* on the ahsh algorithms.
Quoted 1 line
And I showed that the SHA-1 in
random.cnow can produce collisions.
This, I do not recall. I must have missed it. Will you please show me two inputs that, when fed to the SHA-1 in random.c, will produce identical output?
Quoted 3 lines
So, if your argument against the fallen UFN hashs above (SHA-1 is a UFN hash also btw. We can probably expect more annoucments from the crypto community in early 2005) should it not apply to SHA-1 in
random.c?
No, not at all. The point is that the current random.c design DOES NOT RELY on the security of the hash function. Ted could drop MD4 in there and it still couldn't be broken, although using a better-regarded hash function just feels better.
Quoted 3 lines
Or did I misunderstand you? Were you just mentioning the weakened algorithms as a "what if they were more serious discoveries? Wouldn't be be nice if we didn't rely on them?" ?
Yes. And Fortuna's *only* layer of armor is the block cipher. Yes, it's a damn good layer of armor, but defense in depth sure helps.
That is NOT to say that lots of half-assed algorithms piled on top of each other makes good crypto, but if you can have a good primitive and *then* use it safely as well, that's better.
For example, AES is supposed to be resistant to adaptive chosen plaintext/ciphertext attacks. Suppose you are given two ciphertexts and two corresponding plaintexts, but not which corresponds to which. And then you are given access to an oracle which will, using the same key as was used on the plaintext/ciphertext pairs, give you the plaintext for any ciphertet that's not one of the two, and the ciphertext for any plaintext that's not one of the two. The orace can answer basically an infinite number of questions (well, 2^128-2) and you can look at one set of answers before posing the next.
AES is supposed to prevent you from figuring out, with all that help, which plaintext of the two goes with which ciphertext, with more than 50% certainty. I.e. you are given an infinite series of such challenges and offered even-odds bets on your answer. In the long run, you shouldn't be able to make money.
Yes, AES *should* be able to hold up even to that, but that's really placing all your eggs in one basket. If you can give it more help without weakening other parts, that's Good Design.
If I'm designing a protocol, I'll try to design it so that an attacker *doesn't* have access to such an oracle, or the responses are too slow to make billions of them, or asking more than a few dozen questions will raise alarms, or some such. I'll change keys so the time in which an attacker has to mount their attack is limited. I'll do any of a number of things which let the German navy keep half of their U-boat traffic out of the hands of Bletchley park even through they didn't know there were vast gaping holes in the underlying cipher.
Quoted 2 lines
The decision to place trust in a entropy estimation scheme vs. a crypto algorithm we have different views on. I can live with that.
Better crypto is fine. But why *throw out* the entropy estimation and rely *entirely* on the crypto? Feel free to argue that the crypto in Fortuna is better (although Ted is making some strong points that it *isn't*), but is it necessary to throw the baby out with the bathwater? Can't you get the best of both worlds?
Quoted 3 lines
I "completly and totally" agree. I'm pointing out that no added padding makes me, the new guy reading your code, work harder to decide if it's a weakness. You shouldn't do that to people if you can avoid it.
Sorry, but if you know enough to know why the padding is necessary, you should know when it isn't. Feel free to say "isn't this a weakness? I read in $BOOK that that padding was important to prevent some attacks" and propose a comment patch. But to say "this is crap because I don't understand one little detail and you should replace it with my shiny new 2005 model" when it's your ignorance and not a real problem is unbelievably arrogant.
Quoted 3 lines
Just like you shouldn't obfuscate code, even if it doesn't "weaken" its implementation. It's just rude. Take the performance penalty to avoid scaring people away from a very important peice of the kernel.
Tell it to the marines. I'd say "tell it to Linus", because he'll laugh louder, but his time is valuable to me.
Part of the Linux developer's credo, learned at Linus' knee, is that Performance Matters. If you don't worry about 5% all the time, after 15 revisions you've running at half speed and it's a lot of work to catch up.
The -mm guys have been doing backflips for years to try to get good paging behaviour without high run-time overhead. This is one of the major reasons why the kernel refuses to promise a stable binary interface to kernel modules. Rearranging the order of fields in a strucure for better cache performance is a minor revision.
In fact, large parts of /dev/random deliberately *don't* care about performance. The entire output mixing stage is not performance critical, and is deliberately slow.
What *is* critical is the input mixing stage, because that happens at interrupt time, and many many people care passionately about interrupt latency. And /dev/random wants to be non-optional, always there for people to use so they don't have to invent their own half-assed equivalent.
Quoted 7 lines
The quantitaive aspects of the two RNGs in question are not being discussed. It's the qualitative aspects we do not see eye to eye on. So I will no longer suggest replacing the status-quo. I'd like to submit a patch to let users chose at compile-time under Cryptographic options weither to drop in Fortuna.
Ted, can we leave it at this?
You're welcome to write the patch. But I have to warn you, if you hope to get it into the standard kernel rather than just have a separately maintained patch, you'll need to persuade Linus or someone he trusts (who in theis case is probably Ted) that your patch is
a) better in some way or another than the existing code, and
b) important enough to warrant the maintenance burden that having two sets of equivalent code imposes.
You're being offered a lot of clues. Please, take some.
Quoted 5 lines · On Sun, Sep 26, 2004 at 06:46:17AM -0000, [email protected] wrote:
Quoted 1 line
And I showed that the SHA-1 in
random.cnow can produce collisions.This, I do not recall. I must have missed it. Will you please show me two inputs that, when fed to the SHA-1 in
random.c, will produce identical output?
SHA-1 without padding, sure.
hash("a") = hash("a\0") = hash("a\0\0") = ...hash("b") = hash("b\0") = hash("b\0\0") = ...hash("c") = hash("c\0") = hash("c\0\0") = ...
I've failed in my attempt to present a good argument for Fortuna. Guess I'll just sit on this patch. Is this above a big issue? No because as you two pointed out the hash() uses full block sizes.
This is a trying thread for me to continue, by no fault of yours. I thought I made it very clear when I started that I saw *no* vulnerability in the current /dev/random. This did not prevent Ted and yourself to ignore this statement as immediately assume when I say "you could have done this better" to mean "ha! I've hax0rd your silly code, I'm l33t." - an infuriating blow to my professionalism. Then I simply follow that up with insult to injury by trying to clear up the whole mess and only making things worse.
Quoted 31 lines
Quoted 3 lines
Or did I misunderstand you? Were you just mentioning the weakened algorithms as a "what if they were more serious discoveries? Wouldn't be be nice if we didn't rely on them?" ?
Yes. And Fortuna's *only* layer of armor is the block cipher. Yes, it's a damn good layer of armor, but defense in depth sure helps.
That is NOT to say that lots of half-assed algorithms piled on top of each other makes good crypto, but if you can have a good primitive and *then* use it safely as well, that's better.
For example, AES is supposed to be resistant to adaptive chosen plaintext/ciphertext attacks. Suppose you are given two ciphertexts and two corresponding plaintexts, but not which corresponds to which. And then you are given access to an oracle which will, using the same key as was used on the plaintext/ciphertext pairs, give you the plaintext for any ciphertet that's not one of the two, and the ciphertext for any plaintext that's not one of the two. The orace can answer basically an infinite number of questions (well, 2^128-2) and you can look at one set of answers before posing the next.
AES is supposed to prevent you from figuring out, with all that help, which plaintext of the two goes with which ciphertext, with more than 50% certainty. I.e. you are given an infinite series of such challenges and offered even-odds bets on your answer. In the long run, you shouldn't be able to make money.
Yes, AES *should* be able to hold up even to that, but that's really placing all your eggs in one basket. If you can give it more help without weakening other parts, that's Good Design.
Quoted 8 lines
If I'm designing a protocol, I'll try to design it so that an attacker *doesn't* have access to such an oracle, or the responses are too slow to make billions of them, or asking more than a few dozen questions will raise alarms, or some such. I'll change keys so the time in which an attacker has to mount their attack is limited. I'll do any of a number of things which let the German navy keep half of their U-boat traffic out of the hands of Bletchley park even through they didn't know there were vast gaping holes in the underlying cipher.
If say, the key for the AES256-CTR layer changed after every block-read from /dev/random?
Quoted 8 lines
Quoted 2 lines
The decision to place trust in a entropy estimation scheme vs. a crypto algorithm we have different views on. I can live with that.
Better crypto is fine. But why *throw out* the entropy estimation and rely *entirely* on the crypto? Feel free to argue that the crypto in Fortuna is better (although Ted is making some strong points that it *isn't*), but is it necessary to throw the baby out with the bathwater? Can't you get the best of both worlds?
My past arguments for removing entropy estimation were hand-waving at best (rate of /dev/random output ~= rate of event sources' activity like keyboards, disks, etc). This could (not likely) lead to information about what the system is doing. If an attacker could open and close tcp ports, or ping an ethernet card to generate IRQs which are fed into the PRNG and increasing the entropy count - would this be usable in an attack? Not likely. Would you want to close-off this avenue of attack? Majority seems to say "no", but I personally would like to. And that is where my argument falls apart.
Quoted 11 lines
Quoted 3 lines
I "completly and totally" agree. I'm pointing out that no added padding makes me, the new guy reading your code, work harder to decide if it's a weakness. You shouldn't do that to people if you can avoid it.
Sorry, but if you know enough to know why the padding is necessary, you should know when it isn't. Feel free to say "isn't this a weakness? I read in $BOOK that that padding was important to prevent some attacks" and propose a comment patch. But to say "this is crap because I don't understand one little detail and you should replace it with my shiny new 2005 model" when it's your ignorance and not a real problem is unbelievably arrogant.
Sigh. Perhaps I need to be excruciatingly clear:
- SHA1-nopadding() is less secure than SHA1-withpadding()
- It doesn't apply to random.c
I though it was clear ... clearly I was delusional.
Quoted 10 lines
Quoted 3 lines
Just like you shouldn't obfuscate code, even if it doesn't "weaken" its implementation. It's just rude. Take the performance penalty to avoid scaring people away from a very important peice of the kernel.
Tell it to the marines. I'd say "tell it to Linus", because he'll laugh louder, but his time is valuable to me.
Part of the Linux developer's credo, learned at Linus' knee, is that Performance Matters. If you don't worry about 5% all the time, after 15 revisions you've running at half speed and it's a lot of work to catch up.
I see. And in the -mm examples, is the code easily readable for other os-MemMgt types? If no, then I guess random.c is not the exception and I apologize.
Quoted 5 lines
What *is* critical is the input mixing stage, because that happens at interrupt time, and many many people care passionately about interrupt latency. And
/dev/randomwants to be non-optional, always there for people to use so they don't have to invent their own half-assed equivalent.
And the ring-buffer system which delays the expensive mixing stages untill a a sort interrupt does a great job (current and my fortuna-patch). Different being, fortuna-patch appears to be 2x faster.
Quoted 16 lines
Quoted 7 lines
The quantitaive aspects of the two RNGs in question are not being discussed. It's the qualitative aspects we do not see eye to eye on. So I will no longer suggest replacing the status-quo. I'd like to submit a patch to let users chose at compile-time under Cryptographic options weither to drop in Fortuna.
Ted, can we leave it at this?
You're welcome to write the patch. But I have to warn you, if you hope to get it into the standard kernel rather than just have a separately maintained patch, you'll need to persuade Linus or someone he trusts (who in theis case is probably Ted) that your patch is
a) better in some way or another than the existing code, and
b) important enough to warrant the maintenance burden that having two sets of equivalent code imposes.
Quoted 1 line
You're being offered a lot of clues. Please, take some.
I appreciate the feedback for what it's worth. Thanks.
JLC
Quoted 3 lines
I was trying to point out a flaw in Ted's logic. He said "we've recently discoverd these hashes are weak because we found collsions. Current
/dev/randomdoesn't care about this."
And he's exactly right. The only attack that would be vaguely relevant to /dev/random's use would be a (first) preimage attack, and even that's probably not helpful.
There *is* no flaw in his logic. The attack we need to guard against is, given hash(x) and a (currently mostly linear) state mixing function mix(), one that would let you compute (partial information about) y[i+1] = hash(x[i+1]) from y[1] = hash(x[1]) ... y[i] = hash(x[i]) where x[i] = mix(x[i-1]).
Given that y[i] is much smaller than x[i], you'd need to put together a lot of them to derive something, and that's distinctly harder than a single-output preimage attack.
Quoted 4 lines
I certainly wasn't saying padding was a requirment. But I was trying to point out that the SHA-1 implementaion crrently in
/dev/randomby design is collision vulnerable. Collision resistance isn't a requirment for its purposes obviously.
No, it is, by design, 100% collision-resistant. An attacker neither sees nor controls the input x, so cannot use a collision attack. Thus, it's resistant to collisions in the same way that it's resistant to AIDS.
[There's actually a flaw in my logic. I know Ted knows about it, because he implemented a specific defense in the /dev/random code against it; it's just not 100% information-theoretic ironclad. If anyone else can spot it, award yourself a clue point. But it's still not a plausible attack.]
FURTHERMORE, even if an attacker *could* control the input, it's still exactly as collision resistant as unmodified SHA-1. Because it only accepts fixed-size input blocks, padding is unnecessary and irrelevant to security. Careful padding is ONLY required if you are working with VARIABLE-SIZED input.
The fact that collision resistance is not a security requirement is a third point.
Quoted 1 line
Guess my pointing this out is a lost cause.
In much the same way that pointing out that the earth is flat is a lost cause. If you want people to believe nonsense, you need to dress it up a lot and call it a religion.
As for Ted's words:
Quoted 4 lines
Whether or not we should trust the design of something as critical to the security of security applications as
/dev/randomto someone who fails to grasp the difference between these two rather basic issues is something I will leave to the others on LKML.
Fortuna may be a good idea after all (I disagree, but I can imagine being persuaded otherwise), but it has a very bad advocate right now. Would anyone else like to pick up the torch?
By the way, I'd like to repeat my earlier question: you say Fortuna ia well-regarded in crypto circles. Can you cite a single paper to back that conclusion? Name a single well-known cryptographer, other than the authors, who has looked at it in some detail?
There might be one, but I don't know of any. I respect the authors enough to know that even they recognize that an algorithm's designers sometimes have blind spots.
Team,
I have attempted to gather everyones comments into this re-write of my Fortuna /dev/random patch. I will summarize.
1. Requires the Cryptographic API.
2. Enable the Fortuna replacement to random.c in the Cryptographic Options menu
of kernel config.
3. As-is, it checks at compile time that AES and SHA256 are built-in modules.
4. You can change this block cipher and message digest setting in the
crypto/random-fortuna.c file. /proc/sys/kernel/random/digest_algo and cipher_algo are now strings telling the users what algorithms are being used.
5. Entropy estimation still exists in much the same way as in the Legacay
random.c with the following exceptions:
a. /proc/sys/kernel/random/read_wakeup_thresholds lower limit was 8, it is now
0 for those of us crazy enough to want to remove blocking.
b. /proc/sys/kernel/random/entropy_avail only increases when data is added to
pool-0. Pool-0 is the only 1 out of 32 Fortuna pools which is drawn from at every reseeding. So we don't over-estimate the amount of entropy we consume, this change was done.
c. Since Fortuna resists consuming its entropy, it seemed inappropriate to debit
1MB of entropy from the count when reading 1MB from /dev/urandom. Now, every reseeding deducts min(cipherKeySize, hashDigestSize) from the entropy count. It should be noted that by doubling the blocksize from which you read /dev/urandom, you double the speed since you reduce the number of reseeds by a half.
6. The input mixing and output generation functions now use Fortuna
a. 32 independent feedback input mixing pools using a cryptographic hash from the
CryptoAPI are feed event data in round robin.
b. A block cipher in CTR mode generates the output.
c. Every file system block read from /dev/{u}random causes Fortuna to reseed
the block cipher's key with the digest output from 1 or more of the input mixing pools. Pool-0 is used every time, pool-j is used every 2^j times.
7. Since Fortuna resists consuming its entropy, saving the 2048 byte random-seed
should be changed to: dd if=/dev/urandom of=$seedfile bs=256 count=8. After 2^3 = 8 block reads, pools 0, 1, 2, and 3 will certainly be used. After 2^4 = 16, pools up to number 4 will be used and so on.
8. The difference in bzImage size is 7,268 bytes on my P4 laptop. This is a
compressed image. My comparison was the 2.6.8.1 tarball with no kernel config changes vs. Enabling the cryptoapi, Fortuna, AES (i586 assembly) and SHA256. I have not yet done run-time memory consumption comparisons, but Fortuna is certainly heavier than Legacy.
9. The difference in performance in /dev/random is roughly a 32x decrease in
output rates due to the 32x decrease in entropy estimation (see 5.c)
10. The difference in performance in /dev/urandom is 3x increase in output rates
for a 512 byte block size. A doubling in block size, doubles the performance. I produced 512,000,000 bytes of output with a 32k block size in less than 10 seconds. The legacy /dev/urandom by comparison accomplished the same thing in 2.5 minutes. The assembly version of AES for the i586 gets credit for this.
I tried to test the syn-cookie code but was unable to determine if it works. Printk()s in the syn cookie generation function were never called even though I echod 1 to the proc file. If someone can tell me what Im going wrong, I'd love to test this further.
I'd appreciate beta-testers on other platforms to provide feedback.
JLC
crypto/Kconfig +9 -0
@@ -9,6 +9,15 @@ help This option provides the core Cryptographic API. +config CRYPTO_RANDOM_FORTUNA + bool "The Fortuna RNG" + help + Replaces the legacy Linux RNG with one using the crypto API + and Fortuna by Ferguson and Schneier. Entropy estimation, and + a throttled /dev/random remain. Improvements include faster + /dev/urandom output and event input mixing. + Note: Requires AES and SHA256 to be built-in. + config CRYPTO_HMAC bool "HMAC support" depends on CRYPTO
crypto/random-fortuna.c +2027 -0
2,027 lines not on this page · raw message
drivers/char/random.c +13 -0
@@ -261,6 +261,17 @@#include <asm/io.h> /* +* In September 2004, Jean-Luc Cooke wrote a Fortuna RNG for Linux +* which was non-blocking and used the Cryptographic API. +* We use it now if the user wishes. +*/ +#ifdef CONFIG_CRYPTO_RANDOM_FORTUNA +#warning using the Fortuna PRNG for /dev/random +#include "../crypto/random-fortuna.c" +#else /* CONFIG_CRYPTO_RANDOM_FORTUNA */ +#warning using the Linux Legacy PRNG for /dev/random + +/* * Configuration information */ #define DEFAULT_POOL_SIZE 512
@@ -2483,3 +2494,5 @@return (cookie - tmp[17 ]) &COOKIEMASK ;/* Leaving the data behind */ }#endif + +#endif /* CONFIG_CRYPTO_RANDOM_FORTUNA */
include/linux/sysctl.h +3 -1
@@ -198,7 +198,9 @@RANDOM_READ_THRESH =3 ,RANDOM_WRITE_THRESH =4 ,RANDOM_BOOT_ID =5 , - RANDOM_UUID=6 +RANDOM_UUID =6 , +RANDOM_DIGEST_ALGO =7 , + RANDOM_CIPHER_ALGO=8 };/* /proc/sys/kernel/pty */
Theodore Ts'o
maintainerWhile addition of the entropy estimator helps protect the Fortuna Random number generator against a state extension attack, /dev/urandom is using the same entropy extraction routine as /dev/random, and so Fortuna is still vulernable to state extension attacks. This is because a key aspect of the Fortuna design has been ignored in JLC's implementation.
This missing piece to assure that a rekey can only take place when there has been sufficient entropy built up in the higher order pools in order to assure a catastrophic rekey. Otherwise, the attacker can simply brute force a wide variety of entropy inputs from the hardware, and see if any of them matches output from the /dev/urandom (from which the attacker is continuously pulling output). So in the original design, the rekey from a higher order pool only takes place after k*2^n seconds, where n is the order of the pool, and k is some constant. The idea is that after some period of time hopefully one of the pools has built up at least 128 bits or so worth of entropy, and so the catastrophic reseeding will prevent an attacker from trying all possible inputs and determining the state of the pool. (Neils recommends that k be at least a tenth of a second; see pages 38-40 of
http://th.informatik.uni-mannheim.de/people/lucks/papers/Ferguson/Fortuna.pdf).
Unfortunately, Fortuna will call random_reseed() after every single read from /dev/urandom. This is not time-limited at all, so as long as the attacker can call /dev/urandom fast enough, it can continue to monitor the various higher-level pools. This can be fixed easily by simply changing the rekey function so that it only attempts a reseed after some period of time has gone by.
There is of course the question of whether a state extension attack is realistic. After all, most attacks where the attacker as sufficient privileges to obtain the complete state of the RNG is also one where the attacker also has enough privileges to install a rootkit, or compromise the kernel by loading a hostile loadable kernel module, etc. Also, there is the question about whether an attacker could read sufficient amounts of to keep track of the the contents of the pool, and whether the attacker can either do the brute-forcing on the local machine, or send the large amounts of information read from /dev/urandom to an outside machine, without using enough CPU time that it would be noticed by a system administrator ---- but then again, the Crypto academics that are worried about things like state extension attacks aren't worried about practical niceties. But then again, if we decide that state extension attacks aren't practically possible, or otherwise not worthy of concern, or if JLC's Fortuna implementation is vulnerable to state extension attacks, there's no reason to use JLC's implementation in the first place.
- Ted
Why would we want to miss that when so much effort was made to meet the requirements of the traditional /dev/random? So...
Here's patch v2.1.2 that waits at least 0.1 sec before reseeding for non-blocking reads to alleviate Ted's concern wrt waiting for reseeds.
When reading nbytes from /dev/{u}random, Legacy /dev/random would:
- Mix nbytes of data from primary pool into secondary pool
- Then generate nbytes from secondary pool
When reading nbytes from /dev/{u}random, Fortuna-patch /dev/random would:
- Mix ??? of data from input pools into the AES key for output generation
- Then generate nbytes from AES256-CTR
Perhaps I miss the subtlety of the difference in terms of security. If nbytes >= size of both pools - wouldn't Legacy also be vulnerable to the same attack?
JLC
Quoted 6 lines · Theodore Ts'o
While addition of the entropy estimator helps protect the Fortuna Random number generator against a state extension attack,
/dev/urandomis using the same entropy extraction routine as/dev/random, and so Fortuna is still vulernable to state extension attacks. This is because a key aspect of the Fortuna design has been ignored in JLC's implementation.
Theodore Ts'o
maintainerQuoted 5 lines · Jean-Luc Cooke
When reading nbytes from
/dev/{u}random, Legacy/dev/randomwould:
- Mix nbytes of data from primary pool into secondary pool
- Then generate nbytes from secondary pool
Quoted 7 lines
When reading nbytes from
/dev/{u}random, Fortuna-patch/dev/randomwould:
- Mix ??? of data from input pools into the AES key for output generation
- Then generate nbytes from AES256-CTRPerhaps I miss the subtlety of the difference in terms of security. If nbytes >= size of both pools - wouldn't Legacy also be vulnerable to the same attack?
Sure, but the Fortuna is supposed to be "more secure" because it resists the state extension attack. I don't think the state extension attack is at all realistic, for the reasons cited above. But if your implementation doesn't resist the state extension attack, then why bloat the kernel with an alternate random algorithm that's no better as far as security is concerned? (And is more heavy weight, and is more wasteful with its entropy, etc., etc.?)
- Ted
P.S. I'll also note by the way, that in more recent versions of /dev/random, we use a separate pool for /dev/urandom and /dev/random. A further enhancement which I'm thinking might be a good one to add is to limit the rate at which we transfer randomness from the primary pool to the urandom pool. So that it's not that I'm against making changes; it's just that I want the changes to make sense, and protect against realistic threats, not imaginary ones.
Theodore Ts'o
maintainerQuoted 3 lines · Jean-Luc Cooke
Here's patch v2.1.2 that waits at least 0.1 sec before reseeding for non-blocking reads to alleviate Ted's concern wrt waiting for reseeds.
You didn't include the patch, and in any case, you'll probably want to probably want to do it for both blocking as well as non-blocking reads. And keep in mind, it's not *my* concerns, but it's Neil Ferguson and Bruce Schneier's concerns. After all, if you're going to call it Fortuna, you might as well be faithful to their design, especially since if you don't, you're leaving it to be utterly vulnerable to this state extension attack they are so worried about.
- Ted
Oops! my bad. Attached here along with a few other changes. I'm running a change log now at the top of the random-fortuna.c file.
Being 100% faithful to their designs would require such constructions as each event source would hold its own pool index pointer, right now event collection is separated from event mixing for API and performance reasons.
Trying to find solace and more articulate advise I've sat down with Practical Crypto again reviewed the state compromise-extension attack recovery section.
If copyright laws smile on me, I'll quote section 10.5.2 starting at chapter 6 on page 170 of the soft-cover print.
-- start quote --
The speed at which the system recovers from a compromised state depends on the rate at which entropy (with respect to the attacker) flaws into the pools. If we assume that this is a fixed rate R, then after t seconds we have in total R*t bits of entropy. Each pool receives about R*t/32 bits in this time period. The attacker can no longer keep track of the state if the generator is reseeded with a pool with more then 128 bits of entropy in it. There are two cases. If pool P_0 collects 128 bits of entropy before the next reseed operation, then we have recovered from the compromise. How fast this happens depends on how large we let P_0 grow before we reseed. The second case is when P_0 is reseeding too fast, due to random events unknown to (or generated by) the attacker. Let t be the time between reseeds. Then pool P_i collects 2^i*R*t/32 bits of entropy between reseeds, and is used in a reseed every 2^i*t seconds. The recovery from the compromise happens the first time we reseed with pool P_i where 128 <= 2^i*R*t < 256. (The upper bound derives from the fact that otherwise pool P_{i-1} would contain 128 bits of entropy between reseeds.) This inequality gives us
2^i * R * t
----------- < 256
32
and thus
8192
2^i * t < ----
R
In other words, the time between recovery points (2^i*t) is bounded by the time it takes to collect 2^13 bits of entropy (8192 / R). The number 2^13 seems a bit large, but it can be explained in the following way. We need at least 2^7 bits to recover from a compromise. We might be unlucky if the system reseeds just before we have collected 2^7 bits in a particular pool, and then we have to use the next pool, which collect close to 2^8 bits before the reseed. Finally, we divide our data over 32 pools, which accounts for another factor of 2^5.
This is a very good result. The solution is within a factor of 64 of an ideal solution (it needs at most 64 times as much randomness as an ideal solution would need). The is a constant factor and it ensures that we can never do terribly badly, and will always recover eventually. Furthermore, we do not need to know how much entropy out events have or how much the attacker knows. That is the real advantage Fortuna has over Yarrow. The impossible-to-construct entropy estimators are gone for good. Everything is fully automatic; if there is a good flow of random data, the PRNG will recover quickly. If there is only a trickle of random data, it takes a long time to recover.
-- end quote --
Hopefully the above quote from the book will be interpreted as free advertising and not theft.
Quoted 14 lines · Theodore Ts'o
Quoted 3 lines · Jean-Luc Cooke
Here's patch v2.1.2 that waits at least 0.1 sec before reseeding for non-blocking reads to alleviate Ted's concern wrt waiting for reseeds.
You didn't include the patch, and in any case, you'll probably want to probably want to do it for both blocking as well as non-blocking reads. And keep in mind, it's not *my* concerns, but it's Neil Ferguson and Bruce Schneier's concerns. After all, if you're going to call it Fortuna, you might as well be faithful to their design, especially since if you don't, you're leaving it to be utterly vulnerable to this state extension attack they are so worried about.
- Ted
Damn,
Need to eat me some brain-food.
JLC
Quoted 13 lines · Theodore Ts'o
Quoted 3 lines · Jean-Luc Cooke
Here's patch v2.1.2 that waits at least 0.1 sec before reseeding for non-blocking reads to alleviate Ted's concern wrt waiting for reseeds.
You didn't include the patch, and in any case, you'll probably want to probably want to do it for both blocking as well as non-blocking reads. And keep in mind, it's not *my* concerns, but it's Neil Ferguson and Bruce Schneier's concerns. After all, if you're going to call it Fortuna, you might as well be faithful to their design, especially since if you don't, you're leaving it to be utterly vulnerable to this state extension attack they are so worried about.
Quoted 5 lines
- Ted
_______________________________________________Subscription: http://lists.logix.cz/mailman/listinfo/cryptoapi
List archive: http://lists.logix.cz/pipermail/cryptoapi
crypto/Kconfig +9 -0
@@ -9,6 +9,15 @@ help This option provides the core Cryptographic API. +config CRYPTO_RANDOM_FORTUNA + bool "The Fortuna RNG" + help + Replaces the legacy Linux RNG with one using the crypto API + and Fortuna by Ferguson and Schneier. Entropy estimation, and + a throttled /dev/random remain. Improvements include faster + /dev/urandom output and event input mixing. + Note: Requires AES and SHA256 to be built-in. + config CRYPTO_HMAC bool "HMAC support" depends on CRYPTO
crypto/random-fortuna.c +2100 -0
2,100 lines not on this page · raw message
drivers/char/random.c +13 -0
@@ -261,6 +261,17 @@#include <asm/io.h> /* +* In September 2004, Jean-Luc Cooke wrote a Fortuna RNG for Linux +* which was non-blocking and used the Cryptographic API. +* We use it now if the user wishes. +*/ +#ifdef CONFIG_CRYPTO_RANDOM_FORTUNA +#warning using the Fortuna PRNG for /dev/random +#include "../crypto/random-fortuna.c" +#else /* CONFIG_CRYPTO_RANDOM_FORTUNA */ +#warning using the Linux Legacy PRNG for /dev/random + +/* * Configuration information */ #define DEFAULT_POOL_SIZE 512
@@ -2483,3 +2494,5 @@return (cookie - tmp[17 ]) &COOKIEMASK ;/* Leaving the data behind */ }#endif + +#endif /* CONFIG_CRYPTO_RANDOM_FORTUNA */
include/linux/sysctl.h +3 -1
@@ -198,7 +198,9 @@RANDOM_READ_THRESH =3 ,RANDOM_WRITE_THRESH =4 ,RANDOM_BOOT_ID =5 , - RANDOM_UUID=6 +RANDOM_UUID =6 , +RANDOM_DIGEST_ALGO =7 , + RANDOM_CIPHER_ALGO=8 };/* /proc/sys/kernel/pty */
This should be the last one for a while.
v2.1.4 crypto/random-fortuna.c
Ted, since this is a crypto-API feature as well as an optional replacement to /dev/random, should I be passing this threw James or both of you?
Cheers,
JLC
Quoted 5 lines · Jean-Luc Cooke
Damn,
Need to eat me some brain-food.
JLC
crypto/Kconfig +9 -0
@@ -9,6 +9,15 @@ help This option provides the core Cryptographic API. +config CRYPTO_RANDOM_FORTUNA + bool "The Fortuna RNG" + help + Replaces the legacy Linux RNG with one using the crypto API + and Fortuna by Ferguson and Schneier. Entropy estimation, and + a throttled /dev/random remain. Improvements include faster + /dev/urandom output and event input mixing. + Note: Requires AES and SHA256 to be built-in. + config CRYPTO_HMAC bool "HMAC support" depends on CRYPTO
crypto/random-fortuna.c +2092 -0
2,092 lines not on this page · raw message
drivers/char/random.c +13 -0
@@ -261,6 +261,17 @@#include <asm/io.h> /* +* In September 2004, Jean-Luc Cooke wrote a Fortuna RNG for Linux +* which was non-blocking and used the Cryptographic API. +* We use it now if the user wishes. +*/ +#ifdef CONFIG_CRYPTO_RANDOM_FORTUNA +#warning using the Fortuna PRNG for /dev/random +#include "../crypto/random-fortuna.c" +#else /* CONFIG_CRYPTO_RANDOM_FORTUNA */ +#warning using the Linux Legacy PRNG for /dev/random + +/* * Configuration information */ #define DEFAULT_POOL_SIZE 512
@@ -2483,3 +2494,5 @@return (cookie - tmp[17 ]) &COOKIEMASK ;/* Leaving the data behind */ }#endif + +#endif /* CONFIG_CRYPTO_RANDOM_FORTUNA */
include/linux/sysctl.h +3 -1
@@ -198,7 +198,9 @@RANDOM_READ_THRESH =3 ,RANDOM_WRITE_THRESH =4 ,RANDOM_BOOT_ID =5 , - RANDOM_UUID=6 +RANDOM_UUID =6 , +RANDOM_DIGEST_ALGO =7 , + RANDOM_CIPHER_ALGO=8 };/* /proc/sys/kernel/pty */
Quoted 6 lines · Jean-Luc Cooke
This should be the last one for a while.
v2.1.4
crypto/random-fortuna.cTed, since this is a crypto-API feature as well as an optional replacement to
/dev/random, should I be passing this threw James or both of you?
Whatever the case, I would follow Ted's advice on this code.
- James
Signature · 2 lines
James Morris <[email protected]>
Quoted 1 line · Jean-Luc Cooke
<fortuna-2.6.8.1.patch>
You said AES and SHA-256 _must_ be built-in, but I can't see any code on your patch that enforces selection of those config options. Thus, it's possible to compile the kernel when CONFIG_CRYPTO_SHA256=n and CONFIG_CRYPTO_AES=n although, of course, it will fail.
In the random-fortuna.c file I have some "#if !defined CONFIG_CRYPTO_SHA256"
As Jan-Benedict Glaw pointed out, I could just manually select the algorithms, which is what I did.
Updated patch, only changes are to crypto/Kconfig.
Cheers,
JLC
Quoted 8 lines · Felipe Alfaro Solana
Quoted 1 line · Jean-Luc Cooke
<fortuna-2.6.8.1.patch>
You said AES and SHA-256 _must_ be built-in, but I can't see any code on your patch that enforces selection of those config options. Thus, it's possible to compile the kernel when
CONFIG_CRYPTO_SHA256=nandCONFIG_CRYPTO_AES=nalthough, of course, it will fail.
crypto/Kconfig 2004-09-30 09:33:39.775410632 -0400 renamed from crypto/Kconfig 2004-08-14 06:56:22.000000000 -0400 +11 -0
@@ -9,6 +9,17 @@ help This option provides the core Cryptographic API. +config CRYPTO_RANDOM_FORTUNA + bool "The Fortuna RNG" + select CRYPTO_SHA256 + select CRYPTO_AES + help + Replaces the legacy Linux RNG with one using the crypto API + and Fortuna by Ferguson and Schneier. Entropy estimation, and + a throttled /dev/random remain. Improvements include faster + /dev/urandom output and event input mixing. + Note: Requires AES and SHA256 to be built-in. + config CRYPTO_HMAC bool "HMAC support" depends on CRYPTO
crypto/random-fortuna.c +2092 -0
2,092 lines not on this page · raw message
drivers/char/random.c +13 -0
@@ -261,6 +261,17 @@#include <asm/io.h> /* +* In September 2004, Jean-Luc Cooke wrote a Fortuna RNG for Linux +* which was non-blocking and used the Cryptographic API. +* We use it now if the user wishes. +*/ +#ifdef CONFIG_CRYPTO_RANDOM_FORTUNA +#warning using the Fortuna PRNG for /dev/random +#include "../crypto/random-fortuna.c" +#else /* CONFIG_CRYPTO_RANDOM_FORTUNA */ +#warning using the Linux Legacy PRNG for /dev/random + +/* * Configuration information */ #define DEFAULT_POOL_SIZE 512
@@ -2483,3 +2494,5 @@return (cookie - tmp[17 ]) &COOKIEMASK ;/* Leaving the data behind */ }#endif + +#endif /* CONFIG_CRYPTO_RANDOM_FORTUNA */
include/linux/sysctl.h +3 -1
@@ -198,7 +198,9 @@RANDOM_READ_THRESH =3 ,RANDOM_WRITE_THRESH =4 ,RANDOM_BOOT_ID =5 , - RANDOM_UUID=6 +RANDOM_UUID =6 , +RANDOM_DIGEST_ALGO =7 , + RANDOM_CIPHER_ALGO=8 };/* /proc/sys/kernel/pty */
Chris Han pointed out that my #include of "random-fortuna.c" could be done much cleaner if the drivers/char/Makefile had some ifeq-else-endif logic in it. He also pointed our my #include of crypto/internal.h was not needed anymore.
Here is an update. v2.1.5 1-Oct-2004
JLC
Quoted 5 lines · Jean-Luc Cooke
In the
random-fortuna.cfile I have some "#if !definedCONFIG_CRYPTO_SHA256"As Jan-Benedict Glaw pointed out, I could just manually select the algorithms, which is what I did.
Quoted 15 lines
Updated patch, only changes are to
crypto/Kconfig.Cheers,
JLC
Quoted 8 lines · Felipe Alfaro Solana
Quoted 1 line · Jean-Luc Cooke
<fortuna-2.6.8.1.patch>
You said AES and SHA-256 _must_ be built-in, but I can't see any code on your patch that enforces selection of those config options. Thus, it's possible to compile the kernel when
CONFIG_CRYPTO_SHA256=nandCONFIG_CRYPTO_AES=nalthough, of course, it will fail.
crypto/Kconfig 2004-09-30 09:33:39.775410632 -0400 renamed from crypto/Kconfig 2004-08-14 06:56:22.000000000 -0400 +11 -0
@@ -9,6 +9,17 @@ help This option provides the core Cryptographic API. +config CRYPTO_RANDOM_FORTUNA + bool "The Fortuna RNG" + select CRYPTO_SHA256 + select CRYPTO_AES + help + Replaces the legacy Linux RNG with one using the crypto API + and Fortuna by Ferguson and Schneier. Entropy estimation, and + a throttled /dev/random remain. Improvements include faster + /dev/urandom output and event input mixing. + Note: Requires AES and SHA256 to be built-in. + config CRYPTO_HMAC bool "HMAC support" depends on CRYPTO
include/linux/sysctl.h +3 -1
@@ -198,7 +198,9 @@RANDOM_READ_THRESH =3 ,RANDOM_WRITE_THRESH =4 ,RANDOM_BOOT_ID =5 , - RANDOM_UUID=6 +RANDOM_UUID =6 , +RANDOM_DIGEST_ALGO =7 , + RANDOM_CIPHER_ALGO=8 };/* /proc/sys/kernel/pty */
drivers/char/Makefile +7 -1
@@ -7,7 +7,13 @@ # FONTMAPFILE = cp437.uni -obj-y += mem.o random.o tty_io.o n_tty.o tty_ioctl.o pty.o misc.o +obj-y += mem.o +ifeq ($(CONFIG_CRYPTO_RANDOM_FORTUNA),y) + obj-y += random-fortuna.o + else + obj-y += random.o +endif +obj-y += tty_io.o n_tty.o tty_ioctl.o pty.o misc.o obj-$(CONFIG_VT) += vt_ioctl.o vc_screen.o consolemap.o \ consolemap_deftbl.o selection.o keyboard.o
drivers/char/random-fortuna.c +2094 -0
2,094 lines not on this page · raw message
On Thu, 2004-09-30 00:23:03 -0400, Jean-Luc Cooke <[email protected]> wrote in message <[email protected]>:
Quoted 7 lines
crypto/Kconfig +1
-0@@ -9,6 +9,15 @@ help This option provides the core Cryptographic API. +config CRYPTO_RANDOM_FORTUNA
crypto/Kconfig line 22
Quoted 10 lines
crypto/Kconfig +8
-0+ bool "The Fortuna RNG" + help + Replaces the legacy Linux RNG with one using the crypto API + and Fortuna by Ferguson and Schneier. Entropy estimation, and + a throttled /dev/random remain. Improvements include faster + /dev/urandom output and event input mixing. + Note: Requires AES and SHA256 to be built-in. + config CRYPTO_HMAC bool "HMAC support"
Instead of mentioning AES and SHA256 being required built-in, why not just "select" them?
MfG, JBG
Signature · 4 lines
Jan-Benedict Glaw [email protected] . +49-172-7608481 _ O _ "Eine Freie Meinung in einem Freien Kopf | Gegen Zensur | Gegen Krieg _ _ O fuer einen Freien Staat voll Freier Bürger" | im Internet! | im Irak! O O O ret = do_actions((curr | FREE_SPEECH) & ~(NEW_COPYRIGHT_LAW | DRM | TCPA));