Bitcoin Forum
April 23, 2014, 09:14:51 AM *
News: Due to the OpenSSL heartbleed bug, changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 5 6  All
  Print  
Author Topic: New Attack Vector  (Read 18377 times)
Enochian
Member
**
Offline Offline

Activity: 88


View Profile

Ignore
May 15, 2011, 05:00:58 PM
 #1

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.

Unbeatable Service & Product Support
Grab Your Miners at GAWMiners.com
Order Before April 25th to receive
Double your Hashing Power for 1 week!

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1398244491
Hero Member
*
Offline Offline

Posts: 1398244491

View Profile Personal Message (Offline)

Ignore
1398244491
Reply with quote  #2

1398244491
Report to moderator
1398244491
Hero Member
*
Offline Offline

Posts: 1398244491

View Profile Personal Message (Offline)

Ignore
1398244491
Reply with quote  #2

1398244491
Report to moderator
1398244491
Hero Member
*
Offline Offline

Posts: 1398244491

View Profile Personal Message (Offline)

Ignore
1398244491
Reply with quote  #2

1398244491
Report to moderator
1398244491
Hero Member
*
Offline Offline

Posts: 1398244491

View Profile Personal Message (Offline)

Ignore
1398244491
Reply with quote  #2

1398244491
Report to moderator
Pieter Wuille
Hero Member
*****
qt
Offline Offline

Activity: 938


View Profile WWW

Ignore
May 15, 2011, 05:36:54 PM
 #2

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Gavin Andresen
Hero Member
*****
qt
Offline Offline

Activity: 1330


Chief Scientist


View Profile WWW

Ignore
May 15, 2011, 06:05:11 PM
 #3

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?

Will I see you in Amsterdam?
  http://bitcoin2014.com/
Enochian
Member
**
Offline Offline

Activity: 88


View Profile

Ignore
May 15, 2011, 06:22:23 PM
 #4

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
Sr. Member
****
expert
Offline Offline

Activity: 413


View Profile

Ignore
May 15, 2011, 07:27:45 PM
 #5

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
Member
**
Offline Offline

Activity: 88


View Profile

Ignore
May 15, 2011, 07:52:55 PM
 #6

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
Hero Member
*****
qt
Offline Offline

Activity: 938


View Profile WWW

Ignore
May 16, 2011, 09:21:12 AM
 #7

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

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Enochian
Member
**
Offline Offline

Activity: 88


View Profile

Ignore
May 16, 2011, 01:41:49 PM
 #8

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
Newbie
*
Offline Offline

Activity: 10



View Profile WWW

Ignore
May 17, 2011, 05:30:35 PM
 #9

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
Hero Member
*****
Offline Offline

Activity: 1022


You are WRONG! :D


View Profile

Ignore
May 17, 2011, 05:44:52 PM
 #10

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.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
Enochian
Member
**
Offline Offline

Activity: 88


View Profile

Ignore
May 18, 2011, 04:03:38 PM
 #11

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
Full Member
***
Offline Offline

Activity: 140


View Profile

Ignore
May 18, 2011, 04:08:18 PM
 #12

good job guys we need this sort of check and balance on the regular
Pieter Wuille
Hero Member
*****
qt
Offline Offline

Activity: 938


View Profile WWW

Ignore
May 18, 2011, 04:09:28 PM
 #13

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?

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Mike Hearn
Hero Member
*****
expert
Offline Offline

Activity: 1232


View Profile

Ignore
May 18, 2011, 04:17:27 PM
 #14

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.

12LMm82ZgAzf7yNDpPydEYxEr4Ap7XtSSK
Enochian
Member
**
Offline Offline

Activity: 88


View Profile

Ignore
May 18, 2011, 04:30:49 PM
 #15

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
Sr. Member
****
expert
Offline Offline

Activity: 469


View Profile WWW

Ignore
August 22, 2012, 01:46:33 PM
 #16

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
Hero Member
*****
qt
Offline Offline

Activity: 938


View Profile WWW

Ignore
August 22, 2012, 02:21:31 PM
 #17

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Gavin Andresen
Hero Member
*****
qt
Offline Offline

Activity: 1330


Chief Scientist


View Profile WWW

Ignore
August 22, 2012, 02:22:50 PM
 #18

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.

Will I see you in Amsterdam?
  http://bitcoin2014.com/
Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 469


View Profile WWW

Ignore
August 22, 2012, 03:31:44 PM
 #19

Thank you Sipa and Gavin, I'll keep researching on this..
Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 469


View Profile WWW

Ignore
October 04, 2012, 09:26:46 PM
 #20

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.
Pages: [1] 2 3 4 5 6  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!