This message was too old and has been purged

[gmaxwell]

Would that be impossible or just take a good amount of time but still possible.

It's not possible. Though the fact that you can 'search from both directions' is why 256-bit ECC has 2^128 security. Rho is an enormous speedup but the parameters are chosen to make it irrelevant.

I think I've pointed out the fraud in this thread clearly enough.  The impression was made that this tool was able to find the private keys of some portion of random keys enough for shill demonstrations in this thread.   I posted 200,000 keys with a substantial bounty for giving me the private key of any one of them.  Evil, where is my private key?  You said your software takes a few minutes— please either solve one of the keys I posted or admit that you cannot and that people have been mislead by this thread.

[piotr_n]

But, of course, there isn't. The group is complete, all $ORDER points are reachable by multiplying the generator from 1..$ORDER-1. Some points _can't_ be more likely than others as a property of the curve with a uniform input, or otherwise some points would be unreachable (obvious by the pigeonhole principle) and the order would be less.

OK - that's a solid statement.
But he only makes the stats for the least 32 bits, and not for the entire numbers - it doesn't matter?

[gmaxwell]

But he only makes the stats for the least 32 bits, and not for the entire numbers - it doesn't matter?

It doesn't matter (and for some curves— e.g. ones where the x^2 term is non-zero, though IIRC in scep256k1 there isn't a tidy LSB pattern, some 32 bit LSB patterns are unused entirely). About half of the X values are not points on the curve, but this is accounted for in the order of the group. There are ORDER points on the curve, and the private keys 1..ORDER-1 uniquely map to them.  Lets say that all the X values were even— they're not— but lets say— it doesn't matter since any search is already limiting itself to valid X values, e.g. any statement about the security already excludes the points which are not part of the curve, which can't be reached by any private key, and which wouldn't be included in any key search.

[piotr_n]

So you are saying that there is no way for the numbers ending with a certain value (of the last LSBs) to have a certain set of the optimal "randezvouz points" to start with, for cracking?
I mean, a different set of "randezvouz points" for different values of the last LSBs - obviously.

EDIT:
Maybe not even a set of points - maybe it is as simple as a single "randezvouz point" for each specific value of the LSBs.
Are you sure that we are talking about a total nonsense here?
Because if he manages to prove by statistics that there is such a correlation, then building a complete rainbow table for mapping N LSBs to a specific randezvouz point should be just a matter of time.
And when/if it happens - then it is 'goodbye bitcoin'.

[itod]

Itod, you realize that the software you're running is indistinguishable from a cracker of EC keys, right?  I mean— no real reason to believe that anyone will find anything, but...

I disagree, I would never run an EC kracker but I'm running this, thinking of it as a statistical analysis tool.

I think I've pointed out the fraud in this thread clearly enough.  The impression was made that this tool was able to find the private keys of some portion of random keys enough for shill demonstrations in this thread.   I posted 200,000 keys with a substantial bounty for giving me the private key of any one of them.  Evil, where is my private key?  You said your software takes a few minutes— please either solve one of the keys I posted or admit that you cannot and that people have been mislead by this thread.

I really can't understand where do you see the fraud in this. Guy paid his due yesterday, and he said that he will continue paying until he spends 10 BTC. I'll let you know immediately if me misses todays payment. Those 10 BTC have to come from somewhere, and although the thread title is a bit on the high tone, he haven't said a single lie in the explanation. Regarding your challenge to him, it's a really a low blow because he never, ever said he can crack usual private/public keypair. All he said is if you generate the private key, who's 1/8 of the corresponding public key matches the 5000 values he gave - he will crack your keypair in minutes. There's no point in challenging someone to do what he never claimed he could do.

[forzendiablo]

gweedo why dont u put there 1BTC o nthe wallet if you believe he cant crack it. 16$ doesnt sound like u really are not worried.

[BurtW]

gweedo why dont u put there 1BTC o nthe wallet if you believe he cant crack it. 16$ doesnt sound like u really are not worried.

gmaxwell already put up 50 BTC if he can crack any one of 200,000 different keypairs. 

Now, everyone, including him, knows he cannot do it. 

He may never have claimed he could, that is another matter.

[Ritual]

gweedo why dont u put there 1BTC o nthe wallet if you believe he cant crack it. 16$ doesnt sound like u really are not worried.

gmaxwell already put up 50 BTC if he can crack any one of 200,000 different keypairs. 

Now, everyone, including him, knows he cannot do it. 

He may never have claimed he could, that is another matter.

I'd like to see what happens with this. Just because it hasn't been done in a couple of hours doesn't mean it CAN'T be done.

As has been well established on this thread, this is a rainbow table attack, and one of those 200,000 keypairs could lie within reach. Remember that we have NO IDEA how keypairs are spread along the curve, so it's not possible to tell how "weak" an address is before it's tried.

gmaxwell has the massive advantage of the entire space to choose from, obviously, but there is a possibility (however vanishingly small) that he could get caught here.

Give it some time

Rit.

PS: I also agree this is a valuable experiment, even if it comes to nothing. A security system claiming to be this unbreakable *needs* someone to try to prove it wrong sometimes - otherwise stagnancy sets in and no progress is made.

[piotr_n]

I'd like to see what happens with this. Just because it hasn't been done in a couple of hours doesn't mean it CAN'T be done.

As has been well established on this thread, this is a rainbow table attack, and one of those 200,000 keypairs could lie within reach. Remember that we have NO IDEA how keypairs are spread along the curve, so it's not possible to tell how "weak" an address is before it's tried.

gmaxwell has the massive advantage of the entire space to choose from, obviously, but there is a possibility (however vanishingly small) that he could get caught here.

Yeah. So if anyone wants to help ripping gmaxwell of 50 BTC, please make sure to start EK's tool before going to bed tonight

But much more important thing than Greg's 50 BTC is that we all would help to (dis)prove the actual security of secp256k1.
Losers or winners - we're all in this together and we all care to know the answer. Don't we?

[forzendiablo]

gweedo why dont u put there 1BTC o nthe wallet if you believe he cant crack it. 16$ doesnt sound like u really are not worried.

gmaxwell already put up 50 BTC if he can crack any one of 200,000 different keypairs. 

Now, everyone, including him, knows he cannot do it. 

He may never have claimed he could, that is another matter.

oih missed that post somehow.

[BurtW]

gweedo why dont u put there 1BTC o nthe wallet if you believe he cant crack it. 16$ doesnt sound like u really are not worried.

gmaxwell already put up 50 BTC if he can crack any one of 200,000 different keypairs. 

Now, everyone, including him, knows he cannot do it. 

He may never have claimed he could, that is another matter.

oih missed that post somehow.

https://bitcointalk.org/index.php?topic=421842.msg4809012#msg4809012

[gadman2]

I'd like to see what happens with this. Just because it hasn't been done in a couple of hours doesn't mean it CAN'T be done.

As has been well established on this thread, this is a rainbow table attack, and one of those 200,000 keypairs could lie within reach. Remember that we have NO IDEA how keypairs are spread along the curve, so it's not possible to tell how "weak" an address is before it's tried.

gmaxwell has the massive advantage of the entire space to choose from, obviously, but there is a possibility (however vanishingly small) that he could get caught here.

Yeah. So if anyone wants to help ripping gmaxwell of 50 BTC, please make sure to start EK's tool before going to bed tonight

But much more important thing than Greg's 50 BTC is that we all would help to (dis)prove the actual security of secp256k1.
Losers or winners - we're all in this together and we all care to know the answer. Don't we?

Not necessarily. It would prove one of two things. It's either been broken or that he's lying that he can break it. Not the fact that it "could still" be broken .

[deepceleron]

You don't need him to offer a bounty; there's about 1 million BTC of unspent (Satoshi) 50BTC blocks, where the block reward is paid to public keys instead of Bitcoin addresses. Go get 'em!

[piotr_n]

You don't need him to offer a bounty; there's about 1 million BTC of unspent (Satoshi) 50BTC blocks, where the block reward is paid to public keys instead of Bitcoin addresses. Go get 'em!

That is only 20000 addresses - gmaxwell gave 10 times more...
It's BTW also a good input into the research - so if he loses I promise to refund him with 10BTC

[xb0x]

Watching

[BurtW]

Watching

What are you watching?  This thread?  Sorry.

[Wardan_reloadeD]

HELLO!!

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

[BurtW]

HELLO!!

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

Hey, I remember that from when you first posted it!  That was a very long time ago in Bitcoin time.

[TheRealSteve]

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

I think that's a teensie bit different in that that seems to scan pretty much the entire address space.. apparently at random ..whereas this takes a more narrow look, and I'm pretty sure doesn't claim it can crack random-public-key, only public-key-within-defined-parameters.  That's not to say that I think somebody should pay the 2BTC guy for the software (though if people have 10,000BTC laying around, what's 2BTC less, eh?), but the goals seem rather different.  That guy's really just in it for the sale, this guy seems to at least package it all up in a scientific wrapper.

[Ritual]

Can I ask one of you mathematical guys to tell me what is the difference in what EK is doing, as opposed to what I am doing atm.

A little background:

My missus mined BTC back in early 2010 on her laptop. She got 200 BTC and paid out 1 for something. She had the wallet on a defunct macbook, long since gone to the great landfill in the sky. But she has her address. So...we work from that. I've found her on the Blockchain, and am trying to crack the wallet to get the BTC back. I know 199 seems a small amount, but it's life-changing for us. She did remember <something> about her wallet - she used a brainwallet system, picked a passphrase, and promptly forgot it. She's unsure, but she reckons it was about 8-12 words long, and one of the words was "2,4 Dynitrophenylhydrazone". In other words, she was being a smartarse and trying to show off her vocab and education.

So I've run a dictionary attack (cobbled together from many different sources) against it for about 6 months now, with no success.

Recently I've adopted a different approach, which I am running in parallel.

Her address starts with "12g". I have been using Vanitygen64 to generate keys at approx 25000 per sec with this pattern. This then compares against her (our) key to see if it fits. It's been running for several weeks now with no result (I won't lie, I've also picked a few other interesting, apparently dead addresses starting with 12g to attack in the meantime - the compare time is negligible). The range of "interesting" keys is approx 1500.

So, to multiply 1500 by 25000, we get 37500000. Every second.

Looking at the size of the name space, this is irrelevantly small. I can probably expect a result shortly after the sun puts on it's snowhat, but nevertheless, I want that damn wallet.

Can someone knowledgeable please answer this question:

Is what I am doing any less efficient than EKs method? I think not. I'm reducing the namespace (in theory) by a factor of 58^2. But this is not enough to make a difference. I might be here all yea, I might hit it tomorrow.

The man obviously has serious mathematical knowledge, but in the case of trying to crack an elliptic curve, is it actually any use? And I have about the same odds to hit I reckon?

Thanks,

Rit./