Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

[Tier Nolan <tier.nolan@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 --]