Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

From: Ethan Heilman <eth3rs@gmail•com>
To: Leandro Coutinho <lescoutinhovr@gmail•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Cc: Steve Davis <steven.charles.davis@gmail•com>
Subject: Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers
Date: Sat, 25 Feb 2017 11:10:02 -0500	[thread overview]
Message-ID: <CAEM=y+WkgSkc07ZsU6APAkcu37zVZ7dwSc=jAg1nho31S5ZyxQ@mail.gmail.com> (raw)
In-Reply-To: <CAN6UTayzQRowtWhLKr8LyFuXjw3m+GjQGtHfkDj-Xu41Hym32w@mail.gmail.com>

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

>SHA1 is insecure because the SHA1 algorithm is insecure, not because
160bits isn't enough.

I would argue that 160-bits isn't enough for collision resistance. Assuming
RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle), collisions
can be generated in 2^80 queries (actually detecting these collisions
requires some time-memory additional trade-offs). The Bitcoin network at
the current hash rate performs roughly SHA-256 ~2^78 queries a day or 2^80
queries every four days. Without any break in RIPEMD-160(SHA-256(msg)) the
US could build an ASIC datacenter and produce RIPEMD-160 collisions for a
fraction of its yearly cryptologic budget.

The impact of collisions in RIPEMD-160(SHA-256(msg)) according to "On
Bitcoin Security in the Presence of Broken Crypto Primitives"(
https://eprint.iacr.org/2016/167.pdf):

>Collisions are similar, though in this case both public keys are under the
adversary’s control, and again the adversary does not have access to the
private keys. In both scenarios, there is a question of nonrepudiation
external to the protocol itself: by presenting a second pre-image of a key
used to sign a transaction, a user/adversary can claim that his coins were
stolen.

How would such an event effect the price of Bitcoin when headlines are
"Bitcoin's Cryptography Broken"? How much money could someone make by
playing the market in this way?

For both reasons of credibility and good engineering (safety
margins) Bitcoin should strive to always use cryptography which is beyond
reproach.

On Sat, Feb 25, 2017 at 9:50 AM, Leandro Coutinho via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:

> Google recommeds "migrate to safer cryptographic hashes such as SHA-256
> and SHA-3"
> It does not mention RIPEMD-160
>
> https://security.googleblog.com/2017/02/announcing-first-
> sha1-collision.html?m=1
>
>
> Em 25/02/2017 10:47, "Steve Davis via bitcoin-dev" <bitcoin-dev@lists.
> linuxfoundation.org> escreveu:
>
>
> > On Feb 24, 2017, at 7:01 PM, Peter Todd <pete@petertodd•org> wrote:
> >
> > On Fri, Feb 24, 2017 at 05:49:36PM -0600, Steve Davis via bitcoin-dev
> wrote:
> >> If the 20 byte SHA1 is now considered insecure (with good reason), what
> about RIPEMD-160 which is the foundation of Bitcoin addresses?
> >
> > SHA1 is insecure because the SHA1 algorithm is insecure, not because
> 160bits isn't enough.
> >
> > AFAIK there aren't any known weaknesses in RIPEMD160,
>
> …so far. I wonder how long that vacation will last?
>
> > but it also hasn't been
> > as closely studied as more common hash algorithms.
>
> ...but we can be sure that it will be, since the dollar value held in
> existing utxos continues to increase...
>
> > That said, Bitcoin uses
> > RIPEMD160(SHA256(msg)), which may make creating collisions harder if an
> attack
> > is found than if it used RIPEMD160 alone.
>
> Does that offer any greater protection? That’s not so clear to me as the
> outputs (at least for p2pkh) only verify the public key against the final
> 20 byte hash. Specifically, in the first (notional) case the challenge
> would be to find a private key that has a public key that hashes to the
> final hash. In the second (realistic) case, you merely need to add the
> sha256 hash into the problem, which doesn’t seem to me to increase the
> difficulty by any significant amount?
>
>
> /s
> _______________________________________________
> 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
>
>

[-- Attachment #2: Type: text/html, Size: 5697 bytes --]