Sergio_Demian_Lerner (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 08:48:11 PM Last edit: November 12, 2012, 09:27:47 PM by Sergio_Demian_Lerner |
|
Because Grau's supernode is still not in production, I will publish the details of this vulnerability.
I also decided to publish it in this thread (an not in supernode source repository) because it's interesting how vulnerabilities are hidden in the code.
Supernode implements a signature cache, like Satoshi client. The data structure to hold the cache is
private Set<String> validSignatureCache;
To check if a signature is on the cache, the code does:
StringBuffer c = new StringBuffer (); c.append (new String (Hex.encode (sig), "US-ASCII")); c.append (new String (Hex.encode (pubkey), "US-ASCII")); c.append (new String (Hex.encode (hash), "US-ASCII")); cacheKey = c.toString (); if ( validSignatureCache.contains (cacheKey) ) { return true; }
The problem is that the fields (sig,pubkey,hash) are concatenated without a separator, so it's possible to "move" bytes from sig to pubkey an viceversa.
POSSIBLE ATTACK
1) The attacker creates one non-standard transactions tx1 with one output 0 whose scriptPubKey is: OP_CHECKSIG (Tx1 is sent directly to a miner, and included in a block)
2) The attacker then creates a correct transaction TxA that spends Tx1 whose scriptSig is: <sig> <pubKey> This transaction must be very large and not include any fees, so it's not included in a block by miners.
When bitsofproof supernode receives TxA by a peer it validates the signature (which is correct) and it adds the (sig|pubkey|hash) to the cache.
3) The attacker creates a transaction TxB similar to TxA in every field except for the scriptSig, which becomes: <sig'> <pubKey'> Where <sig'> = <sig'> | RirstByte(<pubKey'>) and <pubKey'> = RemoveFirstByte(<pubKey'>)
4) The attacker mines a block including TxB.
5) The block is sent to the supernode. Because (sig|pubkey|hash) is in the signature cache of the application, this node accepts the block as valid.
But no other node accepts this block, because TxB has clearly an invalid signature
Maybe there is an easy way to attack using this vulnerability.
POSSIBLE SOLUTION
Add some separators:
c.append (new String (Hex.encode (sig), "US-ASCII")); c.append ("|"); c.append (new String (Hex.encode (pubkey), "US-ASCII")); c.append ("|"); c.append (new String (Hex.encode (hash), "US-ASCII"));
Best regards, Sergio Lerner
|
|
|
|
mskwik
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:00:12 PM |
|
Doesn't changing the length of the sig and pubkey also change the hash?
|
|
|
|
apetersson
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:09:18 PM |
|
i would have proposed standard java object oriented notation. create a value object (all final values) of the key, provide efficient equal/hashcode implementations, build a Cache from that. that way the impl. is both correct and the fastest possible.
|
|
|
|
apetersson
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:20:22 PM |
|
i would implement it as such: http://pastebin.com/FAT80Xh0i have still some trouble getting the ivy/dependencies to run cleanly on my machine therefore i submit this here instead of a pull req.
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:21:35 PM |
|
Regarding the attack: I think the attack would not work since the hash part of the key would be different with other than 0 out value. Nevertheless the point is fair, separators would be appropriate here to cast any doubt. I suggest to raise these issues on the github link below, so I can refer them in code/version as resolved. i would have proposed standard java object oriented notation. create a value object (all final values) of the key, provide efficient equal/hashcode implementations, build a Cache from that. that way the impl. is both correct and the fastest possible.
Object key would not work since the byte arrays are instantiated from the script, their content matches, not their identity.
|
|
|
|
apetersson
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:25:13 PM |
|
Object key would not work since the byte arrays are instantiated from the script, their content matches, not their identity.
well, thats why i provided you with a clean equals + hashCode method for your pleasure ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) is there any particular reason why you use edu.emory.mathcs.backport.java.util.Arrays ? the one from java.util works just fine imo. edit: after re-reading the code provided - i think you can squeeze out performance by using only partial data of the arrays in hashCode() - maybe just the last 2 bytes from hash array.
|
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:31:52 PM |
|
Yes, but the value part of the TxOut structure would be different isn't it ? That is part of the hash.
|
|
|
|
Sergio_Demian_Lerner (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:33:14 PM |
|
Yes, but the value part of the TxOut structure would be different isn't it ? That is part of the hash. IMHO, No. The only difference between TxA and TxB is the signature and the public key, and both are removed before the hash is calculated.
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:36:12 PM |
|
is there any particular reason why you use edu.emory.mathcs.backport.java.util.Arrays ? the one from java.util works just fine imo.
That must have been a false auto import by eclipse. Thanks for pointing out, I delete it.
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 09:56:42 PM |
|
IMHO, No. The only difference between TxA and TxB is the signature and the public key, and both are removed before the hash is calculated.
So there is no change in value, that I assumed. Then hash is same. Still does not work, since the signature cache is only valid for the transaction in question, thereafter evicted, since there is no chance other transactions produce the same hash. The cache is only an optimization for several inputs using same key. The cache is transaction scope also since I do parallel validation of transactions of a block on a number of threads.
|
|
|
|
mskwik
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 12, 2012, 10:20:15 PM |
|
IMHO, No. The only difference between TxA and TxB is the signature and the public key, and both are removed before the hash is calculated.
So there is no change in value, that I assumed. Then hash is same. Still does not work, since the signature cache is only valid for the transaction in question, thereafter evicted, since there is no chance other transactions produce the same hash. The cache is only an optimization for several inputs using same key. The cache is transaction scope also since I do parallel validation of transactions of a block on a number of threads. Ok, actually went and found the code in question. Yes it does appear that the hash is the same because it is generated from the tx to sign, not the full tx. So no the attack will not work as described, but it does seem that one could get it to accept an invalid transaction such that the first signature in the transaction was correct but a later input with the same key could have an invalid signature like the one described in the original post and still get accepted due to the cache.
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 13, 2012, 05:51:06 AM Last edit: November 13, 2012, 06:32:55 AM by grau |
|
Ok, actually went and found the code in question. Yes it does appear that the hash is the same because it is generated from the tx to sign, not the full tx. So no the attack will not work as described, but it does seem that one could get it to accept an invalid transaction such that the first signature in the transaction was correct but a later input with the same key could have an invalid signature like the one described in the original post and still get accepted due to the cache.
The point is that signature is correct, if it is correct for the hash and public key combination. This is not violated by the code. If the hash would not contain information needed, then this would be a design problem for the bitcoin protocol itself, since the bitsofproof supernode implements that correctly (otherwise it would not validate the entire chain and testnet3). Let us think about this longer...
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 13, 2012, 07:29:18 AM |
|
A byproduct of your scrutiny is that I found that the scope of synchronization around the signature validation was wider than necessary, reduced it: https://github.com/bitsofproof/supernode/commit/b750ef94a7f00756fd4fa2afe9a532caa4cf76e0and it gives a real boost on my server. well, thats why i provided you with a clean equals + hashCode method for your pleasure ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) This is nice, would you mind submitting a pull since copy from pastebin failed to patch for me? Thanks a lot to all of you, this is exactly the feedback I expected and opened the source for !
|
|
|
|
mskwik
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 13, 2012, 03:32:22 PM |
|
The point is that signature is correct, if it is correct for the hash and public key combination. This is not violated by the code.
It's not necessarily a point of it being incorrect, yes it does still prove ownership of the associated private key when put together properly but if it is handled differently than the satoshi client it could cause problems. Here's a raw TX example which is not validated by the default client but seems (if I did the manipulation right by hand) like it should get past your code. 0100000002979bf5e04fb980f214c7b8f3ca28ebd1526fde456953210532e42246843e199f2f000 0008b48304502210081eaa77b0dcef66c0d0e62dafe932503cd8ab8bd83e4d132c9b42fd5a5be90 4202204a281c9c320f60b4a11bd7f162d8296d8246a13a43bc9e5e6fe831e8587bd8d9014104c55 f8edc724bc89b356bc1280f720b27e62839743e549d51bd9d537bd168b3b36f655b87f5aa492c15 eec23120f87abe36693830608a0f91b325a4f76570daf1ffffffffb1d3647334b5531f4831a48e1 fdda96472bd11b95140f0baf7fca5836854d45f2f0000008b49304502210081eaa77b0dcef66c0d 0e62dafe932503cd8ab8bd83e4d132c9b42fd5a5be904202204a281c9c320f60b4a11bd7f162d82 96d8246a13a43bc9e5e6fe831e8587bd8d9010440c55f8edc724bc89b356bc1280f720b27e62839 743e549d51bd9d537bd168b3b36f655b87f5aa492c15eec23120f87abe36693830608a0f91b325a 4f76570daf1ffffffff010d787000000000001976a914fe9c3e50dd8a5263571764dfa9e80300d1 5f612188ac00000000
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 13, 2012, 10:37:07 PM |
|
Parsed in the transaction and it reads as below. The second input has wrong length for the first push therefore it takes up the first byte from the pub key. This will not validate in Satoshi and not in bitsofproof. { "hash":"6b3a189c0e2ea87ceb878eb1efbc367d5338498a7c92f29e7afa26558524afcf", "version":1, "inputs":[ { "sourceHash":"9f193e844622e4320521536945de6f52d1eb28caf3b8c714f280b94fe0f59b97", "sourceIx":47, "script":"304502210081eaa77b0dcef66c0d0e62dafe932503cd8ab8bd83e4d132c9b42fd5a5be904202204a281c9c320f60b4a11bd7f162d8296d8246a13a43bc9e5e6fe831e8587bd8d901 04c55f8edc724bc89b356bc1280f720b27e62839743e549d51bd9d537bd168b3b36f655b87f5aa492c15eec23120f87abe36693830608a0f91b325a4f76570daf1", "sequence":4294967295 }, { "sourceHash":"5fd4546883a5fcf7baf04051b911bd7264a9dd1f8ea431481f53b5347364d3b1", "sourceIx":47, "script":"304502210081eaa77b0dcef66c0d0e62dafe932503cd8ab8bd83e4d132c9b42fd5a5be904202204a281c9c320f60b4a11bd7f162d8296d8246a13a43bc9e5e6fe831e8587bd8d90104 c55f8edc724bc89b356bc1280f720b27e62839743e549d51bd9d537bd168b3b36f655b87f5aa492c15eec23120f87abe36693830608a0f91b325a4f76570daf1", "sequence":4294967295 } ], "outputs":[ { "value":7370765, "script":"OP_DUP OP_HASH160 fe9c3e50dd8a5263571764dfa9e80300d15f6121 OP_EQUALVERIFY OP_CHECKSIG" } ], "lockTime":0 }
|
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4242
Merit: 8647
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 14, 2012, 06:43:13 PM |
|
since the bitsofproof supernode implements that correctly (otherwise it would not validate the entire chain and testnet3). Let us think about this longer...
Validating the existing chain is _NOT_ proof that it implements it correctly. To be correct all implementations must accept AND reject the same things. Most possible things are not in the chains because, if for no other reason, most possible things are rejected. Grau, Please confirm that you understand this. It's very important.
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 14, 2012, 07:59:44 PM |
|
since the bitsofproof supernode implements that correctly (otherwise it would not validate the entire chain and testnet3). Let us think about this longer...
Validating the existing chain is _NOT_ proof that it implements it correctly. To be correct all implementations must accept AND reject the same things. Most possible things are not in the chains because, if for no other reason, most possible things are rejected. Grau, Please confirm that you understand this. It's very important. I certainly do and I did not state the contrary. I said more than you quoted. Specifically, I started with: The point is that signature is correct, if it is correct for the hash and public key combination. This is not violated by the code.
Now, that the bitsofproof node validates the production and the test chain lowers the probability that it calculates incorrect hashes for signature checking to a negligible magnitude.
|
|
|
|
xblitz
Newbie
Offline
Activity: 32
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 18, 2012, 11:17:12 PM |
|
is there any particular reason why you use edu.emory.mathcs.backport.java.util.Arrays ? the one from java.util works just fine imo.
That must have been a false auto import by eclipse. Thanks for pointing out, I delete it. it seems there are still imports using edu.emory.mathcs.backport.java.util.Arrays like in AddressConverter.java maybe you can fix those too ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
|
|
|
|
grau
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 18, 2012, 11:35:52 PM |
|
I wish I knew why eclipse does that...
I do a grep now.
|
|
|
|
|