Wagner's Birthday Attack - How to Break InsecureMuSig

Wagner's Birthday Attack is a cryptographic attack that broke InsecureMuSig, the original version of the MuSig multi-signature protocol. The attack exploits the absence of a nonce-commitment phase: a malicious co-signer (Carol) opens many concurrent signing sessions, waits for peers to reveal their nonces, then uses Wagner's Algorithm to find rogue nonces that manipulate the aggregated signing challenges so they sum to an evil challenge of Carol's choosing. This allows Carol to forge a valid Schnorr signature on an arbitrary message. The post explains the full attack procedure step by step, then dives deep into Wagner's Algorithm itself — covering list generation, probabilistic analysis, tree-based merging, complexity analysis, and optimizations. The vulnerability was patched in MuSig1 by adding a nonce-commitment round, but understanding the attack remains important for protocol designers.