Are fully deterministic sessions broken?

[real-or-random]

Participants currently derive all randomness from their seeds. I'm concerned that this was a bad idea.

If a (victim) participant gets stuck in a session, the caller may want to restart. In a second attempt, other malicious participants can present different VSS commitments (and other data) than in the first session. Depending on the position where the victim gets stuck, it can happen that the victim has sent a signature already for the first session. Then it will send a signature on different data in the second round. (This makes the victim equivocate like a malicious participant...)

Similar issues can happen if you re-initialize a device with a backup of the seed (but not yet with the recovery data). Then you may be tricked into rerunning the session, possibly with different data. It may then even happen that you recover the initial session later, and then you have two sessions with the same parameters but different outputs.

I haven't thought through all the consequences, but all these scenarios, though perhaps unlikely, sound at least highly undesirable.

The obvious fix would be to have some kind of session "nonce". Every participant then adds the nonce to the derivation of secrets. But every participant needs to make sure that the nonce is fair, i.e., the others at least couldn't fix it to a given value. We need to store the nonce in the recovery data. This makes it a bit cumbersome. Here are all the possibilities that I can think of:

1. Everyone can send their own nonce n_i along in the first round. That adds O(n) to the recovery data.
2. Participants run the typical commit-and-reveal coin tossing protocol to create a common nonce by xoring their committed values. This adds only O(1) to the recovery data, but this would add two early rounds to the protocol....
3. Participants send a nonce n_i * G along with a pop of n_i before the first round. We can add all nonces up to a common nonce of size O(1), and the pops exclude cancellation attacks. This just adds one early round, bad enough.
4. Pre-generate the Schnorr signature nonces for the pops and abuse them as session nonces (lol no, this is a huge footgun for nonce reuse...)

[real-or-random]

If a (victim) participant gets stuck in a session, the caller may want to restart. In a second attempt, other malicious participants can present different VSS commitments (and other data) than in the first session. Depending on the position where the victim gets stuck, it can happen that the victim has sent a signature already for the first session. Then it will send a signature on different data in the second round. (This makes the victim equivocate like a malicious participant...)

I spent some more thought on this over the weekend, and I don't think it's an issue.

Indeed, what can happen is that you end up with two finalized sessions, but that's somewhat expected given that you have started two sessions. That's also not equivocation. There's not even a clearly defined "context string" for which you would give two signatures. (We don't have a guarantee that there's only one session per SessionParams).

(to be continued)

[real-or-random]

I spent some more thought on this over the weekend, and I don't think it's an issue.

I've discussed this with @jonasnick, and he agrees that signing the transcript in multiple sessions is not an issue.

---

But what could be an issue is unforgeability. The unforgeability proof in https://eprint.iacr.org/2023/899.pdf relies on the property that honest participants receive pops before they reply to FROST signing queries... But if an honest participant simulated by the reduction can run multiple DKG sessions, we could have the following order of events:

1. Finish first DKG session (with some local polynomial f_i and secret x_i = f_i(0))
2. Reply to FROST first-round signing queries for first DKG session
3. Receive pops in second DKG session
4. Reply to FROST second-round signing queries for first DKG session (using x_i)
5. Finish second DKG session
6. Get forgery for second DKG session (with a threshold key to which x_i is a contribution)

Step 3 involves multi-forking and thus the reduction will need to answer many DL queries in step 4 in different worlds. Certainly more than two (= number of nonces) worlds, which already breaks the reduction. (This is similar to the MuSig2 ROM proof, which also can't rely on multi-forking and needs to resort to bi-forking instead.)

Apart from that, I have no idea how on actual attack would look like. The above order of events suggests a pop forgery (perhaps on -X_i), but I can't see how to exploit the signing sessions to get such a forgery. Wagner/BLLOR simply don't work due to the two nonces. (This may be similar to the MuSig2 which needs four nonces in the ROM to make the proof work, but two appear to be enough to rule out attacks. But here would need poly many nonces due to the multi-forking, so there's no constant number like 4 that could be hoped for to make that work.)

And matching this observation, I suspect that the reduction would just work if one assumes that the pops are straight-line extractable, e.g., in the AGM or using schnorr-koe. SpeedyMuSig shows that interleaving pops with signing queries is possible.

But talk is cheap, and we currently don't have such proof with straight-line extractable pops[^proof], and I'd rather err on the side of caution here. Moreover, having additional per-session entropy sounds like good practice anyway (e.g., it would repair predictable seeds).

@jonasnick and I think that solution 1 above, namely "Everyone can send their own nonce n_i along in the first round." is acceptable, though the increase of 32n bytes in the recovery data hurts a bit. This means we should not forget to add the nonce also to the pad derivation to avoid reuse of pads across sessions. (This also means that simply making the polynomials ephemeral is not a proper solution because then we'll reuse pads unless we add randomness somewhere else in the encryption.)

[^proof]: We have the CKM proof, of course, but it doesn't apply to FROST3, and also the PedPop in the CKM proof differs from SimplPedPop quite a bit...

[real-or-random]

But talk is cheap, and we currently don't have such proof with straight-line extractable pops1, and I'd rather err on the side of caution here. Moreover, having additional per-session entropy sounds like good practice anyway (e.g., it would repair predictable seeds).

Did this in 5d93a8bbcff8d8092bdc1f677befc1738c2edfa2 by switching to ephemeral-static ECDH.