[Cryptography] Conservation of security in threshold crypto...

[Phillip Hallam-Baker]

  As folk know, I have been working on various threshold crypto schemes. I
recently realized a rather stunning anti-symmetry akin to conservation of
well something.

Recall that if {A, a}, {B,b} are {public, private} ECDH keypairs that we
can construct a new keypair {Z, z} as follows:

z = a+b mod Q
Z = A+B

(where Q is the order of the prime subgroup.)

Proof:

A = a.P, B = b.P =>
Z = A+B = a.P + b.P = (a+b).P  = ( a+b mod Q).P + nQ.P = z.P

Now for the interesting part. There seems to be a conservation of security
law going on.

The unguessability of z is the maximum of the unguessability of a, b. If we
design the protocol right with appropriate hashes to avoid stride issues,
we can get the  unguessability to be the sum of the  unguessability of a, b
(with a ceiling of course)

Bottom line, using this approach to generating private keys means that you
can mitigate many weak key attacks that are real issues in deployed systems.


But now lest see what happens when you try to play games on the public key
side to achieve integrity. It turns out that the trustworthiness of the
composite public key is the lesser of the trustworthiness of A, B.

Lets say Alice and Bob both contribute keys to a joint signature key Z and
Alice goes first. Bob can determine the value Z buy picking B = Z-A.

This is the basis for rogue key attacks in threshold signatures.


So it seems like there is a conservation thing going on. Using naive
approaches, we get the maximum trustworthiness on the private key side and
the minimum on the public key side.

Of course the control here is to either use a key generation approach that
constrains Bob in some way (e.g. he has to commit to his value B before he
sees A) or we have to limit the functionality we provide. I do not support
threshold signatures created by people specifying their own independently
generated keys. I only support generating a key pair and then splitting it.
So I effectively eliminate the attack by ruling it out as a security
control being provided.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20200126/a7979b56/attachment.htm>