[Cryptography] A possibility for random device drivers

[dj at deadhat.com]

>...
> My question is whether it might be equally effective and somewhat more
> efficient to use the authentication code from AES-GCM or a similar
> system instead. These authenticators are designed to replace hashes,
> specifically HMAC, for packet-level authentication in various
> protocols, and efficiency is one of their main design goals.
>
> AES-GCM is the commonest; there is a NIST standard for it and RFCs for
> using it in IPsec, TLS and SSH. There are several other such
> authenticators in use as well, and the CAESAR competition for new
> authenticated cipher modes has proposals for more.
>
>...

What is your goal? Are you suggesting replacing the pool mixing function?
Or the PRNG? Or the entropy extraction? Linux muddies the boundaries, do
you want to sharpen them?

We have many good algorithms and proofs for entropy extraction. The
difficulty is usually in correctly characterizing the entropy source in OS
software that doesn't know what hardware it will be run on. So you can't
know if you are meeting the input assumptions of the extractor proof that
you rely on for correctness.

Pool mixing doesn't seem to have received as much attention from the
mathematicians, but I think it devolves down to a 2 input extractor
problem new_pool_state=f(the pool state, the input entropy).

On PCs, any AES mode gets a boost because of the AES instructions, but
that's not fundamental to the algorithms. Hardware will change over time.
Your ARM based phone is not like your PC when it comes to entropy sources
and hardware crypto support.

PRNGs are PRNGs. Take your pick. The random driver could have PRNGs tuned
for software and PRNGs tunes for instruction level crypto support. Take
your pick.

My hardware oriented approach has been to share an AES for PRNG and
extraction, because the AES is relatively expensive in hardware but it
works well for both uses. HMACs are mess in hardware and hashes have
inconvenient word lengths. What drives software choices is different and
to my mind it's a Hobson's choice.

<your chosen block cipher>-CBC-MAC is a good extractor. So are hashes and
HMACs.  http://link.springer.com/chapter/10.1007%2F978-3-540-28628-8_30

Simple GF arithmetic makes a good extractor when you have independent
inputs. These algorithms are certainly faster than any block cipher, given
the key setup requirements, even with AES instructions to hand:
http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BIW04/BIW.pdf

So sure, write a block cipher based random driver replacement, but the
bigger problems lay elsewhere. I think maybe we need a checklist for
random(4) replacement proposals:

1) Does it allow the OS to know the min-entropy of sources?
2) Does it cause /dev/random to not block?
3) Does it cause /dev/urandom to have > 256 bits of initial entropy in its
pool
4) Does it correctly and conservatively account for entropy?
5) Does it prevent load on /dev/random starving /dev/urandom and visa-versa.
6) Can mortals understand why it is good?