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 ------------------------------------------------------------------------------ _______________________________________________ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
