From: Anthony Towns <aj@erisian•com.au>
To: Gavin Andresen <gavinandresen@gmail•com>
Cc: bitcoin-dev@lists•linuxfoundation.org
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
Date: Sat, 9 Jan 2016 01:33:29 +1000 [thread overview]
Message-ID: <20160108153329.GA15731@sapphire.erisian.com.au> (raw)
In-Reply-To: <CABsx9T1gmz=sr_sEEuy8BQU6SXdmi58O30rzRWNW=0Ej98fi4A@mail.gmail.com>
On Fri, Jan 08, 2016 at 07:38:50AM -0500, Gavin Andresen via bitcoin-dev wrote:
> Lets see if I've followed the specifics of the collision attack correctly,
> Ethan (or somebody) please let me know if I'm missing something:
>
> So attacker is in the middle of establishing a payment channel with
> somebody. Victim gives their public key, attacker creates the innocent
> fund-locking script '2 V A 2 CHECKMULTISIG' (V is victim's public key, A
> is attacker's) but doesn't give it to the victim yet.
Using Ethan Heilman's procedure, the attacker can create two scripts:
2 V __A1__ 2 CHECKMULTISIG
2 V __A2__ 2 CHECKMULTISIG
and find values A1 and A2 which hash the scripts to the same result
with under 3*2**80 work. I think you can do that by setting the next
private key as the result of RIPEMD(SHA256(script with pubkey)), so you
could still spend either. But it doesn't change the script, so it's not
*that* helpful -- you've just got two different keys you can use.
Ah, but you can make the form of the script be a function of your key, so:
if privkey % 2 == 0:
script = "2 V %s 2 CHECKMULTISIG" % (pubkey)
else:
script = "%s CHECKSIG" % (pubkey)
hash = ripemd160(sha256(script))
nextprivkey = hash
Then you have a 50% chance of your cycle giving you a matching hash for
one script with A1 and the other script with A2, and you can find the
cycle with under 3*2**80 work. Doing five attempts should give you ~96%
chance of hitting a usable pair, and should take under 15*2**80 work ~=
2**84 work, with trivial memory use.
Trying that in python with a vastly weakened hash function (namely,
the first five bytes of ripemd160(sha256()), with 40 bits of security
and 3*2**20 work) works as expected -- I got a "useful" collision on my
second try in about 7 seconds, seeding with "grumpycat3" ("grumpycat2"
didn't work) with the result being:
hexlify(ripemd160(sha256("foo%sbar"%unhexlify("86f9fbac1a")))[:5])
'ae94d9f908'
hexlify(ripemd160(sha256("baz%squux"%unhexlify("104fc5093f")))[:5])
'ae94d9f908'
Cheers,
aj
next prev parent reply other threads:[~2016-01-08 15:33 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-01-07 19:02 Gavin Andresen
2016-01-07 19:13 ` Matt Corallo
2016-01-07 19:19 ` Adam Back
2016-01-07 20:56 ` Dave Scotese
2016-01-07 21:06 ` Gavin Andresen
2016-01-07 22:56 ` Ethan Heilman
2016-01-07 23:39 ` Gavin Andresen
2016-01-08 1:26 ` Matt Corallo
2016-01-08 1:54 ` Gavin Andresen
2016-01-08 17:38 ` Pieter Wuille
2016-01-08 18:41 ` Peter Todd
2016-01-07 20:40 ` Ethan Heilman
2016-01-07 23:52 ` Pieter Wuille
2016-01-08 1:00 ` Gavin Andresen
2016-01-08 1:27 ` Watson Ladd
2016-01-08 3:30 ` Rusty Russell
2016-01-08 3:41 ` Matt Corallo
2016-01-08 12:02 ` Rusty Russell
2016-01-08 12:38 ` Gavin Andresen
2016-01-08 14:34 ` Watson Ladd
2016-01-08 15:26 ` Adam Back
2016-01-08 15:33 ` Anthony Towns [this message]
2016-01-08 15:46 ` Gavin Andresen
2016-01-08 15:50 ` Gavin Andresen
2016-01-08 15:59 ` Gavin Andresen
2016-01-11 20:32 ` Jorge Timón
2016-01-08 16:06 ` Gavin Andresen
2016-01-11 3:57 ` Rusty Russell
2016-01-11 6:57 ` Peter Todd
2016-01-11 23:57 ` Tier Nolan
2016-01-12 0:00 ` Tier Nolan
2016-01-12 12:08 ` Gavin Andresen
2016-01-12 23:22 ` Zooko Wilcox-O'Hearn
2016-01-08 18:52 ` Peter Todd
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20160108153329.GA15731@sapphire.erisian.com.au \
--to=aj@erisian$(echo .)com.au \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=gavinandresen@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox