[Bitcoin-development] REWARD offered for hash collisions for SHA1, SHA256, RIPEMD160 and others

[Peter Todd <pete@petertodd.org>]

[-- Attachment #1: Type: text/plain, Size: 4108 bytes --]

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:

0100000001f3194f7c2a39809d6ea5fa2db68326932df146aaab7be2f398a524bd269d0b62000000008a473044022039bc13cb7fe565ff2e14b16fbc4a9facd36b25a435d2f49de4534463212aeaee022076413c7591385cd813df37d8104dd8110745c28178cef829b5ab3e56b7c30d22014104d34775baab521d7ba2bd43997312d5f663633484ae1a4d84246866b7088297715a049e2288ae16f168809d36e2da1162f03412bf23aa5f949f235eb2e7141783ffffffff03207e7500000000001976a9149bc0bbdd3024da4d0c38ed1aecf5c68dd1d3fa1288ac0000000000000000126a6e879169907c9087086e879169907c908740420f000000000017a914fe441065b6532231de2fac563152205ec4f59c748700000000

0100000001f18cda90bbbcfb031c65ceda17c82dc046c7db0b96242ba4c5b53c411d8c056e020000000c510181086e879169907c9087ffffffff01a0bb0d00000000001976a9149bc0bbdd3024da4d0c38ed1aecf5c68dd1d3fa1288ac00000000

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

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]