Brute Forceing 128 bit ECDSA keys

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 an 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