Bitcoin Forum
March 28, 2024, 11:17:57 PM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 [4]  All
  Print  
Author Topic: [SUCCESS] Double Spend against a satoshidice loss  (Read 19038 times)
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1147


View Profile
January 30, 2013, 05:15:46 AM
Last edit: January 30, 2013, 06:19:01 AM by retep
 #61

So the input wasn't even re-signed.  The old signature was simply left-padded with an extra zero byte, changing the txid.

Just to re-iterate: this kind of modification, transaction malleability, is something that can be done by miners without the person who submitted the transaction even knowing. In other words that "high-roller" may not have had anything to do with the double-spend at all.

It's especially ugly because an evil miner can simply watch the mempool for all losing satoshi-dice transactions, and then modify every one of them and attempt to mine a block filled with now-modified transactions. Of course the miner doesn't know satoshidice's secret, so they can't pick winners or losers - they are essentially rolling the dice again - but for every game with a win probability of p your new win probability will be p + p^2. For instance if you bet on a 50% chance game, you'll now have a 75% chance of winning. On a 25% chance, you'll now have 37.5% chance.

In fact, it can be done by a non-miner who is well connected too: again, watch for satoshidice wins, and this time use a form of transaction malleability that is a standard transaction and thus will be relayed by other nodes. Now immediately broadcast the modified transaction to as many nodes as you can. The vast majority of the time nothing will happen - the modified tx won't be accepted because nodes already have the original - but every once in awhile it will happen to be accepted by a miner and get confirmed.

A simple way to fix this issue would be to first only accept bet transactions whose inputs are confirmed, and secondly change the lucky number algorithm from hmac_sha512(secert,txid:out_idx) to hmac_sha512(secert,txin_1:out_idx | txin_2:out_idx ... | txin_n:out_idx) This works because the betting transaction refers to the txin's by hash, so if you change the betting transaction hash, the lucky number doesn't change, on the other hand the txin's are already confirmed in the chain and can't be changed. Note that you'll need to ensure the SIGHASH bits in the signatures are their standard value; ANYONECANPAY still allows changing the txin set without invalidating the signatures. Of course regular double-spends are still possible, but at least they can't be done by a third party.

Note that having the txin's be confirmed is essential: if they aren't you can pull an even worse version of the same trick by modifying the txin hash, thus invalidating the bet transaction.

EDIT: While we're at it, I also noticed that satoshidice is accepting transactions with non-default SIGHASH's for the signatures. For instance I just made bde69c82fa0870bb156edb334da4a8013d5d385e93608110313a8695184d6365 with the signature using SINGLE|ANYONECANPAY, which means any node on the network is free to add their own inputs and outputs to the transaction provided they do not modify the one input and one output I signed, again changing the tx hash. It's a more minor issue, but it would allow people to setup co-operating decentralized double-spenders without even having to communicate what transactions to double-spend too.

EDIT2: The really interesting thing would be to come up with a form of malleability that is undetectable after the fact. Satoshidice could also just not transmit wins when the second, winning, transaction gets mined. They can prove their honestly by just pointing out that the second tx was modified, and the first was normal. However if you can come up with a form of malleability where both transactions are indistinguishable there will be know way of knowing if the miner turned a win to a loss or vice-versa, and hence satoshidice doesn't have much choice other than paying out the wins. At this point they simply have to change the way wins are calculated.

1711667877
Hero Member
*
Offline Offline

Posts: 1711667877

View Profile Personal Message (Offline)

Ignore
1711667877
Reply with quote  #2

1711667877
Report to moderator
1711667877
Hero Member
*
Offline Offline

Posts: 1711667877

View Profile Personal Message (Offline)

Ignore
1711667877
Reply with quote  #2

1711667877
Report to moderator
Bitcoin mining is now a specialized and very risky industry, just like gold mining. Amateur miners are unlikely to make much money, and may even lose money. Bitcoin is much more than just mining, though!
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
dooglus
Legendary
*
Offline Offline

Activity: 2940
Merit: 1327



View Profile
January 30, 2013, 05:48:43 AM
 #62

Just to re-iterate: this kind of modification, transaction malleability, is something that can be done by miners without the person who submitted the transaction even knowing. In other words that "high-roller" may not have had anything to do with the double-spend at all.

That is a very good point!  Anybody at all can create modified versions of any transaction in that manner and change its txid arbitrarily.  This presents a way for satoshidice to cheat their players too, by transmitting modified versions of winning bets before they confirm.

Just-Dice                 ██             
          ██████████         
      ██████████████████     
  ██████████████████████████ 
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
    ██████████████████████   
        ██████████████       
            ██████           
   Play or Invest                 ██             
          ██████████         
      ██████████████████     
  ██████████████████████████ 
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
    ██████████████████████   
        ██████████████       
            ██████           
   1% House Edge
apetersson
Hero Member
*****
Offline Offline

Activity: 668
Merit: 501



View Profile
January 30, 2013, 12:14:29 PM
 #63

That is a very good point!  Anybody at all can create modified versions of any transaction in that manner and change its txid arbitrarily.
If i understand that correctly, that means SD will be exploited soon by players, well-connected hosts or miners?
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1147


View Profile
January 30, 2013, 04:15:03 PM
 #64

That is a very good point!  Anybody at all can create modified versions of any transaction in that manner and change its txid arbitrarily.
If i understand that correctly, that means SD will be exploited soon by players, well-connected hosts or miners?

Not at all. Remember that the modified transaction still goes to the same place, so SD still gets their money. SD just needs to stop paying out twice when it sees two transactions spending the same input.

Re-read my last point at the bottom about undetectable forms of malleability, and keep in mind it's only an issue because players communicate with SD via the blockchain, and the blockchain is public.

SRoulette
Sr. Member
****
Offline Offline

Activity: 364
Merit: 252



View Profile WWW
February 20, 2013, 07:39:29 AM
 #65

A simple way to fix this issue would be to first only accept bet transactions whose inputs are confirmed, and secondly change the lucky number algorithm from hmac_sha512(secert,txid:out_idx) to hmac_sha512(secert,txin_1:out_idx | txin_2:out_idx ... | txin_n:out_idx)

That is an excellent proposal, one which we will be implementing shortly Smiley

Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1147


View Profile
February 20, 2013, 11:24:52 AM
Last edit: February 20, 2013, 02:17:06 PM by retep
 #66

A simple way to fix this issue would be to first only accept bet transactions whose inputs are confirmed, and secondly change the lucky number algorithm from hmac_sha512(secert,txid:out_idx) to hmac_sha512(secert,txin_1:out_idx | txin_2:out_idx ... | txin_n:out_idx)

That is an excellent proposal, one which we will be implementing shortly Smiley

Good to hear!

One last thing, you also need to mandate that at least one txin signature uses SIGHASH_ALL so the txin list can't be changed after the fact. Once you've taken that step you'll only be vulnerable to regular, miner-supported, double-spends.

EDIT: fixed SIGHASH_NONE brainfart.

Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1128


View Profile
February 20, 2013, 12:07:00 PM
 #67

You meant SIGHASH_ALL, right? SIGHASH_NONE is not generated by any client today and makes a wildcard transaction that can have any outputs.
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1147


View Profile
February 20, 2013, 02:16:20 PM
 #68

You meant SIGHASH_ALL, right? SIGHASH_NONE is not generated by any client today and makes a wildcard transaction that can have any outputs.

Good catch, fixed.

SRoulette
Sr. Member
****
Offline Offline

Activity: 364
Merit: 252



View Profile WWW
February 21, 2013, 11:56:56 AM
Last edit: February 21, 2013, 01:58:38 PM by SRoulette
 #69

Say if you connected to a 1 well connected node (eg slushpool) and used -nolisten, would this also prevent seeing modified versions of the same txid ?
Or is it possible for a non malicious node to rebroadcast the same spending of inputs a 2nd time using a diff signature ?

Quote
In fact, it can be done by a non-miner who is well connected too: again, watch for satoshidice wins, and this time use a form of transaction malleability that is a standard transaction and thus will be relayed by other nodes. Now immediately broadcast the modified transaction to as many nodes as you can. The vast majority of the time nothing will happen - the modified tx won't be accepted because nodes already have the original - but every once in awhile it will happen to be accepted by a miner and get confirmed.

re-reading this I appreciate it a bit more, so by connecting to trusted peers "should" eliminate risk of a re-roll.

Something my code monkey suggested
Code:
# just testing and brain storming alt solutions to this issue on the test engine
hmac_sha512(secret(join(sort(@all_vout_txids)))

Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1147


View Profile
February 21, 2013, 01:58:35 PM
 #70

Say if you connected to a 1 well connected node (eg slushpool) and used -nolisten, would this also prevent seeing modified versions of the same txid ?
Or is it possible for a non malicious node to rebroadcast the same spending of inputs a 2nd time using a diff signature ?

Quote
In fact, it can be done by a non-miner who is well connected too: again, watch for satoshidice wins, and this time use a form of transaction malleability that is a standard transaction and thus will be relayed by other nodes. Now immediately broadcast the modified transaction to as many nodes as you can. The vast majority of the time nothing will happen - the modified tx won't be accepted because nodes already have the original - but every once in awhile it will happen to be accepted by a miner and get confirmed.

re-reading this I appreciate it a bit more, so by connecting to trusted peers "should" eliminate risk of a re-roll.

No, the re-roll there happens because the tx gets mined, and thus the first tx gets removed from your mempool, and you see the second one. After the fact it will look like you received a bet but never paid out.

Something my code monkey suggested
Code:
# just testing and brain storming alt solutions to this issue on the test engine
hmac_sha512(secret(join(sort(@all_vout_txids)))

If sorting the txin's makes it easier to code, that's fine, but remember that regardless you must ensure at least one of the signatures uses SIGHASH_ALL or anyone can add extra txin's and change the lucky number.

SRoulette
Sr. Member
****
Offline Offline

Activity: 364
Merit: 252



View Profile WWW
February 21, 2013, 02:26:59 PM
Last edit: February 21, 2013, 02:38:42 PM by SRoulette
 #71

I see, so the unconfirmed gets broadcasted, then the modified tx double spends it successfully it gets 1 confirmation and is relayed after 1 or more confirmations by all nodes regardless of the first unconfirmed (now invalid) tx.

Very very cool, code monkey and I are looking @ bitcoin Script now, might have to hack up a parser for perl - fortunately it is extremely well documented in the wiki Smiley .
Another suggestion he made is to keep a list of inputs spent against the casino and decline any bets that attempt to reuse the inputs.

edit: seems a perl bitcoin Script implementation already exists Cheesy https://github.com/grondilu/libbitcoin-perl/blob/master/Bitcoin/Script.pm

Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1128


View Profile
February 21, 2013, 02:31:02 PM
 #72

SIGHASH_ALL is the default so it should work fine.
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1147


View Profile
February 21, 2013, 02:34:54 PM
 #73

SIGHASH_ALL is the default so it should work fine.

It may be the default, but if you don't make sure SIGHASH_ALL is actually being used an attacker can make bets and use the malleability as a way of recovering their loses while denying that they did it. I also explained elsewhere how people could agree to help each other recover their loses using this method, and that cooperation can happen without any central co-ordination at all.

dooglus
Legendary
*
Offline Offline

Activity: 2940
Merit: 1327



View Profile
February 21, 2013, 10:17:18 PM
 #74

Another suggestion he made is to keep a list of inputs spent against the casino and decline any bets that attempt to reuse the inputs.

How about just rejecting transactions with non-canonical signatures.  The bot that is making the double-spends is simply adding an extra 00 to the front of one of the signatures.  If you filter out all such transactions you'll be OK.

In the event that the bot's cloned transaction gets mined and the original bet transaction doesn't, it will look as if you ignored a bet, but you can point out that the bet has a non-standard signature which is why you didn't accept it.

Just-Dice                 ██             
          ██████████         
      ██████████████████     
  ██████████████████████████ 
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
    ██████████████████████   
        ██████████████       
            ██████           
   Play or Invest                 ██             
          ██████████         
      ██████████████████     
  ██████████████████████████ 
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
██████████████████████████████
    ██████████████████████   
        ██████████████       
            ██████           
   1% House Edge
Pages: « 1 2 3 [4]  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!