I’ve been ignoring Bitcoin for a while but the recent troubles of Mt. Gox intersect with two long-standing topics here: Postel bugs and self-hashing documents (previously, previously, previously, previously).
Mt. Gox is a bitcoin exchange that apparently lost $350 million in bitcoins due to a known issue with the bitcoin protocol called transaction malleability. Briefly, bitcoin transactions are identified by a cryptographic hash. Usually, cryptographic hashes can be thought of as “fingerprints” of documents, that is, they have two critical properties: (1) different documents have different hashes; and (2) different hashes come from different documents.
Due to the details of the bitcoin protocol, the hashes of bitcoin transactions fail property (2)—a bitcoin transaction can have more than one hash. Think of a bitcoin transaction id (hash) as a check number: each check that you write has a unique number, and you reconcile your checkbook by looking at the checks cashed by your bank, making sure each one matches your records. As you can imagine, you might have trouble balancing your account if a check can have multiple check numbers. In particular, if your bank never shows a withdrawal for the check number of a check that you wrote, you might assume that it got lost and write a second, replacement check. This is essentially what happened to Mt. Gox, on a massive scale.
This is all caused by transaction malleability, a technical blunder in the bitcoin protocol described here. There are two sources of malleability, first:
Signature Malleability
The first form of malleability is in the signatures themselves. Each signature has exactly one DER-encoded ASN.1 octet representation, but openssl does not enforce this, and as long as a signature isn’t horribly malformed, it will be accepted.[1] In addition for every ECDSA signature (r,s), the signature (r, -s (mod N)) is a valid signature of the same message.[2]
Efforts are underway to first make Bitcoin nodes not relay non-standard signatures, and eventually disallow them from being included in new blocks entirely.
This is what I call a Postel bug: instead of rejecting unexpected or out-of-spec inputs, implementations are lenient and try their best to complete transactions whenever possible. This is a terrible mistake when the inputs are supplied by malicious parties (see my posts linked above).
Second:
scriptSig Malleability
The signature algorithm used in Bitcoin does not sign any of the scriptSig to create the signature. While signing the whole scriptSig would be impossible - the signature would be signing itself - this does mean that additional data can be added such that it will be pushed on the stack prior to the required signatures and public keys. Similarly OP_DROP can be added to leave the stack exactly as before prior to scriptPubKey execution.
Although this is phrased as a digital signature problem, it is in fact related to the self-hashing problem, because the way that digital signatures work is that you sign the cryptographic hash of a document rather than the document itself. And the fact that you can’t have a cryptographic hash of a document containing the hash itself means that bitcoin must use a second hash for the transaction id. This leads directly to the underspecification/Postel bug described above.
Recommendations
Obviously I think it’s desireable to eliminate Postel bugs from all security-critical software. This can be done by eliminating ambiguities in the bitcoin “specification” (such as it is) and by implementing strict checks in bitcoin software. This is quite difficult, by the way, given the state of the art in software engineering, and given that bitcoin relies on OpenSSL and ASN.1 (see the ASN.1 comments in Peter Gutmann’s rant, or this vulnerability note from 2002, or this from 2003 to see how long this has been going on). I don’t see another way forward, however.
A solution to the self-hashing problem would also be nice.