6 ms·

Peter Todd (Bitcoin core dev) set up a SHA-1 “Pinata” and it's been claimed

130 points by j_s 10y ago

mrb 10y ago
So it was claimed by reusing the collision data from shattered.io: https://bitcointalk.org/index.php?topic=293382.msg17950195#msg17950195 https://bitcointalk.org/index.php?topic=293382.msg17950195#m... Pretty cool.
- mikeash 10y ago
  I'm really interested in the comment about someone else running a bot that tries a double-spend based on the answer in the original transaction. It sounds like it didn't work, but it could have. Is there a way to set up these sorts of automated challenges in a way that isn't vulnerable to that?
  - jstanley 10y ago
    I can't see how you'd do it for a case like this. The script is just checking that the spender knows 2 pieces of data that are different but have the same SHA1 hash. I can't see a way to do that that can't be easily replayed by somebody else spending to a different address. As soon as the transaction is broadcast, you reveal your 2 pieces of data that are different but have the same SHA1 hash.
    - nullc 10y ago
      Either by using interaction (with a ZKCP) or by using a two phase redemption and a covenant (https://blockstream.com/2016/11/02/covenants-in-elements-alpha.html https://blockstream.com/2016/11/02/covenants-in-elements-alp... which requires OP_CAT and friends which are disabled but could easily be reenabled after the segwit improvement to Bitcoin).
      - jstanley 10y ago
        Fascinating stuff, thanks!
      - just_one_time_ 10y ago
        Please don't listen to/encourage this guy, he is a well known purveyor of false information, from Wikipedia vandalism to Reddit censorship. He is now trying to insinuate himself into Bitcoin as if he were some kind of expert not just a professional internet troll. 9:10 he is lying, confused or just being a jerk for no reason.
  - kolinko 10y ago
    It's possible in Ethereum. You set a two-step process, in the first step you claim the solution - providing a hash of it, and your address. In the second step (in the next block), you provide the solution, and a smart contract can only send money to the address you provided in the first step.
    - nullc 10y ago
      It's possible in Bitcoin too and not just for the kind of trivial program you could plausible execute in a public blockchain. https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ https://bitcoincore.org/en/2016/02/26/zero-knowledge-conting... (And to not put too fine a point on it: the existing track record of ethereum smart contracts suggests that if such a bounty had been created there it would have simply been stolen due to contract/vm flaws by now.)
    - SergeAx 10y ago
      > you claim the solution - providing a hash of it, and your address Unless it is SHA-1 hash :)
  - ikeboy 10y ago
    Discussed in https://www.reddit.com/r/Bitcoin/comments/1mavh9/trustless_bitcoin_bounty_for_sha1_sha256_etc/cc7fiqe/ https://www.reddit.com/r/Bitcoin/comments/1mavh9/trustless_b... You'd need a system supporting zero knowledge proofs.
    - mikeash 10y ago
      Excellent post, thanks for linking to it.
  - DINKDINK 10y ago
    In addition to the zero knowledge proof points discussed below, one could (if they had the mean) to not publish the tx but include it in a block that they work on privately. It's not fool proof (once you announce the block, you've only given yourself one block worth of proof of work lead and an attacker could copy your proof and include it in a competing chain) ZKCP is a much more robust solution.
- illumin8 10y ago
  How much BTC did he get?
  - jstanley 10y ago
    https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2c... 2.48 BTC
    - tyingq 10y ago
      ~$2860 USD. Fairly good payoff for probably setting up a Google Alert and a small amount of scripting.
  - deleted 10y ago
    [deleted]
  - mrb 10y ago
    2.48 BTC, valued at 2800 USD at the moment.
j_s 10y ago
BitBet: A SHA1 collision will be found before the end of 2017 https://bitbet.us/bet/1351/a-sha1-collision-will-be-found-before-the/ https://bitbet.us/bet/1351/a-sha1-collision-will-be-found-be...
- tyingq 10y ago
  One of the "no" bets was for ~7.4 BTC (~$8500 USD). Interesting that somebody was willing to lay down that much.
  - edaemon 10y ago
    There was also an 8 BTC (~$9250 USD) bet placed on "Yes" two days before the collision announcement.
    - nullc 10y ago
      even knowing about these things in advance, the risk that the site loses your funds is so great that it's not very attractive to bet on these things.
      - fru2013 10y ago
        The site publishes the bitcoin txids + addresses so it is trivial to verify whether they are paying out the winnings.
        Y_Y 10y ago
        I think the issue is that like any other outfit that holds bitcoin they may just "lose" them and vanish.
        nullc 10y ago
        Until they don't. Other betting sites have 'lost' everyone's coins.
- jerf 10y ago
metaglog 10y ago
Apparently this was the winning script: https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc?show_adv=true https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2c... If you 'unhexlify' both hex strings on that page, you can see that the first 320 bytes of each PDF from shattered.io were used as input. In [1]: import binascii, hashlib In [2]: input1 = binascii.unhexlify('255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034 ...: 203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706 ...: f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2 ...: 560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70 ...: f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1') In [3]: input2 = binascii.unhexlify('255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034 ...: 203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706 ...: f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2 ...: 560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71 ...: f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1') In [4]: input1[:8], input2[:8] Out[4]: ('%PDF-1.3', '%PDF-1.3') In [5]: hashlib.sha1(input1).hexdigest() == hashlib.sha1(input2).hexdigest() Out[5]: True
vinhboy 10y ago
This thread seriously need a ELI5... or ELI don't have a degree in Mathematics.
- danbruc 10y ago
  When you send Bitcoins you are not really sending them to any recipient but you place them in the block chain and attach a challenge. Everyone who can solve a challenge can spend the coins associated with this challenge. Usually the challenge is to prove that you have the private key to a public key included in the challenge so that the public key can function as an address for you and only you can spend the coins because only you have the private key. But in this case Peter Todd placed 2.48 BTC in the block chain with the challenge to provide two different but otherwise arbitrary pieces of data yielding the same SHA-1 hashes. Someone now used the collision generated by Google to spend those coins.
  - ninov 10y ago
    Can everyone place a custom challenge in the Bitcoin blockchain?
    - danbruc 10y ago
      Yes, challenge and response are just small programs. Every transaction is essentially just two small programs, one that solves the current challenge proving that you are allowed to spent the coins and a new challenge to be solved by the next one who wants to spent the coins.
      - euyyn 10y ago
        So the way to "collect" those coins is to post the solution to the hash collision and, as a followup challenge, something encrypted with your public key so only you can decrypt it later on. Correct?
        danbruc 10y ago
mrfusion 10y ago
I have no idea what's going on. Is this bad for bitcoin?
- bitexploder 10y ago
  No. Bitcoin uses "scripts" to validate transactions. It is a small turing-incomplete language with specialized operators that let you perform comparisons and such. This script was set up such that you could spend the coins if you could make a hash collision in SHA1.
deleted 10y ago
[deleted]

130 points by j_s 10y ago

mrb 10y ago

So it was claimed by reusing the collision data from shattered.io: https://bitcointalk.org/index.php?topic=293382.msg17950195#msg17950195 https://bitcointalk.org/index.php?topic=293382.msg17950195#m... Pretty cool.

mikeash 10y ago
I'm really interested in the comment about someone else running a bot that tries a double-spend based on the answer in the original transaction. It sounds like it didn't work, but it could have. Is there a way to set up these sorts of automated challenges in a way that isn't vulnerable to that?
- jstanley 10y ago
  I can't see how you'd do it for a case like this. The script is just checking that the spender knows 2 pieces of data that are different but have the same SHA1 hash. I can't see a way to do that that can't be easily replayed by somebody else spending to a different address. As soon as the transaction is broadcast, you reveal your 2 pieces of data that are different but have the same SHA1 hash.
  - nullc 10y ago
    Either by using interaction (with a ZKCP) or by using a two phase redemption and a covenant (https://blockstream.com/2016/11/02/covenants-in-elements-alpha.html https://blockstream.com/2016/11/02/covenants-in-elements-alp... which requires OP_CAT and friends which are disabled but could easily be reenabled after the segwit improvement to Bitcoin).
    - jstanley 10y ago
      Fascinating stuff, thanks!
    - just_one_time_ 10y ago
      Please don't listen to/encourage this guy, he is a well known purveyor of false information, from Wikipedia vandalism to Reddit censorship. He is now trying to insinuate himself into Bitcoin as if he were some kind of expert not just a professional internet troll. 9:10 he is lying, confused or just being a jerk for no reason.
- kolinko 10y ago
  It's possible in Ethereum. You set a two-step process, in the first step you claim the solution - providing a hash of it, and your address. In the second step (in the next block), you provide the solution, and a smart contract can only send money to the address you provided in the first step.
  - nullc 10y ago
    It's possible in Bitcoin too and not just for the kind of trivial program you could plausible execute in a public blockchain. https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ https://bitcoincore.org/en/2016/02/26/zero-knowledge-conting... (And to not put too fine a point on it: the existing track record of ethereum smart contracts suggests that if such a bounty had been created there it would have simply been stolen due to contract/vm flaws by now.)
  - SergeAx 10y ago
    > you claim the solution - providing a hash of it, and your address Unless it is SHA-1 hash :)
- ikeboy 10y ago
  Discussed in https://www.reddit.com/r/Bitcoin/comments/1mavh9/trustless_bitcoin_bounty_for_sha1_sha256_etc/cc7fiqe/ https://www.reddit.com/r/Bitcoin/comments/1mavh9/trustless_b... You'd need a system supporting zero knowledge proofs.
  - mikeash 10y ago
    Excellent post, thanks for linking to it.
- DINKDINK 10y ago
  In addition to the zero knowledge proof points discussed below, one could (if they had the mean) to not publish the tx but include it in a block that they work on privately. It's not fool proof (once you announce the block, you've only given yourself one block worth of proof of work lead and an attacker could copy your proof and include it in a competing chain) ZKCP is a much more robust solution.
illumin8 10y ago
How much BTC did he get?
- jstanley 10y ago
  https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2c... 2.48 BTC
  - tyingq 10y ago
    ~$2860 USD. Fairly good payoff for probably setting up a Google Alert and a small amount of scripting.
- deleted 10y ago
  [deleted]
- mrb 10y ago
  2.48 BTC, valued at 2800 USD at the moment.

j_s 10y ago

BitBet: A SHA1 collision will be found before the end of 2017 https://bitbet.us/bet/1351/a-sha1-collision-will-be-found-before-the/ https://bitbet.us/bet/1351/a-sha1-collision-will-be-found-be...

tyingq 10y ago
One of the "no" bets was for ~7.4 BTC (~$8500 USD). Interesting that somebody was willing to lay down that much.
- edaemon 10y ago
  There was also an 8 BTC (~$9250 USD) bet placed on "Yes" two days before the collision announcement.
  - nullc 10y ago
    even knowing about these things in advance, the risk that the site loses your funds is so great that it's not very attractive to bet on these things.
    - fru2013 10y ago
      The site publishes the bitcoin txids + addresses so it is trivial to verify whether they are paying out the winnings.
      - Y_Y 10y ago
        I think the issue is that like any other outfit that holds bitcoin they may just "lose" them and vanish.
      - nullc 10y ago
        Until they don't. Other betting sites have 'lost' everyone's coins.
jerf 10y ago

metaglog 10y ago

Apparently this was the winning script: https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc?show_adv=true https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2c... If you 'unhexlify' both hex strings on that page, you can see that the first 320 bytes of each PDF from shattered.io were used as input. In [1]: import binascii, hashlib In [2]: input1 = binascii.unhexlify('255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034 ...: 203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706 ...: f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2 ...: 560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70 ...: f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1') In [3]: input2 = binascii.unhexlify('255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034 ...: 203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706 ...: f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2 ...: 560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71 ...: f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1') In [4]: input1[:8], input2[:8] Out[4]: ('%PDF-1.3', '%PDF-1.3') In [5]: hashlib.sha1(input1).hexdigest() == hashlib.sha1(input2).hexdigest() Out[5]: True

vinhboy 10y ago

This thread seriously need a ELI5... or ELI don't have a degree in Mathematics.

danbruc 10y ago
When you send Bitcoins you are not really sending them to any recipient but you place them in the block chain and attach a challenge. Everyone who can solve a challenge can spend the coins associated with this challenge. Usually the challenge is to prove that you have the private key to a public key included in the challenge so that the public key can function as an address for you and only you can spend the coins because only you have the private key. But in this case Peter Todd placed 2.48 BTC in the block chain with the challenge to provide two different but otherwise arbitrary pieces of data yielding the same SHA-1 hashes. Someone now used the collision generated by Google to spend those coins.
- ninov 10y ago
  Can everyone place a custom challenge in the Bitcoin blockchain?
  - danbruc 10y ago
    Yes, challenge and response are just small programs. Every transaction is essentially just two small programs, one that solves the current challenge proving that you are allowed to spent the coins and a new challenge to be solved by the next one who wants to spent the coins.
    - euyyn 10y ago
      So the way to "collect" those coins is to post the solution to the hash collision and, as a followup challenge, something encrypted with your public key so only you can decrypt it later on. Correct?
      - danbruc 10y ago

mrfusion 10y ago

I have no idea what's going on. Is this bad for bitcoin?

bitexploder 10y ago
No. Bitcoin uses "scripts" to validate transactions. It is a small turing-incomplete language with specialized operators that let you perform comparisons and such. This script was set up such that you could spend the coins if you could make a hash collision in SHA1.

deleted 10y ago

[deleted]