[Cfrg] Vulnerability in threshold keygen and fix.

[Phillip Hallam-Baker <[e-mail]>]

I have been thinking further about the threshold key gen problem. There is
an important security caveat to add: Each side should only present a given
keypair contribution once and must keep both parts secret. Reuse provides
the attacker with a means of constructing an oracle for the base key which
is a bad thing.

The basic attack works like this:

Alice generates {a. P , a}, presents it to the service.
Service returns a value {s.P , s} via a confidential out of band
channel.

The composite key AS = (a+s). P

[NB in the Mesh the service actually returns a seed value x and Alice
generates a private key s = KDF (x, <stuff>)]

Alice presents {a. P , a}, presents to Mallet.
Service returns a value {m. P , m} via a confidential out of band
channel.

The composite key AM = (a+m).P

So if Mallet, knowing s is able to provoke Alice to return as.B he can then
recover the value am.P = (a+s).B - s.B + m.B.

This does not appear to affect the use cases I intend this scheme for in
the Mesh which are limited to providing some sort of limited defense
against weak key generation in IoT devices and devices compromised in the
supply chain.