[Cryptography] RFC possible changes for Linux random device

[Sandy Harris]

On Tue, Sep 16, 2014 at 10:37 AM, Jerry Leichter <leichter at lrw.com> wrote:

> On Sep 16, 2014, at 6:43 AM, John Denker <jsd at av8n.com> wrote:

> Suppose we implemented an AES-CTR PRNG, initialized using a TRNG.
>
> - If I'm implementing a 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 crypto system can survive a break of AES (probably because it doesn't use AES at all - many systems rely on the security of AES *plus* the security of, say, RSA, and they are just as vulnerable to a break of AES), then I should *not* rely on this PRNG as my source of randomness. ...


> In practice today, many widely-used algorithms are inherently dependent on the security of AES, so relying on an AES-dependent PRNG has minor, if any, affects on the security of the system as a whole. ...

There are at least two ways to reduce the dependence on AES security
while using AES.

The Preneel et al papers prove that encrypt(X, key) xor X is
non-invertible. Apply that to a counter-mode AES and you get a
guarantee the enemy cannot use the output data to attack the AES
instance. There are details and limits that apply, but in principle
this solves a large part of the problem.

The Even and Mansour paper looks at the xor-permutation-xor structure
and proves that for n-bit blocks and D known or chosen plaintexts, the
time T to break it is bounded by DT >= 2^n . We can choose D to make
that bound close to 2^128, and this is a provable minimum security
level not based on an assumption that there is no attack on AES better
than brute force. In fact their proof assumes the permutation is
broken -- the enemy has oracles that give him permutation output for
any input and vice versa. All we need from AES in this structure is
that it be a permutation, a requirement it obviously meets.

A Shamir et al paper shows that the Even-Mansour bounds holds with +
instead of xor and the pre-whitening and post-whitening data the same.
That means we can use:

     start with counter as plaintext
     whiten with +
     AES
     whiten with +
     xor in counter to guarantee non-invertibility

My submission to the CAESAR competition uses some of these ideas (not
the non-invertibility since that would be remarkably undesirable in a
cipher) and has a fairly detailed analysis:
https://aezoo.compute.dtu.dk/doku.php?id=enchilada