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

[Zooko Wilcox-O'Hearn via bitcoin-dev]

Folks:

I don't fully understand this thread, but it sounds like to me it
might be omitting consideration of multi-target attacks. For example,
Tier Nolan's attack
(http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012230.html),
which seems to be the best attack on this thread, seems to start with
one specific public key of an intended victim, but if the attacker is
happy to find a collision with *any* one out of a large number of
potential victims, he gets an advantage proportional to the number of
potential victims.

So it would be wise, in addition to the kind of analysis already done
on this thread (which appears to have already settled at "Yes, we need
> 80-bit security."), to make a nice optimistic estimate of how many
public keys we could eventually have in use. 2⁴⁰? 2⁵⁰? Or maybe be
*very* optimistic, with some added IoT [*] goodness, and budget for
2⁶⁰?

Then we need to budget that many more bits of security to keep the
future attacker's chances of success low enough that the attacker will
never succeed. (Assuming that's our requirement.)

You might enjoy this recent blog post by DJB, legendary cryptographer
who works in this niche of cryptography as well as several other
niches:

http://blog.cr.yp.to/20151120-batchattacks.html

It has some interesting philosophical musings about the "Attacker
Economist" approach. (N.B. My respect for DJB's accomplishments is
tremendous, but that doesn't mean I automatically agree with
everything he says. I haven't made up my mind what I think about this
particular philosophical argument.)

Sincerely,

Zooko

[*] The Internet of Targets
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

I'm convinced-- it is a good idea to worry about 80-bit collision attacks
now.

Thanks to all the people smarter than me who contributed to this
discussion, I learned a lot about collision attacks that I didn't know
before.

Would this be a reasonable "executive summary" :

If you are agreeing to lock up funds with somebody else, and they control
what public key to use, you are susceptible to collision attacks.

It is very likely an 80-bit-collision-in-ten-minutes attack will cost less
than $1million in 10 to twenty years (possibly sooner if there are crypto
breaks in that time).

If you don't trust the person with whom you're locking up funds and you're
locking up a significant amount of money (tens of millions of dollars
today, tens of thousands of dollars in a few years):

Then you should avoid using pay-to-script-hash addresses and instead use
the payment protocol and "raw" multisig outputs.

AND/OR

Have them give you a hierarchical deterministic (BIP32) seed, and derive a
public key for them to use.


--

Following the security in depth and validate all input secure coding
principles would mean doing both-- avoid p2sh AND have all parties to a
transaction exchange HD seeds, add randomness, and use the resulting public
keys in the transaction.


-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Tier Nolan via bitcoin-dev]

On Mon, Jan 11, 2016 at 11:57 PM, Tier Nolan  wrote:
>
> else:
> script = "CHECKSIG %s OP_DROP" % (prev_hash, const_pub_key)
>

That should be

script = "%s CHECKSIG %s OP_DROP" % (const_pub_key, prev_hash)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Tier Nolan via bitcoin-dev]

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.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Jorge Timón via bitcoin-dev]

On Fri, Jan 8, 2016 at 4:50 PM, Gavin Andresen via bitcoin-dev
 wrote:
> And to fend off the messag that I bet somebody is composing right now:
>
> Yes, I know about a "security first" mindset.  But as I said earlier in the
> thread, there is a tradeoff here between crypto strength and code
> complexity, and "the strength of the crypto is all that matters" is NOT
> security first.

If the crypto code is properly encapsulated, the code complexity costs
of choosing one hashing function over another should be non-existent.
You made the space argument which is valid, but in my opinion code
complexity shouldn't be a valid concern in this discussion.

As a maybe uninteresting anecdote, I proposed the asset IDs in
https://github.com/ElementsProject/elements/tree/alpha-0.10-multi-asset
to do the same ```ripemd160 . sha256``` choice that Mark Friedenbach
had proposed and I had approved for
https://github.com/jtimon/freimarkets/blob/master/doc/freimarkets_specs.org#asset-tags
. More humble than me, he admitted he had made a design mistake much
earlier than me, who (maybe paradoxically) probably had less knowledge
for making crypto choices at the low level. In the end I was convinced
with examples I failed to write down for documentation and can't
remember.

That's not to say I have anything to say in this debate other than
code complexity (which I do feel qualified to talk about) shouldn't be
a concern in this debate. Just want to focus the discussion on what it
should be: security vs space tradeoff.
Since I am admittedly in doubt, I tend to prefer to play safe, but
neither my feelings nor my anecdote are logical arguments and should,
therefore, be ignored for any conclusions in the ```ripemd160 .
sha256``` vs sha256d debate. Just like you non-sequitor "sha256d will
lead to more code complexity", if anything, sha256d should be simpler
than ```ripemd160 . sha256``` (but not simpler enough that it matters
much).
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Peter Todd via bitcoin-dev]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA512



On 10 January 2016 22:57:15 GMT-05:00, Rusty
>Cheers,
>Rusty.
>[1] Weirdly, the bitcoin network is doing this much work every 57
>days, for about $92M.  If that's all the attack costs, it's under
>1M in 10 years.

Don't get too caught up in Moore's law here - more likely the attack will 
become feasible because SHA2 is partially weakened, as happened with SHA1. 
Having industry standard safety margins would make such a weakening be an 
academic problem rather than an emergency.
-BEGIN PGP SIGNATURE-

iQE9BAEBCgAnIBxQZXRlciBUb2RkIDxwZXRlQHBldGVydG9kZC5vcmc+BQJWk1Jc
AAoJEMCF8hzn9Lncz4MH/RYReh4+oPkt8D4uW2FhiB/BlzY5Q1FP94nyi/jQAAh9
er3cUA47RhSLLd2ukC2XDgbw8CZzhnzECs7vBVsXacc3dGpzV59n8L/pnX47IRJh
i1BPWHzEl/UeE/uBYUVgmy+kCVkJ80gnL2GGgZ3IXL5P+CHYY9dvhBrr53Q3HSpi
aEXVivBvBnX0GeATMVY5TAiailUfsUbUmPdEHu0x5hqqTh0sUpi+R+wXWJfPESB2
hzMVZd8ALz1SJhDqbkmBNHy2CX0fhGlnMSapm6EkQksfshkcwJ7tj8s2CEOYD68T
4mR7Xh+FsOA2bbZP8M/lMd3rrXbwFzXi0rWPa70mxqI=
=2W58
-END PGP SIGNATURE-

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Rusty Russell via bitcoin-dev]

Gavin Andresen via bitcoin-dev  writes:
> 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?

vanitygen can generate keypairs pretty fast (on my CPU it's comparable
with hashing time), and there are ways to make it faster.  Since you can
generate multiple script variations, too, I think hashing is the
bottleneck.

Antminer S7 can do 4.73 Terahash per second for $1.2k.  (Double SHA, but
let's assume RIPEMD160(SHA256()) is the same speed).

766,760,562,123 seconds to do 3*2^80, so you'd need over 200 million
S7s to do it in an hour.[1] If you want to do that for $1M, wait 27
years and hope Moore's Law holds?

Also, a colleague points out you could use this attack against a site
like bitrated.com which publishes one side's pubkey, giving you a much
longer attack window.
 
Cheers,
Rusty.
[1] Weirdly, the bitcoin network is doing this much work every 57
days, for about $92M.  If that's all the attack costs, it's under
1M in 10 years.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Peter Todd via bitcoin-dev]

On Fri, Jan 08, 2016 at 02:00:11PM +1030, Rusty Russell via bitcoin-dev wrote:
> Pieter Wuille via bitcoin-dev 
> writes:
> > Yes, this is what I worry about. We're constructing a 2-of-2 multisig
> > escrow in a contract. I reveal my public key A, you do a 80-bit search for
> > B and C such that H(A and B) = H(B and C). You tell me your keys B, and I
> > happily send to H(A and B), which you steal with H(B and C).
> 
> FWIW, this attack would effect the current lightning-network "deployable
> lightning" design at channel establishment; we reveal our pubkey in the
> opening packet (which is used to redeem a P2SH using normal 2of2).
> 
> At least you need to grind before replying (which will presumably time
> out), rather than being able to do it once the channel is open.
> 
> We could pre-commit by exchanging hashes of pubkeys first, but contracts
> on bitcoin are hard enough to get right that I'm reluctant to add more
> hoops.

Note how this is a good example where trying to avoid the relatively
small amount of complexity of having two different segregated witness
schemes to allow for 128bit security could lead to a significant amount
of upper level complexity trying to regain security. I wouldn't be
surprised at all if this upper level complexity leads to exploits; at
the very least it'll lead to a lot of wasted mental effort from
cryptographers concerned about the potential weakness, both within and
external to the Bitcoin development community.

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


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Peter Todd via bitcoin-dev]

On Thu, Jan 07, 2016 at 08:54:00PM -0500, Gavin Andresen via bitcoin-dev wrote:
> ---
> 
> I'm really disappointed with the "Here's the spec, take it or leave it"
> attitude. What's the point of having a BIP process if the discussion just
> comes down to "We think more is better. We don't care what you think."

I'll point out that I personally raised an issue with segpregated
witnesses quite recently - my concern that it could make validationless
mining easier and more profitable(1). Neither Pieter Wuille nor Gregory
Maxwell believed my concern to be important at first in private
communication. However, it was still discussed on IRC, with Pieter,
Greg, and others contributing valuable input on the problem and my
proposed fix. Right now I think the next step for me is to write the
code to implement my fix and submit a pull-req against the segwit
branch.

I certainly wouldn't describe that experience as "Here's the spec, take
it or leave it; We don't what what you think."

1) "Segregated witnesses and validationless mining",
Peter Todd, Dec 23 2015, Bitcoin-dev mailing list,

http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-December/012103.html

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


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

And to fend off the messag that I bet somebody is composing right now:

Yes, I know about a "security first" mindset.  But as I said earlier in the
thread, there is a tradeoff here between crypto strength and code
complexity, and "the strength of the crypto is all that matters" is NOT
security first.

-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

On Fri, Jan 8, 2016 at 10:46 AM, Gavin Andresen 
wrote:

> And Ethan or Anthony:  can you think of a similar attack scheme if you
> assume we had switched to Schnorr 2-of-2 signatures by then?


Don't answer that, I was being dense again, Anthony's scheme works with
Schnorr...


-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

On Fri, Jan 8, 2016 at 10:50 AM, Gavin Andresen 
wrote:

> But as I said earlier in the thread, there is a tradeoff here between
> crypto strength and code complexity, and "the strength of the crypto is all
> that matters" is NOT security first.


I should be more explicit about code complexity:

The big picture is "segwitness will help scale in the very short term."

So the spec gives two ways of stuffing the segwitness hash into the
scriptPubKey -- one way that uses a 32-bit hash, but if used would actually
make scalability a bit worse as coins moved into segwitness-locked
transactions (DUP HASH160 EQUALVERIFY pay-to-script-hash scriptpubkeys are
just 24 bytes).

And another way that add just one byte to the scriptpubkey.

THAT is the code complexity I'm talking about.  Better to always move the
script into the witness data, in my opinion, on the keep the design as
simple as possible principle.

It could be a 32-byte hash... but then the short-term scalability goal is
compromised.

Maybe I'm being dense, but I still think it is a no-brainer

-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

Thanks, Anthony, that works!

So...

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?

And Ethan or Anthony:  can you think of a similar attack scheme if you
assume we had switched to Schnorr 2-of-2 signatures by then?


And to everybody who might not be reading this closely:  All of the above
is discussing collision attacks; none of it is relevant in the normal case
where your wallet generates the scriptPubKey.



-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Pieter Wuille via bitcoin-dev]

On Fri, Jan 8, 2016 at 2:54 AM, Gavin Andresen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> I'm saying we can eliminate one somewhat unlikely attack (that there is a
> bug in the code or test cases, today or some future version, that has to
> decide what to do with "version 0" versus "version 1" witness programs) by
> accepting the risk of another insanely, extremely unlikely attack.

Ok, just having one witness program version now is a somewhat different
proposal. It would be simpler for sure. The reasoning was that you'd need
this to not add significant overhead to small scripts, but that may not be
the case anymore. I wouldn't mind seeing numbers.

> My proposal would be to just do a version 0 witness program now, that is
> RIPEMD160(SHA256(script)).

I don't think that is wise. Bitcoin has a 128-bit security target for
everything else. We did not know that P2SH and similar constructs were
vulnerable to a collision attack at the time, but now we do, so the obvious
choice is to pick a size that is sufficiently large to maintain the 128-bit
security target. This is a no brainer to me; we're not proposing switching
to a 160-bit EC curve either, right?

> I'm really disappointed with the "Here's the spec, take it or leave it"
> attitude. What's the point of having a BIP process if the discussion just
> comes down to "We think more is better. We don't care what you think."

It is a proposal and we are discussing it. You first brought up some
criticisms in private, and I agreed with several things you said.

But it remains the proposal of a few people including me, and I do not
agree with the specific suggestion of reducing the security target for
witness scripts to 80 bits.

We are not deciding what the system will be. We're making a proposal, and
hope that due to its technical merit, the ecosystem will adopt it. You're
free to participate in that discussion.

-- 
Pieter
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Anthony Towns via bitcoin-dev]

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

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Adam Back via bitcoin-dev]

Tricky choice. On the one hand I had spotted this too before and maybe
one or two more exceptions to bitcoin's 128-bit security target and
been vaguely tut-tutting about them in the background.  It's kind of a
violation of crypto rule of thumb that you want to balance things and
not have odd weak points as Watson was implying, it puts you closer to
the margin if there is a slip or other problem so you have an
imbalanced crypto format.

On the other hand it's not currently a problem as such and it's less
change and slightly more compact.

RIPEMD probably is less well reviewed than SHA2.  However SHA1 has
problems, and SHA2 is a bigger SHA1 basically so, hence the NIST
motivation for SHA3 designed to fix the design flaw in SHA1 (and SHA2
in principle).

So then if we agree with this rule of thumb (and not doing so would
fly against best practices which we probably shouldnt look to do in
such a security focussed domain) then what this discussion is more
about is when is a good time to write down tech debt.

I think that comes to segregated-witness itself which writes down a
tidily organised by lines of code robust fix to a bunch of long
standing problems.

Doing a 2MB hard-fork in comparison fixes nothing really.  Leaving
known issues to bake in for another N years eventually builds up on
you (not even in security just in software engineering) as another
rule of thumb.  I mean if we dont fix it now that we are making a
change that connects, when will we?

In software projects I ran we always disguised the cost of tech-debt
as non-negotiable baked into our estimates without a line item to
escape the PHB syndrome of haggling for features instead of tech debt
(which is _never_ a good idea:)

Pragmatism vs refactoring as you go.

But for scale I think segregated-witness does offer the intriguing
next step of being able to do 2 of 2, 3 of 3 and N of N which give
size of one sig multisig (indistinguishable even for privacy) as well
as K of N key tree sigs, which are also significantly more compact.

There was also the other thing I mentioned further up the thread that
if we want to take an approach of living with little bit of bloat from
getting back to a universal 128-bit target, there are still some
fixable bloat things going on:
a) sending pubKey in the signature vs recovery (modulo interference
with Schnorr batch verify compatibility*);
b) using the PubKey instead of PKH in the ScriptPubKey, though that
loses the nice property of of not having the key to do DL attacks on
until the signed transaction is broadcast;
c) I think there might be a way to combine hash & PubKey to keep the
delayed PubKey publication property and yet still save the bloat of
having both.

* I did suggest to Pieter that you could let the miner decide to forgo
Schnorr batch verifiability to get compaction from recovery - the pub
key could be optionally elided from the scriptSig serialisation by the
miner.

The other thing we could consider is variable sized hashes (& a few
pubkey size choices) that is software complexity however.  We might be
better of focussing on the bigger picture like IBLT/weak-blocks and
bigger wins like MAST, multiSig Schnorr & key tree sigs.

Didnt get time to muse on c) but a nice crypto question for someone :)

Another thing to note is combining has been known to be fragile to bad
interactions or unexpected behaviours.  This paper talks about things
tradeoffs and weaknesses in hash combiners.
http://tuprints.ulb.tu-darmstadt.de/2094/1/thesis.lehmann.pdf

Weak concept NACK I think for losing a cleanup opportunity to store it
up for the future when there is a reasonable opportunity to fix it?

Adam


On 8 January 2016 at 15:34, Watson Ladd via bitcoin-dev
 wrote:
> On Fri, Jan 8, 2016 at 4:38 AM, Gavin Andresen via bitcoin-dev
>  wrote:
>> On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell  wrote:
>>>
>>> Matt Corallo  writes:
>>> > Indeed, anything which uses P2SH is obviously vulnerable if there is
>>> > an attack on RIPEMD160 which reduces it's security only marginally.
>>>
>>> I don't think this is true?  Even if you can generate a collision in
>>> RIPEMD160, that doesn't help you since you need to create a specific
>>> SHA256 hash for the RIPEMD160 preimage.
>>>
>>> Even a preimage attack only helps if it leads to more than one preimage
>>> fairly cheaply; that would make grinding out the SHA256 preimage easier.
>>> AFAICT even MD4 isn't this broken.
>>
>>
>> It feels like we've gone over that before, but I can never remember where or
>> when. I believe consensus was that if we were using the broken MD5 in all
>> the places we use RIPEMD160 we'd still be secure today because of Satoshi's
>> use of nested hash functions everywhere.
>>
>>>
>>> But just with Moore's law (doubling every 18 months), we'll worry about
>>> economically viable attacks in 20 years.[1]
>>>
>>>
>>> That's far enough away that I would choose simplicity, and have all SW
>>> scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
>>> no

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

[Watson Ladd via bitcoin-dev]

On Fri, Jan 8, 2016 at 4:38 AM, Gavin Andresen via bitcoin-dev
 wrote:
> On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell  wrote:
>>
>> Matt Corallo  writes:
>> > Indeed, anything which uses P2SH is obviously vulnerable if there is
>> > an attack on RIPEMD160 which reduces it's security only marginally.
>>
>> I don't think this is true?  Even if you can generate a collision in
>> RIPEMD160, that doesn't help you since you need to create a specific
>> SHA256 hash for the RIPEMD160 preimage.
>>
>> Even a preimage attack only helps if it leads to more than one preimage
>> fairly cheaply; that would make grinding out the SHA256 preimage easier.
>> AFAICT even MD4 isn't this broken.
>
>
> It feels like we've gone over that before, but I can never remember where or
> when. I believe consensus was that if we were using the broken MD5 in all
> the places we use RIPEMD160 we'd still be secure today because of Satoshi's
> use of nested hash functions everywhere.
>
>>
>> But just with Moore's law (doubling every 18 months), we'll worry about
>> economically viable attacks in 20 years.[1]
>>
>>
>> That's far enough away that I would choose simplicity, and have all SW
>> scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
>> not a no-brainer.
>
>
> 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.
>
> Instead they then generate about 2^81scripts that are some form of
> pay-to-attacker 
> ... wait, no that doesn't work, because SHA256 is used as the inner hash
> function.  They'd have to generate 2^129 to find a cycle in SHA256.

For 2^80 they simply generate 2^80 scripts that look innocent, and
2^80 that are not. With high probability there is a collision. I agree
that most cryptanalysis won't work because of the nesting, but 2^80 is
not good.
>
> Instead, they .. what? I don't see a viable attack unless RIPEMD160 and
> SHA256 (or the combination) suffers a cryptographic break.
>
>
> --
> --
> Gavin Andresen
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell  wrote:

> Matt Corallo  writes:
> > Indeed, anything which uses P2SH is obviously vulnerable if there is
> > an attack on RIPEMD160 which reduces it's security only marginally.
>
> I don't think this is true?  Even if you can generate a collision in
> RIPEMD160, that doesn't help you since you need to create a specific
> SHA256 hash for the RIPEMD160 preimage.
>
> Even a preimage attack only helps if it leads to more than one preimage
> fairly cheaply; that would make grinding out the SHA256 preimage easier.
> AFAICT even MD4 isn't this broken.
>

It feels like we've gone over that before, but I can never remember where
or when. I believe consensus was that if we were using the broken MD5 in
all the places we use RIPEMD160 we'd still be secure today because of
Satoshi's use of nested hash functions everywhere.


> But just with Moore's law (doubling every 18 months), we'll worry about
> economically viable attacks in 20 years.[1]


> That's far enough away that I would choose simplicity, and have all SW
> scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
> not a no-brainer.


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.

Instead they then generate about 2^81scripts that are some form of
pay-to-attacker 
... wait, no that doesn't work, because SHA256 is used as the inner hash
function.  They'd have to generate 2^129 to find a cycle in SHA256.

Instead, they .. what? I don't see a viable attack unless RIPEMD160 and
SHA256 (or the combination) suffers a cryptographic break.


-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Rusty Russell via bitcoin-dev]

Matt Corallo  writes:
> Indeed, anything which uses P2SH is obviously vulnerable if there is
> an attack on RIPEMD160 which reduces it's security only marginally.

I don't think this is true?  Even if you can generate a collision in
RIPEMD160, that doesn't help you since you need to create a specific
SHA256 hash for the RIPEMD160 preimage.

Even a preimage attack only helps if it leads to more than one preimage
fairly cheaply; that would make grinding out the SHA256 preimage easier.
AFAICT even MD4 isn't this broken.

But just with Moore's law (doubling every 18 months), we'll worry about
economically viable attacks in 20 years.[1]

That's far enough away that I would choose simplicity, and have all SW
scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
not a no-brainer.

Cheers,
Rusty.

[1] Assume bitcoin-network-level compute (collision in 19 days) costs
$1B to build today.  Assume there will be 100 million dollars a day
in vulnerable txs, and you're on one end of all of them (or can MITM
if you find a collision), *and* can delay them all by 10 seconds,
and none are in parallel so you can attack all of them.  IOW, just
like a single $100M opportunity for 3650 seconds each year.

Our machine has a 0.11% chance of finding a collision in 1 hour, so
it's worth about $110,000.  We can build it for that in about 20
years.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Matt Corallo via bitcoin-dev]

Indeed, anything which uses P2SH is obviously vulnerable if there is an attack 
on RIPEMD160 which reduces it's security only marginally. While no one thought 
hard about these attacks when P2SH was designed, we realized later this was not 
such a good idea to reuse the structure from P2PKH. Hence why this discussion 
came up.

On January 7, 2016 7:30:11 PM PST, Rusty Russell via bitcoin-dev 
 wrote:
>Pieter Wuille via bitcoin-dev 
>writes:
>> Yes, this is what I worry about. We're constructing a 2-of-2 multisig
>> escrow in a contract. I reveal my public key A, you do a 80-bit
>search for
>> B and C such that H(A and B) = H(B and C). You tell me your keys B,
>and I
>> happily send to H(A and B), which you steal with H(B and C).
>
>FWIW, this attack would effect the current lightning-network
>"deployable
>lightning" design at channel establishment; we reveal our pubkey in the
>opening packet (which is used to redeem a P2SH using normal 2of2).
>
>At least you need to grind before replying (which will presumably time
>out), rather than being able to do it once the channel is open.
>
>We could pre-commit by exchanging hashes of pubkeys first, but
>contracts
>on bitcoin are hard enough to get right that I'm reluctant to add more
>hoops.
>
>Cheers,
>Rusty.
>___
>bitcoin-dev mailing list
>bitcoin-dev@lists.linuxfoundation.org
>https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Rusty Russell via bitcoin-dev]

Pieter Wuille via bitcoin-dev 
writes:
> Yes, this is what I worry about. We're constructing a 2-of-2 multisig
> escrow in a contract. I reveal my public key A, you do a 80-bit search for
> B and C such that H(A and B) = H(B and C). You tell me your keys B, and I
> happily send to H(A and B), which you steal with H(B and C).

FWIW, this attack would effect the current lightning-network "deployable
lightning" design at channel establishment; we reveal our pubkey in the
opening packet (which is used to redeem a P2SH using normal 2of2).

At least you need to grind before replying (which will presumably time
out), rather than being able to do it once the channel is open.

We could pre-commit by exchanging hashes of pubkeys first, but contracts
on bitcoin are hard enough to get right that I'm reluctant to add more
hoops.

Cheers,
Rusty.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Watson Ladd via bitcoin-dev]

On Jan 7, 2016 5:22 PM, "Gavin Andresen via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> On Thu, Jan 7, 2016 at 6:52 PM, Pieter Wuille 
wrote:
>>
>> Bitcoin does have parts that rely on economic arguments for security or
privacy, but can we please stick to using cryptography that is up to par
for parts where we can? It's a small constant factor of data, and it
categorically removes the worry about security levels.
>
> Our message may have crossed in the mod queue:
>
> "So can we quantify the incremental increase in security of
SHA256(SHA256) over RIPEMD160(SHA256) versus the incremental increase in
security of having a simpler implementation of segwitness?"

There are several clever ways to exploit even chosen prefix collisions
using the scripting language. One could search for collisions where one
message is some data and the other is a jump over a critical check.

>
> I believe the history of computer security is that implementation errors
and sidechannel attacks are much, much more common than brute-force breaks.
KEEP IT SIMPLE.

Ask the Iranian nuclear program. Or those brainwallet users.
>
> (and a quibble:  "do a 80-bit search for B and C such that H(A and B) =
H(B and C)"  isn't enough, you have to end up with a C public key for which
you know the corresponding private key or the attacker just succeeds in
burning the funds)
>
>
> --
> --
> Gavin Andresen
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

On Thu, Jan 7, 2016 at 8:26 PM, Matt Corallo 
wrote:

> So just because other attacks are possible we should weaken the crypto
> we use? You may feel comfortable weakening crypto used to protect a few
> billion dollars of other peoples' money, but I dont.
>

No...

I'm saying we can eliminate one somewhat unlikely attack (that there is a
bug in the code or test cases, today or some future version, that has to
decide what to do with "version 0" versus "version 1" witness programs) by
accepting the risk of another insanely, extremely unlikely attack.

Reference for those who are lost:

https://github.com/CodeShark/bips/blob/segwit/bip-codeshark-jl2012-segwit.mediawiki#witness-program

My proposal would be to just do a version 0 witness program now, that is
RIPEMD160(SHA256(script)).

And ten or twenty years from now, if there is a plausible attack on
RIPEMD160 and/or SHA256, revisit and do a version 11 (or whatever).

It will simplify the BIP, means half as many test cases have to be written,
means a little more scalability, and is as secure as the P2SH and P2PKH
everybody is using to secure their bitcoin today.

Tell you what:  I'll change my mind if anybody can describe a plausible
attack if we were using MD5(SHA256), given what we know about how MD5 is
broken.


---

I'm really disappointed with the "Here's the spec, take it or leave it"
attitude. What's the point of having a BIP process if the discussion just
comes down to "We think more is better. We don't care what you think."

-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Matt Corallo via bitcoin-dev]

So just because other attacks are possible we should weaken the crypto
we use? You may feel comfortable weakening crypto used to protect a few
billion dollars of other peoples' money, but I dont.

On 01/07/16 23:39, Gavin Andresen via bitcoin-dev wrote:
> Thanks, Ethan, that's helpful and I'll stop thinking that collision
> attacks require 2^(n/2) memory...
> 
> So can we quantify the incremental increase in security of
> SHA256(SHA256) over RIPEMD160(SHA256) versus the incremental increase in
> security of having a simpler implementation of segwitness?
> 
> I'm going to claim that the difference in the first case is very, very,
> very small-- the risk of an implementation error caused by having
> multiple ways of interpreting the segwitness hash in the scriptPubKey is
> much, much greater.
> 
> And even if there IS some risk of collision attack now or at some point
> in the future, I claim that it is easy for wallets to mitigate that
> risk. In fact, the principle of security in depth means wallets that
> don't completely control the scriptPubKeys they're creating on behalf of
> users SHOULD be coded to mitigate that risk (e.g. not allowing arbitrary
> data around a user's public key in a Script so targeted substring
> attacks are eliminated entirely).
> 
> Purely from a security point of view, I think a single 20-byte
> segwitness in the scriptPubKey is the best design.
> "Keep the design as simple and small as possible"
> https://www.securecoding.cert.org/confluence/plugins/servlet/mobile#content/view/2426
> 
> Add in the implied capacity increase of smaller scriptPubKeys and I
> still think it is a no-brainer.
> 
> 
> On Thu, Jan 7, 2016 at 5:56 PM, Ethan Heilman  > wrote:
> 
> >Ethan:  your algorithm will find two arbitrary values that collide. That 
> isn't useful as an attack in the context we're talking about here (both of 
> those values will be useless as coin destinations with overwhelming 
> probability).
> 
> I'm not sure exactly the properties you want here and determining
> these properties is not an easy task, but the case is far worse than
> just two random values. For instance: (a). with a small modification
> my algorithm can also find collisions containing targeted substrings,
> (b). length extension attacks are possible with RIPEMD160.
> 
> (a). targeted cycles:
> 
> target1 = "str to prepend"
> target2 = "str to end with"
> 
> seed = {0,1}^160
> x = hash(seed)
> 
> for i in 2^80:
> x = hash(target1||x||target2)
> x_final = x
> 
> y = hash(tartget1||x_final||target2)
> 
> for j in 2^80:
> if y == x_final:
> print "cycle len: "+j
> break
> y = hash(target1||y||target2)
> 
> If a collision is found, the two colliding inputs must both start with
> "str to prepend" and end with the phrase "str to end with". As before
> this only requires 2^81.5 computations and no real memory. For an
> additional 2**80 an adversary has an good change of finding two
> different targeted substrings which collide. Consider the case where
> the attacker mixes the targeted strings with the hash output:
> 
> hash("my name is=0x329482039483204324423"+x[1]+", my favorite number
> is="+x) where x[1] is the first bit of x.
> 
> (b). length extension attacks
> 
> Even if all the adversary can do is create two random values that
> collide, you can append substrings to the input and get collisions.
> Once you find two random values hash(x) = hash(y), you could use a
> length extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).
> 
> Now the bitcoin wiki says:
> "The padding scheme is identical to MD4 using Merkle–Damgård
> strengthening to prevent length extension attacks."[1]
> 
> Which is confusing to me because:
> 
> 1. MD4 is vulnerable to length extension attacks
> 2. Merkle–Damgård strengthening does not protect against length
> extension: "Indeed, we already pointed out that none of the 64
> variants above can withstand the 'extension' attack on the MAC
> application, even with the Merkle-Damgard strengthening" [2]
> 3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin
> using a non-standard version of RIPEMD-160.
> 
> RIPEMD160(SHA256()) does not protect against length extension attacks
> on SHA256, but should protect RIPEMD-160 against length extension
> attacks as RIPEMD-160 uses 512-bit message blocks. That being said we
> should be very careful here. Research has been done that shows that
> cascading the same hash function twice is weaker than using HMAC[3]. I
> can't find results on cascading RIPEMD160(SHA256()).
> 
> RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security
> should not rest on the notion that an attacker requires 2**80 memory,
> many targeted collision attacks can work without much memory.

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

[Gavin Andresen via bitcoin-dev]

On Thu, Jan 7, 2016 at 6:52 PM, Pieter Wuille 
wrote:

> Bitcoin does have parts that rely on economic arguments for security or
> privacy, but can we please stick to using cryptography that is up to par
> for parts where we can? It's a small constant factor of data, and it
> categorically removes the worry about security levels.
>
Our message may have crossed in the mod queue:

"So can we quantify the incremental increase in security of SHA256(SHA256)
over RIPEMD160(SHA256) versus the incremental increase in security of
having a simpler implementation of segwitness?"

I believe the history of computer security is that implementation errors
and sidechannel attacks are much, much more common than brute-force breaks.
KEEP IT SIMPLE.

(and a quibble:  "do a 80-bit search for B and C such that H(A and B) = H(B
and C)"  isn't enough, you have to end up with a C public key for which you
know the corresponding private key or the attacker just succeeds in burning
the funds)


-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

Thanks, Ethan, that's helpful and I'll stop thinking that collision attacks
require 2^(n/2) memory...

So can we quantify the incremental increase in security of SHA256(SHA256)
over RIPEMD160(SHA256) versus the incremental increase in security of
having a simpler implementation of segwitness?

I'm going to claim that the difference in the first case is very, very,
very small-- the risk of an implementation error caused by having multiple
ways of interpreting the segwitness hash in the scriptPubKey is much, much
greater.

And even if there IS some risk of collision attack now or at some point in
the future, I claim that it is easy for wallets to mitigate that risk. In
fact, the principle of security in depth means wallets that don't
completely control the scriptPubKeys they're creating on behalf of users
SHOULD be coded to mitigate that risk (e.g. not allowing arbitrary data
around a user's public key in a Script so targeted substring attacks are
eliminated entirely).

Purely from a security point of view, I think a single 20-byte segwitness
in the scriptPubKey is the best design.
"Keep the design as simple and small as possible"
https://www.securecoding.cert.org/confluence/plugins/servlet/mobile#content/view/2426

Add in the implied capacity increase of smaller scriptPubKeys and I still
think it is a no-brainer.


On Thu, Jan 7, 2016 at 5:56 PM, Ethan Heilman  wrote:

> >Ethan:  your algorithm will find two arbitrary values that collide. That
> isn't useful as an attack in the context we're talking about here (both of
> those values will be useless as coin destinations with overwhelming
> probability).
>
> I'm not sure exactly the properties you want here and determining
> these properties is not an easy task, but the case is far worse than
> just two random values. For instance: (a). with a small modification
> my algorithm can also find collisions containing targeted substrings,
> (b). length extension attacks are possible with RIPEMD160.
>
> (a). targeted cycles:
>
> target1 = "str to prepend"
> target2 = "str to end with"
>
> seed = {0,1}^160
> x = hash(seed)
>
> for i in 2^80:
> x = hash(target1||x||target2)
> x_final = x
>
> y = hash(tartget1||x_final||target2)
>
> for j in 2^80:
> if y == x_final:
> print "cycle len: "+j
> break
> y = hash(target1||y||target2)
>
> If a collision is found, the two colliding inputs must both start with
> "str to prepend" and end with the phrase "str to end with". As before
> this only requires 2^81.5 computations and no real memory. For an
> additional 2**80 an adversary has an good change of finding two
> different targeted substrings which collide. Consider the case where
> the attacker mixes the targeted strings with the hash output:
>
> hash("my name is=0x329482039483204324423"+x[1]+", my favorite number
> is="+x) where x[1] is the first bit of x.
>
> (b). length extension attacks
>
> Even if all the adversary can do is create two random values that
> collide, you can append substrings to the input and get collisions.
> Once you find two random values hash(x) = hash(y), you could use a
> length extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).
>
> Now the bitcoin wiki says:
> "The padding scheme is identical to MD4 using Merkle–Damgård
> strengthening to prevent length extension attacks."[1]
>
> Which is confusing to me because:
>
> 1. MD4 is vulnerable to length extension attacks
> 2. Merkle–Damgård strengthening does not protect against length
> extension: "Indeed, we already pointed out that none of the 64
> variants above can withstand the 'extension' attack on the MAC
> application, even with the Merkle-Damgard strengthening" [2]
> 3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin
> using a non-standard version of RIPEMD-160.
>
> RIPEMD160(SHA256()) does not protect against length extension attacks
> on SHA256, but should protect RIPEMD-160 against length extension
> attacks as RIPEMD-160 uses 512-bit message blocks. That being said we
> should be very careful here. Research has been done that shows that
> cascading the same hash function twice is weaker than using HMAC[3]. I
> can't find results on cascading RIPEMD160(SHA256()).
>
> RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security
> should not rest on the notion that an attacker requires 2**80 memory,
> many targeted collision attacks can work without much memory.
>
> [1]: https://en.bitcoin.it/wiki/RIPEMD-160
> [2]: "Merkle-Damgard Revisited: How to Construct a Hash Function"
> https://www.cs.nyu.edu/~puniya/papers/merkle.pdf
> [3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf
>
> On Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev
>  wrote:
> > Maybe I'm asking this question on the wrong mailing list:
> >
> > Matt/Adam: do you have some reason to think that RIPEMD160 will be broken
> > before SHA256?
> > And do you have some reason to think that they will be so broken that the
> > nested hash construction RIPEMD160(

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

[Pieter Wuille via bitcoin-dev]

> "The problem case is where someone in a contract setup shows you a
script, which you accept as being a payment to yourself. An attacker could
use a collision attack to construct scripts with identical hashes, only one
of which does have the property you want, and steal coins.
>
> So you really want collision security, and I don't think 80 bits is
something we should encourage for that. Normal pubkey hashes don't have
that problem, as they can't be constructed to pay to you."
>
> ... but I'm unconvinced:
>
> "But it is trivial for contract wallets to protect against collision
attacks-- if you give me a script that is "gavin_pubkey CHECKSIG
arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, just
ignore that arbitrary data" a wallet can just refuse. Even more likely, a
contract wallet won't even recognize that as a pay-to-gavin transaction.
>
> I suppose it could be looking for some form of "gavin_pubkey
somebody_else_pubkey CHECKMULTISIG ... with the attacker using
somebody_else_pubkey to force the collision, but, again, trivial contract
protocol tweaks ("send along a proof you have the private key corresponding
to the public key" or "everybody pre-commits pubkeys they'll use at
protocol start") would protect against that.

Yes, this is what I worry about. We're constructing a 2-of-2 multisig
escrow in a contract. I reveal my public key A, you do a 80-bit search for
B and C such that H(A and B) = H(B and C). You tell me your keys B, and I
happily send to H(A and B), which you steal with H(B and C).

Sending along a proof does not help, you can't prove that you do not know
of a collision. Pre-committing does help, but is a very non-obvious
security requirement, something I strongly believe is far riskier in
practice.

Bitcoin does have parts that rely on economic arguments for security or
privacy, but can we please stick to using cryptography that is up to par
for parts where we can? It's a small constant factor of data, and it
categorically removes the worry about security levels.

-- 
Pieter
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Ethan Heilman via bitcoin-dev]

>Ethan:  your algorithm will find two arbitrary values that collide. That isn't 
>useful as an attack in the context we're talking about here (both of those 
>values will be useless as coin destinations with overwhelming probability).

I'm not sure exactly the properties you want here and determining
these properties is not an easy task, but the case is far worse than
just two random values. For instance: (a). with a small modification
my algorithm can also find collisions containing targeted substrings,
(b). length extension attacks are possible with RIPEMD160.

(a). targeted cycles:

target1 = "str to prepend"
target2 = "str to end with"

seed = {0,1}^160
x = hash(seed)

for i in 2^80:
x = hash(target1||x||target2)
x_final = x

y = hash(tartget1||x_final||target2)

for j in 2^80:
if y == x_final:
print "cycle len: "+j
break
y = hash(target1||y||target2)

If a collision is found, the two colliding inputs must both start with
"str to prepend" and end with the phrase "str to end with". As before
this only requires 2^81.5 computations and no real memory. For an
additional 2**80 an adversary has an good change of finding two
different targeted substrings which collide. Consider the case where
the attacker mixes the targeted strings with the hash output:

hash("my name is=0x329482039483204324423"+x[1]+", my favorite number
is="+x) where x[1] is the first bit of x.

(b). length extension attacks

Even if all the adversary can do is create two random values that
collide, you can append substrings to the input and get collisions.
Once you find two random values hash(x) = hash(y), you could use a
length extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).

Now the bitcoin wiki says:
"The padding scheme is identical to MD4 using Merkle–Damgård
strengthening to prevent length extension attacks."[1]

Which is confusing to me because:

1. MD4 is vulnerable to length extension attacks
2. Merkle–Damgård strengthening does not protect against length
extension: "Indeed, we already pointed out that none of the 64
variants above can withstand the 'extension' attack on the MAC
application, even with the Merkle-Damgard strengthening" [2]
3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin
using a non-standard version of RIPEMD-160.

RIPEMD160(SHA256()) does not protect against length extension attacks
on SHA256, but should protect RIPEMD-160 against length extension
attacks as RIPEMD-160 uses 512-bit message blocks. That being said we
should be very careful here. Research has been done that shows that
cascading the same hash function twice is weaker than using HMAC[3]. I
can't find results on cascading RIPEMD160(SHA256()).

RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security
should not rest on the notion that an attacker requires 2**80 memory,
many targeted collision attacks can work without much memory.

[1]: https://en.bitcoin.it/wiki/RIPEMD-160
[2]: "Merkle-Damgard Revisited: How to Construct a Hash Function"
https://www.cs.nyu.edu/~puniya/papers/merkle.pdf
[3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf

On Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev
 wrote:
> Maybe I'm asking this question on the wrong mailing list:
>
> Matt/Adam: do you have some reason to think that RIPEMD160 will be broken
> before SHA256?
> And do you have some reason to think that they will be so broken that the
> nested hash construction RIPEMD160(SHA256()) will be vulnerable?
>
> Adam: re: "where to stop"  :  I'm suggesting we stop exactly at the current
> status quo, where we use RIPEMD160 for P2SH and P2PKH.
>
> Ethan:  your algorithm will find two arbitrary values that collide. That
> isn't useful as an attack in the context we're talking about here (both of
> those values will be useless as coin destinations with overwhelming
> probability).
>
> Dave: you described a first preimage attack, which is 2**160 cpu time and no
> storage.
>
>
> --
> --
> Gavin Andresen
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Ethan Heilman via bitcoin-dev]

Based on current GH/s count of 775,464,121 Bitcoin tests 2^80 every 19 days.
log2(775464121*(1000*1000*1000*60*60*24*19)) = ~80.07

I don't fully understand the security model of segwit, so my analysis
will assume that any collision is bad.

>But it also requires O(2^80) storage, which is utterly infeasible

You don't store all 2^80 previous hashes, instead you just hash a seed
value 2^80 times, then look for a cycle.

seed = {0,1}^160
x = hash(seed)

for i in 2^80:
x = hash(x)
x_final = x

y = hash(x_final)

for j in 2^80:
if y == x_final:
print "cycle len: "+j
break
y = hash(y)

If at any point x collides with a prior value of x it will form a
cycle. Thus y will also cycle and collide with x_final. j gives you
the cycle length, which allows you find the collision:
hash^(2^80-j)(seed) == hash^(j)(hash^(2^80-j)(seed)).

Worst case:
First loop costs 2**80, second loop costs 2**80=j, finding the
colliding value is 2**80. Total cost 2**80+2**80+2**80 = 2**81.5 and
requires storing less than a kilobyte.

This is a toy example, does not exploit parallelism, time memory trade
offs, can be easily made better, etc...

On Thu, Jan 7, 2016 at 2:02 PM, Gavin Andresen via bitcoin-dev
 wrote:
> I'm hoisting this from some private feedback I sent on the segregated
> witness BIP:
>
> I said:
>
> "I'd also use RIPEMD160(SHA256()) as the hash function and save the 12
> bytes-- a successful preimage attack against that ain't gonna happen before
> we're all dead. I'm probably being dense, but I just don't see how a
> collision attack is relevant here."
>
> Pieter responded:
>
> "The problem case is where someone in a contract setup shows you a script,
> which you accept as being a payment to yourself. An attacker could use a
> collision attack to construct scripts with identical hashes, only one of
> which does have the property you want, and steal coins.
>
> So you really want collision security, and I don't think 80 bits is
> something we should encourage for that. Normal pubkey hashes don't have that
> problem, as they can't be constructed to pay to you."
>
> ... but I'm unconvinced:
>
> "But it is trivial for contract wallets to protect against collision
> attacks-- if you give me a script that is "gavin_pubkey CHECKSIG
> arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, just
> ignore that arbitrary data" a wallet can just refuse. Even more likely, a
> contract wallet won't even recognize that as a pay-to-gavin transaction.
>
> I suppose it could be looking for some form of "gavin_pubkey
> somebody_else_pubkey CHECKMULTISIG ... with the attacker using
> somebody_else_pubkey to force the collision, but, again, trivial contract
> protocol tweaks ("send along a proof you have the private key corresponding
> to the public key" or "everybody pre-commits pubkeys they'll use at protocol
> start") would protect against that.
>
> Adding an extra 12 bytes to every segwit to prevent an attack that takes
> 2^80 computation and 2^80 storage, is unlikely to be a problem in practice,
> and is trivial to protect against is the wrong tradeoff to make."
>
> 20 bytes instead of 32 bytes is a savings of almost 40%, which is
> significant.
>
> The general question I'd like to raise on this list is:
>
> Should we be worried, today, about collision attacks against RIPEMD160 (our
> 160-bit hash)?
>
> Mounting a successful brute-force collision attack would require at least
> O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bitcoin
> POW has computed more SHA256 hashes than that). But it also requires O(2^80)
> storage, which is utterly infeasible (there is something on the order of
> 2^35 bytes of storage in the entire world).  Even assuming doubling every
> single year (faster than Moore's Law), we're four decades away from an
> attacker with THE ENTIRE WORLD's storage capacity being able to mount a
> collision attack.
>
>
> References:
>
> https://en.wikipedia.org/wiki/Collision_attack
>
> https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/
>
>
> --
> --
> Gavin Andresen
>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Gavin Andresen via bitcoin-dev]

Maybe I'm asking this question on the wrong mailing list:

Matt/Adam: do you have some reason to think that RIPEMD160 will be broken
before SHA256?
And do you have some reason to think that they will be so broken that the
nested hash construction RIPEMD160(SHA256()) will be vulnerable?

Adam: re: "where to stop"  :  I'm suggesting we stop exactly at the current
status quo, where we use RIPEMD160 for P2SH and P2PKH.

Ethan:  your algorithm will find two arbitrary values that collide. That
isn't useful as an attack in the context we're talking about here (both of
those values will be useless as coin destinations with overwhelming
probability).

Dave: you described a first preimage attack, which is 2**160 cpu time and
no storage.


-- 
--
Gavin Andresen
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Dave Scotese via bitcoin-dev]

Maybe I'm being dense, but I don't see why 2**80 storage is required for
this attack.  Also, I don't see why the attacker ever needs to get the
victim to accept "arbitrary_data".  Perhaps I'm wrong about how the
collision attack works:

   1. Create a script which is perfectly acceptable and would pass the
   sniff test Gavin proposed (no arbitrary_data).
   2. Set off CPU power to construct a second script that lets attacker
   keep his coins and has the same hash. (This is where you get
   "arbitrary_data").
   3. Send a transaction with the first script to the seller as payment.
   4. Wait for the transaction to be included in a block.
   5. Redeem the transaction with the second script, thus stealing the
   coins back.

So the seller would never see the I'd appreciate any correction to my
understanding here.  Where do you need 2**80 storage?  And when does the
seller have to accept "arbitrary_data"?
Thanks!

On Thu, Jan 7, 2016 at 11:19 AM, Adam Back via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> You could say 256 bit ECDSA is overkill lets go to 160 equivalently.
> Saves even more bytes.
>
> The problem with arguing down is where to stop.
>
> As Matt said these things dont degrade gracefully so a best practice
> is to aim for a bit of extra margin.
>
> 256-bit is quite common at this point since AES, SHA256 etc even in
> things with much less at stake than Bitcoin.
>
> You could send the compressed (unhashed) pubkey then there's no hash
> (and omit it from the sig).  Greg had mentioned that in the past.
>
> I think it might be possible to do both (reclaim the hash bits in the
> serialisation of the pub key).
>
> Adam
>
> On 7 January 2016 at 20:02, Gavin Andresen via bitcoin-dev
>  wrote:
> > I'm hoisting this from some private feedback I sent on the segregated
> > witness BIP:
> >
> > I said:
> >
> > "I'd also use RIPEMD160(SHA256()) as the hash function and save the 12
> > bytes-- a successful preimage attack against that ain't gonna happen
> before
> > we're all dead. I'm probably being dense, but I just don't see how a
> > collision attack is relevant here."
> >
> > Pieter responded:
> >
> > "The problem case is where someone in a contract setup shows you a
> script,
> > which you accept as being a payment to yourself. An attacker could use a
> > collision attack to construct scripts with identical hashes, only one of
> > which does have the property you want, and steal coins.
> >
> > So you really want collision security, and I don't think 80 bits is
> > something we should encourage for that. Normal pubkey hashes don't have
> that
> > problem, as they can't be constructed to pay to you."
> >
> > ... but I'm unconvinced:
> >
> > "But it is trivial for contract wallets to protect against collision
> > attacks-- if you give me a script that is "gavin_pubkey CHECKSIG
> > arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off,
> just
> > ignore that arbitrary data" a wallet can just refuse. Even more likely, a
> > contract wallet won't even recognize that as a pay-to-gavin transaction.
> >
> > I suppose it could be looking for some form of "gavin_pubkey
> > somebody_else_pubkey CHECKMULTISIG ... with the attacker using
> > somebody_else_pubkey to force the collision, but, again, trivial contract
> > protocol tweaks ("send along a proof you have the private key
> corresponding
> > to the public key" or "everybody pre-commits pubkeys they'll use at
> protocol
> > start") would protect against that.
> >
> > Adding an extra 12 bytes to every segwit to prevent an attack that takes
> > 2^80 computation and 2^80 storage, is unlikely to be a problem in
> practice,
> > and is trivial to protect against is the wrong tradeoff to make."
> >
> > 20 bytes instead of 32 bytes is a savings of almost 40%, which is
> > significant.
> >
> > The general question I'd like to raise on this list is:
> >
> > Should we be worried, today, about collision attacks against RIPEMD160
> (our
> > 160-bit hash)?
> >
> > Mounting a successful brute-force collision attack would require at least
> > O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that
> Bitcoin
> > POW has computed more SHA256 hashes than that). But it also requires
> O(2^80)
> > storage, which is utterly infeasible (there is something on the order of
> > 2^35 bytes of storage in the entire world).  Even assuming doubling every
> > single year (faster than Moore's Law), we're four decades away from an
> > attacker with THE ENTIRE WORLD's storage capacity being able to mount a
> > collision attack.
> >
> >
> > References:
> >
> > https://en.wikipedia.org/wiki/Collision_attack
> >
> >
> https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/
> >
> >
> > --
> > --
> > Gavin Andresen
> >
> >
> > ___
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/ma