path: root/2a/1fd8556332d49ba166bc3ad1343995a72f9605

Return-Path: <matsuo@mac.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 97891259
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 25 Feb 2017 18:45:49 +0000 (UTC)
X-Greylist: delayed 01:00:00 by SQLgrey-1.7.6
Received: from st11p02im-asmtp002.me.com (st11p02im-asmtp002.me.com
	[17.172.220.114])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C387714D
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 25 Feb 2017 18:45:47 +0000 (UTC)
Received: from process-dkim-sign-daemon.st11p02im-asmtp002.me.com by
	st11p02im-asmtp002.me.com
	(Oracle Communications Messaging Server 7.0.5.38.0 64bit (built Feb 26
	2016)) id <0OLX01800YI2QW00@st11p02im-asmtp002.me.com> for
	bitcoin-dev@lists.linuxfoundation.org;
	Sat, 25 Feb 2017 17:45:46 +0000 (GMT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mac.com; s=4d515a;
	t=1488044746; bh=Jw4eSiJtNiFbVv+cXsfiFQC2CbvQ3jSGGZujN1Eil4c=;
	h=Content-type:MIME-version:Subject:From:Date:Message-id:To;
	b=m1833qIQLKZQAo474zCxu7G+B9VChP+YBri/VyiOLh0+GZ5WvnKHSYPjniFI9UKBN
	TRWDjK1cVXKHAIPG/2jhzbiPIJ6Bos8y5JXaEqpbrftYlecS5+6hsHFRA+/JSa6Lyr
	OIERBDsC30/+Hg1syQEJS/VFKLNvySXH1YrgxdGKym2bY6SeUQuly6zIQaD3TOHWws
	Sp6DsNymvmGkqikQlZhwSbY3tgpQGk0nvYDl0kJgF6R/fXBXFp9ryLhCl94MqkeUid
	IO1baebpn5UiXMGw4mF29qE008ZQUgtir5zd01JF+G9XpQ3gdu75quMz2G5xEjYQfV
	NisD7+vvfot1g==
Received: from icloud.com ([127.0.0.1]) by st11p02im-asmtp002.me.com
	(Oracle Communications Messaging Server 7.0.5.38.0 64bit (built Feb 26
	2016))
	with ESMTPSA id <0OLX00TRQYO68H30@st11p02im-asmtp002.me.com>; Sat,
	25 Feb 2017 17:45:45 +0000 (GMT)
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,,
	definitions=2017-02-25_14:,, signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0
	clxscore=1034 suspectscore=0 malwarescore=0 phishscore=0 adultscore=0
	bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1
	engine=8.0.1-1701120000 definitions=main-1702250177
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>
X-Mailer: Apple Mail (2.3259)
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
	RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Sat, 25 Feb 2017 18:47:08 +0000
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sat, 25 Feb 2017 18:45:49 -0000

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