Re: VNC authentication weakness

[Nate Lawson <nate () cryptography com>]

At 02:16 AM 7/28/2002 -0600, Theo de Raadt wrote:
> > Does anyone have a better solution that doesn't involve calling
> > entropy-gathering routines from all over the program or running a
> > continuous entropy-gathering thread?  Are there any big problems in
> > this solution, other than that it only has (by my pessimistic
> > estimates) about 28 bits of entropy if my "thousandlists" trick isn't
> > really very effective?  28 bits is probably sufficient for my
> > purposes.  Is there some much simpler solution I could have more
> > confidence in?
>
> Yes.
>
> OpenBSD has /dev/arandom, kernel arc4random(), and libc arc4random(3)
> which load a chunk from the real random pool when needed, persistantly
> permit reuse of that pool without having to rely on new entropy, and
> automatically reseeds that pool when we perceive that the quality of
> it may be dropping.  This type of pool is ideal for use as chaff,
> random ids, etc.
>
> It's the right solution for the problem you (and many others) face:
> Where is a very cheap source of fairly strong random data that does
> not deplete the critical resource of very strong random in the kernel
> pool.


To be more specific, there are two things you need in a challenge 
value:  uniqueness and unpredictability.  Lack of uniqueness allows an 
attacker to replay a past response to a future challenge.  Predictability 
allows an attacker to pre-fetch a correct future response from one of the 
parties.

A counter provides perfect uniqueness (up to its maximum range) but easy 
predictability.  A physical random source provides great unpredictability 
but only statistical uniqueness (again based on its maximum range of 
values).  In between is a PRNG seeded with a strong random source -- 
statistically unique (based on its range minus any biases in the generator) 
and unpredictable but leaks information about the seed with each 
output.  To get around these limitations, implementers either reseed 
periodically (as Theo suggests) or put a limit on the number of challenges 
that can be output (say if the seed is fixed at manufacture and no physical 
random source is available).  The latter is open to a DoS attack but can be 
acceptable in some environments.

Please note that these are general observations, not an endorsement of a 
particular system.

-Nate