This message was too old and has been purged

[FiatKiller]

This thread only incites panic as an initial reaction. Anyone who reads
most of it understands that EK's or any other method still has a small
chance of succeeding. I think it's fascinating and it has spurred me to learn
more and do my own research. So bottomiline, it serves a useful purpose.

Plus, going for the 50 BTC is plain fun. lol

[sickpig]

This thread only incites panic as an initial reaction. Anyone who reads
most of it understands that EK's or any other method still has a small
chance of succeeding. I think it's fascinating and it has spurred me to learn
more and do my own research. So bottomiline, it serves a useful purpose.

Plus, going for the 50 BTC is plain fun. lol

If someone will be able to win the gmaxwell's bounty I think the 50 btc premium will be only the beginning. I don't dare to speculate on the value of those btc, though.

[kjj]

Nothing wrong there, though the chances are about as good as with vanitygen (maybe a bit faster, if you directly attack the key and don't have to compare addresses) so far.

It is significantly faster, because the algorithm needs O(sqrt(n)) (expected) operations where vanitygen needs O(n), however with the space size we're talking here sqrt makes practically no difference.
Basically the efficiency of this algorithm is on par with other general-dlp-solving algorithms, of which none practically works on this kind of space.

Ugh.  No, brute force (vanitygen) is O(sqrt(n)) because EC (and, in general, everything that reduces to the discrete log problem) has a strength equal to half the key length.  256 bit EC provides 128 bits of security.  sqrt(2²⁵⁶)=2¹²⁸.

[Evil-Knievel]

This message was too old and has been purged

[BurtW]

Whether order of N or sqrt N I believe the N for vanitygen is 2^160 because any key pair that hashes to the address will do.  However for cracking the key directly N is 2^256

[Evil-Knievel]

This message was too old and has been purged

[prezbo]

Nothing wrong there, though the chances are about as good as with vanitygen (maybe a bit faster, if you directly attack the key and don't have to compare addresses) so far.

It is significantly faster, because the algorithm needs O(sqrt(n)) (expected) operations where vanitygen needs O(n), however with the space size we're talking here sqrt makes practically no difference.
Basically the efficiency of this algorithm is on par with other general-dlp-solving algorithms, of which none practically works on this kind of space.

Ugh.  No, brute force (vanitygen) is O(sqrt(n)) because EC (and, in general, everything that reduces to the discrete log problem) has a strength equal to half the key length.  256 bit EC provides 128 bits of security.  sqrt(2²⁵⁶)=2¹²⁸.

Yes, it has the strength equal to half the keylength because best known algorithms like pohlig-hellman, pollard-rho and shanks reduce it to O(sqrt(n)). Brute force (vanitygen is included here) doesn't use these algorithms and thus has n/2 (expected) complexity (as EK already pointed out), while the algorithms EK is using use some of the ideas of those algorithms mentioned above. Just because some algorithms reduce the complexity of the problem doesn't mean every algorithm is equally as good.

However for cracking the key directly N is 2^256

exactly.

[preshing]

Thanks for the info. We already know what his script is doing, and still discussing it because:

Option I: We are all the same person as Ritual & Evil-Knievel, or we are different persons but we are in this scam together;
Option II: We are sado-masochists who love to waist everyone's time and money;
Option III: There's something very interesting in Evil-Knievel ideas, and we would like to talk a bit about it.

Pick your choice.

Is it on-topic, though? The topic of this thread is "OpenCL Based, Optimized BTC Private-Key Cracker", and it opens with misleading statements like "who knows, this tool is giving you good chances to get one of these lost 10 MILLION US$ accounts."

Those are alarming claims for people who care about the security of the blockchain.

Meanwhile, the tool (while it is clever) has no more chance of cracking a real key in the wild than a doorstop. Nobody disputes this, not even Evil-Knievel, who wrote it.

The logical thing is to close the thread so that it's clear to readers that the cracker has no practical use, there's no threat, and the security of the blockchain has not been compromised. For example, I was directed to this thread from somewhere else, and it took me considerable time to gain assurance that everything was OK. It's always possible to create new threads for other discussions.

[jaesyn]

The logical thing is to close the thread so that it's clear to readers that the cracker has no practical use, there's no threat, and the security of the blockchain has not been compromised. For example, I was directed to this thread from somewhere else, and it took me considerable time to gain assurance that everything was OK. It's always possible to create new threads for other discussions.

^^ this. New thread in a forum more appropriate to the research aspect that this thread has taken on would be appreciated.

[BurtW]

Whether order of N or sqrt N I believe the N for vanitygen is 2^160 because any key pair that hashes to the address will do.  However for cracking the key directly N is 2^256

It is not sufficient to find a collision in the 2^160 space.
Even if you find a Keypair, that Hashes to the same RIPEMD160 Bitcoin Address - it would be impossible to sign any outgoing transaction as you have to do it with the full 256bit private key  

Listen to yourself here.  First you say "if you find a Keypair"  then later on in the same sentence you say "it would be impossible to sign"  because you "have to do it with the full 256bit private key" but the first phrase in the same sentence is "you find a Keypair".

If I find a keypair that hashes to a specific Bitcoin address then by definition I have one of the (on average) 2⁹⁶ possible private keys that will allow me to move the funds at that address.

I stand by my statement that the search space for a specific Bitcoin addresses is N=2¹⁶⁰ and the search space for a specific public key is N=2²⁵⁶  

[Evil-Knievel]

This message was too old and has been purged

[BurtW]

So we are in agreement that the search space for vanitygen, if used as a Bitcoin address cracker, is 2¹⁶⁰ and it is impossible to use vanitygen as a Bitcoin address cracker.

We also agree that the search space for cracking a specific public key is 2²⁵⁶ which is 2⁹⁶ times larger than the search space for cracking a Bitcoin address.

If you are able to quickly compare to 2⁴⁰ known keys in parallel then you have somewhat reduced your search space for cracking a specific public key from 2²⁵⁶ down to 2²⁵⁶ / 2⁴⁰ = 2²¹⁶

[Supercomputing]

Whether order of N or sqrt N I believe the N for vanitygen is 2^160 because any key pair that hashes to the address will do.  However for cracking the key directly N is 2^256

It is not sufficient to find a collision in the 2^160 space.
Even if you find a Keypair, that Hashes to the same RIPEMD160 Bitcoin Address - it would be impossible to sign any outgoing transaction as you have to do it with the full 256bit private key  

Listen to yourself here.  First you say "if you find a Keypair"  then later on in the same sentence you say "it would be impossible to sign"  because you "have to do it with the full 256bit private key" but the first phrase in the same sentence is "you find a Keypair".

If I find a keypair that hashes to a specific Bitcoin address then by definition I have one of the (on average) 2⁹⁶ possible private keys that will allow me to move the funds at that address.

I stand by my statement that the search space for a specific Bitcoin addresses is N=2¹⁶⁰ and the search space for a specific public key is N=2²⁵⁶  

Yes that is correct. And you can even take it a step further by saying that each secp256k1 ECDSA privet key can be expressed in two ways: a 33 byte and a 65 byte version. So now we have about 2^97 ON AVERAGE  possibilities for a collision per private key. Also, two-thirds of those keys can be calculated very cheaply with a single multiplication. Then your run-time complexity will be in the order of 2^127 ON AVERAGE operations.

So it turns out that attacking secp256k1 is much more efficient and dangerous than looking for address collisions. Hash functions are designed to be collision resistant, therefore the best you can do is about 2^159 ON AVERAGE operations for RIPEMD-160. There is no group composition/operation with hash functions and that is why we use them.

[BurtW]

Evil, you are starting to lose credibilty because you have not responded to the claim of bounty in your thread here:

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

[FiatKiller]

Question for the mathmaticians: can you somehow take advantage of taking the ellipitical
curve from 2D to 3D, either along the vertical or X axis? Seems like there could be some
voodoo you could do with a corresponding point on the opposite side kind of thing.  :-D

[Evil-Knievel]

This message was too old and has been purged

[BurtW]

Question for the mathmaticians: can you somehow take advantage of taking the ellipital
curve from 2D to 3D, either along the vertical or X axis? Seems like there could be some
voodoo you could do with a corresponding point on the opposite side kind of thing.  :-D

Sure, this would be absolute plausible. I am right now modelling the ECDSA search space as a five dimensional torus.

Yes, your mathematical ingenuity knows no bounds yet your reputation for paying your debts is heading for the gutter:

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

[TheRealSteve]

minerpeabody, I have just checked your solution and it indeed meets all requirements in the original posting.
So it looks like you have perfectly succeeded the task and thus qualified to claim the bounty.

Current Mt.Gox BTC Price: 1 BTC = 915 US$
If I calculate correctly, 200 US$ = (200/915)*1BTC = 0.2185... BTC - I will round it up to 0.22.

All you have to do, is provide me your BTC address.

Back on topic, perhaps?
( Insofar as it ever was on topic past the first few posts )

[BurtW]

minerpeabody, I have just checked your solution and it indeed meets all requirements in the original posting.
So it looks like you have perfectly succeeded the task and thus qualified to claim the bounty.

Current Mt.Gox BTC Price: 1 BTC = 915 US$
If I calculate correctly, 200 US$ = (200/915)*1BTC = 0.2185... BTC - I will round it up to 0.22.

All you have to do, is provide me your BTC address.

Back on topic, perhaps?
( Insofar as it ever was on topic past the first few posts )

Yes, I see he took care of that issues so everything is back on track.

[fran2k]

Just for clarification:

In fact it is mathematically much more complex than this, but the basic principle is as follows:

Imagine the black line being the complete search space. This searchspace has hundreds to thousands of rendevous points (depicted in red).
Addresses which lie in the middle of two (marked green in the picture) rendezvous points (e.g. the maximum distance to each neighboring rendezvous point) are going to take a long time to crack.
However, all keys that are in a certain area around these rendezvous points (certain area however can also mean several billion apart of course) are being cracked very easily (in a manner of days). Those weak addresses are marked blue in the picture.

Now there is not just black and white but many different nuances, from very easy over tough but doable to very hard  
The number of weak addresses is almost unlimited, so I can give you dozen examples that would hit one of the rendezvous points pretty easily.

I will try to make a video presentation by the next week, just to describe the technical background behind this. Its too much to write down.

Could you give any literature reference about this?