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 62B936C for ; Sat, 25 Feb 2017 18:37:31 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-vk0-f68.google.com (mail-vk0-f68.google.com [209.85.213.68]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DF1A914E for ; Sat, 25 Feb 2017 18:37:30 +0000 (UTC) Received: by mail-vk0-f68.google.com with SMTP id r136so3538671vke.1 for ; Sat, 25 Feb 2017 10:37:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=k0BpqV/9DBJSAzeDAUUXuJr/bzQ3jhX1I3QVhNsLrNA=; b=ZYqVe95VMpZswyWCN80bQIL1N4K7SH1ZxJSn63KT7lGmUdKrCdIjY46GveqvhCwXfF o2g8VmWFtipvDLBkkZpORyCT5kdLAtEAXPoOxzjjZ4vnV86jYSDu6inGNRkLnE31z8+i 6c+MsleOGabdAsgaYI5Kf0VbpwxK0dRVPLgiAAKg390Prpm1V66Cjda0FNHl38SDKmlK I+t3FW9gNLxxoiTKxxk+DFZVcc5+PMVvbPpG3aIBrakR9KRzCQh5vP1PUpIsM2Ll9B5B iBm/VKaCCjtnfCI+UqPp3TAoGXCCFxNb63vmIAwCvKkdlzLCQ7URe5Yy0E6sWVQQj1ni M4qg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=k0BpqV/9DBJSAzeDAUUXuJr/bzQ3jhX1I3QVhNsLrNA=; b=t+79kFLruWEfCUNCMmQ1ovzaLgQVo4e05ikPwxJiyc+X3VPP0u5IQA08BNi9HvEDnr W0cLlE8h1lQ04u9bBZMF65HYpQOvVVYvPSv1mLLppzcMJu7Zdk66QAC41sXUyttkb5J0 DRRdwPTdFwN2L3sgwxx8olRZQpYIMpOcS185ouPwGOQx17kAS4USrkrL4Pwaw3sNfUfy ZLhQv2tIEP0vQqEsKZ2U8KGB7AFK4Mruqfl3F8wvHC8jZA76G8cB0NYMdC1ncCCKxahx x71III8javof/lGyj1suJY6PE/6N0pXzX346pPTl/PUay7ZUsF/pittRFPNBcs2MgPla vmiQ== X-Gm-Message-State: AMke39mWKzYMd1YAmlyw3HVsxNOMnBiRr+tR6D7qZ98/7UhzVK4uynUaBfVsuh+2ROUatPNGonpl2gOJsKvBJg== X-Received: by 10.31.70.66 with SMTP id t63mr2844924vka.19.1488047850065; Sat, 25 Feb 2017 10:37:30 -0800 (PST) MIME-Version: 1.0 Received: by 10.176.6.106 with HTTP; Sat, 25 Feb 2017 10:36:49 -0800 (PST) In-Reply-To: References: <8F096BE1-D305-43D4-AF10-2CC48837B14F@gmail.com> <20170225010122.GA10233@savin.petertodd.org> <208F93FE-B7C8-46BE-8E00-52DBD0F43415@gmail.com> From: Ethan Heilman Date: Sat, 25 Feb 2017 13:36:49 -0500 Message-ID: To: Alice Wonder , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=001a11484ae083228c05495f234b X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org 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:37:31 -0000 --001a11484ae083228c05495f234b Content-Type: text/plain; charset=UTF-8 >You have to not only produce a ripemd160 collision, you have to produce a collision that is also a valid sha-256 hash - and that's much much much more difficult. I agree that merely finding a collision in RIPEMD-160 will be hard to use in Bitcoin. However finding a collision in RIPEMD-160(SHA-256(msg)) via bruteforce (2^80 queries) is not particular more difficult than finding a collision in RIPEMD-160 via brute force. Furthermore if you find a collision in RIPEMD-160(SHA-256(msg)) you also get a valid SHA-256 hash for which you know the preimage. On Sat, Feb 25, 2017 at 1:19 PM, Alice Wonder via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > On 02/25/2017 08:10 AM, Ethan Heilman via bitcoin-dev wrote: > >> 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. >> > > You have to not only produce a ripemd160 collision, you have to produce a > collision that is also a valid sha-256 hash - and that's much much much > more difficult. > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --001a11484ae083228c05495f234b Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
>You have to not only = produce a ripemd160 collision, you have to produce a collision that is also= a valid sha-256 hash - and that's much much much more difficult.

= I agree that merely finding a collision in RIPEMD-160 will be hard to use i= n Bitcoin.

However finding a collision in RIPEMD-160(SHA-256(msg)) v= ia bruteforce (2^80 queries) is not particular more difficult than finding = a collision in RIPEMD-160 via brute force. Furthermore if you find a collis= ion in RIPEMD-160(SHA-256(msg)) you also get a valid SHA-256 hash for which= you know the preimage.


On Sat, Feb 25, 2017 at 1:19 PM, Alice Wonder via bitco= in-dev <bitcoin-dev@lists.linuxfoundation.org><= /span> wrote:
On 02/25/2= 017 08:10 AM, Ethan Heilman via bitcoin-dev wrote:
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.

 You have to not only produce a ripemd160 collision, you have to produce a c= ollision that is also a valid sha-256 hash - and that's much much much = more difficult.


_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev

--001a11484ae083228c05495f234b--