[Cryptech Tech] backup and replication of hashsig keys

[Paul Selkirk]

This comes out of a conversation with Russ, Phil, and Dominique at the
end of the face-to-face meeting in Stockholm.

Background and rationale:
Diamond Key Systems (DKS) are building a box that will have two or more
CrypTech Alpha boards within a tamper enclosure, with a Raspberry Pi as
a user front-end and load-balancer. They desire to duplicate private
keys between the alphas, so that either/any of the boards can sign with
them.

Brief review of hashsig structure:
The hashsig "private key" is a hash tree of one-time signing keys. To
keep key generation time and key storage manageable, it is organized as
a tree of trees, where each tree signs the public key of tree below it,
and the lowest-level tree is used to sign user messages. Following the
recommendation of draft-mcgrew, only the top-level one-time keys are
stored in the flash-based keystore, and the lower-level trees are stored
in the volatile (RAM-based) keystore.

In this discussion, we'll use an example with L=2, h=10, so there are
2^10 (1024) keys in each tree, and 2^20 (about a million) potential
one-time signing keys.

One axiom of hash-based signatures is that one-time signing keys may
never be re-used, so hashsig keys cannot be copied verbatim from one
signer to another, nor can a key even be backed up and restored, because
it may have been used in the meantime.

So we need to partition the keyspace. For this example, each of the
alpha boards in the DKS box would have 2^9 (512) LM-OTS keys in the
top-level tree, and could generate 2^19 (half a million) signatures, all
of which could be verified with the same public key. If there were 4
alphas in the box, or if two boxes were deployed for geographic
redundancy, each alpha would get a quarter of the keyspace.

In the original white-board discussion, we had equal-size partitions,
with the number known at key-generation time. However, I'm now in favor
of a more ad-hoc approach where the caller specifies the exact number of
keys to export. For example, in the case of geographic redundancy, one
box might be expected to have to sign more things, so would need a
bigger share of the keyspace.

Then there is the question of how exactly the key export works. At
present, each one-time signing key is randomly generated, so the export
would consist of one hal_hashsig_key_t and 1024 lmots_key_t, which would
exceed the RPC message buffer size. (All LM-OTS keys need to be
exported, even though the importing alpha can only use a portion of
them, because the hash tree has to be rebuilt before the hashsig key can
be used.)

So there would have to be some kind of fragmentation and reassembly
scheme. One possibility would be to call hal_rpc_pkey_export() first
with the desired number of keys, which returns the hal_hashsig_key_t;
then call hal_rpc_pkey_export() repeatedly with a "next" flag, or a key
quantity of 0, and get one LM-OTS key on each call. But this feels like
a huge hack, and a large window in which things can go wrong.

Fortunately, draft-mcgrew Appendix A includes a scheme for pseudorandom
generation of the LM-OTS keys, so only the hal_hashsig_key_t key needs
to be exported, and the full tree can be regenerated on the importing
alpha(s).

If the user sets the "exportable" flag in the call to
hal_rpc_pkey_generate_hashsig(), the pseudorandom key generation method
will be used. Otherwise, the random keygen method will be used, because
it's somewhat faster and simpler. Or maybe the top-level tree is always
pseudo-randomly generated. All lower-level trees will be generated with
random keys, because they will never be exported.

I plan to start work on this in a couple weeks, because the findings of
the security audit are a higher priority.

				paul