1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
Return-Path: <henning.kopp@uni-ulm.de>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id DEE9095E
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 27 Feb 2017 09:27:32 +0000 (UTC)
X-Greylist: delayed 00:11:52 by SQLgrey-1.7.6
Received: from smtp.uni-ulm.de (smtp.uni-ulm.de [134.60.1.26])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4A156106
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 27 Feb 2017 09:27:31 +0000 (UTC)
X-Virus-Scanned: amavisd-new at uni-ulm.de
Received: from banane.informatik.uni-ulm.de (banane.informatik.uni-ulm.de
[134.60.77.114]) (authenticated bits=0)
by mail.uni-ulm.de (8.14.9/8.14.9) with ESMTP id v1R9FT2k004614
(version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256 verify=NOT);
Mon, 27 Feb 2017 10:15:30 +0100 (CET)
Date: Mon, 27 Feb 2017 10:15:29 +0100
From: Henning Kopp <henning.kopp@uni-ulm.de>
To: "Shin'ichiro Matsuo" <matsuo@mac.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20170227091529.GB2538@banane.informatik.uni-ulm.de>
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>
<81BE82BA-EDFC-45D1-84DE-D65EC24C9F41@mac.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <81BE82BA-EDFC-45D1-84DE-D65EC24C9F41@mac.com>
User-Agent: Mutt/1.7.1 (2016-10-04)
X-DCC-INFN-TO-Metrics: poseidon 1233; Body=3 Fuz1=3 Fuz2=3
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_NONE,
RP_MATCHES_RCVD autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.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
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: Mon, 27 Feb 2017 09:27:33 -0000
Hi all,
I did not follow the whole discussion, but wanted to throw in some
literature on the failure of crypto primitives in Bitcoin.
There is a paper which discusses the problems, but does not give any
remedies: https://eprint.iacr.org/2016/167.pdf
And there are also contingency plans on the wiki:
https://en.bitcoin.it/wiki/Contingency_plans These are not very
detailed and my impression is that this information should be viewed
very critically (E.g., when ECDSA is broken, the suggested vague
response is "Switch to the stronger algorithm." Yeah. And "Code for
all of this should be prepared." Surely. As far as I know, there is no
such code and no-one is working on it).
Best,
Henning
On Sat, Feb 25, 2017 at 09:45:36AM -0800, Shin'ichiro Matsuo via bitcoin-dev wrote:
> 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)).
>
> We can also refer the security assumption of hash chain in Asiacrypt 2004 Paper.
> 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’m working on this subject and will present an idea at IEEE S&B.
>
> Shin’ichiro Matsuo
>
>
> > On Feb 25, 2017, at 8:10 AM, Ethan Heilman via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> 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. 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.
> >
> > 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):
> >
> > >Collisions are similar, though in this case both public keys are under the adversary’s 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.
> >
> > 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?
> >
> > For both reasons of credibility and good engineering (safety margins) Bitcoin should strive to always use cryptography which is beyond reproach.
> >
> >
> > 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
> >
> > https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html?m=1
> >
> >
> > Em 25/02/2017 10:47, "Steve Davis via bitcoin-dev" <bitcoin-dev@lists.linuxfoundation.org> escreveu:
> >
> > > 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,
> >
> > …so far. I wonder how long that vacation will last?
> >
> > > but it also hasn't been
> > > as closely studied as more common hash algorithms.
> >
> > ...but we can be sure that it will be, since the dollar value held in existing utxos continues to increase...
> >
> > > That said, Bitcoin uses
> > > RIPEMD160(SHA256(msg)), which may make creating collisions harder if an attack
> > > is found than if it used RIPEMD160 alone.
> >
> > Does that offer any greater protection? That’s 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’t seem to me to increase the difficulty by any significant amount?
> >
> >
> > /s
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--
Henning Kopp
Institute of Distributed Systems
Ulm University, Germany
Office: O27 - 3402
Phone: +49 731 50-24138
Web: http://www.uni-ulm.de/in/vs/~kopp
|
