[Cryptography] /dev/random is not robust

[John Kelsey]

On Nov 3, 2013, at 5:27 PM, Alan Braggins <alan.braggins at gmail.com> wrote:

> On 24 October 2013 16:16, Phillip Hallam-Baker <hallam at gmail.com> wrote:
...           [I hope I got the attribution right]
>> If I was asked three months ago my position would be 'generate the keys on
>> the device that is going to use them and they never leave unless it is a
>> really constrained device like a credit card.'
>> 
>> I have completely changed my mind on this. I now think public keys should be
>> generated in device adapted for that purpose and migrated out using some
>> form of secure protocol that ensures only the intended device can use them.
> 
> Given that we're assuming the device can't reliably generate a secure key pair,
> and assuming that it doesn't already have a secret specific to the device, what
> protocols would be suitable for doing that?

Yep, this is an unfixable problem. 

Suppose you have a program to get a keypair, either by generating it or receiving it over the net.  But your program has no entropy.  Another way of saying that is that I (the attacker) can write a program that can do anything your program can do, because I have access to the same information as your program has.  

If your program generates a keypair, mine will generate the same one.

If your program makes an encrypted channel to get the keypair from some trusted server, my program will know the encryption key and can decrypt it.  My program can play man in the middle, too, because your program can't do anything my program can't also do.  

Without entropy--enough entropy to make me do an impossible amount of work getting my program to run like yours--there's just no way to get your program to generate or retrieve a keypair my program can't also generate or retrieve.

Now, if there is local traffic I can't intercept, your program can feed that into its RNG.  If I also can't guess that local traffic, then your program has enough entropy to generate a keypair. 

> (And if we can ask a device to generate keys and securely migrate them to us,
> we can ask it to generate some random seed material that isn't visible to an
> attacker, which solves the problem of local generation.)

Yep.  It seems like getting random secure starting seeds into devices would be a huge win here.  Then they can combine that with whatever information they have locally, and initialize their RNG, and then generate their keypair.  

> alan.braggins at gmail.com
> http://www.chiark.greenend.org.uk/~armb/

--John