John Kelsey
Wed, 28 Jul 1999 18:25:32 -0700
-----BEGIN PGP SIGNED MESSAGE----- [ To: Perry's Crypto List, Bram, James, Dave ## Date: 07/28/99 ## Subject: Re: depleting the random number generator ] >Date: Mon, 26 Jul 1999 11:16:54 -0700 >To: bram <[EMAIL PROTECTED]> >From: "James A. Donald" <[EMAIL PROTECTED]> >Subject: Re: depleting the random number generator >Cc: David Wagner <[EMAIL PROTECTED]>, [EMAIL PROTECTED] >At 1018 AM 7/26/99 -0700, bram wrote >> The threat model for yarrow and other SRNG's is that the >> attacker can not only tell when entropy is coming in, but >> control it's contents as well. >The assumption was that entropy was the time of arrival. >Even if the attacker has control over the entropy added to >the RC4 state, this cannot give him any additional >information about the state of the RC4 generator. I think we're talking about different things, here. I will agree with you that if you take a totally unknown, pristine, RC4 state, and then apply the RC4 key schedule to it with bytes I get to choose, I will learn nothing about the resulting RC4 state. This is just another way of saying that multiplying an unknown permutation by a known one yields an unknown permutation, right? But the problem is a little different. In normal use, RC4 is keyed, and then is used to generate (say) a few million bytes of keystream. An attacker might be able to retrieve these bytes of keystream, and might try to recover the key, or some information about the RC4 state, at some point during the encryption. (Since RC4 is reversible, knowing the state at any point lets you learn the state at all other points in the keystream.) In this kind of use, the attacker gets to observe outputs, and then choose inputs, and then observe some more outputs, and then choose some more inputs, etc. The attacker is in an *enormously* more powerful situation here than in attacking the normal RC4. Now, right off the top of my head, I don't have an attack on RC4 under these circumstances. But since essentially nobody has looked at RC4 under these circumstances, it would be foolish to design a system that assumed no such attacks existed. [ Some stuff deleted. ] >> The idea is to build something which only fails if the >> attacker both knows the state of the pool at some point and >> manages to control all attempted reseedings. >An RC4 state fulfills this requirement, plus if we reseed >from the time of arrival of packets, the attacker cannot >control all incoming packets, thus even if at some point he >knows the state of the pool, that knowledge will soon be >lost. No, this ignores the iterative guessing attack: a. I know your RC4 state, maybe because your program started out with insufficient entropy. b. You output a few bytes as a nonce or something. I verify that it matches with my knowledge of your state. It does, so I do nothing else. c. You receive a packet whose precise arrival time I don't know, but which I can restrict to only a few hundred possibilities. d. You output a few bytes from your RC4 state as a nonce or something. e. I see that these bytes don't agree with my model, and so try guessing the inputs to the RC4 state until they do agree. When I guess the right value, I learn your new state. At this point, the entropy from that packet has given you no benefit. You can repeat steps c-e many, many times, feeding thousands of bits of entropy into your RC4 state, while still leaving an attacker with complete knowledge of that state. Since he only has to guess a few bits at a time, he never has to face an impossibly large guess. This is like having a good passphrase that is hashed one letter at a time, and all the intermediate hashes are stored. Even a really good passphrase would be trivial to ``guess,'' given this information. There are only two reasons to add entropy to a PRNG once you believe you have a secure state: a. You think that your generator might not have a long enough cycle length or might not be secure for arbitrarily long output sequences, and thus use entropy-bearing inputs to sort-of rekey it. You want to ensure that your PRNG's generator doesn't have to output so many bits that some statistical flaw shows through or something. b. You are concerned with some kind of state compromise, most likely from starting up with insufficient entropy. You want to ensure that your PRNG eventually has a chance to recover from such a compromise. Note that these are the *only* reasons to collect and feed in entropy. Otherwise, once you have a secure state, why bother? It allows an attacker to send in inputs, which is one more thing you have to worry about, and it doesn't do any good otherwise. If you're going to bother to add in entropy, then you need to do it in such a way that you actually recover from key compromises and defend against short cycles and such. The best way to do this is probably something like keeping your entropy inputs in a hashing context, and then rekeying your RC4 context with the hash output, once you're convinced you've collected enough entropy. Naturally, there are about a hundred other engineering issues there, like how you estimate the amount of entropy you're collecting, specifically how you rekey RC4, etc. The other issue with RC4 is that there are small statistical flaws in its output sequence. Golic found some of these, which were published at Eurocrypt a couple of years ago; previously, someone (Roos? Jenkins?) found that pairs of the same output byte appear either too commonly or too rarely. Neither of these have any impact to speak of on its usefulness as a stream cipher, but in rare instances, may have some impact on its usefulness as a PRNG. (For example, there are some protocols in which the random numbers used must be truly indistinguishable from random numbers.) That clearly isn't the case for the application being discussed here, though. >--digsig > James A. Donald - --John Kelsey, Counterpane Internet Security, [EMAIL PROTECTED] NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF -----BEGIN PGP SIGNATURE----- Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com> iQCVAwUBN5+hjCZv+/Ry/LrBAQEmtQP9GNYcnB/kkX9qWRc1WqXa6fejtuRLCspK VBIV9xgXTwt/Gdg6XNkBozB7zlMjstyXIvBBapkdPaaWkR6En1pn8J+pGGJOPNdy y3W3ue2RJqVLrggEcbD9l01lNal5JRFtIRtOEgs0VMTkDIiSUzr9ZRmlXnUjNcBr YfByDYDKrCg= =NvHc -----END PGP SIGNATURE-----