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
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <hozer@grid.coop>) id 1WTC4F-0004sO-Px
for bitcoin-development@lists.sourceforge.net;
Thu, 27 Mar 2014 15:18:07 +0000
X-ACL-Warn:
Received: from nl.grid.coop ([50.7.166.116])
by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1WTC4E-0002FS-9L for bitcoin-development@lists.sourceforge.net;
Thu, 27 Mar 2014 15:18:07 +0000
Received: from localhost (localhost [127.0.0.1]) (uid 1000)
by nl.grid.coop with local; Thu, 27 Mar 2014 10:17:58 -0500
id 000000000006A348.0000000053344126.00005B33
Date: Thu, 27 Mar 2014 10:17:58 -0500
From: Troy Benjegerdes <hozer@hozed.org>
To: Thomas Voegtlin <thomasv1@gmx.de>
Message-ID: <20140327151758.GE3180@nl.grid.coop>
References: <CANEZrP2hbBVGqytmXR1rAcVama4ONnR586Se-Ch=dsxOzy2O4w@mail.gmail.com>
<53340999.807@gmx.de>
<CAJna-HhmFya+3W67qQt0wMhW=B4vJvwdkr-5WnU+KEaKq7uaUA@mail.gmail.com>
<5334144A.9040600@gmx.de>
<CANEZrP37dO53Jp2rXpPqO3eMd6AWamtXaReq0arMfC=uY2aFUA@mail.gmail.com>
<CANEZrP21X_Uk+_XWN6y2tgiup07Xd12bZZoFfnheG_Lz-ipbPQ@mail.gmail.com>
<53342C6C.2060006@gmx.de>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
In-Reply-To: <53342C6C.2060006@gmx.de>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Mime-Autoconverted: from 8bit to quoted-printable by courier 0.68.2
X-Spam-Score: -0.4 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-0.4 RP_MATCHES_RCVD Envelope sender domain matches handover relay
domain
X-Headers-End: 1WTC4E-0002FS-9L
Cc: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] New BIP32 structure
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Thu, 27 Mar 2014 15:18:08 -0000
On Thu, Mar 27, 2014 at 02:49:32PM +0100, Thomas Voegtlin wrote:
>=20
>=20
> Le 27/03/2014 13:49, Mike Hearn a =E9crit :
> > Ah, BIP32 allows for a range of entropy sizes and it so happens that
> > they picked 256 bits instead of 128 bits.
> >
> > I'd have thought that there is a right answer for this. 2^128 should =
not
> > be brute forceable, and longer sizes have a cost in terms of making t=
he
> > seeds harder to write down on paper. So should this be a degree of fr=
eedom?
> >
>=20
>=20
> Here is what I understand:
>=20
> 2^128 iterations is not brute forcable today, and will not be for the=20
> foreseeable future.
I foresee 2^128 being brute forceable in 20-25 years. See below.
=20
> An EC pubkey of length n can be forced in approximately 2^(n/2)=20
> iterations (see http://ecc-challenge.info/) Thus, Bitcoin pubkeys, whic=
h=20
> are 256 bits, would require 2^128 iterations. This is why unused=20
> addresses (160 bits hash) are better protected than already used ones.
>=20
> However, people tend to believe that a public key of size n requires 2^=
n=20
> iterations. This belief might have been spread by this popular image:
> https://bitcointalk.org/index.php?topic=3D508880.msg5616146#msg5616146
So I assume this image is using the Landauer principle for minimum=20
energy ( http://en.wikipedia.org/wiki/Landauer%27s_principle ), however
it is unknown (to me at least) if a reversible computing ecdsa forcing
algorithm could be implemented. (this may or may not be a quantum
computing device)
Let's suppose for a moment you could, and get a million times better=20
than the Landauer pinciple limit of 2.85 zJ per bit, so we have total
energy to cycle through 128 bits of address space of:
units "2**128 * 2.85zJ / 1e6" "megawatt*hours"
* 269.39021
An attacker with a sub-Landauer limit/1e6 cracker would need a lot of
silicon area, and a couple of hours energy from a large wind farm, and
could siphon that energy out in a rural area without anyone noticing=20
anything other than a few shipping containers and that the wind turbines
are running more on windy days.
If we go back to just Landauer limit, and assume a 10MW system that=20
runs 24x7 (much like the NCSA Blue Waters Cray machine), we need:
(please check my math, or point out any stupid assumptions I've made)
units "2**128 * 2.85zJ / 10 megawatts" " years"
* 3073.1914
Or 3000 years. Well that still sounds pretty safe. How about 250MW?
units "2**128 * 2.85zJ / 250 megawatts" " years"
* 122.92766
Now I'm starting to get worried, because when I started computing, it
was on an 8-bit CPU that was measured in thousand operations-per-second.
In 1996 the largest supercomputer in the world was ASCII Red, with an
amazing 1 trillion floating-point operations per second. This morning
I have a 1-2 Teraflop water-cooled graphics processor sitting next to
me warming the room.
I expect in 5-10 years we'll have silicon with 256 bit registers that
may be able to do thousands or millions of ECDSA calculations per
second per computation unit.
So if you stop hearing from me here, it's because I found a better=20
mailing list, or a got a contract to develop and ECDSA cracker, in=20
which case you probably won't hear from me again until I have a talk
at DEFCON showing it off.
-- Troy Benjegerdes
|