From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 97891259 for ; 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 ; 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 In-reply-to: Date: Sat, 25 Feb 2017 09:45:36 -0800 Content-transfer-encoding: quoted-printable Message-id: <81BE82BA-EDFC-45D1-84DE-D65EC24C9F41@mac.com> References: <8F096BE1-D305-43D4-AF10-2CC48837B14F@gmail.com> <20170225010122.GA10233@savin.petertodd.org> <208F93FE-B7C8-46BE-8E00-52DBD0F43415@gmail.com> To: Bitcoin Protocol Discussion 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 = 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 = 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" = escreveu: >=20 > > On Feb 24, 2017, at 7:01 PM, Peter Todd 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