[Cryptography] RFC possible changes for Linux random device

[John Denker]

On 09/16/2014 07:37 AM, Jerry Leichter wrote:

> Agreed.  But let's also be more careful about attacks.
> 
> Suppose we implemented an AES-CTR PRNG, initialized using a TRNG.
> 
> - If I'm implementing a [downstream] crypto system whose fundamental
>  security depends on AES "acting like a random function" (yes, this 
> should be formalized carefully), then relying on this PRNG as my 
> source of random values does not add any new weaknesses.

> - If, on the other hand, my [downstream] system can survive a break 
> of AES (probably because it doesn't use AES at all [...] then I 
> should *not* rely on this PRNG as my source of randomness.

Those are good questions.  Professionalism demands that we 
ask such questions.  However the answer IMHO is not quite 
that scary, for multiple reasons.

1) The block cipher inside a RNG is under less stress than 
many others.  A lot of attacks rely on known plaintexts, 
chosen plaintexts, and/or huge amounts of ciphertexts, 
whereas in the RNG the plaintext is unknown /and/ the 
cipher gets re-keyed at not-very-long intervals.

I'm not rash enough to say this makes the RNG unbreakable;
I'm just saying it pushes the break rather far down the
list of things to worry about.

2) As with other block ciphers, you can (for a reasonable
price) buy additional safety margin by superencryption,  
putting one cipher in series with a dissimilar cipher.

3) See below:

> One thing to note is that if you ever decide that AES is vulnerable,
> you can upgrade the generator to something else *entirely on your
> own*:  Unlike changing the ciphers used in communication, the cipher
> or other mechanism used to build a PRNG is a purely local decision.

Right.  This is the poster child for "cipher agility"
that actually works, actually makes things better not
worse.

There is a space on the block diagram labeled "cipher
goes here" and you can drop in a new cipher any time 
you want.  If it's an embedded system that cannot be
recompiled, you can (for verrrry small cost) compile
a bunch of stuff in advance and make it switchable at 
runtime.

Bottom line on this topic:  Professionalism demands 
that we ask such questions.  However, it seems to me 
that other things are far, far higher on the list of 
things to worry about.

Segueing now to the larger list:

On 09/14/2014 11:06 AM, Bear wrote:

> In my very strong opinion, a requirement for boot-time entropy can 
> result only from bad design.  Systems that need boot time entropy 
> can need it only because they are doing things at boot time which 
> should not be done at boot time, and failure to correct this OS 
> design failure is actively harmful to security. 

That's strictly true if we assume the word "entropy" is
being used correctly.

In my very strong opinion, a kernel PRNG should be secure
from the first moment of the boot process ... just as a 
baby rattlesnake is venomous from the moment of birth.  
The PRNG should be able to produce computationally-strong 
pseudo-randomness, even if it cannot produce very much 
actual entropy.

On 09/15/2014 09:55 AM, William Allen Simpson wrote:

> Once upon a time, I submitted a patch for Linux to delay
> selection of the secret for TCP syncookies, until an actual TCP
> packet arrived!  And to change the secret on a regular basis....
> 
> David Miller rejected it.

I appreciate the sentiment, but that is not a particularly
strong example.  A CSPRNG is perfectly adequate for syn-
cookies, for ASLR, and a wide range of other things that
happen early in the boot sequence.

Giving these consumers what they want -- high-grade
randomness -- is not super-easy, but it is eaiser than

Please, folks:  If we're going to make progress in this
field, we need to be really fastidious about the distinction
between pseudo-randomness and actual entropy.