From: Tier Nolan <tier.nolan@gmail•com>
Cc: Bitcoin Dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
Date: Mon, 11 Jan 2016 23:57:59 +0000 [thread overview]
Message-ID: <CAE-z3OUMRivWPVA+3BgC_95MGYBHN34+hoo6xfCu_gNeLFVknA@mail.gmail.com> (raw)
In-Reply-To: <CABsx9T3MfndREm9icE-TUF58zsRZ5YsBMvUAMy4E-MmYWxWV=A@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 1030 bytes --]
On Fri, Jan 8, 2016 at 3:46 PM, Gavin Andresen via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> How many years until we think a 2^84 attack where the work is an ECDSA
> private->public key derivation will take a reasonable amount of time?
>
I think the EC multiply is not actually required. With compressed public
keys, the script selection rule can just be a sha256 call instead.
V is the public key of the victim, and const_pub_key is the attacker's
public key.
if prev_hash % 2 == 0:
script = "2 V 0x02%s 2 CHECKMULTISIG" % (sha256(prev_hash)))
else:
script = "CHECKSIG %s OP_DROP" % (prev_hash, const_pub_key)
next_hash = ripemd160(sha256(script))
If a collision is found, there is a 50% chance that the two scripts have
different parity and there is a 50% chance that a compressed key is a valid
key.
This means that you need to run the algorithm 4 times instead of 2.
The advantage is that each step is 2 sha256 calls and a ripemd160 call. No
EC multiply is required.
[-- Attachment #2: Type: text/html, Size: 1609 bytes --]
next prev parent reply other threads:[~2016-01-11 23:58 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
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 [this message]
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=CAE-z3OUMRivWPVA+3BgC_95MGYBHN34+hoo6xfCu_gNeLFVknA@mail.gmail.com \
--to=tier.nolan@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/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