Bitcoin Forum
August 22, 2018, 06:11:19 AM *
News: Latest stable version of Bitcoin Core: 0.16.2  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: REWARD offered for hash collisions for SHA1, SHA256, RIPEMD160 and other  (Read 38413 times)
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1106
Merit: 1000


View Profile
September 13, 2013, 06:19:33 AM
 #1

Rewards at the following P2SH addresses are available for anyone able to demonstrate collision attacks against a variety of cryptographic algorithms. You collect your bounty by demonstrating two messages that are not equal in value, yet result in the same digest when hashed. These messages are used in a scriptSig, which satisfies the scriptPubKey storing the bountied funds, allowing you to move them to a scriptPubKey (Bitcoin address) of your choice.

Further donations to the bounties are welcome, particularly for SHA1 - address 37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP - for which an attack on a single hash value is believed to be possible at an estimated cost of $2.77M (4)

Details below; note that the "decodescript" RPC command is not yet released; compile bitcoind from the git repository at http://github.com/bitcoin/bitcoin

SHA1:

$ btc decodescript 6e879169a77ca787
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP"
}


SHA256:

$ btc decodescript 6e879169a87ca887
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA256 OP_SWAP OP_SHA256 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "35Snmmy3uhaer2gTboc81ayCip4m9DT4ko"
}


RIPEMD160:

$ btc decodescript 6e879169a67ca687
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_RIPEMD160 OP_SWAP OP_RIPEMD160 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "3KyiQEGqqdb4nqfhUzGKN6KPhXmQsLNpay"
}


RIPEMD160(SHA256()):

$ btc decodescript 6e879169a97ca987
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_HASH160 OP_SWAP OP_HASH160 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "39VXyuoc6SXYKp9TcAhoiN1mb4ns6z3Yu6"
}


SHA256(SHA256()):

$ btc decodescript 6e879169aa7caa87
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_HASH256 OP_SWAP OP_HASH256 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "3DUQQvz4t57Jy7jxE86kyFcNpKtURNf1VW"
}

and last but not least, the absolute value function:

$ btc decodescript 6e879169907c9087
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_ABS OP_SWAP OP_ABS OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "3QsT6Sast6ghfsjZ9VJj9u8jkM2qTfDgHV"
}

For example, this pair of transactions created, and then collected, an
absolute value function bounty:

0100000001f3194f7c2a39809d6ea5fa2db68326932df146aaab7be2f398a524bd269d0b6200000 0008a473044022039bc13cb7fe565ff2e14b16fbc4a9facd36b25a435d2f49de4534463212aeaee 022076413c7591385cd813df37d8104dd8110745c28178cef829b5ab3e56b7c30d22014104d3477 5baab521d7ba2bd43997312d5f663633484ae1a4d84246866b7088297715a049e2288ae16f16880 9d36e2da1162f03412bf23aa5f949f235eb2e7141783ffffffff03207e7500000000001976a9149 bc0bbdd3024da4d0c38ed1aecf5c68dd1d3fa1288ac0000000000000000126a6e879169907c9087 086e879169907c908740420f000000000017a914fe441065b6532231de2fac563152205ec4f59c7 48700000000

0100000001f18cda90bbbcfb031c65ceda17c82dc046c7db0b96242ba4c5b53c411d8c056e02000 0000c510181086e879169907c9087ffffffff01a0bb0d00000000001976a9149bc0bbdd3024da4d 0c38ed1aecf5c68dd1d3fa1288ac00000000

Specifically with the scriptSig: 1 -1 6e879169907c9087


Notes:

1) We advise mining the block in which you collect your bounty yourself; scriptSigs satisfying the above scriptPubKeys do not cryptographically sign the transaction's outputs. If the bounty value is sufficiently large other miners may find it profitable to reorganize the chain to kill your block and collect the reward themselves. This is particularly profitable for larger, centralized, mining pools.

2) Note that the value of your SHA256, RIPEMD160, RIPEMD160(SHA256()) or SHA256^2 bounty may be diminished by the act of collecting it.

3) Due to limitations of the Bitcoin scripting language bounties can only be collected with solutions using messages less than 521 bytes in size.

4) "When Will We See Collisions for SHA-1?" - Bruce Schneier -https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html

1534918279
Hero Member
*
Offline Offline

Posts: 1534918279

View Profile Personal Message (Offline)

Ignore
1534918279
Reply with quote  #2

1534918279
Report to moderator
1534918279
Hero Member
*
Offline Offline

Posts: 1534918279

View Profile Personal Message (Offline)

Ignore
1534918279
Reply with quote  #2

1534918279
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2478
Merit: 1384



View Profile
September 13, 2013, 06:52:39 AM
 #2

I wrote up little description of how these scripts work on reddit.  This might be an honorable use for any "tainted" coins you have that you don't want associated with your identity and important outputs to watch if you want to learn about impressive cryptographic breakthroughs.

Bitcoin will not be compromised
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 500



View Profile WWW
September 13, 2013, 08:48:16 AM
 #3

This is both incredibly fascinating, and a beautiful show of the kinds of innovation the Bitcoin system supports!

cypherdoc
Legendary
*
Offline Offline

Activity: 1764
Merit: 1002



View Profile
September 13, 2013, 11:33:02 AM
 #4

Not to take away from Peters wonderful challenge to the world but shouldn't this have been better directed at the ECDSA weaknesses implied by Schnier assuming of course this was his motivation for posting this?
TierNolan
Legendary
*
Offline Offline

Activity: 1190
Merit: 1001


View Profile
September 13, 2013, 12:14:34 PM
 #5

Not to take away from Peters wonderful challenge to the world but shouldn't this have been better directed at the ECDSA weaknesses implied by Schnier assuming of course this was his motivation for posting this?

All of Satoshi's coins are a reward for breaking the ECDSA, since they are not protected by the RIPEMD160 hash function.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
cypherdoc
Legendary
*
Offline Offline

Activity: 1764
Merit: 1002



View Profile
September 13, 2013, 01:04:02 PM
 #6

Not to take away from Peters wonderful challenge to the world but shouldn't this have been better directed at the ECDSA weaknesses implied by Schnier assuming of course this was his motivation for posting this?

All of Satoshi's coins are a reward for breaking the ECDSA, since they are not protected by the RIPEMD160 hash function.

Well they are as a public key is protected by an unspent address.
jackjack
Legendary
*
Offline Offline

Activity: 1134
Merit: 1013


May Bitcoin be touched by his Noodly Appendage


View Profile
September 13, 2013, 01:08:21 PM
 #7

Not to take away from Peters wonderful challenge to the world but shouldn't this have been better directed at the ECDSA weaknesses implied by Schnier assuming of course this was his motivation for posting this?

All of Satoshi's coins are a reward for breaking the ECDSA, since they are not protected by the RIPEMD160 hash function.

Well they are as a public key is protected by an unspent address.

No they aren't. Satoshi's early public keys aren't protected by anything.

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
DannyHamilton
Legendary
*
Offline Offline

Activity: 2198
Merit: 1371



View Profile
September 13, 2013, 01:15:58 PM
 #8

- snip -

2) Note that the value of your SHA256, RIPEMD160, RIPEMD160(SHA256()) or SHA256^2 bounty may be diminished by the act of collecting it.

- snip -

 Grin  Grin  Grin

cypherdoc
Legendary
*
Offline Offline

Activity: 1764
Merit: 1002



View Profile
September 13, 2013, 01:27:27 PM
 #9

Not to take away from Peters wonderful challenge to the world but shouldn't this have been better directed at the ECDSA weaknesses implied by Schnier assuming of course this was his motivation for posting this?

All of Satoshi's coins are a reward for breaking the ECDSA, since they are not protected by the RIPEMD160 hash function.

Well they are as a public key is protected by an unspent address.

"Satoshi's early public keys"

What are those and how do they compare to what we have today?
TierNolan
Legendary
*
Offline Offline

Activity: 1190
Merit: 1001


View Profile
September 13, 2013, 02:11:34 PM
 #10

What are those and how do they compare to what we have today?

The standard transaction is "This coin can be spent by someone who signs the transaction with the private key that matches a public key that hashes to <hash>".

To spend that, you need to provide the public key and then sign it.  Even if the signature algorithm was broken, those coins couldn't be spent, since the attacker wouldn't know the public key.  This is one of the reasons why re-using addresses is a bad idea.  Once you spend money from the address, you give away the public key.

The original transactions were "This coin can be spent by someone who signs the transactions with the private key that matches <some public key>".  If the signature algorithm is broken, then those coins can be spent by the attacker, since he would know the public key.

The updated system requires the hashing function and the signing algorithm to be broken at around the same time.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
cypherdoc
Legendary
*
Offline Offline

Activity: 1764
Merit: 1002



View Profile
September 13, 2013, 02:22:37 PM
 #11

What are those and how do they compare to what we have today?

The standard transaction is "This coin can be spent by someone who signs the transaction with the private key that matches a public key that hashes to <hash>".

To spend that, you need to provide the public key and then sign it.  Even if the signature algorithm was broken, those coins couldn't be spent, since the attacker wouldn't know the public key.  This is one of the reasons why re-using addresses is a bad idea.  Once you spend money from the address, you give away the public key.

The original transactions were "This coin can be spent by someone who signs the transactions with the private key that matches <some public key>".  If the signature algorithm is broken, then those coins can be spent by the attacker, since he would know the public key.

The updated system requires the hashing function and the signing algorithm to be broken at around the same time.

interesting.  i never knew that the original Bitcoin didn't involve Hash160's.

but doesn't this get back to the point i was making to you that pubkeys are in fact more moderately protected by unspent addresses, ie Hash160's, of those pubkeys?

furthermore, my original point was i'd love to see Peter erect a scripting challenge to hack an ECDSA-related problem that Schnier so blatantly highlighted.
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1001


View Profile
September 13, 2013, 04:03:46 PM
 #12

No, there's no relation between a pubkey and a pubkey-hash. Once the pubkey is known, hash160 isn't relevant at all. Coinbase transactions in the pre-pool days were simply the public key and OP_CHECKSIG. "All" you have to spend this is find a way to generate a signature from the public key only. No hash preimage is required.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2478
Merit: 1384



View Profile
September 13, 2013, 04:45:12 PM
 #13

Not to take away from Peters wonderful challenge to the world but shouldn't this have been better directed at the ECDSA weaknesses implied by Schnier assuming of course this was his motivation for posting this?
I don't believe there is a way to construct such a thing— beyond all the coins which are pay to pubkey (e.g. early unspent blocks) and all the coins which are assigned to addresses which have spent before so the pubkey is known.

I'm not sure if anyone has identified any known-lost pay to pubkeys which can be redeemed without stealing from someone. Might be good for someone to do that.

Bitcoin will not be compromised
jgarzik
Legendary
*
qt
Offline Offline

Activity: 1554
Merit: 1001


View Profile
September 13, 2013, 08:03:29 PM
 #14

Added 1.0 BTC to SHA1 bounty.

Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
Visit bloq.com / metronome.io
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
Carlton Banks
Legendary
*
Offline Offline

Activity: 2100
Merit: 1320



View Profile
September 13, 2013, 09:39:34 PM
 #15

Is there a way to know that someone hasn't already tested such a possibility? And that this (government backed security services employed) someone has not publicly disclosed it? I would suggest not, although I'd like to hear commentary from the more technically informed.

Vires in numeris
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2478
Merit: 1384



View Profile
September 13, 2013, 09:57:28 PM
 #16

And that this (government backed security services employed) someone has not publicly disclosed it
They now have a way to get paid a bit for anonymously disclosing it. How sure do you want to be? Insert coins.

Bitcoin will not be compromised
iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 250


View Profile
September 16, 2013, 10:08:10 AM
 #17

The updated system requires the hashing function and the signing algorithm to be broken at around the same time.

You need a preimage attack on the hash function where the preimage is a valid pubkey for which you know the corresponding privkey. There are about 2^256 pubkeys and 2^160 hashed addresses, so the attacker has to find one ECDSA keypair as the preimage out of about 2^96 possible candidates.

It's true to say that if the hash function is resistant to preimage attacks then we have 160 bits of security, compared to the 128 bits of security of ECDSA with 256 bit security parameter. But saying that the attacker must break both the hash function and ECDSA is too strong.
Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2422
Merit: 1011



View Profile
December 20, 2013, 12:25:43 AM
 #18

Not to take away from Peters wonderful challenge to the world but shouldn't this have been better directed at the ECDSA weaknesses implied by Schnier assuming of course this was his motivation for posting this?

All of Satoshi's coins are a reward for breaking the ECDSA, since they are not protected by the RIPEMD160 hash function.
Stealing someone's coins by breaking ECDSA is not the same as a reward specifically for breaking something.

Also, this has nothing to do with "Satoshi's coins". All block rewards generated by bitcoind's internal miner or getwork are at risk.

gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2478
Merit: 1384



View Profile
December 20, 2013, 12:47:10 AM
 #19

are at risk.
In context, of course— thats assuming a compromise of ECC on our curve. Smiley

Bitcoin will not be compromised
oakpacific
Hero Member
*****
Offline Offline

Activity: 798
Merit: 1000


View Profile
December 20, 2013, 08:59:35 AM
 #20

Someone please produce a news article with this sensational title :" The Bitcoin creator's $ 1 billion hidden reward to those who break NSA's super secret algorithm".

https://tlsnotary.org/ Fraud proofing decentralized fiat-Bitcoin trading.
Pages: [1] 2 »  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!