public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Troy Benjegerdes <hozer@hozed.org>
To: Thomas Voegtlin <thomasv1@gmx.de>
Cc: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] New BIP32 structure
Date: Thu, 27 Mar 2014 10:17:58 -0500	[thread overview]
Message-ID: <20140327151758.GE3180@nl.grid.coop> (raw)
In-Reply-To: <53342C6C.2060006@gmx.de>

On Thu, Mar 27, 2014 at 02:49:32PM +0100, Thomas Voegtlin wrote:
> 
> 
> Le 27/03/2014 13:49, Mike Hearn a écrit :
> > 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 the
> > seeds harder to write down on paper. So should this be a degree of freedom?
> >
> 
> 
> Here is what I understand:
> 
> 2^128 iterations is not brute forcable today, and will not be for the 
> foreseeable future.

I foresee 2^128 being brute forceable in 20-25 years. See below.
 
> An EC pubkey of length n can be forced in approximately 2^(n/2) 
> iterations (see http://ecc-challenge.info/) Thus, Bitcoin pubkeys, which 
> are 256 bits, would require 2^128 iterations. This is why unused 
> addresses (160 bits hash) are better protected than already used ones.
> 
> However, people tend to believe that a public key of size n requires 2^n 
> iterations. This belief might have been spread by this popular image:
> https://bitcointalk.org/index.php?topic=508880.msg5616146#msg5616146

So I assume this image is using the Landauer principle for minimum 
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 
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 
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 
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 
mailing list, or a got a contract to develop and ECDSA cracker, in 
which case you probably won't hear from me again until I have a talk
at DEFCON showing it off.


-- Troy Benjegerdes



  parent reply	other threads:[~2014-03-27 15:18 UTC|newest]

Thread overview: 100+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-03-26 20:49 [Bitcoin-development] New BIP32 structure Mike Hearn
2014-03-26 23:37 ` Andreas Schildbach
2014-03-27  1:01   ` Alan Reiner
2014-03-27  6:15     ` Mike Belshe
2014-03-27 10:57   ` Thomas Voegtlin
2014-03-27 11:39     ` Mike Hearn
2014-03-27 13:30       ` Thomas Voegtlin
2014-03-27 13:38         ` Mike Hearn
2014-03-27  1:13 ` Allen Piscitello
2014-03-27  5:34 ` Troy Benjegerdes
2014-03-27  7:09 ` Tamas Blummer
2014-03-27  9:42   ` Mike Hearn
2014-03-27 11:35   ` Pavol Rusnak
2014-03-27 15:43   ` Jeff Garzik
2014-03-27 15:57     ` Allen Piscitello
2014-03-27 16:06       ` Pavol Rusnak
2014-03-27 16:13         ` Allen Piscitello
2014-03-27 16:07       ` Tamas Blummer
2014-03-27 16:14       ` Pieter Wuille
2014-03-27 16:21         ` Pavol Rusnak
2014-03-27 16:28           ` Pieter Wuille
2014-03-27 17:49             ` Allen Piscitello
2014-03-28 14:59             ` slush
2014-04-08 12:43               ` slush
2014-04-08 13:18                 ` Pieter Wuille
2014-04-08 13:40                   ` slush
2014-04-08 13:43                     ` slush
2014-04-08 13:53                       ` Pieter Wuille
2014-04-08 13:59                         ` Thomas Voegtlin
2014-04-08 14:00                         ` Tamas Blummer
2014-04-08 14:35                         ` Pavol Rusnak
2014-04-08 15:41                         ` slush
2014-04-23 17:42                           ` Pieter Wuille
2014-04-23 18:01                             ` slush
2014-04-23 18:18                               ` slush
2014-04-23 18:39                                 ` Tier Nolan
2014-04-23 18:46                                   ` Pavol Rusnak
2014-04-23 19:00                                     ` Tier Nolan
2014-04-23 19:06                                       ` slush
2014-04-23 19:36                                         ` Tamas Blummer
2014-04-23 19:46                                           ` slush
2014-04-23 19:07                                       ` Tamas Blummer
2014-04-23 19:29                                       ` Pavol Rusnak
2014-04-23 19:44                                         ` Luke-Jr
2014-04-23 19:49                                           ` Pavol Rusnak
2014-04-23 19:55                                             ` Luke-Jr
2014-04-23 19:57                                               ` slush
2014-04-23 20:01                                                 ` Luke-Jr
2014-04-23 20:04                                                   ` Pavol Rusnak
2014-04-23 20:09                                                     ` Luke-Jr
2014-04-23 20:16                                                       ` Pavol Rusnak
2014-04-23 20:32                                                         ` Luke-Jr
2014-04-23 20:35                                                           ` Pavol Rusnak
2014-04-23 20:41                                                             ` Luke-Jr
2014-04-23 20:43                                                               ` Pavol Rusnak
2014-04-23 20:54                                                                 ` Pieter Wuille
2014-04-23 21:06                                                                   ` Pavol Rusnak
2014-04-23 21:18                                                                     ` Luke-Jr
2014-04-23 21:22                                                                       ` Gregory Maxwell
2014-04-23 21:33                                                                         ` Pavol Rusnak
2014-04-23 21:42                                                                           ` Pieter Wuille
2014-04-23 21:44                                                                             ` Pavol Rusnak
2014-04-23 21:48                                                                             ` Gregory Maxwell
2014-04-23 21:53                                                                           ` Luke-Jr
2014-04-23 21:24                                                                       ` Pavol Rusnak
2014-04-23 21:07                                                                   ` slush
2014-04-23 20:59                                                                 ` Luke-Jr
2014-04-23 20:17                                                       ` Tamas Blummer
2014-04-23 20:12                                                     ` Pieter Wuille
2014-04-23 20:08                                                   ` Pieter Wuille
2014-04-23 20:01                                               ` Tamas Blummer
2014-04-23 20:02                                                 ` Luke-Jr
2014-04-23 20:04                                                   ` Tamas Blummer
2014-04-24  6:54                                           ` Thomas Voegtlin
2014-04-24  7:10                                             ` Pieter Wuille
2014-04-24  7:21                                               ` Gregory Maxwell
2014-04-24  8:15                                                 ` Thomas Voegtlin
2014-04-24  7:42                                               ` Thomas Voegtlin
2014-04-24  8:09                                               ` Mike Hearn
2014-04-23 18:48                                   ` Tamas Blummer
2014-04-08 14:49                 ` Andreas Schildbach
2014-04-08 15:46                   ` slush
2014-04-08 15:58                     ` Andreas Schildbach
2014-04-08 16:24                       ` slush
2014-03-27 11:20 ` Thomas Voegtlin
     [not found]   ` <CAJna-HhmFya+3W67qQt0wMhW=B4vJvwdkr-5WnU+KEaKq7uaUA@mail.gmail.com>
2014-03-27 12:06     ` Thomas Voegtlin
2014-03-27 12:28       ` Mike Hearn
2014-03-27 12:49         ` Mike Hearn
2014-03-27 13:12           ` Thomas Kerin
2014-03-27 13:19             ` Mike Hearn
2014-03-27 13:49           ` Thomas Voegtlin
2014-03-27 13:58             ` Jim
2014-03-27 14:20               ` Mike Hearn
2014-03-27 15:17             ` Troy Benjegerdes [this message]
2014-03-27 13:07         ` Matias Alejo Garcia
2014-03-27 13:44       ` Pavol Rusnak
2014-03-27 13:53         ` Thomas Voegtlin
2014-03-27 14:03           ` Pavol Rusnak
     [not found]       ` <CAJna-HitjJbL9TnfxTY=+TvfaeNvZM6aPWmNYmHUCwmw6V8PUg@mail.gmail.com>
2014-03-27 15:04         ` Thomas Voegtlin
2014-03-27 11:36 ` Pavol Rusnak

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20140327151758.GE3180@nl.grid.coop \
    --to=hozer@hozed.org \
    --cc=bitcoin-development@lists.sourceforge.net \
    --cc=thomasv1@gmx.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox