Topic: Not understanding security of private key (Read 1412 times)
Yes, sorry, 1200 days, not 120, I misread my calculator...
Let's see for a quantum computer:
- Time complexity to find a collision for SHA256 using a quantum computer : 2^64 (assuming quadratic speedup)
That's still a LOT of operations, and if we could make a quantum computer manipulate qubits as fast as that i7 is manipulating bits, it would still need 10^8 seconds to execute that function, or about 120 days! (Or 6 days for a cluster of 20 of such computers and so on...)
- Time complexity to find a collision for SHA256 using a quantum computer : 2^64 (assuming quadratic speedup)
That's still a LOT of operations, and if we could make a quantum computer manipulate qubits as fast as that i7 is manipulating bits, it would still need 10^8 seconds to execute that function, or about 120 days! (Or 6 days for a cluster of 20 of such computers and so on...)
I think that cluster of quantum computer are not so easy to build. Anyway I obtain more than 3 years: 10^8sec=1127days.
And we have made the assumption that 1 instruction=1 operation that is not true. You need at least 250 computer to find a collision in a little more than 6 days. Assuming that actual quantum computer have the requested power, and that there'll be an halving of prices/power ratio every 3 years it tooks at least 30 years to have such a cluster cost less than a milion dollar.
With the same investment of 3 quantum computer (30M$) today you can easily take over the whole bitcoin network (with FPGA you obtain more than 30THash, with ASIC you can build at least a 2-3000THash network) so I don't really worry about quantum computer for some years.
Quote
For some problems, quantum computers offer a polynomial speedup. The most well-known example of this is quantum database search, which can be solved by Grover's algorithm using quadratically fewer queries to the database than are required by classical algorithms. In this case the advantage is provable. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.
Consider a problem that has these four properties:
-The only way to solve it is to guess answers repeatedly and check them,
-The number of possible answers to check is the same as the number of inputs,
-Every possible answer takes the same amount of time to check, and
-There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.
An example of this is a password cracker that attempts to guess the password for an encrypted file (assuming that the password has a maximum possible length).
For problems with all four properties, the time for a quantum computer to solve this will be proportional to the square root of the number of inputs. That can be a very large speedup, reducing some problems from years to seconds. It can be used to attack symmetric ciphers such as Triple DES and AES by attempting to guess the secret key.
This looks like exactly what someone bruteforcing SHA256 would need to do.Consider a problem that has these four properties:
-The only way to solve it is to guess answers repeatedly and check them,
-The number of possible answers to check is the same as the number of inputs,
-Every possible answer takes the same amount of time to check, and
-There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.
An example of this is a password cracker that attempts to guess the password for an encrypted file (assuming that the password has a maximum possible length).
For problems with all four properties, the time for a quantum computer to solve this will be proportional to the square root of the number of inputs. That can be a very large speedup, reducing some problems from years to seconds. It can be used to attack symmetric ciphers such as Triple DES and AES by attempting to guess the secret key.
Aren't database search and keyspace search pretty similar?
Isn't "lucking out and coming across a private key" similar to "finding collisions to two-to-one functions"?
From SHA-256 page :
Quote
For a hash function for which L is the number of bits in the message digest, finding a message that corresponds to a given message digest can always be done using a brute force search in 2^L evaluations. This is called a preimage attack and may or may not be practical depending on L and the particular computing environment. The second criterion, finding two different messages that produce the same message digest, known as a collision, requires on average only 2^L/2 evaluations using a birthday attack.
Damn, so the fastest seems to be 2^128, 2^64 for a quantum computer...Third time's a charm :
- Time complexity to find a collision for SHA256 using a classical computer : 2^128
- An Intel Core i7 Extreme Edition 3960X (Hex core) at 3.33 Ghz can do 178x10^9 instructions per second.
(Still assuming instructions=time complexity)
2x10^27 seconds or 60 billion billion years. Much less ridiculous, but still QUITE a lot!
Let's see for a quantum computer:
- Time complexity to find a collision for SHA256 using a quantum computer : 2^64 (assuming quadratic speedup)
That's still a LOT of operations, and if we could make a quantum computer manipulate qubits as fast as that i7 is manipulating bits, it would still need 10^8 seconds to execute that function, or about 120 days! (Or 6 days for a cluster of 20 of such computers and so on...)
So some day Bitcoin might have a problem with quantum computers, but it would require improvements in quantum computing greater than those which happened for classical computing since the time of the first mechanical computers! We're only able to manipulate a few qubits for now, even though that might change quickly with new breakthroughs :
http://newsroom.unsw.edu.au/news/technology/breakthrough-bid-create-first-quantum-computer
(With this breakthrough we might not need for quantum computers to like go all the way from the first mechanical computers to current ones, but jump right in at the start of the "silicon age".)
Quantum computers don't count faster or search a keyspace faster. What they do is allow certain types of mathimatical problems like finding factors a linear problem instead of a logerithmic one.
(This is WRONG, look at my post lower!)
Another try at it : (all info taken from Wikipedia)
- Best time complexity to bruteforce SHA256 is at this moment 2^251.7 (NOT!) (or about 30 seconds of current world energy output using a perfect quantum computer that is quadratically better than a regular one).
- An Intel Core i7 Extreme Edition 3960X (Hex core) at 3.33 Ghz can do 178x10^9 instructions per second.
So, assuming instructions=time complexity (while actually AFAIK instructions
Another try at it : (all info taken from Wikipedia)
- Best time complexity to bruteforce SHA256 is at this moment 2^251.7 (NOT!) (or about 30 seconds of current world energy output using a perfect quantum computer that is quadratically better than a regular one).
- An Intel Core i7 Extreme Edition 3960X (Hex core) at 3.33 Ghz can do 178x10^9 instructions per second.
So, assuming instructions=time complexity (while actually AFAIK instructions
To answer my own question, it would seem that the speedup for a quantum computer would most likely be quadratic, effectively like halving the key length from 256 to 128.
And to count to 2^128 would require about 2 minutes of total world output using a perfect computer...
And to count to 2^128 would require about 2 minutes of total world output using a perfect computer...
Can't someone luck out and . . .
. . .Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row. . .
also, this:
https://i.imgur.com/VjtG3.jpg
(Of course when such quantum computers are available, the global banking system will probably be in a much worse situation than bitcoin, but would be nice to know if bitcoin is at least somewhat "quantum-proof"...)
quantum computer are still in early projct status and no one knows exactly the efficiency in solve a cryptographic problem. But even if they are 10^20 more powerfull than the ipotetical computer they're still not able to brute-force the 256bit key in a usable lapse of time
I didn't see any numbers. What energy efficiency is the guy basing the calculations on?
Boltzman Constant
http://en.wikipedia.org/wiki/Boltzmann_constant
a) Efficiency of an ideal computer: 4.4×10^-16 ergs / bit (at the average ambient temp of space)
b) Annual energy output of our star: 1.21x10^41 ergs
c) Estimated life of our star: 5 billion years
d) Estimated potential energy of our star: 6.05x10^50 ergs (b*c)
e) Estimated potential bit changes using entire energy output of our star: 1.38x10^66 (d/a)
1.38x10^66 bits ~= count from 0 to ~2^220
(note it is actually less than that because the increment of some values involve changing more than one bit so that could be considered an upper limit).
To show how far away we are from even that. Total human energy consumption in all forms for all activities in on the order of ~132,000 TWh (4.47x10^27) annually. If all energy consumption of the human race was diverted to power an as of yet uninvented ideal computer and that computer loaded with a program to increment a counter we could increment that counter to only ~2^146 in a year (less than one quadrillionth of one quadrillionth of a one percent of 2^256).
By luck? Then you better use that luck to find the private key of a bank or of a government or whatelse on this planet, since tons of people use sha-256 
Can't someone luck out and . . .
. . .Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row. . .
also, this:
https://i.imgur.com/VjtG3.jpg
(Of course when such quantum computers are available, the global banking system will probably be in a much worse situation than bitcoin, but would be nice to know if bitcoin is at least somewhat "quantum-proof"...)
. . .What energy efficiency is the guy basing the calculations on?
I'm not certain, but I suspect that the originator of the concept is referring to Landauer's Principle.http://en.wikipedia.org/wiki/Landauer%27s_principle
Can't someone luck out and . . .
. . .Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row. . .
also, this:
https://i.imgur.com/VjtG3.jpg
Yes you can. There is even a program to find the private key for a given public key. It is called "vanitygen".
You just type:
vanitygen
It will eventually come up with the matching private key. It is not fast though.
You just type:
vanitygen
It will eventually come up with the matching private key. It is not fast though.
Can't someone luck out and . . .
. . .Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row. . .
also, this:
https://i.imgur.com/VjtG3.jpg
Can't someone luck out and jumble a bunch of numbers and letters, luck across a private key, and steal all the money off the paper wallet?
If it's pure luck, the odds are so astronomically low as to be pretty much zero.
And by low, I don't mean "winning the lottery" low. I don't mean winning the lottery while getting struck by lightning low. I mean like, pretty much zero.
Perhaps you mean winning the lottery while getting struck by lightning in the middle of taking a crap low.
Can't someone luck out and jumble a bunch of numbers and letters, luck across a private key, and steal all the money off the paper wallet?
If it's pure luck, the odds are so astronomically low as to be pretty much zero.
And by low, I don't mean "winning the lottery" low. I don't mean winning the lottery while getting struck by lightning low. I mean like, pretty much zero.
Can't someone luck out and jumble a bunch of numbers and letters, luck across a private key, and steal all the money off the paper wallet?
Depends on how the private key was generated. The official bitcoin client uses the openssl library to generate the keys, which is supposed to contain enough entropy that key generation is truly random. However, if you have an unsecure implementation for key generation, in principle someone could recreate the specific condition under which the key was generated and thus come across the same key, because key generation is a deterministic process.
Can't someone luck out and jumble a bunch of numbers and letters, luck across a private key, and steal all the money off the paper wallet?
Jump to: