Content-type: text/plain; charset=utf-8
MIME-version: 1.0 (Mac OS X Mail 10.2 \(3259\))
From: Shin'ichiro Matsuo <matsuo@mac.com>
In-reply-to: <CAEM=y+WkgSkc07ZsU6APAkcu37zVZ7dwSc=jAg1nho31S5ZyxQ@mail.gmail.com>
Date: Sat, 25 Feb 2017 09:45:36 -0800
Content-transfer-encoding: quoted-printable
Message-id: <81BE82BA-EDFC-45D1-84DE-D65EC24C9F41@mac.com>
References: <mailman.22137.1487974823.31141.bitcoin-dev@lists.linuxfoundation.org>
	<8F096BE1-D305-43D4-AF10-2CC48837B14F@gmail.com>
	<20170225010122.GA10233@savin.petertodd.org>
	<208F93FE-B7C8-46BE-8E00-52DBD0F43415@gmail.com>
	<CAN6UTayzQRowtWhLKr8LyFuXjw3m+GjQGtHfkDj-Xu41Hym32w@mail.gmail.com>
	<CAEM=y+WkgSkc07ZsU6APAkcu37zVZ7dwSc=jAg1nho31S5ZyxQ@mail.gmail.com>
To: 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
Precedence: list

We should distinguish collision resistance from 2nd pre-image =
resistance, in general.

As previously written, we should care both hash output length and =
algorithm itself. The weakness of SHA-0 (preliminary version of SHA-1) =
was reported in 2004, then many research on the structure of SHA-1 were =
conducted. In the case of SHA-2, it is harder than SHA-1 to find =
collisions.

Existing security consideration and evaluation criteria were extensively =
discussed in the NIST SHA-3 competition. Please see the following sites.

https://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo
https://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories

We need similar analysis on RIPEMD160 and impacts of attacks on =
(RIPEMD160(SHA2(msg)).=20

We can also refer the security assumption of hash chain in Asiacrypt =
2004 Paper.=20
https://home.cyber.ee/~ahtbu/timestampsec.pdf

In the discussion of SHA3 competition, we choose another hash design =
structure, so called "sponge structure." This leads diversity of design =
principles of hash function and gives resilience even when one hash =
design structure becomes vulnerable. As Peter Todd wrote, discussion on =
design structure and algorithm is important. Discussions on all of =
algorithm, output length and security requirements are needed.

At some future moment, we should think about transition of underlying =
hash functions. I=E2=80=99m working on this subject and will present an =
idea at IEEE S&B.

Shin=E2=80=99ichiro Matsuo


> On Feb 25, 2017, at 8:10 AM, Ethan Heilman via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> >SHA1 is insecure because the SHA1 algorithm is insecure, not because =
160bits isn't enough.
>=20
> 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.
>=20
> 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):
>=20
> >Collisions are similar, though in this case both public keys are =
under the adversary=E2=80=99s 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.=20
>=20
> 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?=20
>=20
> For both reasons of credibility and good engineering (safety margins) =
Bitcoin should strive to always use cryptography which is beyond =
reproach.
>=20
>=20
> 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
>=20
> =
https://security.googleblog.com/2017/02/announcing-first-sha1-collision.ht=
ml?m=3D1
>=20
>=20
> Em 25/02/2017 10:47, "Steve Davis via bitcoin-dev" =
<bitcoin-dev@lists.linuxfoundation.org> escreveu:
>=20
> > 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,
>=20
> =E2=80=A6so far. I wonder how long that vacation will last?
>=20
> > but it also hasn't been
> > as closely studied as more common hash algorithms.
>=20
> ...but we can be sure that it will be, since the dollar value held in =
existing utxos continues to increase...
>=20
> > That said, Bitcoin uses
> > RIPEMD160(SHA256(msg)), which may make creating collisions harder if =
an attack
> > is found than if it used RIPEMD160 alone.
>=20
> Does that offer any greater protection? That=E2=80=99s 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=E2=80=99t=
 seem to me to increase the difficulty by any significant amount?
>=20
>=20
> /s
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>=20
>=20
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>=20
>=20
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev