At 1:49 PM -0700 7/25/99, David Wagner wrote:
>In article <v04011700b3c0b0807cfc@[24.218.56.100]>,
>Arnold G. Reinhold <[EMAIL PROTECTED]> wrote:
>> One nice advantage of using RC4 as a nonce generator is that you can easily
>> switch back and forth between key setup and code byte generation. You can
>> even do both at the same time. (There is no need to reset the index
>> variables.) This allows you to intersperse entropy deposits and withdrawals
>> at will.
>
>Oh dear! This suggestion worries me.
>Is it reasonable to expect this arrangement to be secure
>against e.g. chosen-entropy attacks? [John Kelsey makes the same point]
You raise a good question, but I think I can demonstrate that it is safe.
Here is the inner loop of the algorithm I am proposing in its most extreme
case: generating cipher bytes and accepting entropy at the same time.
(using Bruce Schneier's notation from Applied Cryptography, 2nd ed.):
i = i + 1 mod 256
j = j + S[i] + K[n] mod 256
swap S[i] and S[j]
t = S[i] + S[j] mod 256
next cipher byte = S[t]
Here K[n] is the next byte of entropy.
Note that RC4 code generation is exactly the same except that K[n] = 0 for
all n.
Assume an attacker initially does not know the state of the S array or the
value of j (you used 256 bytes of strong entropy as your initial RC4 key
and then discarded the next 256 cipher bytes like your mama taught you),but
does know i. (The attacker has been counting, knows the length of your
initial key setup and was able to shut out all other activity.) Also
assume the attacker gets to choose each K[n] and then gets to see each
cipher byte.
If you look at the last two lines of the loop, you can see that the
attacker needs to know something about the new value of j to learn any
information about the state of the S array from a cipher byte. Now focus
on the second line of the algorithm. To know anything about the new value
of j, he needs to know something about the old value of j AND something
about the value of S[i]. By assumption he knows neither. Therefore he
learns nothing about the new value of j and thus nothing about the state of
the S array.
Since addition mod 256 is a group, being able to choose K is no more
helpful in learning the new value of j than knowing K's value, which you
always know during code generation in RC4 (it's zero, as pointed out
above). You might think there could be a special situation that you could
wait for where you can use your ability to pick K to keep RC4 in a small
loop, but step 1 insures that a new S[i] is brought into the calculations
each time.
I believe this shows that adding entropy as you go, even if it might be
chosen by an attacker, is no more risky than a known plaintext attack
against vanilla RC4.
Of course in the original situation I proposed, the attacker could at best
choose only some of the entropy added.
For extra insurance, someone using RC4 as a nonce generator might want to
discard a random number (>256) of cipherbytes after the initial key setup.
This would deny an attacker any knowledge of the value of i beforehand.
Also, generating nonces and adding entropy in separate operations, which is
the natural thing to do from a programming perspective, results in
additional mixing and further complicates the problem for an attacker.
At 11:55 PM -0500 7/25/99, John Kelsey wrote:
>
>>[Arnold R] In particular, if you deposit the time of each entropy
>>withdrawal, the proposed denial of service attack that
>>started this thread would actually replenish a few bits of
>>entropy with each service request.
>
>[John K] This isn't a bad idea, but I'd be careful about assuming
>that those times hold much entropy. After all, a given
>piece of code which has thirty calls to the PRNG probably
>runs in about the same amount of time every time, barring
>disk or network I/O.
>
I was careful to say a "a few bits of entropy with each service request."
The service requests I was refering to were the attacker's attempt to set
up an IPsec tunnel. These involve network traffic and so can be expected to
generate some entropy. Here is John Denker's <[EMAIL PROTECTED]>
original description of the attack:
>Step 1) Suppose some as-yet unknown person (the "applicant") contacts
>Whitney and applies for an IPsec tunnel to be set up. The good part is that
>at some point Whitney tries to authenticate the Diffie-Hellman exchange (in
>conformance with RFC2409 section 5) and fails, because this applicant is an
>attacker and is not on our list of people to whom we provide service. The
>bad part is that Whitney has already gobbled up quite a few bits of entropy
>from /dev/random before the slightest bit of authentication is attempted.
>
>Step 2) The attacker endlessly iterates step 1. This is easy. AFAIK there
>is no useful limit on how often new applications can be made. This quickly
>exhausts the entropy pool on Whitney.
>
>Step 3a) If Whitney is getting key material from /dev/random, the result is
>a denial of service. All the IPsec tunnels will time out and will be
>replaced slowly or not at all, because of the entropy shortage.
My quick reading of RFC2409 Sec. 5, Main Mode, suggests that several
messages are exchanged before a request is denied, so there should be more
than a few bits of entropy, but even a few bits are enough to radically
change RC4's output stream.
Arnold Reinhold
