Re: cprng_fast implementation benchmarks

[<Paul_Koning%Dell.com@localhost>]

On Apr 24, 2014, at 12:40 PM, Mindaugas Rasiukevicius 
<rmind%netbsd.org@localhost> wrote:

> <Paul_Koning%Dell.com@localhost> wrote:
>>> No.  There is a "strong" RNG, based on the NIST SP800-90 CTR_DRBG with
>>> AES128 as the block transform.
>>> 
>>> There is also a "fast" RNG, based on RC4.
>>> 
>>> We are discussing the replacement of the "fast" RNG.
>> 
>> Ok. But if that’s a non-strong RNG, why are we discussing security
>> properties?  And why are we considering algorithms this complex, rather
>> than using a PRNG?
>> 
>> In other words, this is being treated like it’s in between a PRNG and a
>> strong RNG.  I don’t understand why there can be a middle ground like
>> that, and what its required properties would be.
> 
> There are cases when both security and performance matters.  Consider
> TCP ISN generation or UDP port number generation (i.e. randomisation).
> There are known security issues if these numbers can be predicted, but
> at the same time, high performance penalty is undesirable in the network
> stack.  However, the requirements are a bit different: the life time of
> a packet or connection tends to be much smaller than of some encrypted
> and permanently stored piece of information.  Arguably, given a short
> life time, a weaker (but faster) CPRNG is enough for making potential
> attacks unpractical.  Do you disagree?

I think I do.  The description you gave seems to amount to: we need something 
that is better than a PRNG but it doesn’t have to be as strong as the real 
crypto RNG we have.  But that’s not a particularly precise definition, and it’s 
hard to judge whether a proposed implementation meets the requirements, or not. 
 

In general, where security issues are involved, it is desirable to have 
properties expressed quantitatively.  For example, security equivalent to brute 
force search over a 2^128 (128 bit) key space.  Or brute force over  some other 
2^n (n bit) key space.

Knowing that there are “security issues” with UDP port number generation may 
mean that a PRNG is inadequate.  Deciding what sort of generator IS adequate, 
though, means starting with a more definite description of the nature of the 
attacks that we’re worried about, and the strength of the defense that is 
desired.

> 
> Finally, if we make a weaker CPRNG really fast, why bother with a third
> implementation of PRNG?

Only if the “weaker CPRNG” is good enough.  Right now I don’t see any way to 
decide that.

Now, if you were to propose using the AES-based strong RNG for the functions in 
question, we’re probably done as far as security is concerned; then the only 
remaining question is whether that function can be optimized well enough that 
we’re comfortable with its performance.

        paul