How to steal Satoshi's stash?

[Cheena]

You cannot steal my stash.

Regards

Satoshi Nakamoto

[Syke]

tl,dr: brute forcing a private key being it 128bit or 256bit is impossible today it's stupid to even try, and I've already provided the math for this and we do not disagree on this, my point is, in the next few decades we will eventually reach the point where we will have enough computing power to be able to do so as happened in the past!  

I'll let Bruce educate you.

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38×10-16 erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume 4.4×10-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21×1041 ergs. This is enough to power about 2.7×1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

But that's just one star, and a measly one at that. A typical supernova releases something like 1051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

No, it's not going to happen in a few decades. It will never happen.

[krampus]

Are you twelve ? You are making yourself looks worst and worst, so again where are your proves? where are your facts? your arguments? weren't you calling me an uneducated idiot in your previous comment? what's happened to that?

Re-read my post. I'm not offering any "proves" or facts. It would be a monumental waste of effort, since several people (who are probably smarter than me) have already tried to explain the basics to you right here in this thread. You dismissed them out of hand, without even a very good rationale for doing so. Why would I offer insight to someone who clearly isn't interested in it? What kind of an idiot would I be if I took that particular bait?

Nope. Not going to do it. I understand the problem in ways that you clearly don't, and I'm utterly un-interested in trying to "help" you. You're a willful fucking idiot, and I'm quite happy to let you go on being a willful fucking idiot for the rest of your stupid life.

Ta-ta!

[jonald_fyookball]

This was answered before and I'll answer this again 10^70Flops is something inconceivable today! I don't think we disagree with this point, and I've been repeating this for a dozens of times, today we cannot brute force a 256bit encryption heck not even close to 128bit this is not even a point.

Where we disagree is in terms of future prospect.  

Dude...bro... You are STILL missing the freaking point!

No one is questioning the advancement of technology
or even our ability to predict...but its essentially
PHYSICALLY IMPOSSIBLE to make a computer that
would do 10^70 FLOPS.

Let's do the math, shall we:


1. size of atom is roughly 0.0000000000001 meters

...therefore...

2. Number of atoms in a meter = 10^13
3. Number of atoms you could fit into a cubic meter = 10^39

...also...


4. speed of light = 299,792,458 metres per second

...thus...

5. time required for light to travel the distance of 1 meter =
1/299792458 seconds = .000000003335 seconds.

6. time required for light to travel the length of 1 atom =
0.000000000000000000003335 seconds.
 
7. If SOMEHOW, in this tiny timeframe,
a floating point operation could be
done using the space of a single atom,
you would get 2.99*10^20 FLOPS for each atom-size "bit".
(take the reciprocal of the above number)

8. So a cubic-meter sized computer filled with atoms
back to back, each calculating at the speed of light
would still only get you 2.99 *10^59 FLOPS.

9. to get to 10^70, you would need 33 billion of these
cubic meters sized computers.  Stacked end to end, these cubes
would go to the moon and back 42 times.  

See, it always comes down to the answer: 42.

[kuroman]

I'll let Bruce educate you.

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38×10-16 erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume 4.4×10-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21×1041 ergs. This is enough to power about 2.7×1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

But that's just one star, and a measly one at that. A typical supernova releases something like 1051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

Thanks refresh on the basics thermodynamics, The calculation is a bit off and pretty simplistic and in fact the amount of energy needed is more than that, but again that calculation is only taking into consideration TODAYS computing power and we are just repeating our selfs here,And I don't understand what you don't get here, there is no point on starting a computation today to do such a thing and this what the argument above is presenting no more no less. the minimum amount of time needs is in the order of 10^55 years, in by the second law of themodynamics by that time there will be nothing left in the universe not a single star the only things left would be blackholes and even those will eventually start evaporating (degenerescence or blackhole era)

Anyway let me simplify things since a lot of people seems to be confused here:

Just to put things in a human scale, let's assume that there are no oceans and you can "walk" all the way between continents, a few centuries ago, it would be impossible to go around the world (objective here to go around the world at the equator 10 times) and at the period the best you can do on ground is walking/running using horses and as we can it was impossible to come even close to a faction of the necessary distance to achieve the objective (the circumference of earth at the equator is 40 075,017, and your speed won't exceed an average of 5km an hour it's easy to see the issue here we are talking easily millennias ). Today, it take the International space station around 90min to orbit the earth so 10 orbits should take around 15hrs.

brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

This is totally wrong, and it is your own misinterpretation, and you are welcome to quote the exact word they used. I'm pretty sure what they mean is that with todays technology to be able to brute force against 256bit you'll need a computer of a size bigger than the universe (which is to say yet again Impossible!)

I'll also invite you just for the sake of reference, to check the 80s tech and security magazines if you have access to those in your city library and check what they were saying about 56bit encryption at the time, you'll be really surprised on how the argument you are advancing are similar if not the same of what was said at the time.

[DeathAndTaxes]

brute forcing a private key being it 128bit or 256bit is impossible today it's stupid to even try, and I've already provided the math for this and we do not disagree on this, my point is, in the next few decades we will eventually reach the point where we will have enough computing power to be able to do so as happened in the past!  

No we won't.   You seem to vastly underestimate how large 10^70, 2^128, and 2^160 are.

In 40 years Moore's law has provided roughly 1*10^6 improvement in transistor density and a roughly comparable improvement in cost per unit of computing power and power per unit of computing power.  It is highly likely that Moore's law will not be sustained for another 40 years, Intel may actually slip below that "benchmark" for the first in this decade.  The cost to build smaller and smaller process nodes is increasing exponentially and the time between process nodes (which should be no more than 24 months) is slowly inching upward.  Lets not even get into the fact that there are only 8 maybe 9 process nodes before we get down to the transistors using 3 atoms a piece.  

Still lets assume that an equivalent amount of improvement occurs over the next 4 decades.  That is a ~10^6.  Today top supercomputers are PFLOP scale.  Lets ignore the fact that Integer performance is often a magnitude worse and that it takes tens of thousands of operations to complete a single keypair (and even more to perform lookups).  Lets just naively assume that 1 ECDSA key generation and lookup can be done in 1 FLOP (which doesn't even make sense but trying to be ultra conservative).  That would mean today a top super computer could do ~34 PK/s (peta keys per second).  To keep the math simple lets just round up to 100 PK/s or 1*10^17 kps.

If we then assume a 1*10^6 factor improvement in relative performance in the next 40 years that would make a top SC something on the order of 1*10^23 kps.  Now lets assume you build one for every man woman and child on the planet (estimated to be ~10 B in 2054).  That would put world wide key breaking power at 1*10^33 kps.   You aren't even within the same ballpark as  10^70.

In reality performance will probably slip below Moore's law, you can't process on key per clock cycle, and even if you could we are looking at an energy requirement greater than what is used by the entire human race for all other purposes.

[porcupine87]

This is totally wrong, and it is your own misinterpretation, and you are welcome to quote the exact word they used. I'm pretty sure what they mean is that with todays technology to be able to brute force against 256bit you'll need a computer of a size bigger than the universe (which is to say yet again Impossible!)

I can understand your point. A few centuries ago things seemed to be so far away like today breaking a 256 bit key. Although it is funny to watch a documentary from 1970 "how will the year 2000 look like?". No, we are not flying with cars around and no, we have no 15h weeks

I am on your side, that we never know what the future brings. But the statement from "Bruce" has nothing to do with "today's technology". He just makes the assumption that you need energy to represent information. To turn around a bit. Without that you cannot count or calculate. You need energy. And in our solar system we have a limited amount of energy (to a given time). So when you use all the energy of the solar system over its whole life span, you still have not enough energy to count to 2^256.

This has nothing to do with today's technology. Again: The statement is about energy, which you need for counting and energy is limited.

[DeathAndTaxes]

Thanks refresh on the basics thermodynamics, The calculation is a bit off and pretty simplistic and in fact the amount of energy needed is more than that, but again that calculation is only taking into consideration TODAYS computing power.

How about you read what was written?   It was talking about a PERFECT computer (a theoretical construct), not a computer built today, or one built with technology a century from now but one which operates at the thermodynamic limit and in roughly absolute zero.  Nothing more efficient is possible.  It is many quadrillions of times more efficient than today's computers.  The human race may never build a perfect classical computer but it is often used as an upper bound as it takes into account all possible performance increases.  Not only does the example use a perfect computer but it is powered using the entire output of our star for the next four billion years or so.  The example was just counting (i.e. 1 bit flip per increment).   Generating a single ECDSA key involves tens of thousands of operations and each of those involve hundreds of bits so even for a perfect computer it is something on the order of millions of bit flips per ECDSA key and thus the power requirements would be millions of times higher.

Keys of 128 bit strength are unbreakable by brute force on a classical computer (even a perfect one).

This doesn't mean they can never be broken but it will be because of:
a) a break in the algorithm itself
b) it becomes possible to implement Shor's algorithm against 256 bit keys using a quantum computer.
c) implementation attack (flawed RNG, backdoor in processor, etc)

None of that has anything to do with your false claim that Moore's law will make classical computers fast enough to break 128 bit keys in a few decades.  Please find a single cite for any reputable cryptography who shares your opinion.

[Bigeyeone]

Anyone took in consideration you dont actually loose energy when you flip a bit ?

A processor just converts electric energy into heat energy . in theorie technology could be developed to convert all the heat back into electricity. it already exists , it is just not very efficient at the moment.

[criptix]

until we discover new laws of nature and physics  

Anyone took in consideration you dont actually loose energy when you flip a bit ?

A processor just converts electric energy into heat energy . in theorie technology could be developed to convert all the heat back into electricity. it already exists , it is just not very efficient at the moment.

we would still need alot of space then...

[kuroman]

Anyone took in consideration you dont actually loose energy when you flip a bit ?

A processor just converts electric energy into heat energy . in theorie technology could be developed to convert all the heat back into electricity. it already exists , it is just not very efficient at the moment.

While this is true, the second law of thermodynamics doesn't allow it or rather you can't do it indefinitly

[kuroman]

Dude...bro... You are STILL missing the freaking point!

No one is questioning the advancement of technology
or even our ability to predict...but its essentially
PHYSICALLY IMPOSSIBLE to make a computer that
would do 10^70 FLOPS.

Let's do the math, shall we:


1. size of atom is roughly 0.0000000000001 meters  

...therefore...

2. Number of atoms in a meter = 10^13       not necessary but lets assume so
3. Number of atoms in a cubic meter = 10^39  

...also...


4. speed of light = 299,792,458 metres per second

...thus...

5. time required for light to travel the distance of 1 meter =
1/299792458 seconds = .000000003335 seconds.  
6. time required for light to travel the length of 1 atom =
0.000000000000000000003335 seconds.    
7. If SOMEHOW, in this tiny timeframe,
a floating point operation could be
done using the space of a single atom,
you would get 2.99*10^20 FLOPS for each atom-size "bit".
(take the reciprocal of the above number)  

8. So a cubic-meter sized computer filled with atoms
back to back, each calculating at the speed of light
would still only get you 2.99 *10^59 FLOPS.  

9. to get to 10^70, you would need 33 billion of these
cubic meters sized computers.  Stacked end to end, these cubes
would go to the moon and back 42 times.  

See, it always comes down to the answer: 42.

I'm not going trough all the zeros not because it's not interesting, but because it hurt my eyes, please use Exponentiation.

Just to answer you claim above I just have one question : between the nucleus and and the electrons what do we have?, and inside the nucleus between Quarks what do we have? and what is the scale of this thing in comparison of real stuff there, maybe you understand what I'm getting at by now, because you made a hypothesis above about the possible number of atoms in cubic meter.

Also another thing that picked my attention which is 2.99 *10^59 FLOPS so for you this number seems to be fine right? You agree that this number is more than enough to brute force 128bit AES almost instantly right? ok do you know the link between 256bit ECDSA in private key and 128bit AES?

No we won't.   You seem to vastly underestimate how large 10^70, 2^128, and 2^160 are.

In 40 years Moore's law has provided roughly 1*10^6 improvement in transistor density and a roughly comparable improvement in cost per unit of computing power and power per unit of computing power.  It is highly likely that Moore's law will not be sustained for another 40 years, Intel may actually slip below that "benchmark" for the first in this decade.  The cost to build smaller and smaller process nodes is increasing exponentially and the time between process nodes (which should be no more than 24 months) is slowly inching upward.  Lets not even get into the fact that there are only 8 maybe 9 process nodes before we get down to the transistors using 3 atoms a piece.  

Still lets assume that an equivalent amount of improvement occurs over the next 4 decades.  That is a ~10^6.  Today top supercomputers are PFLOP scale.  Lets ignore the fact that Integer performance is often a magnitude worse and that it takes tens of thousands of operations to complete a single keypair (and even more to perform lookups).  Lets just naively assume that 1 ECDSA key generation and lookup can be done in 1 FLOP (which doesn't even make sense but trying to be ultra conservative).  That would mean today a top super computer could do ~34 PK/s (peta keys per second).  To keep the math simple lets just round up to 100 PK/s or 1*10^17 kps.

If we then assume a 1*10^6 factor improvement in relative performance in the next 40 years that would make a top SC something on the order of 1*10^23 kps.  Now lets assume you build one for every man woman and child on the planet (estimated to be ~10 B in 2054).  That would put world wide key breaking power at 1*10^33 kps.   You aren't even within the same ballpark as  10^70.

In reality performance will probably slip below Moore's law, you can't process on key per clock cycle, and even if you could we are looking at an energy requirement greater than what is used by the entire human race for all other purposes.

I've already made a more precise calculus in my previous post about, but lets take your calculus for the moment

The 10^6 factor of improvement is wrong, is the minimum of current improvement is between 10^3 and 10^4 per decade (I'll invite you to check the list of the top supercomputers in the world and approve this fact by yourself (again we are talking about classical computing we aren't even considering QC for example) We also agree that Moors law in electronics has it limits due the Quantum effects at the small scale, let me just remind you that Flops != transistor count, it's one of many facture, such architecture, alghorithms and firmwires....ect ect but this is just a side note) .

10^17KPS is your initial point right? with a factor of improvement between 10^3 and 10^4 per decade, lets just say 2 decades of 10^4 and 2 others 10^3 in over the 4 decades you took as an example, we should have an improvement of 10^14 so we will have by then (if we assume only classic computing which is by then would be obsolete in my opinion anyway we are at 10^30+ (and this is something I've already mentioned in my initial comment, and this is goes with what I said in my previous comments and I'm pretty sure it was a reply to you "in the next few decades, we will reach 10^30-10^40Flops which is more than to crach 128Bit AES in a few seconds, and we will eventually reach 10^70+" And like I said before this just considering classical computing, which will become obsolete in the next decade or two, at least in terms of supercomputing

[DeathAndTaxes]

The example provided was as extreme as I could get
1) assumes 1 key per FLOP (more like 1 key per 80,000 integer ops)
2) assumes moore's law will continue for 40 years (20 if we are lucky)
3) assumes 1 super computer per human on the planet (really)

Even that would be insufficient.  Yet you still stick with a belief that 10^70 is realistic.   There are only 10^50 atoms on the planet.   Even assuming terrahertz scale processor you would need to convert the entire planet into chips and then magically process billions of operations per atom.    What is going to power this?  Where are all the organic life going to go?

Feel free to have the last (delusional) word.  I won't see it because it isn't worth my time anymore.   You can have your own opinions but you can't have your own facts.  128 bit keys are beyond brute force with classical computing.  It doesn't matter if it is today, next decade, next millennium, or using a perfect computer and all the matter and energy in our solar system.

[jonald_fyookball]

Wake me up when there's quark based computers and
free energy generators... Until then,
I'm done with this debate.  Cheers.

[googlemaster1]

Sometimes I just go to directory.io and type in a random page number in the morning.... its like playing the lottery.... except your odds are infinitely worse (quite literally), but hey, YOU NEVER KNOW!

[tl121]

Here are some links to subjects discussed in this thread.

1. The 56 bit key used in the original NBS data encryption standard was known to be inadequate shortly after the standard was published, as this 1977 paper by Whit Diffie and Marty Hellman demonstrated:

http://vanilla47.com/PDFs/Cryptography/Cryptoanalysis/Exhaustive%20Cryptoanalysis%20of%20the%20NBS%20data%20encryption%20standards.pdf



2. Some people have claimed that it would take too much energy to calculate private keys from public keys or to reverse hash algorithms used in constructing bitcoin addresses or mining.  That's true in an engineering sense based on today's technology, but not in a physical sense.  Many years ago it was believed that the laws of thermodynamics set minimum energy limits on computation, but this was found to not be the case.  The minimum energy requirements apply to computations that are not reversible, but if the computation can be reversible, there is no theoretical minimum energy required, other than the small amount of energy to copy out the final answer so it won't be erased when the computation is reversed. As the references cited in the linked article indicate, it is possible to make any computation reversible (at the cost of extra memory).

http://en.wikipedia.org/wiki/Reversible_computing


3. Shor's algorithms for factoring and discrete log are described in his paper:

http://arxiv.org/abs/quant-ph/9508027

[DeathAndTaxes]

1. The 56 bit key used in the original NBS data encryption standard was known to be inadequate shortly after the standard was published, as this 1977 paper by Whit Diffie and Marty Hellman demonstrated:

Agreed.  The idea that anyone credible said 56 bits would never be broken is laughable.  There is even some speuclation that DES was made 56 bits specifically because the NSA already had the capability to break it from day zero.  At the time there were stronger already implemented 64 bit ciphers in place by IBM and others.  That isn't to say 64 bit would be unbreakable either but it was probably unbreakable in the 1970s (and 1980s as well).

Some people have claimed that it would take too much energy to calculate private keys from public keys or to reverse hash algorithms used in constructing bitcoin addresses or mining.  That's true in an engineering sense based on today's technology, but not in a physical sense.  Many years ago it was believed that the laws of thermodynamics set minimum energy limits on computation, but this was found to not be the case.  The minimum energy requirements apply to computations that are not reversible, but if the computation can be reversible, there is no theoretical minimum energy required, other than the small amount of energy to copy out the final answer so it won't be erased when the computation is reversed. As the references cited in the linked article indicate, it is possible to make any computation reversible (at the cost of extra memory).

Reversible computing is a theoretical concept.  No functional system has ever been produced, no even on a scale of a simple 8 bit adder.   It also isn't a new concept either there are papers going back to 1961.  six decades later are pretty much no closer than we were then.  It is entirely possible that the human race will never

http://en.wikipedia.org/wiki/Reversible_computing

3. Shor's algorithms for factoring and discrete log are described in his paper:

http://arxiv.org/abs/quant-ph/9508027

Progress on general purpose quantum computers has been agonizingly slow.  In 2001 a 4 bit number was factored.  In 2012 a 5 bit number was.   I will start to get more interested in post-quantum cryptography when they can factor a 32 bit number faster than a classical computer can.  Even that benchmark would put breaking 256 bit ECDSA years if not decades away.  NIST does a pretty good job of analyzing cryptographic threats and they still consider 256 bit ECC to be the highest level of security.  Top Secret documents are required to be safe from enemy decryption for at least 40 years (think a stealth fighter design would be obsolete by then) and ECC is good enough.  

The largest threat is probably the most boring and that is the slow and inevitable decline in effective security as academic cryptographers finds flaws and build more and more powerful attacks.  All public key systems have had a pretty bad track record against cryptanalysis over the last fifty years or so (far worse than symmetric encryption and hashing algorithms).  If I was a betting man that is where I would put my coins.  Of course if the public key is unknown the private key can be protected to a limited degree if ECDSA is partially compromised.  If your public key is known you may just be out of luck.  The early mined rewards have the public key exposed so it will be interesting when that happens.

[Twilight_Sparkle]

To get the thread back on topic. How to actually steal his stash, Brute force clearly is not a method. The earlier post about changing the protocol would work. First create a client that takes the blockchain, and have it so that it accepts transfers of the addresses of "known" satoshi coins without needing/proof of a private key, and then get everyone to use your client. Easy  

[krampus]

Sorry, but you are thinking inside the box of todays technology.
Come back after you study fractal computing (using light waves instead of those atoms).
Electromagnetic waves are the answer.

It's true what they say. Bitcointalk has no shortage of dumb fuckwits. Unfortunately, half of them think they're actually smart.

[bountygiver]

To get the thread back on topic. How to actually steal his stash, Brute force clearly is not a method. The earlier post about changing the protocol would work. First create a client that takes the blockchain, and have it so that it accepts transfers of the addresses of "known" satoshi coins without needing/proof of a private key, and then get everyone to use your client. Easy  

what you mean is create a different branch and trick everyone that your branch is the main fork?