Author

Topic: Not understanding security of private key (Read 1414 times)

full member
Activity: 164
Merit: 100
Gone for a minute now back again
November 09, 2012, 04:57:04 AM
#18
Yes, sorry, 1200 days, not 120, I misread my calculator...
legendary
Activity: 938
Merit: 1000
November 09, 2012, 04:16:28 AM
#17
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...)

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.
full member
Activity: 164
Merit: 100
Gone for a minute now back again
November 07, 2012, 05:38:26 AM
#16
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.
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".)
newbie
Activity: 56
Merit: 0
November 07, 2012, 12:21:46 AM
#15
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.
full member
Activity: 164
Merit: 100
Gone for a minute now back again
November 06, 2012, 12:47:09 PM
#14
(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
full member
Activity: 164
Merit: 100
Gone for a minute now back again
November 06, 2012, 12:31:42 PM
#13
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...
legendary
Activity: 938
Merit: 1000
November 06, 2012, 12:09:17 PM
#12
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
Hmm, what about future quantum computers? Wouldn't they theoretically be able to brute-force 256-bit keys using not such ridiculous amounts of energy?
(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
sr. member
Activity: 476
Merit: 250
Tangible Cryptography LLC
November 06, 2012, 11:40:04 AM
#11
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).  
legendary
Activity: 1148
Merit: 1008
If you want to walk on water, get out of the boat
November 06, 2012, 11:34:03 AM
#10
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  Cheesy
full member
Activity: 164
Merit: 100
Gone for a minute now back again
November 06, 2012, 11:17:24 AM
#9
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
Hmm, what about future quantum computers? Wouldn't they theoretically be able to brute-force 256-bit keys using not such ridiculous amounts of energy?
(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"...)
legendary
Activity: 3472
Merit: 4801
November 06, 2012, 11:13:37 AM
#8
. . .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
donator
Activity: 994
Merit: 1000
November 06, 2012, 11:07:25 AM
#7
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
I didn't see any numbers. What energy efficiency is the guy basing the calculations on?
newbie
Activity: 56
Merit: 0
November 06, 2012, 10:49:59 AM
#6
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.
legendary
Activity: 3472
Merit: 4801
November 06, 2012, 09:28:06 AM
#5
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
newbie
Activity: 39
Merit: 0
November 06, 2012, 12:12:07 AM
#4
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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
November 05, 2012, 11:26:25 PM
#3
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.
donator
Activity: 994
Merit: 1000
November 05, 2012, 11:09:39 PM
#2
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.
legendary
Activity: 1025
Merit: 1000
November 05, 2012, 10:57:49 PM
#1
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: