diff options
| author | Shin'ichiro Matsuo <matsuo@mac.com> | 2017-02-25 09:45:36 -0800 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2017-02-25 18:45:49 +0000 |
| commit | d51db9d2bd545e6e5f3c8d3e6985cb2fff6fde84 (patch) | |
| tree | 6a549d6ed3f895cb4d2582c407cd6133826be4d2 | |
| parent | 7a7f129120ed7281e495a7d7318f0b31ee1c5b36 (diff) | |
| download | pi-bitcoindev-d51db9d2bd545e6e5f3c8d3e6985cb2fff6fde84.tar.gz pi-bitcoindev-d51db9d2bd545e6e5f3c8d3e6985cb2fff6fde84.zip | |
Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers
| -rw-r--r-- | 2a/1fd8556332d49ba166bc3ad1343995a72f9605 | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/2a/1fd8556332d49ba166bc3ad1343995a72f9605 b/2a/1fd8556332d49ba166bc3ad1343995a72f9605 new file mode 100644 index 000000000..54fc94bcf --- /dev/null +++ b/2a/1fd8556332d49ba166bc3ad1343995a72f9605 @@ -0,0 +1,214 @@ +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 + + |