On Thu, Feb 03, 2000 at 12:19:57AM -0800, Bill Stewart wrote:
> At 09:15 AM 02/02/2000 -0800, Eric Murray wrote:
> >Until Intel releases the design for the RNG, I would treat it the same
> >as any suspect source of entropy- assume that it can contain no
> >entropy. That means that you whiten its output before mixing it
> >together with your other entropy sources (some of which you beleive do
> >provide real entropy) to provide random numbers.
>
> Doesn't this add one more level of isolation than you really need?
> I'm reading your statement "whiten before mixing" as
> pool = hash1( pool, hash2(intelrng) )
> as opposed to the presumably-safe-enough
> pool = hash1( pool, intelrng )
> which mixes in the raw intelrng rather than whitening.
> (Hash1 is abstractly whatever complex mixing process you've got,
> including keys, multiple entropy sources, etc.)
>
> Do you think there are attacks where this is really necessary,
> assuming the pool is used in some hashed fashion rather than
> exposed to the public directly?
It's probably overkill. I didn't want to get sidetracked into an
argument about how far down different RNG pools hash their input
or about how much source was taken from the Intel RNG vs other sources.
And if you really didn't trust the output but thought there was
still some real entropy there, that'd be a way to deal with it.
OTOH, now that I think about it, it could also be useless....
Let's play Worst Case Scenario:
The Intel RNG h/w can be put into 'snoop mode' by a secret instruction
(or set of instructions). It sends a special value to the Intel RNG API
which then produces "random-looking" known values when called.
The attackers can snoop the victim's net connections-- let's say
that they're attempting to decrypt something that the victim sends
encrypted in a session key read directly from the victim's random
pool s/w, which calls the Intel RNG API for some of it's entropy input.
The attackers know how the victim's random pool works. The attackers do
not know the other non-Intel RNG input bytes which went into the
random pool (if they could know them they would have no need for the
snoop mode). However the attackers do know how the random pool gets
it's other entropy sources from s/w, and know about any non-randomness
in this method.
The attackers can exaust the output of the random pool. This will force
it to obtain new entropy from its sources when the call is made to
obtain the session key the attackers want to crack. So it will
then be reading in known values from the Intel RNG API in snoop mode.
Random pool version A takes 75% of it's bytes from the Intel RNG API and
25% from the system (since h/w RNGs produce bytes much faster than s/w
methods this is reasonable if the random pool programmer wants
performance). When the call is made to obtain a session key, the random
pool mechanisim will have to request entropy from both the Intel RNG and
from the s/w sources. Since getting s/w entropy is slow, this random
pool is one-for-one, that is it produces a (hashed) byte of output for
each byte of input. So, if it's hash is SHA, it'll read 5 bytes from
the s/w entropy source and 15 from the Intel RNG (the random pool
programmer is going to let his SHA-1 software pad the input out to the
SHA block size). The random pool s/w outputs the SHA1 hash of the 20
byte input which is used directly as the session key. The attacker now
has to do a brute-force search over 2^40 (2^39 on average) combinations
to find the session key. If the s/w entropy sources aren't perfectly
random (which is likely- this is one of the reasons for using h/w RNGs
in the first place) then the attacker can further reduce his search
space or discard unlikey input values. 2^40 isn't very secure, although
this is a particularly awful random pool design.
Version A.1 is the same but with the pool hashing inputs to outputs 2:1-
it would have to read in 10 bytes from s/w entropy sources and 30 from
the Intel RNG. This raises the attacker's brute force search space to
2^80. That mightbe good enough for some uses, but non-randomness in the
s/w entropy inputs could make this breakable with reasonable effort.
Version A.N hashes the input down Y:1, where Y is sufficiently large
to result in a secure session key. However it's going to be limited
in speed to the speed of obtaining entropy from s/w sources, so
the Intel RNG input is superfluous.
Version B also takes 75% of it's bytes from the Intel RNG, but hashes it
down 5:1 beforehand. That is, when the random pool requests 15 bytes of
entropy input from the h/w RNG, a software layer reads (5 * hash size)
bytes returns 15 and keeps the rest in the output buffer for the next
call. Since we're using SHA1, it would read 100 bytes hash them down to
20 and return 15 to the pool, which then hashes that together with the 5
bytes from s/w entropy sources to produce the 20 byte output. The
attacker knows all the "random-looking" output values of the Intel RNG
when it's put into snoop mode. So the attacker, who also knows what the
victim's random pool is doing with the output of the Intel RNG (i.e.
hashing it down) can easily perform the same hash with the known input
values.
So hashing entropy _input_ to the random pool is worthless if
the attacker knows all the input that's getting hashed.
But, like I said above, if snoop mode doesn't set all the output to
known values but only sets some of it, and the rest is therefore real
random values, hashing down the output would 'concentrate' the entropy
(against a brute force attack) and therefore be of value.
The paranoid or those with high-value things to protect would
probably want to do both- hash down the Intel RNG output to 'concentrate'
whatever entropy is there, and then hash down their random pool output
far enough so that the results would still be good enough even of
the hashed Intel RNG output were completely known by the attacker.
Practically, you have to ask yourself, what's the chances that the
output of the Intel RNG is completely compromised vs. what ar the chances
that your other entropy sources are compromised vs. how long will it take
to gather enough entropy to make you happy?
Since PGP is a tool used by security-concious people, I would
at least include some options for users to determine what they
feel comfortable with- i.e. don't use the Intel RNG H/W at all,
hash its output down X:Y, , etc.
--
Eric Murray www.lne.com/~ericm ericm at the site lne.com PGP keyid:E03F65E5
