Private Key cracker apparently demonstrated

[Chimsley]

Please see this https://bitcointalk.org/index.php?topic=421842.0

Towards the end of page 4 of this topic is apparently proof this guy derived the private key matching the public key submitted in a previous post.  Can any developers comment on this.  Not sure if this is an elaborate troll or the guy is on to something.

[1715375330]

1715375330

[1715375330]

1715375330

[1715375330]

1715375330

[1715375330]

1715375330

[Chimsley]

oh lol. he is selling his secret and not stealing coins? 

So it seems.  I am more interested in the technical aspects of what he is claiming rather than his motives.

[piotr_n]

I love this guy - he's smart, prompt and funny.

Bitcoin definitely needs more people like this, who would be exposing any possible threats in the digital signatures which we use to protect our money.
Especially that the core devs apparently don't give much shit about such a minor details.

From all the works I have seen, Evil-Knievel has done the best job - not only theoretical, but also (most important) practical.

[GoldenWings91]

PUBLIC key cracker

Don't reuse addresses.

[Chimsley]

On re-use of addresses.

I can think of a few scenarios where one must re-use addresses.  Lets say for example Wikipedia decides to accept donations in Bitcoin.  They put up a donation address.  Should they generate a new donation address every time someone visits the donation link?  They probably should from a security point of view.  Seems inconvenient for donators that have saved the address in their address book.  

Our own Bitcoin Foundation re-uses its donation address as well.  https://blockchain.info/address/1BTCorgHwCg6u2YSAWKgS17qUad6kHmtQW There it is on blockchain.info 556 transactions at the time of this posting. Looks like address re-use to me. I wonder how many people who are either members or donators to the foundation tell people in the forums not to re-use addressess.

All of you who have an address in your signature for tips and such are also guilty of address re-use.  Basically any address that is publicly advertised for business/charity or what have you will be re-used.  This goes for all those that generated vanity addresses specifically to have a visually unique address for personal or business use.

If the solution is don't re-use addresses then this makes things inconvenient.  Does anyone really think that the masses are going to stick with one address per use?

Can someone tell me where I am going wrong here?  I can't see stopping address re-use as a solution to this potential threat.

***Edited for punctuation***

[Sonny]

To motivate people participating in this, I am paying BTC for participating in this study. However, the BTC have to come from somewhere and it is hard to get some scientific funding.

This sounds a bit strange to me...
So, you are "co-operating" with others to crack the keys and share the proceeds?

[eightcylinders]

I have not looked to far into the Satoschi wallet code, but am I correct that each public BTC address in Satoshi's wallet has a unique private key?  Or is there one private key and many public keys? 

This is relevant because if I (or anyone) wants to participate, you would want to use a wallet (private/public key combo) that does not risk exposing the private key(s) where you actually have substantial BTC holdings.  Create a whole new separate wallet versus creating a new public BTC address ... that is the question?

[cp1]

On re-use of addresses.

I can think of a few scenarios where one must re-use addresses.  Lets say for example Wikipedia decides to accept donations in Bitcoin.  They put up a donation address.  Should they generate a new donation address every time someone visits the donation link?  They probably should from a security point of view.  Seems inconvenient for donators that have saved the address in their address book.  

Cash out every week? month? to coinbase and change the donation address at that time.

[Chimsley]

On re-use of addresses.

I can think of a few scenarios where one must re-use addresses.  Lets say for example Wikipedia decides to accept donations in Bitcoin.  They put up a donation address.  Should they generate a new donation address every time someone visits the donation link?  They probably should from a security point of view.  Seems inconvenient for donators that have saved the address in their address book.  

Cash out every week? month? to coinbase and change the donation address at that time.

That is certainly an option though its inconvenient.  And the entity in this example would still need to hold onto that address and probably sweep it periodically because someone somewhere is going to send to the old address that they saved in the address book as "Wikipedia donation address".

I suppose one would have to sweep at a very high frequency because anyone else that uses the tool in question to get the private key would also be sweeping that address.  Whoever gets there first gets the prize.

[kwest]

This seriously needs to get fixed. Although Mike Hearn did say that they are scrapping the address system altogether eventually, right? Will that solve this problem?

[Sonny]

Although Mike Hearn did say that they are scrapping the address system altogether eventually, right?

Could you share a link to it? Thanks.

[kwest]

Although Mike Hearn did say that they are scrapping the address system altogether eventually, right?

Could you share a link to it? Thanks.

Here:

https://bitcointalk.org/index.php?topic=428777.0

Time to scrap addresses. They are too limited and problematic.
The Payment Protocol to replace addresses. Supports refunds, memos, receipts, proof-of-purchase, and digital signature.

[gmaxwell]

Analysis of Bitcoin Address Distribution Around Certain Rendezvous Points on the Elliptic Curve
http://bitprobing.com/

This is indistinguishable from a ECC cracking tool.

After reading the source code, it appears to me that you're using this crap as a cover to try to trick people into performing computation for you in an attempt to crack a couple thousand selected keys.

Unfortunately its impossible to determine which keys you're attempting to crack because its possible to cryptographically blind the cracking process (e.g. the matches are against key + s*G for some s known only to you).

It's pointless and a waste of time, but I guess you figure so long as other people are doing the computation for you that its worth doing.

It's doubly hilarious that you claim to have (and offer to sell) a GPU tool that can compute keys a "terra-tries per second", and yet you'd ask people to waste their time crunching with this rubbish python EC implementation.

[gmaxwell]

So you claim you can crack some random keys provided by people on the forum? Oh really.

Well here, I'll make it very profitable for you then:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256


I, Greg Maxwell, do hereby promise to pay 50 BTC to the first person that
provides the discrete log of _any_ of the following randomly generated
200,000 secp256k1 public keys. This offer is open until 2014-04-01.

None of the below public keys have been used on the Bitcoin blockchain as
of the time of the creation of this offer.

04abb9239d3a5131de45b977807c62bf879119b05c3da33e37d8e7be0901985ce73b6ca6dff5b97 34d1225ce0120bbe023066669c29e23d3ea82de9a57dd259b63

Full message at https://people.xiph.org/~greg/keysfun.asc

Surely if you can crack a single key provided by a person in the thread cracking any one of 200k keys should be a cinch.

[mufa23]

So you claim you can crack some random keys provided by people on the forum? Oh really.

Well here, I'll make it very profitable for you then:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256


I, Greg Maxwell, do hereby promise to pay 50 BTC to the first person that
provides the discrete log of _any_ of the following randomly generated
200,000 secp256k1 public keys. This offer is open until 2014-04-01.

None of the below public keys have been used on the Bitcoin blockchain as
of the time of the creation of this offer.

04abb9239d3a5131de45b977807c62bf879119b05c3da33e37d8e7be0901985ce73b6ca6dff5b97 34d1225ce0120bbe023066669c29e23d3ea82de9a57dd259b63

Full message at https://people.xiph.org/~greg/keysfun.asc

Surely if you can crack a single key provided by a person in the thread cracking any one of 200k keys should be a cinch.

Quoted.

[Sonny]

Although Mike Hearn did say that they are scrapping the address system altogether eventually, right?

Could you share a link to it? Thanks.

Here:

https://bitcointalk.org/index.php?topic=428777.0

Time to scrap addresses. They are too limited and problematic.
The Payment Protocol to replace addresses. Supports refunds, memos, receipts, proof-of-purchase, and digital signature.

Thanks a lot.
I totally miss it.

[prezbo]

So you claim you can crack some random keys provided by people on the forum? Oh really.

Fwiw I haven't seen him claim that anywhere in his thread, and honestly think he's well enough versed in math to know he will not be able to crack an address with any amount of bitcoins in it in the foreseeable feature. I don't really know what he's trying to achieve, though.

[gmaxwell]

Fwiw I haven't seen him claim that anywhere in his thread, and honestly think he's well enough versed in math to know he will not be able to crack an address with any amount of bitcoins in it in the foreseeable feature. I don't really know what he's trying to achieve, though.

The thread has several instances of newbie accounts providing single pubkeys which evil claims to crack e.g: https://bitcointalk.org/index.php?topic=421842.msg4800547#msg4800547

[prezbo]

Fwiw I haven't seen him claim that anywhere in his thread, and honestly think he's well enough versed in math to know he will not be able to crack an address with any amount of bitcoins in it in the foreseeable feature. I don't really know what he's trying to achieve, though.

The thread has several instances of newbie accounts providing single pubkeys which evil claims to crack e.g: https://bitcointalk.org/index.php?topic=421842.msg4800547#msg4800547

Ah, I see, my apologies.

edit: he's saying the addresses need to be "generated completely as to the manual" though... I'm pretty sure that means being close to the step in his baby-step-giant-step algorithm he's using.

[stompix]

Fwiw I haven't seen him claim that anywhere in his thread, and honestly think he's well enough versed in math to know he will not be able to crack an address with any amount of bitcoins in it in the foreseeable feature. I don't really know what he's trying to achieve, though.

The thread has several instances of newbie accounts providing single pubkeys which evil claims to crack e.g: https://bitcointalk.org/index.php?topic=421842.msg4800547#msg4800547

Ah, I see, my apologies.

edit: he's saying the addresses need to be "generated completely as to the manual" though...

So , I generate an address , send him the private key and then he can crack it? =))))))))))))0

[prezbo]

So , I generate an address , send him the private key and then he can crack it? =))))))))))))0

If it's the kind of address public key his program is searching for, sure. However the chances of any real-life addresses that have coins in it falling into that range are abysmal.

[fpgaminer]

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]

so that Evil-Knievel could just be banned for misleading and scamming people.

The crappy and super slow implementation of ECC arithmetic linked to on that website checks keys generated against a couple thousand 32 bit values. (Why use a slow thing like that if you've supposedly got some amazing gpu thing). My guess was that he's using this as bait to get people to run that program and the values that its looking for are all 'near' high value keys.

Or other wise it just another lame market manipulation attempt. Either way, ... if he actually can crack something I welcome him to go solve any of the 200,000 keys I listed and collect his bounty.

Thanks for decoding his JS, I'd just ignored it.

[Mivexil]

To motivate people participating in this, I am paying BTC for participating in this study. However, the BTC have to come from somewhere and it is hard to get some scientific funding.

This sounds a bit strange to me...
So, you are "co-operating" with others to crack the keys and share the proceeds?

Actually I am not cracking anything. I am trying to determine the distribution of complete random addresses (with no balance whatsoever) around certain points on the elliptic curve. Most people say (or better "repeat what they've heard"): "Well if the addresses are completely random and come from a good entropy source, there will be no patterns in the distribution at all".

But who tells us this is the true? Nobody to my knowledge has ever questioned it nor is there any literature about this published. For instance, I think something different, and thus I perform a larger (mathematical) analysis on how random bitcoin addresses really are.

You're basically breaking ECDSA, claiming that privkey-to-pubkey transition results in a non-uniform distribution.

[cp1]

So he wrote a script to generate a (relatively) small and predictable number of keys that he then "cracks" to prove his program works.  Of course because the number of keys that he can crack is something like 1/1e39 of the number of possible keys there's literally no chance he can crack an address that has anything in it to steal.  So instead he sells his program for 2 BTC, if he even sells 1 copy then he'll have more BTC than if he had actually used his program.

[Altoidnerd]

http://en.wikipedia.org/wiki/Baby-step_giant-step

What? Why does this "cyclic group" appear to have two operations? This is invoking the ring structure I guess?

Sloppy article!

Evil can't (and never said he could) crack fair keys.  He has shown something subtly different.  Nobody should be afraid, nor do I think he could be called a scammer for selling software, unless he is lying about something.

[jaesyn]

The paradox here is that if someone has broken ECDLP and obtains the keys to the kingdom (BTC and all of the other crypto coins that rely on ECDSA), and they go public with it, then they will assume ownership of nothing because the currency would cease to have any value.  

Does this mean that ECDLP remains unsolved?  Not necessarily.  There are attacks based on randomly finding collisions in the EC space in order to derive unknown variables in the algebraic space (Pollard Rho and Kangaroo come to mind), and a clever person may have figured out ways to make this more efficient, or at least less random in nature.  Hopefully, they remain clever and not seek fame or attention.

In this case, though, I agree that it appears the script on GitHub is being used as a vehicle for a distributed search for the private keys that generate well-known public keys... or similarly, a search for "k" that results in a well-known signature R value (which can then be used to derive the private key for the public key used by that signature).  

[fpgaminer]

nor do I think he could be called a scammer for selling software, unless he is lying about something.

The current title of his thread is:  "[WTS] OpenCL Based, Optimized BTC Private-Key Cracker with Sources [WITH VIDEO]"

The first post says things like:

And who knows, this tool is giving you good chances to get one of these lost 10 MILLION US$ accounts

This project is [...] to recover lost private keys.

Working on real bitcoin network with real addresses and real coins.

This again shows you that there is an infinite number of weak bitcoin addresses.

The only thing in the first post of that thread that indicates that this isn't what people think it is, is the following:

Randomly generated Bitcoin Adresses are used (however they are all special-weak).

Which is incredibly confusing, but alludes to the fact that the program only works on special keys that no one is likely to ever find in the wild.

So, if all that isn't misleading, I don't know what is.  I guess if what he's doing is acceptable, I might as well sell my "OpenCL Based, Optimized BTC Miner with Sources, 10 TH/s".  It works with any SHA-256 Proof of Work (however they are all special-weak)!  You could crack that 10 MILLiON US$ chain of blocks!

[Altoidnerd]

So, if all that isn't misleading, I don't know what is.  I guess if what he's doing is acceptable, I might as well sell my "OpenCL Based, Optimized BTC Miner with Sources, 10 TH/s".  It works with any SHA-256 Proof of Work (however they are all special-weak)!  You could crack that 10 MILLiON US$ chain of blocks!

Well, I do think if one is not savy or paying attention they would misunderstand what he is saying - yes this will mislead many.  But then he also said if you're not savy, and don't know what you're doing this isn't for you.  Yes he's a salesman, but he's not scamming... just an interesting word choice and provocative, tabloid-ish title.

[Zangelbert Bingledack]

Actually I am not cracking anything. I am trying to determine the distribution of complete random addresses (with no balance whatsoever) around certain points on the elliptic curve. Most people say (or better "repeat what they've heard"): "Well if the addresses are completely random and come from a good entropy source, there will be no patterns in the distribution at all".

But who tells us this is the true? Nobody to my knowledge has ever questioned it nor is there any literature about this published. For instance, I think something different, and thus I perform a larger (mathematical) analysis on how random bitcoin addresses really are.

Random means "no pattern," by definition.

You could question whether addresses are truly being generated randomly, but you can't question whether addresses that are ex hypothesi random might actually have a pattern - at least not without falling into incoherence.

[medUSA]

The maths well exceeded my comprehension. It seems the approach is a "hit and miss and aim again".
Could it be summerized as "possible but improbable"?

Whether the cracking scrypt works or not...
At least OP has stated that address is safe when the public key is not broadcasted,
thus confirming reusing addresses is not safe, this is all I need to know.

[BurtW]

It seems to me EK has simply shown us something we all already know.

If there is a weakness in the random number generator used to generate the private keys and this RNG weakness is known or can be determined then the search space for the public key -> private key problem can be reduced.

All EK has done is prove that given public keys calculated from private keys generated by his personal totally bogus non-RNG (NRNG^TM) he can easily recover the private keys.

EK:  A bit of advice.  You published your program too soon.  It would have not been that much more work and would have been a lot more convincing if you had taken the time to do the hashing in your program so that you could show it "cracking" Bitcoin addresses.  You also made the mistake of trying to sell it here in a forum filled with people that know more about cryptography than you do.

Next time add the hashing and pitch your wares on a less technical forum.  Here is a pitch that might work for you (somewhere else, not here):

Everyone!  I have a program that can crack weak Bitcoins addresses.  Only 2 BTC.  Immediate download!

After downloading the program you can easily check the program for youself and make sure it is working for you!  Do the following steps.  Be sure to follow the instructions exactly:

1) Generate a random private key using my patented NRNG^TM program here:  http://WeakPrivateKeys.org
2) Take this private key to bitaddress.org or any web site of your choice that will calculate a Bitcoin address from a private key and generate the Bitcoin address.
3) Enter this random Bitcoin address into the progam.
4) Run the program and see just how fast it can crack the Bitcoin address and recover the public and private keys!
5) You can run this procedure as many times as you like.  Each time you will be given a different private key by the NRNG^TM and each time you will be totally surpirsed at how fast your new Bitcoin address cracking program can recover the key pair from just the Bitcoin address!

Just imagine the wealth that awaits you once you run this program on some of the Bitcoin addresses that contain thousands of Bitcoins!

It will be just like taking candy from a baby!

[prezbo]

http://en.wikipedia.org/wiki/Baby-step_giant-step

What? Why does this "cyclic group" appear to have two operations? This is invoking the ring structure I guess?

Sloppy article!

Two operations? It only has one, multiplication.

[Altoidnerd]

http://en.wikipedia.org/wiki/Baby-step_giant-step

What? Why does this "cyclic group" appear to have two operations? This is invoking the ring structure I guess?

Sloppy article!

Two operations? It only has one, multiplication.

...x = i m + j

I count two.  The group operation was previously defined as the multiplication... 

[prezbo]

http://en.wikipedia.org/wiki/Baby-step_giant-step

What? Why does this "cyclic group" appear to have two operations? This is invoking the ring structure I guess?

Sloppy article!

Two operations? It only has one, multiplication.

...x = i m + j

I count two.  The group operation was previously defined as the multiplication...  

that's in the exponent, which is an integer - A^x = A^(im+j) = A^(im)*A^j, if you will.

[jaesyn]

http://en.wikipedia.org/wiki/Baby-step_giant-step

What? Why does this "cyclic group" appear to have two operations? This is invoking the ring structure I guess?

Sloppy article!

Two operations? It only has one, multiplication.

...x = i m + j

I count two.  The group operation was previously defined as the multiplication...  

that's in the exponent, which is an integer - A^x = A^(im+j) = A^(im)*A^j, if you will.

Don't confuse the DLP with the ECDLP, though. Similar concepts, but ECDLP doesn't use exponents (it uses EC multiplication instead, which is the operation that is intractable).

Q is public key, n is order of G, set m = sqrt(n)

Baby-step (i) Giant-step (j) is then to find a collision: 

i*G = Q − jm*G

or, in other words, find the sum of two points, i*G + jm*G, that collide with the public key point Q that you're trying to solve. The private key will be i + jm (mod n).

[prezbo]

http://en.wikipedia.org/wiki/Baby-step_giant-step

What? Why does this "cyclic group" appear to have two operations? This is invoking the ring structure I guess?

Sloppy article!

Two operations? It only has one, multiplication.

...x = i m + j

I count two.  The group operation was previously defined as the multiplication...  

that's in the exponent, which is an integer - A^x = A^(im+j) = A^(im)*A^j, if you will.

Don't confuse the DLP with the ECDLP, though. Similar concepts, but ECDLP doesn't use exponents (it uses EC multiplication instead, which is the operation that is intractable).

Q is public key, n is order of G, set m = sqrt(n)

Baby-step (i) Giant-step (j) is then to find a collision:  

i*G = Q − jm*G

or, in other words, find the sum of two points, i*G + jm*G, that collide with the public key point Q that you're trying to solve. The private key will be i + jm (mod n).

Obviously, once you change the group from multiplicative to additive it won't be an exponent anymore But in the end, it's all just notation, the concept is exactly the same.

[cp1]

It's a good reminder to only generate addresses using "reliable" methods.  EK could buy out the top google listing for bitcoin paper wallet and replace its RNG with his own fake RNG.