This work is a collaboration between Niklas Gögge (Brink) and Antoine Poinsot (Wizardsardine).
Btcd prior to version 0.24.2 does not correctly implement the consensus rules for legacy signature verification. The incompatible behavior can be triggered by a standard transaction, making it possible for anyone to fork off vulnerable btcd nodes at virtually no cost.
Details
When verifying a signature for a transaction input, the script interpreter of a Bitcoin node re-constructs the signed message and checks the signature against it. The original algorithm for re-constructing the message is detailed in this wiki page. Notably, the signed message contains a commitment to the Script being executed. For legacy transaction inputs any occurrence of the signature being verified is first removed from the executed Script committed in the message. This is often referred to as the FindAndDelete behavior, named after the function implementing this in Satoshi Nakamoto’s original Bitcoin codebase.
removeOpcodeByData is Btcd’s equivalent of Bitcoin Core’s FindAndDelete. Prior to version 0.24.2, removeOpcodeByData would remove any data push from the executed Script that contains the signature. Whereas Bitcoin Core’s (and Satoshi’s) FindAndDelete only removes exact matches. Using public key recovery it is possible to create a Script which contains a signature check and an extraneous data push which contains the signature itself and additional padding data. This Script can be committed to in a P2SH output which can be spent by a standard transaction which would be considered valid by Bitcoin Core and invalid by vulnerable Btcd nodes.
This bug was introduced in commit 76339baf6c9407b073828245e3458f4df35190ae in 2014, in reaction to a new Bitcoin Core unit test demonstrating the original implementation was consensus-incompatible.
Credits
Thanks to the Btcd maintainers for awarding us a bug bounty.
Timeline
2024-03-20 Niklas and Antoine discuss the quirks of Bitcoin Core’s FindAndDelete (in relation to Antoine’s research into the worst case block validation time) and decide to take a look at if Btcd got all the quirks right in their reimplementation
2024-03-22 Niklas and Antoine email a detailed report of the issue to Olaoluwa Osuntokun
2024-03-26 Olaoluwa acknowledges the issue and creates a discussion group with another Btcd maintainer
2024-05-07 Antoine reserves CVE-2024-36051 through Mitre
To exploit this you want to have a data push in the scriptpubkey which contains the signature among other dummy data and then execute the signature check. When checking the signature Bitcoin Core’s FindAndDelete won’t drop the data push from the signature hash, but btcd will before version 0.24.2.
To cause a chain split you not only want the sighash calculation to differ, you want it to lead to a different signature check result. The only way to have a valid signature in the scriptpubkey is to generate the signature first and then to recover a public key from it plus the sighash. By performing a public key recovery using Bitcoin Core’s sighash you’ll get a public key such as the signature check passes on Bitcoin Core but fails on btcd. And vice-versa.
I have a documented Bitcoin Core unit test as a patch which generates such a transaction, that we sent to Laolu as part of the original report. I’m hesitant to share it publicly though since it would simplify the job of a script kiddy who wants to be annoying. I’ll share the patch with you privately and share it on this thread later.
In my understanding of the bug, there is feeding of the two consensus-nodes, with the following
scriptCode, where the ECDSA sig and the "noise dummy data must match the length declared in
pushed bytes.
One should note that ECDSA sig length is malleable.
The non-upgraded, pre-0.24.2 btcd peers should remove the whole data push containing
the consensus valid signatures, before it’s verified by the script interpreter. While
bitcoind peers can accept the valid signatures. I’m unsure that you really need public
key recovery to achieve that chain fork as a trick. I believe one has OP_PICK, OP_ROLL and other stack inspection opcodes available, that can be committed in the scriptCode.
No, it’s more fundamental than just which opcode to use. You commit to the signature in the scriptCode, which itself needs to commit to the scriptCode. Short of new signature modes (like ANYPREVOUT) which don’t commit to the scriptCode you need to use pubkey recovery.
Could you describe exactly how you think it’s possible to achieve the same without pubkey recovery?
You commit to the signature in the scriptCode , which itself needs to commit to the scriptCode .
No, a signature does not need to commit to the scriptCode as one can use OP_CODESEPARATOR to spend pre-segwit script.
If you have a data push of the signature, then let the signature on the stack, then you have an OP_CODESEPARATOR, and then you have the OP_CHECKSIG. In that case shouldn’t the pbegincodehash making the scriptCode be only the OP_CHECKSIG itself, i.e a fixed-point ? The OP_CHECKSIG bitcoin core code is popping up the signature and pubkey from the stack, and OP_CODESEPARATOR is a null-op on the script stack.
If you get the signature out of the scriptCode by using an OP_CODESEPARATOR, then you won’t be able to exploit the FindAndDelete discrepancy since there is no signature to find anymore.
Right, unless you’re using an OP_CODESEPARATOR the signature should commit to the scriptCode. Though there is still the possibility that the signature is invalid w.r.t the scriptCode and the script execution still valid.
What if you have : <invalid_sig+noise> <invalid_sig> <OP_CHECKSIG> <OP_SIZE> <length_invalid_sig+noise> OP_EQUALVERIFY.
In my understanding, core’ should only remove 1 instance of <invalid_sig>, fails on the CHECKSIG (though NULLFAIL policy only) and then succeed on the OP_SIZE. On the other hand, non-upgraded btcd should remove the 2 instances of <invalid_sig> (as invalid_sig+noise contains the invalid_sig) and fails the OP_SIZE + OP_EQUALVERIFY.
Sure, but what we want here is a different script execution between btcd and Core. In the context of this disclosure, this was only possible using a discrepancy in the FindAndDelete implementation therefore you need a signature to be found in the scriptCode. Further, you need the signature to be valid for either btcd or Core, which is only possible if you do public key recovery.
I’m not sure what you are trying to get at since your Script is different from what i think you meant:
Here the CHECKSIG would be executed taking <invalid_sig+noise> as signature and <invalid_sig> as public key, which is always going to push 0 on the stack;
OP_SIZE would then be executed on the result of the CHECKSIG, which is always 0, and so would always return 0 as well;
Then OP_EQUALVERIFY would always fail since the length of the invalid sig + noise would never be 0.
I assume you mean that running OP_CHECKSIG would drop the <invalid_sig> (in Bitcoin Core), or both <invalid_sig> and <invalid_sig + noise>, from the Script itself and lead to a discrepancy of the execution when asserting the size of the top element left on the stack. Then you are misunderstanding what FindAndDelete does. It does not tamper with the Script being executed at all, it only modifies a copy of it for the purpose of committing to it in the sighash. Even if your Script from above correctly implemented what i think you intended it to, it would not cause a different execution between btcd and Bitcoin Core: the executed script is always the same so the size of the top stack element would always be the same for both.
The OP_CHECKSIG (or OP_CHECKMULTISIG) consume stack element so <invalid_sig> and pubkey are dropped from the remainder of the Script, as it is executed. Though yes, there might have been a misunderstanding, on how much btcd’s equivalent of FindAndDelete i.e removeOpcodeByData is really broken. Your initial description wasn’t that clear on that i.e “would remove any data push from the executed Script” which doesn’t say that data push removal was only stopping on currently executed OP_CHECKSIG, and not affecting further data push in the Script. Yes I can understand for the script kiddies.
More seriously than rambling on btcd brokeness, which is a wide subject, after re-checking and re-testing a lot of OP_CODESEPARATOR behaviors when used to spend SigVersion::Base in 27.x peers. Some behaviors are interesting, I’ll share it with you privately.