This message was too old and has been purged

[jMyles]

(last message wasn't posted - maybe since I'm new it's awaiting moderation or something?)

Help me out here - is Evil claiming that he has essentially cracked RSA (ie, that given a public key, hey can ascertain its private key)?

If not, what is specific to Bitcoin about this attack?

[JoTheKhan]

(last message wasn't posted - maybe since I'm new it's awaiting moderation or something?)

Help me out here - is Evil claiming that he has essentially cracked RSA (ie, that given a public key, hey can ascertain its private key)?

If not, what is specific to Bitcoin about this attack?

No. Given a public key he might (can't) find the private key to the address. Or at least from what I have been reading. The chances of your BTC being stolen are .000000000001% (randomly low percentage) higher than they were before he wrote this program from my understanding. Also as long as you don't reuse addresses (Don't keep sending stuff from the same address) your public key is never published and then he can't even try to run his program on your public address. You have a better chance of getting a virus and having you BTC stolen off your machine this way.

[jMyles]

...as long as you don't reuse addresses (Don't keep sending stuff from the same address) your public key is never published and then he can't even try to run his program on your public address. You have a better chance of getting a virus and having you BTC stolen off your machine this way.

I understand that, and I'm not concerned about my own security.  I want to understand the difference between what Evil is claiming and a claim to have cracked some part of RSA generally.

[devthedev]

I guess we'll see how this pans out. http://stargate.bitwarrant.com/science/

[zumzero]

Maybe you have some major computer (or perception) issues as the video clearly shows that it (contrary to your claim no address can be cracked easily) is in fact cracking a private key in seconds. More precisely, the private key of a randomly generated address.

Hi EK forgive my cynicism but here goes..,

You didn't crack the private key of a randomly generated address as stated in the above quote.  By your own admission you were generating 'weak' addresses only and cracked one of those.  This prompts the question, what is the estimated number of weak addresses that exist over non weak addresses?

I have an issue with your video.  I am suspicious that your 'rage' is just a diversion from the fact that perhaps you filmed it intentionally with supposed focus and exposure issues.  You were blaming the monitor but clearly the camera was the issue.  Can you please make another video and this time make a greater effort to provide footage that can be verified? Thanks.

[deepceleron]

This cracker is BS. Demonstrating one successful "brute-forcing" is straighforward if the address is generated on purpose very close to a rendez-vous point. There is no weakness here whatsoever, the regions around rendez-vous points are just tiny compared to the whole search space.

Consider that it is basically the same thing as iterating over possible private keys starting from 1, then 2, etc... then saying "uh-oh! I found some addresses that are weak and can crack them quickly!". Of course it will be true for all addresses whose private key is between 1 and few millions... But it is still nothing considering the whole search space.

Do not buy that.

This is kind of what I was thinking reading earlier in the thread, although I haven't looked through the obfuscated in one line "generate the weak address this way" code show here: https://bitcointalk.org/index.php?topic=421842.msg4746108#msg4746108

"my HD7970 is at the moment capable of doing 150 MEGAKEYS per second" says the OP.
If the code actually is: Here's a generator that will generate a private key within a million of 1000 weak points: 2 billion possible keys to search; 50% probability with 1 billion brute forces with no special math.

[BitBits]

As noted above, at least one verifiable example of this thing doing what you claim it may, would "help" taking the claims any seriously. Otherwise, you are selling a packaging box of HD TV for a full price of TV, without any assurance that the TV is indeed inside.
So, please "plug it in" and show us "Myth Busters" episode.

[nmersulypnem]

Stupid question - why is the address he chose one character shorter than the preceding ones?

Also, I'm going to assume that the "random" address generator is, in fact, only generating weak addresses.  The question is, can the degree of weakness be detected in a public key?

[gmaxwell]

Stupid question - why is the address he chose one character shorter than the preceding ones?

Also, I'm going to assume that the "random" address generator is, in fact, only generating weak addresses.  The question is, can the degree of weakness be detected in a public key?

There is no such thing as a weak key in secp256k1. If any non-trivial fraction of uniformly selected keys are weak then all keys are weak because there is a simple bit of algebra to convert an attack on a non-trivial fraction of random keys into an attack on any specific key.

[ny2cafuse]

I have an issue with your video.  I am suspicious that your 'rage' is just a diversion from the fact that perhaps you filmed it intentionally with supposed focus and exposure issues.  You were blaming the monitor but clearly the camera was the issue.  Can you please make another video and this time make a greater effort to provide footage that can be verified? Thanks.

Exactly what I was thinking, and why I said what I said in my comment of this.  Something doesn't add up.  His actions in the video were erratic and looked almost Tourrettes-like.  The part where he curses his $2000 computer, and blames the video not focusing on the 28" monitor not being good enough for the video just seems off.  Why is he using a shitty camera phone quality video to disprove the community skepticism, and not a program like fraps or camtasia?

As noted above, at least one verifiable example of this thing doing what you claim it may, would "help" taking the claims any seriously. Otherwise, you are selling a packaging box of HD TV for a full price of TV, without any assurance that the TV is indeed inside.
So, please "plug it in" and show us "Myth Busters" episode.

It's just like the videos of "ASIC" devices hashing away to get pre-order customers, and they end up being vaporware.

My suggestion to EK is to have a reputable member of the Bitcoin community test this program and validate it's legitimacy.

-Fuse

[User705]

Stupid question - why is the address he chose one character shorter than the preceding ones?

Also, I'm going to assume that the "random" address generator is, in fact, only generating weak addresses.  The question is, can the degree of weakness be detected in a public key?

There is no such thing as a weak key in secp256k1. If any non-trivial fraction of uniformly selected keys are weak then all keys are weak because there is a simple bit of algebra to convert an attack on a non-trivial fraction of random keys into an attack on any specific key.

But how is it known if the fraction of possibly weak keys is non-trivial?  Basically are you saying his approach is totally impossible or are you saying the amount of possibly weak keys he is referring to is too small to matter?

[JoTheKhan]

Here's what's going on.  Evil-Knievel has pre-computed a couple points on the secp256k1 curve.  Specifically points where the exponent is of the form 2**N. (see 1,2)  He then wrote a program, the "cracker", that can search the area around those points.  If a Bitcoin key-pair lies close to one of those points, his program will find it.

This isn't dangerous.  It's improbable (~impossible) that any uniformly random Bitcoin key-pairs are weak to his pre-computed points.  The secp256k1 keyspace is, for all practical purposes, infinitely large.  It doesn't matter if Evil-Knievel had a gabillion-gajillion pre-computed points and all the computing power in the universe.  His approach still wouldn't crack a normal Bitcoin key-pair.

To me, having just read Evil-Knievel's thread, it sounds like he's insinuating that there is danger here.  He's insinuating that a uniformly random Bitcoin key-pair has a reasonable chance of being tractably close to one of his pre-computed points.  There is no reasonable chance of this, and his claims are ridiculous.  The thread should be closed as a scam, because he's asking for money on misleading premises.

If he has nothing to hide, why was his HTML generator obfuscated?  I'll help and de-obfuscate the generator for everyone.  Here's the algorithm:

Code:

Pick a random N, [128, 255].
Pick a random M, [1, 20000000].
Spit out 2**N - M as a private key.

See the problem?  He just needs to take a generated public key, add G to it ~20,000,000 until it matches one of the 128 pre-computed keys (which are of the form 2**N), and BAM the private key is "cracked".  This doesn't make Bitcoin weak.  It never will.  It's a rainbow table attack.  But mankind will never have enough computational and storage power to make rainbow tables work against secp256k1.

As for the bitprobing.com "project".  That's a load of bollocks.  If you don't believe what the experts have to say about ECDSA, that's fine.  But go learn group theory and number theory first, before asking the public to help run unsubstantiated "experiments."


I know these forums are intentionally soft-modded, and appreciate that to an extent.  But it's times like these I wish the forums were more aggressively moderated so that Evil-Knievel could just be banned for misleading and scamming people.


(1)  Actually, he fscked this up.  He interpretes the decimal result of 2**N as hexadecimal.
(2)  2**128 is 340282366920938463463374607431768211456.  Interpret that as a hexadecimal private key and you get a public key of 04864f29af3191e135f5c78499271961f2313110fb2a296bf072733475529da1fb4d5cef64d1212 a946775bfb2db5319fb618089ae8806d618f44d68d3bdb18650.  The least significant 32-bits of the X coordinate is 0x529da1fb.  That matches one of the constant in his script.  I assume the rest match similarly.

[gmaxwell]

But how is it known if the fraction of possibly weak keys is non-trivial?  Basically are you saying his approach is totally impossible or are you saying the amount of possibly weak keys he is referring to is too small to matter?

If he has anything at all then he can demonstrate it by cracking any one of the 200,000 keys I posted as a bounty and collect a bunch of coins from me.

What I was responding to was someone asking about testing if a key is "weak"— it's pointless, if any non-infinitesimal fraction is weak (e.g. by being generated from private keys known to an attacker) all keys are weak.

[SheHadMANHands]

Well, that was fun while it lasted..   

Lock it up.

[DarthNoodle]

so it is possible to identify weak private keys if they are close to any of the rendezvous points on your eliptic curve.

my questions would be:

Are standard wallets (the addresses generated by the QT client) affected by this?
are there any mitigations that can be used?
will the pub/priv key generation sequence require a new, more secure implementation?

i believe one already has been outlined of moving the coins to a new address/wallet? every few months?  would there be any way in which it is possible to increase the difficulty of the private keys?

[BurtW]

Please see:

https://bitcointalk.org/index.php?topic=437220.msg4813821#msg4813821

[toknormal]

To put this into perspective:

[1] - imagine the bitcoin address space is ALL the sand grains on planet earth (it's actually much bigger than that I think but this is easier to visualise)

[2] - imagine going to a particular spot in some country with a magnifying glass and identifying a particular sand grain

[3] - now move out from that sandgrain and identify the 5 sand grains **touching** the one you spotted with your magnifying glass. These are the "weak address" sandgrains

[4] - now imagine an astronaut orbiting the planet who lands at some random location and picks themselves a random sandgrain at their landing spot

Now you can see that the chance of collision with one of the 'weak addresses' is almost the same as the chance of collision with the primary address = no weakness at all.

Forget about it. The issue is of theoretical interest only.

[DarthNoodle]

thanks for the link, so all addresses are affected regardless of the client (due to them being based off the same RNG weakness), has this weakness not been resolved in newer versions of OpenSSL?  if so could it be worth upgrading OpenSSL and recompiling the wallet or have i completely missed the point?

in the mean time, services that use public wallets would have to generate new addresses (to send and receive money periodically?).  whats stopping someone going after the public key of an exchange like cryptsy, what would a service like this do to mitigate this issue?

Please see:

https://bitcointalk.org/index.php?topic=437220.msg4813821#msg4813821

it would be great to identify whether your key is particularly weak and more susceptible and to also identify the risks of services using the same wallet to send and receive payments.. are they going to have to change their addresses regularly from now own just to avoid this attack?

To put this into perspective:

[1] - imagine the bitcoin address space is ALL the sand grains on planet earth (it's actually much bigger than that I think but this is easier to visualise)

[2] - imagine going to a particular spot in some country with a magnifying glass and identifying a particular sand grain

[3] - now move out from that sandgrain and identify the 5 sand grains **touching** the one you spotted with your magnifying glass. These are the "weak address" sandgrains

[4] - now imagine an astronaut orbiting the planet who lands at some random location and picks themselves a random sandgrain at their landing spot

Now you can see that the chance of collision with one of the 'weak addresses' is almost the same as the chance of collision with the primary address = no weakness at all.

Forget about it. The issue is of theoretical interest only.

[BurtW]

DarthNoodle:

You missed my point.  Evil-Knievel created a weak RNG on purpose to show that if you use his totally weak RNG then he can recover the private key.

If you know that all the private keys you are generating are very near certain points then of course you can find them.  He is cheating.

In other words Evil-Knievel has done nothing and found nothing.

Here is the RNG he is using:

Code:

Pick a random N, [128, 255].
Pick a random M, [1, 20000000].
Spit out 2**N - M as a private key.

That is NOT a secure random number generator - it is barely random at all.

[DarthNoodle]

ahh ok, thank you for clearing that up.. so at the minute this is more of a theoretical attack where he has stacked the cards in his favour.

DarthNoodle:

You missed my point.  Evil-Knievel created a weak RNG on purpose to show that if you use his totally weak RNG then he can recover the private key.

If you know that all the private keys you are generating are very near certain points then of course you can find them.  He is cheating.

In other words Evil-Knievel has done nothing and found nothing.

Here is the RNG he is using:

Code:

Pick a random N, [128, 255].
Pick a random M, [1, 20000000].
Spit out 2**N - M as a private key.

That is NOT a secure random number generator - it is barely random at all.