New Attack Vector

[Enochian]

I was surprised to see that Bitcoin passes untrusted signature data received from the outside world to openssl without doing any checking on it.  This leaves bitcoin open to the Litttle Bobby Tables (http://xkcd.com/327/) attack.

Each signature has exactly one DER-encoded ASN.1 octet representation, but openssl doesn't enforce this, and as long as a signature isn't horribly malformed, it will be accepted.

So you can sit on the network, watch for transactions, and echo them with the signatures slightly tweeked, but still valid.  These new transactions will have different hashes, and will compete with the original transactions for inclusion in a block.  When a cloned transaction beats out the original for block inclusion, it will leave the original in the owners wallet unconfirmable forever, resulting in inconvenience and unspendable coins.  Quick echoing and network latency gives this a finite chance of happening.

Of course, you can't create or destroy coins with this, and the money still winds up at the right destination. However, the typical user isn't going to know how to restore an old wallet and rescan the block chain to get his bitcoin client back to working condition.

It might be a good idea to patch this before some enterprising person with excess time on their hands (cough) makes a cloned transaction echobot.

[Pieter Wuille]

I believe the attack you describe is possible and real, but the effect is less troublesome. As soon as a modified echo of the transaction is included in a block, both sender and receiver will see this transaction too. The old transaction will linger on however, unconfirmed.

[Gavin Andresen]

I think sipa is right-- it will just look like a weird double-spend.

Probably a good idea to reject transactions with non-canonical signatures (reject if encode(decode(tx)) != tx ).

I assume the DER-encoded ASN.1 octet representation is the same between different ECDSA implementations (so if a non-openssl-based implementation creates transactions its transactions would be accepted), is that a good assumption?

[Enochian]

I assume the DER-encoded ASN.1 octet representation is the same between different ECDSA implementations (so if a non-openssl-based implementation creates transactions its transactions would be accepted), is that a good assumption?

Yes.  DER is, by design, unique across all implementations.

[ByteCoin]

Yes.  DER is, by design, unique across all implementations.

I presume you actually meant the exact opposite of what you said.

DER is "common" or "the same" across all implementations.

Edit your post and I will delete this one.

ByteCoin

[Enochian]

I presume you actually meant the exact opposite of what you said.

DER is "common" or "the same" across all implementations.

DER is BER with uniqueness enforced.  However, I see what I said lends itself to misinterpretation.

Objects have only a single unique correct DER encoding.  If it's not that encoding, it's wrong.

[Pieter Wuille]

So let me get this straight: bitcoin's signatures are always in DER encoding, but it will accept any BER-encoded signature?

[Enochian]

So let me get this straight: bitcoin's signatures are always in DER encoding, but it will accept any BER-encoded signature?

To encode a positive integer in DER, you convert it to a big endian sequence of octets, using the minimum necessary, and if the sign bit on the leading one is set, you prepend a zero octet so it won't be interpreted as a negative number.  You then prepend an "02", which indicates "integer", and an octet count which is a single byte for lengths up to 127, and 0x80 plus an octet count followed by the length octets for lengths greater than 127.  This maps every integer onto a unique octet sequence.

A signature is a pair of bignum integers, (r,s), so it consists of 0x30, which indicates a sequence of one or more things, an octet count of what follows, followed by two encoded integers.  In addition, bitcoin appends the hashtype, which is always "1", to the end.

Here is a sample bitcoin sig, broken up into the relevant fields.

3046
0221
00c352d3dd993a981beba4a63ad15c209275ca9470abfcd57da93b58e4eb5dce82
0221
00840792bc1f456062819f15d33ee7055cf7b5ee1af1ebcc6028d9cdb1c3af7748
01

openssl doesn't enforce the rule that the leading octet can't be 0x00 or 0xff if it is an extension of the sign bit on the following octet.  So you can prepend any number of 0x00 octets to a positive integer, and 0xff octets to a negative integer, and it is still considered legal.  Thus you can make an unlimited number of working signatures given one of them.

[eamon]

This actually is quite similar to another "corner case" that I've been wondering about.  Consider the following scenario:

User downloads installs bitcoin into a windows virtual machine, the copies the virtual machine to multiple locations.

Each of the virtual machines attempt to engage in transactions (receiving, sending, or even mining and block verification.)

What function is mitigating the collisions between clients, and which client becomes most authorative?  While I see how this could result in issues in transaction confirmation, wouldn't confirmations by those cloned entities result in confirmation corruption?

[kokjo]

This actually is quite similar to another "corner case" that I've been wondering about.  Consider the following scenario:

User downloads installs bitcoin into a windows virtual machine, the copies the virtual machine to multiple locations.

Each of the virtual machines attempt to engage in transactions (receiving, sending, or even mining and block verification.)

What function is mitigating the collisions between clients, and which client becomes most authorative?  While I see how this could result in issues in transaction confirmation, wouldn't confirmations by those cloned entities result in confirmation corruption?

1. none of them.
2. no.

[Enochian]

I believe the attack you describe is possible and real, but the effect is less troublesome. As soon as a modified echo of the transaction is included in a block, both sender and receiver will see this transaction too. The old transaction will linger on however, unconfirmed.

You're right.

I got curious and tried it this morning.  I created two transactions that did the same thing.  The first I let my client see, but didn't let it get broadcast.  The second I broadcast, but didn't let my client see.  Then I waited to see what would happen when the latter transaction arrived back in a block, double spending the earlier unconfirmable one in the wallet.

It added the second transaction to the wallet quite gracefully, and correctly computed the balance.  So this is less of a problem than I originally thought.

I should point out, however, that it used to be possible to segfault the ASN.1 parser in openssl by giving it garbage to decode.  The last such known bug was patched a number of revs back, but it not beyond the realm of possibility that another similar bug might be discovered at some time in the future.

So it's probably a good idea not to pass stuff that comes in over the wire to openssl without checking it first, just in case.

[BitcoinStars.com]

good job guys we need this sort of check and balance on the regular

[Pieter Wuille]

I don't like the idea of openssl segfaulting on garbage data.

Is there an easy way for checking (by looking at the bytes ourselves, not by passing it to openssl and request to encode it again) that the input is a valid DER-encoded signature?

[Mike Hearn]

What function is mitigating the collisions between clients, and which client becomes most authorative?  While I see how this could result in issues in transaction confirmation, wouldn't confirmations by those cloned entities result in confirmation corruption?

It's possible to get a corrupted wallet today by doing that, where by "corrupted" I mean is out of sync with the state of the block chain and so can't reliably create spends.

Sipa is working on patches that can resolve this kind of thing, but until the work is complete it's not safe to do what you are suggesting. Bitcoin assumes that you don't copy your wallet around today.

Note that it doesn't undermine the security of the system though. The block chain will always be consistent.

[Enochian]

I don't like the idea of openssl segfaulting on garbage data.

Is there an easy way for checking (by looking at the bytes ourselves, not by passing it to openssl and request to encode it again) that the input is a valid DER-encoded signature?

Well, you know a valid bitcoin signature (r,s) is going to look like

<30><len><02><len><r bytes><02><len><s bytes><01>

where the r and s values are non-negative, and don't exceed 33 bytes including a possible padding zero byte.

One way to check would be to just create a little function

bool IsValidSig(char *sig, int siglen)

Containing an appropriate stack of if statements.

[Sergio_Demian_Lerner]

I'm re-investigating this past problem because I think there are some other possibilities for this attack vector.

Did Sipa implemented a patch back on MAY 2011 to check the uniqueness and correctness of signatures?

I don't see a IsValidSig() method in the source code.

Bet regards, Sergio.

[Pieter Wuille]

I'm re-investigating this past problem because I think there are some other possibilities for this attack vector.

Did Sipa implemented a patch back on MAY 2011 to check the uniqueness and correctness of signatures?

I don't see a IsValidSig() method in the source code.

Bet regards, Sergio.

No, this was never fixed. Doing it now would at first making transactions which use non-standard but valid encodings non-standard, and then fixing a policy for a transition point after which it becomes illegal.

[Gavin Andresen]

Making transactions with non-DER-encoded (aka BER encoded) signatures non-standard has been on my TODO list for over a year now, but has never been the highest priority.  That's the first step to making non-DER-encoded signatures completely illegal.

Note that if there is a core-dumping bug in OpenSSL's decoding code then it needs to get fixed in OpenSSL. Writing a BER decoder just for Bitcoin is a bad idea, it is much more likely our new code would have a crashing bug.

[Sergio_Demian_Lerner]

Thank you Sipa and Gavin, I'll keep researching on this..

[Sergio_Demian_Lerner]

For the record, there is another possibility of signature malleability.

For every ECDSA signature (r,s), the signature (r, -s (mod N)) is a valid signature of the same message. Note that the new signature has the same size as the original, as opposite as the malleabillity of padding.