OK, I have looked at the link that you provided on MuSig @antioch. The question that you asked is relevant and deserves to be addressed in our scheme.
In your sentence, I thought you were saying that it is the receiver that will choose the message “for the sender” after the sender had sent him the nonce, and I did not read the blog post first.
I’ll explain the Wagner’s attack described in the blog, and then see its applicability (or not) in our scheme. First I’ll explain what the Wagner’s algorithm is in the general case.
What a Wagner’s algorithm does in the general case:
Given a fixed number alpha fixed before the attack, the Wagner’s algorithm allows to find k numbers n_1,...,n_k in reasonbale time such that
alpha = Hash(n_1) + ... + Hash(n_k).
That’s all (the algorithm to be able to do this in reasonable time is actually very refined).
Wagner’s attack in the case of the MuSig with nonce pre-sharing:
In MuSig the total message M of the signature is composed of R, the total nonce, X, the aggregated key, and m, the “extra data” (fees, etc).
What the Wagner’s attack consist of in the setting with nonce-pre-sharing MuSig is that the attacker opens k parallel signing sessions with the victim and collects the k respective partial nonces of the victim (one per signing session) so that he can compute the k total nonces R_1,...,R_k for the respective k signing sessions. This is the first step of the attack.
In the second step, the attacker fixes for himself a message m_0, takes the aggregated key X, and computes the nonce R_0 = R_1 + ... + R_k.
He then computes M_0 = Hash(X||R_0||m_0). Note that M_0 will play the role of alpha.
In the third step of the attack, the attacker, using the Wagner’s algorithm, comes up with k messages m_1,...,m_k that are such that:
M_0 = Hash(X||R_1||m_1) + ... + Hash(X||R_k||m_k).
At the end of the parallel MuSig protocols, the attacker possesses k valid signatures s_i such that for each i:
s_i = r_i + Hash(X||R_i||m_i).x, which is a valid signature for X with nonce R_i.
x being such that x.G = X, and r_i such that r_i.G = R_i.
This is where the attack can be applied to come up with a rogue signature s_attack, signing the aggregated public key X. It is left as an exercise to the reader in the blog post, so I post in what follows the solution to the exercise.
s_attack is in fact just the sum of the k signatures:
s_attack = s_1 + ... + s_k = (r_1 + ... + r_k) + Hash(X||R_1||m_1).x + ... + Hash(X||R_k||m_k).x.
Given that the k signatures were done on the same aggregated key X, with secret key x, the above expression can be actually factorized:
s_attack = r_0 + (Hash(X||R_1||m_1) + ... + Hash(X||R_k||m_k)).x,
where r_0 = r_1 + ... + r_k corresponds to the secret to R_0 (since R_0 = R_1 + ... R_k).
But if we remember, we had, thanks to Wagner’s algorithm:
M_0 = Hash(X||R_0||m_0) = Hash(X||R_1||m_1) + ... + Hash(X||R_k||m_k).
Thus, s_attack = r_0 + Hash(X||R_0||m_0).x, which means that the attacker has been able to create a valid signature against the aggregated key X with nonce R_0, and message m_0 that the victim never actually signed.
This is the end of the attack.
Wagner’s attack in our scheme:
Irrelevant since the receiver always chooses different partial excesses at each signing session.