search

BlockstreamResearch / bip-frost-dkg

49 stars 14 forks source link

Implement Identifiable Aborts #32

Closed real-or-random closed 4 months ago

real-or-random commented 4 months ago
LLFourn commented 4 months ago

We actually specified a DLEQ proof a while ago for ECDSA adaptor signatures: https://github.com/discreetlogcontracts/dlcspecs/blob/master/ECDSA-adaptor.md#proving. It's implemented in libsecp256k1-zkp somewhere by @jesseposner.

I'm not sure you actually need a DLEQ proof. What's wrong with just MAC'ing the ciphertext and providing the shared secret? (I tl;dr'd the citations in the last issue).

Just to confirm this keygen+IA protocol would enlargen the message size back to quadratic in $n$ right or are we now sending the un-aggregated share encryptions in separate messages.

DLEQ oracle attack

It sounds like the recipients key in the ElGamal encryption that they can provide verifiable decryption for will be their static public key. This is very risky when combined with verifiable ElGamal decryption at least if done naively. I might have misunderstood but that's how I interpreted "ephemeral-static ECDH". If so this would let the a malicious coordinator turn an honest participant into a DH oracle for their static key by providing simulated ElGamal encryptions with the right encryption nonce. Perhaps what you had in mind already addresses this but I wanted to bring it up in case.

real-or-random commented 4 months ago

We actually specified a DLEQ proof a while ago for ECDSA adaptor signatures: discreetlogcontracts/dlcspecs@master/ECDSA-adaptor.md#proving. It's implemented in libsecp256k1-zkp somewhere by @jesseposner.

Oh crazy, I couldn't remember this :D https://github.com/BlockstreamResearch/secp256k1-zkp/pull/117 ... I should tell the other team who's working on DLEQ proofs...

I'm not sure you actually need a DLEQ proof. What's wrong with just MAC'ing the ciphertext and providing the shared secret? (I tl;dr'd the citations in the last issue).

Quoting myself from #9:

I don't see how some variant of committing symmetric encryption (e.g., add a hash MAC) would work, at least not without adding a round. The accusing participant could reveal the symmetric key to the coordinator, but if the accusing participant is malicious and reveals a garbage key, the coordinator doesn't know who's wrong and then the accused participant needs to exculpate herself by revealing the real key.

So the victim can reveal the derived symmetric key (or the ECDH shared point), but without a DLEQ proof, the victim can't convince the coordinator that it was the right one. I think revealing the symmetric key is good enough for proving to the coordinator "The ciphertext you have received from the sender decrypts to X (under the key I revealed, which is unique because the encryption is committing)", but not enough for "The ciphertext you have received from the sender fails to decrypt (under the key derived from ECDH)".

(Or am I wrong here?)

As I said, it can be fixed by adding a round, but that's not great. edit: I can't even be an optional round. The accused participant needs to make sure that they either reveal the key or sign the transcript, but never both. This needs an additional accusation round.

DLEQ oracle attack

that's how I interpreted "ephemeral-static ECDH".

I believe you interpreted it correctly. The sender generates an ephemeral key and the receiver has a static key. I guess ElGamal is more or less a synonym to "ephemeral-static ECDH", at least when used as a KEM.

Ugh, and thanks for pointing out the static-DH oracle... I hadn't really thought about this risk here, and we were a bit too enthusiastic here. This breaks the protocol immediately. A malicious coordinator can just send a nonce from a previous successful session and get the shared secret from the participant. And I don't see anything we could do about it.

LLFourn commented 4 months ago

I think you can make the static DH oracle go away if you just don't use a static point G for the ElGamal but some common random string. I don't know if we can get such a string in the general case though.

real-or-random commented 4 months ago

I think you can make the static DH oracle go away if you just don't use a static point G for the ElGamal but some common random string. I don't know if we can get such a string in the general case though.

Oh, randomizing the generator is something I haven't considered. But I'm not sure how much that helps. We'll need a fresh common random point in every session, and I don't see how to agree one without adding another round at the start.

And if we were to add a round, we could instead use ephemeral-ephemeral ECDH and the problem will just disappear. (Well, except that we'll still have an oracle if randomness is reused accidentally.) The only reason why the recipient uses a static key is that it's all the sender has in the first round.

Perhaps that restriction is a bit artificial. The sender anyway needs to obtain the hostpubkey of all recipients anyway before the protocol (call it round 0), at least in the first session with some new recipient, and then it could obtain the nonce as well. Every participant could just send their hostpubkey and nonce when saying hello to the coordinator. But I'm not entirely convinced. It will typically be the coordinator who initiates sessions, and then sending a nonce in round 0 will really mix static data (hostpubkey) and session data. At a minimum, it will complicate the API and make the protocol flow harder to understand.