[Cryptography] HSM's

[ianG]

On 18/01/14 23:07 PM, Jerry Leichter wrote:
> On Jan 18, 2014, at 1:07 PM, Bill Frantz wrote:
>>> Open question:  What do people think of the production of big important
>>> keys using the old compliance method of "must use a HSM" now ?
>>
>> I have always looked at HSMs as black boxes built by people I don't trust. If I built it I would feel different, but you should be uncomfortable using my HSM. Getting mutually suspicious people to trust the same HSM is an interesting social/technical problem.
> I'd look at this differently:  Is there a construction that preserves the good properties of HSM's (potential for a very small attack surface) without the bad ones (you either have to trust a sealed box that someone else built, or be willing to create it yourself from scratch)?  If you look at this as analogous to network routing - where there is great utility in using the large number of "black box" routers out there to communicate, even if you don't trust any of them - then something akin to the construction of a mix suggests itself.  That is, could you define a standard interface to an HSM with the property that it's "securely composable":  You can combine a bunch of HSM's and get something with the same interface, but such that as long as at least one of the HSM's lives up to its security properties, the whole ensemble does?  Can you, under some assumption like "each box may be separately cheating, but they don't cooperate" get something even stronger?
> 
> It seems to me that such a thing should be possible, but it would take some work to actually formalize (a) the relevant security properties; (b) the HSM interface; and only then (c) the proof that what you have is, indeed, securely composable.
>                                                         -- Jerry


Hmmm... So one could imagine a key generation process that worked like this:

a. each box generates its random contribution Rn.
b. each box commits to its random contribution by sharing the MD of it.
c. each shares their Rn with all.
d. all shares are XOR'd together to get R.
e. RSA key is created deterministically out of that combined R.

So for the API, we'd need to map that.  It would be more a messaging and
broadcast protocol than library API.

For signing, it's a simple compare, if it is deterministic.  For
encryption, that should be self-correcting.

Then, what about the negative properties -- proving the negative?  Aside
from the physical security [0], there is the obvious temptation of
spitting secrets out on the message bus.  So messages can be monitored,
but what would happen if for example one of the Rn were an encrypted
version of the last private key generated?

We could take the random generation out of the HSMs.  Principle!?

There could be N RNGs coupled to N HSMs.  The set of Rn could be created
in a write-only fashion, delivered singularly to the matching HSM-n,
committed, and then after the calculations, the RNG set could do the
attest to say they had generated the Rn set independently.  If the RNGs
cannot see the HSM messages, then they cannot be interfered with.



a. each RNG-n generates its random contribution Rn.
b. each RNG-n commits to its random contribution by sharing the MD of it
on its write-only bus interface.
c. each sends its Rn to the write-only bus.
d. each HSM-n reads the full set of Rn  and XOR's together to get R.
e. Private key is created deterministically out of that combined R.
f. Publish.  Compare.
g. Be happy.  Drinks...



       RNGs    Write             Read
               Only      HSMs    Write   BUS
               Lines             Lines
                                         ||
     /-------\                           ||
     | RNG-1 | ----->----->----->------> ||
     \-------/                           ||
                         ~~~~~~~         ||
                        { HSM-1 } <====> ||
                         ~~~~~~~         ||
                                         ||
     /-------\                           ||
     | RNG-2 | ----->----->----->------> ||
     \-------/                           ||
                         ~~~~~~~         ||
                        { HSM-2 } <====> ||
                         ~~~~~~~         ||
                                         ||
     /-------\                           ||
     | RNG-3 | ----->----->----->------> ||
     \-------/                           ||
                         ~~~~~~~         ||
                        { HSM-3 } <====> ||
                         ~~~~~~~         ||
                                         ||






[0] Which we can outsource to the user for now.  Let's leave out
side-channel stuff as well.