This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[1715322277]

1715322277

[1715322277]

1715322277

[1715322277]

1715322277

[1715322277]

1715322277

[1715322277]

1715322277

[b!z]

This is actually for cracking public addresses and finding the private key? lol

[r3wt]

This is actually for cracking public addresses and finding the private key? lol

DOH!

[gweedo]

Don't anyone buy this, it is impossible to brute force a private key, it would take many many lifetimes. This is the protection that addresses give.

[gweedo]

Don't anyone buy this, it is impossible to brute force a private key, it would take many many lifetimes. This is the protection that addresses give.

That's what gweedo says. But who tells us "gweedo is the pure incarnation of physics laws"?
I would rather say, the facts are described in the original posting - now the people may position it in their own world view and judge weather they find it useful or not.

Actually I can prove Gweedo is wrong:
I can generate millions of Public/Private Key pairs that are being cracked within seconds. Alone the existence of one such key should prove that "gweedo" is somewhat ... well ... let's say on the wrong path.

It is called math, people don't have to believe me it is math.

[gweedo]

gweedo, as you are talking about math:

If you say something like: "it is impossible to brute force a private key, it would take many many lifetimes"
And I give you a key, that can be bruteforced in 10 seconds, than - by definition - your statement was proven to be wrong.

Stop playing this, let me use your words and twist them you know what I mean. Just generating a key pair is not brute forcing.

[gweedo]

gweedo, as you are talking about math:

If you say something like: "it is impossible to brute force a private key, it would take many many lifetimes"
And I give you a key, that can be bruteforced in 10 seconds, than - by definition - your statement was proven to be wrong.

Stop playing this, let me use your words and twist them you know what I mean. Just generating a key pair is not brute forcing.

You got it wrong. What I mean is, I could generate a key pair, share the public key with you, and you would be able to recover my private key in an instant with any "script kiddy key cracker" in a manner of seconds.  Alone the existence of such key proves that it does not neccessarily take a lifetime.

That is impossible, so stop lying. If that is true do it on my address https://blockchain.info/address/1GweedoZJYb5CNLfSaBgBBYS2y7BMVb2Wo

[gweedo]

You abviously have not read my answer correctly.
Please do so, then we can continue talking.

Wait so you can't brute force my address in seconds then? $16 in that address it could be yours. The public key is visible since I have done transactions so if that is what you need it is there.

[meowmix4jo]

gweedo, as you are talking about math:

If you say something like: "it is impossible to brute force a private key, it would take many many lifetimes"
And I give you a key, that can be bruteforced in 10 seconds, than - by definition - your statement was proven to be wrong.

Stop playing this, let me use your words and twist them you know what I mean. Just generating a key pair is not brute forcing.

You got it wrong. What I mean is, I could generate a key pair, share the public key with you, and you would be able to recover my private key in an instant with any "script kiddy key cracker" in a manner of seconds.   Alone the existence of such key proves that it does not neccessarily take a lifetime.

That is impossible, so stop lying. If that is true do it on my address https://blockchain.info/address/1GweedoZJYb5CNLfSaBgBBYS2y7BMVb2Wo

He's not saying he can get the privkey for any bitcoin address, it sounds like it can only get the privkeys for certain "weak" addresses and close approximations for others. Some private keys should be MUCH easier to find that others, so this could actually be legit. If it's useful is a different question.

[gweedo]

gweedo, as you are talking about math:

If you say something like: "it is impossible to brute force a private key, it would take many many lifetimes"
And I give you a key, that can be bruteforced in 10 seconds, than - by definition - your statement was proven to be wrong.

Stop playing this, let me use your words and twist them you know what I mean. Just generating a key pair is not brute forcing.

You got it wrong. What I mean is, I could generate a key pair, share the public key with you, and you would be able to recover my private key in an instant with any "script kiddy key cracker" in a manner of seconds.  Alone the existence of such key proves that it does not neccessarily take a lifetime.

That is impossible, so stop lying. If that is true do it on my address https://blockchain.info/address/1GweedoZJYb5CNLfSaBgBBYS2y7BMVb2Wo

He's not saying he can get the privkey for any bitcoin address, it sounds like it can only get the privkeys for certain "weak" addresses and close approximations for others. Some private keys should be MUCH easier to find that others, so this could actually be legit. If it's useful is a different question.

Then he is talking about hacking brain wallets due to the random entropy being a word or something easy.

[blodyx]

This is what i was afraid about when i started the other thred https://bitcointalk.org/index.php?topic=430000.0

That some evil-genius find a smart algorithm to break it all

How many combinations are there to try when you have the public key?

[gweedo]

This is what i was afraid about when i started the other thred https://bitcointalk.org/index.php?topic=430000.0

That some evil-genius find a smart algorithm to break it all

How many combinations are there to try when you have the public key?

No one has broken the ESCDA public key, if he did he would have taken a lot of money and he hasn't. He didn't take my address and the public key is published since I have done transactions with it. He is probably harboring back to the android flaw or something like that. Nothing to be worried about it.

This is just some FUD nothing serious.

[gweedo]

No one has broken the ESCDA public key, if he did he would have taken a lot of money and he hasn't. He didn't take my address and the public key is published since I have done transactions with it. He is probably harboring back to the android flaw or something like that. Nothing to be worried about it.

This is just some FUD nothing serious.

And I do not take your concerns serious. You obviously have no that much ida about cryptography, you have no serious mathematical background, you probably did not even understand a single word of what I was talking about (or at least you prentend). Actually, ECDSA is breakable by nature - the question is just with what complexity. And there are certain tricks to reduce the overall complexity, and there are addresses which complexity is pretty low by nature.

But I think it is wasted time to explain everything to you. And what the hell should I do with your $16 wallet. Have a delicious lunch at McDonald's?   

I have a degree in mathematics so yeah, but don't you want to prove me wrong? I want you to take my money.

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

You simply do not understand it.
I wish I had made this topic moderated, then I could delete such trolls and troublemakers like you and keep the thread clean.

I am not trolling LOL I am proving you very much wrong.

[dbell]

What you are describing sounds like it efficiently detects partial collisions with your rendezvous points and then from there you may be close enough to crack it in matter of days.    You have not reduced the overall search space for cracking any random address but you have greatly increased your chances and efficiency of cracking an address mathematically close to one of your Rendezvous points.

So by definition, a so called "weak" address is one that is close to a Rendezvous point


If the entire address space is 2^N,
Let A = Log2(#Rendezvous points)
Let B = Log2(#of Addresses you can brute force in few days around any one Rendezvous point)

Then within this few day time limit, you can crack any address that falls in the "weak" space of size 2^(A+B) and cannot crack any address that falls in the "hard" space of size 2^(N-A-B)

Is that about right?  If not can you describe sizes of the weak space that you can attack.

[Ritual]

Waiting with anticipation for the video

But I am also interested in an answer to that question. Approximately what proportion of the namespace could be regarded as "reasonably crackable" (i.e. within say a month on a home computer)?

Thanks,

Ritual.

[gweedo]

Hey guys,

here you see a proof of concept video.
- I am using a randomly generated bitcoin address (however they are all weak as you see)
- Alone this shows you that there exist many many many weak (almost an infinite number of) bitcoin addresses.
- I am working live on the block chain with real coins (all transactions in the video can be verified on blockchain.info)
- I am cracking the bitcoin address in a few seconds

Sorry for all the cursing but the day has been pretty stressful. 

Show nothing but ok keep thinking you have a program that can crack private keys.

[Evil-Knievel]

This message was too old and has been purged

[bmoconno]

Very interesting.

As far as the debate going on here, why doesn't Gweedo just generate a weak address (not just any address, one that meets to criteria that Evil-Knievel sets out) and post it here.  Evil-Knievel can send a small amount of coins to the address, then crack the address and take his coins back?

Alternatively, and considerably more interestingly in my opinion, you could agree on a third party/escrow to generate a weak address.  Then both Gweedo and Evil-Knievel deposit a set (small) amount of BTC to the address.  Then Evil-Knievel has a set amount of time to break the private key before the Escrow sends all of the coins to Gweedo.

Just sayin' 

[Evil-Knievel]

This message was too old and has been purged

[Nova!]

So what you are actually claiming is that you have discovered a flaw in ECDSA that narrows the key search space and thus there are not 256 bits to search.
I have to agree, there are very likely flaws in ECDSA and the curve used by bitcoin is one of those that was compromised by the NSA wasn't it?
It's possible Dr Evil here has found something.  Wish he would share with the rest of the class though..  $1600 for a product that is supposedly not to be used for evil purposes is a bit over the top pricing wise.

Gweedo is a good guy Evil also he's a moderator and just looking out for everyones interests. 
Maybe share a copy of your source app/source with him and see what he thinks then.
 

[bmoconno]

I'm off to work, but if this still hasn't been done by the time I get home I'll edit this post with a public key generated in this fashion.

[Ritual]

Please provide private key for: 15789MauDKwkkZSvtNFzFZ5A9a9eXsBViM

Generated using your script.

Thanks,

Rit.

[tsoPANos]

Why would you sell a program for pennies while it can get you rich?

[Evil-Knievel]

This message was too old and has been purged

[Ritual]

I'm not sure it's as simple as that.

Evil gave a number (an example?) of 768 rendezvous points on the curve, and said that a weak key will be within a certain distance of these points. We don't know how far from a rendezvous point is considered "easy".

I don't pretend to have much knowledge of elliptical curves, but it seems to me that that distance is what determines how useful this actually is. After all the number of in-use addresses is a microscopic part of the namespace.

I'm interested though And it has at least inspired me to start reading new stuff if nothing else!

Rit.

EDIT: Yep, sorry Evil - it's 04cb45afa783855907367124413c97e2dc6180a4deddd63a040eec77edc09c87991de58ef830fa0 3515525eea05c8dbf7a1b31ad053819134ea7c9cd7274750250

[Ritual]

Wait! I have just realised that I have given you an incorrect public key - this is not the one associated with the address I posted!

To correct myself:

Address: 15789MauDKwkkZSvtNFzFZ5A9a9eXsBViM

Public Key: 0476febc1aa26b0c53b08f78dff62b563fdbd40197d7d9c1b00dc659fe3d3eb1b44c39844638258 e6e98be51501b35166862f9a641c175528507faccfb594f88e8

Sorry, I dunno how I managed that - I guess I was not paying attention properly. I apologise.

Rit./

[tsoPANos]

Oh there seems to be a bit of confusion there.
Hey, are you willing to test an address for me?

[Ritual]

Agreed - I have caused some confusion here, and I am sorry.

I've PMd the OP to advise that I've given wrong info, but I don't know if he's seen the PM yet. Hope he is not throwing the computer out the window because of the mismatch

[cryptomining]

Im totally buying this, all your bitcoins are mine...

[Ritual]

@cryptomining - if you do, buy me a copy as well will ya?

[Ritual]

Update:

The OP has replied to my PM asking me to verify the details again. I have replied with the details I posted above:

i.e.

Wait! I have just realised that I have given you an incorrect public key - this is not the one associated with the address I posted!

To correct myself:

Address: 15789MauDKwkkZSvtNFzFZ5A9a9eXsBViM

Public Key: 0476febc1aa26b0c53b08f78dff62b563fdbd40197d7d9c1b00dc659fe3d3eb1b44c39844638258 e6e98be51501b35166862f9a641c175528507faccfb594f88e8

Sorry, I dunno how I managed that - I guess I was not paying attention properly. I apologise.

Rit./

[tsoPANos]

for me it looks like Evil-Knievel = Ritual

[Ritual]

Yep, knew someone was going to shout that.

OK, simple solution.

Somebody ELSE come up with one.

FWIW: I don't know Evil AT ALL. However, I believe I am one of the first people to have contacted him regarding buying this. I'm from Ireland, he's from Germany . We have never had contact before except on this board. Please have a look at our seperate profiles, and see if you can spot any crossover? We're not the same person, and we have never "met" (if you can apply that term to a bloody internet bulleting board) before this thread.

@Evil - I did my best to preserve the integrity of this, but it's gone pearshaped. Please take an example from someone else - ignore mine and don't waste any hashes on it.

Rit.

PS: Incidentally, it seems that no matter how transparent anyone attempts to be on these boards, suspicion will be levelled. It's fucking stupid, excuse my Klatchian.

[Evil-Knievel]

This message was too old and has been purged

[Ritual]

tsoPANos:

Then use the above procedure to generate a bitcoin address / public key
and i will prove it to you.

And after this test is successful, I'll accept an apology from the internet's least-successful pseudo-detective, our pal and your pal, tsoPANos.

AKA, "The Idiot".

Rit.

[tsoPANos]

tsoPANos:

Then use the above procedure to generate a bitcoin address / public key
and i will prove it to you.

And after this test is successful, I'll accept an apology from the internet's least-successful pseudo-detective, our pal and your pal, tsoPANos.

AKA, "The Idiot".

Rit.

I will. But no watching some supspicious activity is not idiocy mr. Smart

[Ritual]

tsoPANos:

Then use the above procedure to generate a bitcoin address / public key
and i will prove it to you.

And after this test is successful, I'll accept an apology from the internet's least-successful pseudo-detective, our pal and your pal, tsoPANos.

AKA, "The Idiot".

Rit.

I will. But no watching some supspicious activity is not idiocy mr. Smart

I don't typically call myself "Mr. Smart" - only a few friends of mine, and my GF (when we're RPing VERY specific things) do that. EDIT: For the hard-of-thinking, this was an ironic statement.

But you know what? The nice thing about a forum like this is that activity is public, for the most part. You only had to click on my profile to see my posts, activity, and time logged in. Same with Evil. Please, by all means, point out anything that might point to us being the same person. By extension to your logic, I feel like you are single-handedly every poster on the Greek board, simply because I cannot read Greek. You look like you're all sharing symbols. This must be just one person, right?!

Nah, for now I'll stick with "The Idiot".

Rit/

[tsoPANos]

address: 1LMfkKKqgwSbjJTecGKQLmeh4sbEj95vhy
public key: 047d97cc0ba7063af87532ceff9f0521dc8dbc583dde5e078a4e9efe299a02ff28621a844dad6e5 f382fefb14f2e83ddabd347fad76eacdef81a47d11942d9c8f7



ok, now I bet you won't find the private key.

[Evil-Knievel]

This message was too old and has been purged

[tsoPANos]

Panos, if you created the key in the way depicted earlier in this thread, I will crack it.
Give me some time :-)

All of you, who want to contribute to this project:
Help creating more and more rendezvous-points  
I have made a small python script public, which will generate such points - for each rendezvous point you are paid a certain amount of BTC.
More Infos here: https://bitcointalk.org/index.php?topic=433522.0

I did, also I would like to know if it is possible to check a if a public address is weak

[Ritual]

Really looking forward to the result of this.

Rit.

[RGBKey]

This is the reason why people say to not reuse addresses. When you recieve bitcoins, do so with a fresh address and when you spend them, spend the entire address, the change back to a new fresh address.

[Ritual]

Yeah fair enough.

But the entire network can't run that way - it's impractical.

If there's a weakness, better that it shows up now so that it can be rectified that result in the loss of someone's (possibly) life savings.

Rit.

[urbanogt5]

Hey, Interesting project man

 I was trying to create millions of address with vanitygen and then check the balace ( No bruteforce ), but your method of small range bruteforce sounds great.

Code:

0xe8b50b147a1e371613a9253a5219e46be5875bc7a45d93707b82913e8d7ef16cL	0x6cabea076c54a7bb55e6bfaeff3a9c5e07ff149c8ccfd002bcaa82e729c5343cL	0xd8487b27cbd178a1c409bf84496356abe98c84475a5180f270d615ce065b8f0aL

[Ritual]

It is an interesting project, and Evil is clearly working hard on extending his range of rendezvous points on the curve, but....

What happened to this test?

Did the cracker not work?

Is this no longer for sale?

Is it worth less than was asked?

Is Evil's data-collection on the other thread likely to (a) compromise the security of the network in general? (b) likely to devalue his own product?

I dunno.

An update'd be wonderful, for those of thinking seriously of purchasing. 2BTC is alot to some.

Rit.

[weedoge]

Good luck! ^^ https://blockchain.info/tx/e99fb7b6e2f69a6cb1cda2d83cc0644f93ae6c9413009f11a6a6bc3740cc9ce6

[tsoPANos]

It is an interesting project, and Evil is clearly working hard on extending his range of rendezvous points on the curve, but....

What happened to this test?

Did the cracker not work?

Is this no longer for sale?

Is it worth less than was asked?

Is Evil's data-collection on the other thread likely to (a) compromise the security of the network in general? (b) likely to devalue his own product?

I dunno.

An update'd be wonderful, for those of thinking seriously of purchasing. 2BTC is alot to some.

Rit.

Well we really need an update...\
anyway, I would like to note that even if he cracks the address, he will have a hard time finding weak addresses with bitcoins inside.

[Ritual]

weedoge - you just gave tsoPANos those BTC

He was the one who posted the test, and he has the private key.

But yeah, we've butted heads on this thread, and probably won't go drinking together, but tso is right - we need an update.

What happened to "I'll crack any weak key immediately"?

Rit.

[weedoge]

weedoge - you just gave tsoPANos those BTC

He was the one who posted the test, and he has the private key.

But yeah, we've butted heads on this thread, and probably won't go drinking together, but tso is right - we need an update.

What happened to "I'll crack any weak key immediately"?

Rit.

It's cool, I just felt like sending it. We'll see where it goes anyway.

[weedoge]

Also tbh there's nothing we can do to speed him up while he's offline.... so just wait I guess.

It'll still be impressive if cracked.

[Ritual]

Also tbh there's nothing we can do to speed him up while he's offline.... so just wait I guess.

It'll still be impressive if cracked.

Agree with both.

Feel free to send me a few thousand bitcoins if you're "feeling it " hahah

Rit.

[FiatKiller]

So how can we find out if our addresses are "weak"?

[weedoge]

So how can we find out if our addresses are "weak"?

Probably with a modified version of Evil's program

He's put a lot of time into in, specifically having other people help him by generating thousands of rendezvous points or something, I generated a few myself.

I'm very interested to see how this turns out... and maybe if you could attempt to bruteforce any of a list of bitcoin addresses.

Edit: Although I'm also interested in Bitcoin devs making it more secure if this is real

[FiatKiller]

I would def pay less for a checker program. Please make it available!

[urbanogt5]

Evil, meaby I'm very bad posting this, but I want to understand your work. What do you want to get? All the weak address or only the rendezvous points??


Is something like that?

[Ritual]

So how can we find out if our addresses are "weak"?

You can't.

I'm no expert on elliptical curves, but basically it seems to come down to this:

- Every address is a point on the elliptical curve, described by a triplet.

- Evil has mapped 768 by himself, and is currently mapping thousands more of rendezvous points - fixed points on the curve.

- Your address might, or might not be "close" to any given rendezvous point.

- If it is, he can crack it in a short time, by using an arc-attack. That is, he can figure out a tiny portion of the curve, and attack it.

- If your address is within this tiny arc, it's weak.

- As he adds more rendezvous points (i.e. platforms of attack), every address potentially falls into his attackable zones.

A few things:

1. We do not know how far from a rendezvous point he can reasonably attack.
2. We have no context on how many rendezvous points make a problem - i.e. 768 points could be a serious issue for a large portion of the namespace, or 150 million could be non-serious. We just don;t know this.
3. The namespace is ENORMOUS.
4. The chances of any given address falling in an attackable space appears to be very small.
5. The addresses in use are (we must assume) randomly distributed
6. This means any address could be weak or strong, and we cannot know this either.

Until Evil can do two things, nobody can know if this is a threat:

a. Actually crack an address. He's given a script which should generate a weak address. So anything output by that should have been cracked quickly. i.e. by now.
b. Publish how far from any given rendezvous point his attack can go, and the portion of the curve in total he can attack.

To expand that last point a bit:

Total namespace: 2^160.
Rendezvous points: 768 (at this time)

Divide the namespace by the points and that's a hell of a lot of black space which cannot be attacked.

If he can go 50 trillion points to either side of the points, this might not be a very big portion of the namespace at all.

On the other hand, if Evil has figured out a way to work with only the used namespace, then Bitcoin is in serious shit.

Rit.

PS: I might have alot of the above surmises wrong. I'm no mathematician, and I'm certainly no cryptographer.

[FiatKiller]

Thank you. Very thorough answer.  :-D

[Ritual]

Also, given his work on the mining thread, I'd say that Evil has lost interest in this little piece of software and has instead concentrated his efforts on cracking the entire curve instead.

Doubt we'll see him again here on this thread, but I stand to be corrected - pleasantly so.

Rit.

[starik69]

I will tell you the private key immediately.

Does "immediately" mean more than 24h? 

[urbanogt5]

Also, given his work on the mining thread, I'd say that Evil has lost interest in this little piece of software and has instead concentrated his efforts on cracking the entire curve instead.

Doubt we'll see him again here on this thread, but I stand to be corrected - pleasantly so.

Rit.

You sounds like Evil

[Ritual]

Well, at this point I think we can safely assume this is horseshit.

I hope nobody gave him 2 bitcoins. Damn glad I didn't.

Rit.

[itod]

Well, at this point I think we can safely assume this is horseshit.

-1, it's very interesting.

I hope nobody gave him 2 bitcoins. Damn glad I didn't.

This is debatable, guy needs to pay 10 BTC for the triples somehow. Maybe he got some funds from the academia to finance that.

[Evil-Knievel]

This message was too old and has been purged

[weedoge]

Okay guys, I have found the reason why i am trying to crack those for around 3 days now.

it is clearly not a problem on my side, but the "Secret Exponent" Field is size limited on the brainwallet.org website. Meaning if you paste in a number which is too long, the end gets cut off. DOH!

Please repeat the process with numbers, that actually fit in the secret exponent field completely.
Sorry for this inconvenience ...

If you generate your address completely as to the manual, and the exponent does not get cut off, I will need around 15 minutes per Private Key MAX!

1AHuqqrtfxfmTC4KQNGDX7kedxdgpQnUmD

Pub key: 04db259553306519117692a0175d8abdd8ef2f12fcb3a2a56e7d4879e049f9abdc5a9244906da8f 58879b4de5d0b8c3182e4acfe9c231a379037aba1f5cc541d02

[Evil-Knievel]

This message was too old and has been purged

[Ritual]

Looks like I need to post an apology, so here it is:

My previous response was both premature and immature. Please accept my sincere apology, and congratulations on your successful test.

EDIT: And please give your tool a nicer name 

Thanks,

Ritual.

[Evil-Knievel]

This message was too old and has been purged

[Ritual]

[tsoPANos]

hahah I liked that one 

[weedoge]

Pretty awesome....

but it's a very specific way of generating addresses.

And you have no method of checking which addresses are weak?

Can you attempt to crack multiple addresses at the same time with little performance loss?

[Evil-Knievel]

This message was too old and has been purged

[ny2cafuse]

Disclaimer:
This project is for research purpose only, or to recover lost private keys. It may not be used for any illegal activities and I cannot be held responsible for anything you do with it.

You say it's for research only, but at the end of your video you say the bitcoins in the address are "stolen".  You little comic shows your true intention of just stealing people's coins.  If you were going to do this, why would you announce it?  Wouldn't you just quietly steal all the bitcoins you could find?  It makes no sense. 

And then to top it off, if it really is for research, why wouldn't you just donate the knowledge to the development team to help fix the security hole that you're claiming exists?  You have the possibility of earning more money in donations from the community by providing a fix for what you're trying to prove is a security flaw.  Hell, I'd donate bitcoin to you if you were doing this for the good of the community.  But 2BTC for a copy... it makes no sense.  If it did what you say it does, and it could have very well be proven in the profanity-laced and almost tourettes-like video, why wouldn't you be charging more for it.  2BTC is chump change if this is legit.

Something doesn't add up.  Just my $0.02.

-Fuse

[prezbo]

This is actually for cracking public addresses and finding the private key? lol

Theoretically yes,
I am offering it for "scientific purpose" only. The buyer must agree not to use it for any illegal activity whatsoever.

For clarification: Collisions mean that there is a private key found, of which the public key matches in 32bits (out of 256) the public key you provided as an input. This (at the current speed) happens several times a minute.

If wanted, I can prove that weak private keys are found within a manner of seconds. Weak private keys are all those, who are significantly close (like several million units apart on the x axis) to one of the 768 rendezvous points on the elliptic curve.

Just want to clarify, this is cracking public keys not addresses. There is currently no known way of getting the public key from the address unless sha256 and ripemd-160 are broken.

However, a very interesting project, Evil-Knievel - but I wouldn't put my money on it actually cracking any public key with actual bitcoins on it (unless it's set up, of course).

[Evil-Knievel]

This message was too old and has been purged

[Remember remember the 5th of November]

So what exactly is a rendezvous point? I can't find anything on Google about rendezvous points about ECDSA or curves

[Yogafan00000]

All horseshit aside, to clarify all of this:

It seems that any reused Bitcoin address is potentially vulnerable to attack because right now there is no way to know if it's close to a rendezvous point?

But addresses that haven't been reused are safe, but only because the public key for that address has not been broadcast yet?  As soon as the public key is broadcast by spending from an address it becomes vulnerable?

I've been noticing rumblings of this before from a privacy point of view, but it seems now we have even more reason to stop reusing addresses.

[Evil-Knievel]

This message was too old and has been purged

[prezbo]

This is actually for cracking public addresses and finding the private key? lol

Theoretically yes,
I am offering it for "scientific purpose" only. The buyer must agree not to use it for any illegal activity whatsoever.

For clarification: Collisions mean that there is a private key found, of which the public key matches in 32bits (out of 256) the public key you provided as an input. This (at the current speed) happens several times a minute.

If wanted, I can prove that weak private keys are found within a manner of seconds. Weak private keys are all those, who are significantly close (like several million units apart on the x axis) to one of the 768 rendezvous points on the elliptic curve.

Just want to clarify, this is cracking public keys not addresses. There is currently no known way of getting the public key from the address unless sha256 and ripemd-160 are broken.

However, a very interesting project, Evil-Knievel - but I wouldn't put my money on it actually cracking any public key with actual bitcoins on it (unless it's set up, of course).

I have to correct you here. All public keys are publicly available on blockchain.info.

They are once you sign an input, but any half capable wallet won't reuse addresses, making it so once the public key is known the funds will be gone.

edit: I see you already addressed this.

[Yogafan00000]

To be absolutely safe, you are absolutely correct. You should not reuse addresses, because as you do your public key gets broadcasted.
However, if you only store a few thousand bucks in your wallet, you are not likely to because a target of the "bruteforcers" as they will probably aim for higher accounts.

However, yes: Not reusing the address will make you safe.

I believe the first time a brute-forcer breaks a large bitcoin wallet he will inadvertently or by intent, also break Bitcoin and by extension crypto-currencies.  Confidence in this budding technology is already precarious.  Any notion that one's coins are insecure will not be met well by the masses.

These findings of weakness in the blockchain should be brought to the developers attention and we should be calling for some solution to this issue as soon as possible.

[itod]

Disclaimer:
This project is for research purpose only, or to recover lost private keys. It may not be used for any illegal activities and I cannot be held responsible for anything you do with it.

You say it's for research only, but at the end of your video you say the bitcoins in the address are "stolen".  You little comic shows your true intention of just stealing people's coins.  If you were going to do this, why would you announce it?  Wouldn't you just quietly steal all the bitcoins you could find?  It makes no sense. 

And then to top it off, if it really is for research, why wouldn't you just donate the knowledge to the development team to help fix the security hole that you're claiming exists?  You have the possibility of earning more money in donations from the community by providing a fix for what you're trying to prove is a security flaw.  Hell, I'd donate bitcoin to you if you were doing this for the good of the community.  But 2BTC for a copy... it makes no sense.  If it did what you say it does, and it could have very well be proven in the profanity-laced and almost tourettes-like video, why wouldn't you be charging more for it.  2BTC is chump change if this is legit.

Something doesn't add up.  Just my $0.02.

-Fuse

He is writing the paper, so the research will be published eventually. There is no security hole, and nothing can be fixed by the development team at this moment until more research is done to investigate these phenomenons. The good of the community and the good of the collective knowledge are not the same things, and at this moment Evil-Knievel is doing this for the knowledge that can be gained, if the community will benefit or not is another matter.

[noob2001]

.

[Evil-Knievel]

This message was too old and has been purged

[noob2001]

.

[Evil-Knievel]

This message was too old and has been purged

[noob2001]

.

[FiatKiller]

All horseshit aside, to clarify all of this:

It seems that any reused Bitcoin address is potentially vulnerable to attack because right now there is no way to know if it's close to a rendezvous point?

But addresses that haven't been reused are safe, but only because the public key for that address has not been broadcast yet?  As soon as the public key is broadcast by spending from an address it becomes vulnerable?

I've been noticing rumblings of this before from a privacy point of view, but it seems now we have even more reason to stop reusing addresses.

Since this is very important, can you define "reused"? Do you mean accept incoming funds, but don't transmit any funds out except to drain the address??  thanks

[Sonny]

All horseshit aside, to clarify all of this:

It seems that any reused Bitcoin address is potentially vulnerable to attack because right now there is no way to know if it's close to a rendezvous point?

But addresses that haven't been reused are safe, but only because the public key for that address has not been broadcast yet?  As soon as the public key is broadcast by spending from an address it becomes vulnerable?

I've been noticing rumblings of this before from a privacy point of view, but it seems now we have even more reason to stop reusing addresses.

Since this is very important, can you define "reused"? Do you mean accept incoming funds, but don't transmit any funds out except to drain the address??  thanks

When bitcoin is sent out of an address, the public key of that address will be known to the world.

[Evil-Knievel]

This message was too old and has been purged

[FiatKiller]

Thanks much! This should be in the Bitcoin 101 course. I will put this into practice immediately. I did recently divide-up my hoard into 3 wallets and the two new wallets have not been used for any outgoings transactions. Whew.

[Chimsley]

Copied from my posting in the development thread.

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.

[solomon]

You don't need a new address for every user, just a new address whenever you sweep it. A bigger entity accepting bitcoin could just empty the account periodically and put a new address up. They may only empty the address once every 6 months.

[prezbo]

To be absolutely safe, you are absolutely correct. You should not reuse addresses, because as you do your public key gets broadcasted.
However, if you only store a few thousand bucks in your wallet, you are not likely to because a target of the "bruteforcers" as they will probably aim for higher accounts.

However, yes: Not reusing the address will make you safe.

I believe the first time a brute-forcer breaks a large bitcoin wallet he will inadvertently or by intent, also break Bitcoin and by extension crypto-currencies.  Confidence in this budding technology is already precarious.  Any notion that one's coins are insecure will not be met well by the masses.

These findings of weakness in the blockchain should be brought to the developers attention and we should be calling for some solution to this issue as soon as possible.

They do not pose any realistic threat. When you consider the probabilities, it's all the same, either you need sqrt(n) tries (currently best known algorithm that solves the discrete logarithm problem in general) for 100% chance or sqrt(n)/100 tries for 1% chance of success.

[mufa23]

So this random addy I grabbed off of blockchain.info currently has BTC15.14013694 in it. Since it has sent BTC before, it's public key is now shown, and thus hackable?

Can you prove it by finding the private key yourself, and moving BTC0.00123456 out and back into the address? I want to see a show.

[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. (is the april fools date intentional?)

Show us what you can do, Knievel.

[gmaxwell]

Quoted. (is the april fools date intentional?)

Nah, coincidental. The only reason I put a limit at all is so I wouldn't feel ethically obligated to hold onto 50 BTC beyond that point in time.

[mufa23]

Quoted. (is the april fools date intentional?)

Nah, coincidental. The only reason I put a limit at all is so I wouldn't feel ethically obligated to hold onto 50 BTC beyond that point in time.

Duly noted.

[binaryFate]

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.

[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.

[BurtW]

Calling it a theoretical attack is a stretch.  I would prefer to say he has just "proven" the truism:  If I reduce the private key space enough then, of course, I can find the private keys.

[Blaater]

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.

But the real question is, if you make a special software that would make a big 'rainbow table', how long would it take before you get 0.1% of 'rendez-vous' points mapped? Would that be impossible or just take a good amount of time but still possible.

[Evil-Knievel]

This message was too old and has been purged

[prezbo]

Maybe some more correct explanation.


[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 someone picks a private key which we assume to be our sandgrain and hides is somewhere on any beach on this planet. Lets further assume this sandgrain is painted blue.

[3] - Searching for this particular sand grain is computationally infeasible. But let us say you have placed a colored tennis ball (each with a different color) on each of the world's beaches.

[4] - now imagine you send out 100.000 people to all the beaches of the world simultaneously. If one of these people finds a blue tennis ball somewhere, you can recover the private key.

It's slightly better, but still computationally infeasible.

[FiatKiller]

EK, eagerly awaiting you to hack one of the addresses for 50 BTC. ;-)

I don't understand this stuff enough yet to have an opinion whether it's likely, but
fascinated to see what plays out.

[BurtW]

EK, eagerly awaiting you to hack one of the addresses for 50 BTC. ;-)

Don't hold your breath.

[BurtW]

Maybe some more correct explanation.

[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 someone picks a private key which we assume to be our sandgrain and hides is somewhere on any beach on this planet. Lets further assume this sandgrain is painted blue.

[3] - Searching for this particular sand grain is computationally infeasible. But let us say you have placed a colored tennis ball (each with a different color) on each of the world's beaches.

[4] - now imagine you send out 100.000 people to all the beaches of the world simultaneously. If one of these people finds a blue tennis ball somewhere, you can recover the private key.

How did the private key (blue grain of sand) magically get placed near enough to the blue tennis ball (known point) to be able to be found in a reasonable amount of time?

[Rampion]

So this random addy I grabbed off of blockchain.info currently has BTC15.14013694 in it. Since it has sent BTC before, it's public key is now shown, and thus hackable?

Can you prove it by finding the private key yourself, and moving BTC0.00123456 out and back into the address? I want to see a show.

Interesting. Let's see what Evil can pull out from this.

[gadman2]

This thread will go no where unless he proves himself with gmaxwells bounty.

[Ritual]

Hmmm....from the explanations offered in this thread, would I be correct in thinking:

The generator code allowed for 20million keys each side of a set (i.e. known) rendezvous point. So for each, this is 40 million keys.

Evil appears to have started with 768 points, and is mining thousands more on his other thread.

So let's say that we end up in a month with a million rendezvous points total. This would give us a total number of crackable keys = 40 million * 1 million.

So 40000000000000. That's a big number. Very big. But...

The namespace is 2^160 keys (I think - please correct me if that's wrong), and the number above is insignificant to the point of meaninglessness in that context.

Please correct me if I'm wrong. I'm trying to pick up this stuff as I go along

Rit.

[onzoom]

First the boring but true bit

There is no risk whatsoever in revealing your Public Key.

There is no need to change your Wallet Address

You do not choose your private key. The private key is not weak.
.


Now the fun bit

Maybe some more correct explanation.


[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 someone picks a private key which we assume to be our sandgrain and hides is somewhere on any beach on this planet. Lets further assume this sandgrain is painted blue.

[3] - Searching for this particular sand grain is computationally infeasible. But let us say you have placed a colored tennis ball (each with a different color) on each of the world's beaches.

[4] - now imagine you send out 100.000 people to all the beaches of the world simultaneously. If one of these people finds a blue tennis ball somewhere, you can recover the private key.

[1]  most of the sand is under the sea or in a desert
[2]  someone carefully paints a grain of sand blue before hiding it underneath  some of this sand
[3]  now rather than trekking through oceans and deserts I do a world tour of beaches carelessly littering a load of balls
[4]  I send 100,000 people to all the beaches in the world to find my favourite blue ball (which is pretty cruel since i know where I placed the blue ball) Reunited with my favourite blue tennis ball I celebrate by typing dumpprivkey into the console of my bitcoin wallet and recover my private key



On reflection the most relevant comment on this thread is summarised by the last four words of point [3]

[piotr_n]

I find this thread very interesting.

From myself (since I suck in math these days), I can only add one thing here, though more of a philosophical matter:
There is no way anyone would ever break this curve, without first assuming that the curve can be broken.
At the other hand, assuming that this curve cannot and will never be broken, is the most irresponsible thing a bitcoin holder can do.

Of course currently EK can only crack a tiny (statistically almost non-existent) part of all the possible keys out there.
But he is obviously doing some more research.
From what I see, the guy is literally gathering a statistical data, hoping that maybe there is something about this curve that would make the balls more likely to end up in a certain places on the earth.
It might be a dead end, but you cannot blame him for trying. I personally appreciate it.

[itod]

From what I see, the guy is literally gathering a statistical data, hoping that maybe there is something about this curve that would make the balls more likely to end up in a certain places on the earth.
It might be a dead end, but you cannot blame him for trying. I personally appreciate it.

From http://stargate.bitwarrant.com/science/

Live Key Counter: 51012 keys submitted so far.
What Do I Actually See Here?
We are generating random Bitcoin addresses, that match (in the least significant 32 bits) a few of our rendezvous points on the elliptic curve (read more). Bitcoin addresses themselves are just points on this very elliptic curve. Now if the distribution of BTC addresses is completely random, we should experience a totally balanced distribution of hit rendezvous points (The bar-chart on the right hand side shows these rendezvous points and their distribution).

Time will tell, how random BTC addresses actually are. If the right "point cloud" evolves to a straight blue line, our BTC adresses should be safe. Hence if it doesn't, this will open new topics to be discussed.

Dozens off us with many machines are helping him gather this data, we'll see the results in the paper.

[piotr_n]

Dozens off us with many machines are helping him gather this data, we'll see the results in the paper.

Exactly. It is a highly valuable project, because even if it fails, it still proves something.

Unlike the "there is nothing suspicious about secp256k1 params" or "your tool cannot crack my key" approach - which is totally useless and may be even dangerous, since it strengthens confidence in the technology that uses assumptions, which no sane mathematician would bet his life on.

Besides, if you don't try to break the things that others consider unbreakable, even though there is no proof of them being actually unbreakable - then what kind of fun your life is?

[BurtW]

That looks like great/fun/useful? research into the properties of the RNG used to generate the data.  Might be interesting.  Have no problem with that part of it.  What I have a problem with is his marketing and sales:

[WTS] OpenCL Based, Optimized BTC Private-Key Cracker with Sources [WITH VIDEO]

[FiatKiller]

Can I ask a fine point about reusing address?

When you send your coins to a new address to be safe, can it be in the same wallet or does it have to be a new wallet?

I know say it does not matter, but what the heck. Might as well CYA as much as possible. lol

thanks

[piotr_n]

That looks like great/fun/useful? research into the properties of the RNG used to generate the data.

As I said, I suck at math, but my understanding of this project is that it is a statistical analysis of how the value of the least significant 32 bits of... something (but which has definitely nothing to with RNG), can be projected into the most efficient set of a specific randezvouz points, to be (eventually) used for bruteforcing secp256k1 keys.


EDIT:

Have no problem with that part of it.  What I have a problem with is his marketing and sales:
Quote
[WTS] OpenCL Based, Optimized BTC Private-Key Cracker with Sources [WITH VIDEO]

Well, it's not like anyone bought this tool, is it? It looks like a good ad, though.

One day when I pointed out that nobody cares about my working bitcoin client in Go while everyone was very excited about another one only announced to be made - one guy came to tell me that my software only matters as much, as my marketing is worth.. and there is something about it

[prezbo]

Of course currently EK can only crack a tiny (statistically almost non-existent) part of all the possible keys out there.
But he is obviously doing some more research.
From what I see, the guy is literally gathering a statistical data, hoping that maybe there is something about this curve that would make the balls more likely to end up in a certain places on the earth.
It might be a dead end, but you cannot blame him for trying. I personally appreciate it.

It is a dead end, because he's using old techniques, that were already proven how efficient they are.

[itod]

That looks like great/fun/useful? research into the properties of the RNG used to generate the data.

As I said, I suck at math, but my understanding of this project is that it is a statistical analysis of how the value of the least significant 32 bits of... something (but which has definitely nothing to with RNG), can be projected into the most efficient set of a specific randezvouz point, to be (eventually) used for bruteforcing secp256k1 keys.

Exactly, RNG has nothing to do with it, which is often overlooked because people are used to faulty RNG being the usual suspect. RNG quality on machines generating the triplets is unimportant, because all generated private keys are sieved against an array of predefined values, and if matched is later used in the analysis.

Edit: X EC coordinate (first half of the public key) is calculated, and if last 1/4 of that X-coord matches any value in the array produced triplet is submitted.

Dozens off us with many machines are helping him gather this data, we'll see the results in the paper.

Exactly. It is a highly valuable project, because even if it fails, it still proves something.

Unlike the "there is nothing suspicious about secp256k1 params" or "your tool cannot crack my key" approach - which is totally useless and may be even dangerous, since it strengthens confidence in the technology that uses assumptions, which no sane mathematician would bet his life on.

+1

[gmaxwell]

From what I see, the guy is literally gathering a statistical data, hoping that maybe there is something about this curve that would make the balls more likely to end up in a certain places on the earth.

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.

Dozens off us with many machines are helping him gather this data, we'll see the results in the paper.

Exactly. It is a highly valuable project, because even if it fails, it still proves something.

All it does is reaffirms is that the world is full of fuzzy headed reactionary thinkers, unscrupulous parties, and pump-and-dumpers looking to cash in on hysteria.

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...

[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./

[BurtW]

The only way you are going to get your BTC is to remember or reconstruct the brainwallet phrase and go this direction:

(phrase) -> (private key) -> (public key) -> (Bitcoin address)

By design it is impossible to go the other direction because every step in the reverse process is impossible:

(Bitcoin address) -> (public key) -> (private key) -> (phrase)

(Bitcoin address) -> (public key) have to break through three hashes using two different hashing algorithms

(public key) -> (private key) have to break eliptical curve cryptography

(private key) -> (phrase) would have to break SHA256 again, but this step is not really needed if you have the private key

My suggestion is try to remember every single possible word or phrase she could have or would have maybe used and then go through all combinations of those words and phrases.

[Ritual]

BurtW - you misunderstand me.

I am simply creating billions of addresses with their private keys using Vanitygen. Then checking them against a stored list. I am not trying to go backwards, or break any kind of encryption. I'm just hoping for a match at some point. In my lifetime, preferably.

Point is, I am "reducing" the name space I am searching by specifying:

1) The first 3 chars of the address: 12g
2) The range of addresses I want to match.

It's not much of a reduction, and I'll have to be lottery-winning lucky, but you know what? It runs on my machine 24/7, and it's fine. If it hits, it hits.

What I want is for one of the mathematicians on the forum to explain why EKs approach is any more efficient than mine. As far as I can see, he can only compare a few million keys from a rendezvous point. He can do it very quickly, I grant that, but give me better hardware and I can generate more keys in Vanitygen too

Anyhow, mine is the crudest possible type of attack.

But I still don't see much of a difference between this and EKs. And when you get into the numbers, I'll bet that the advantage he has is microscopically insignificant. Anyone care to calculate it?

Rit./

[BurtW]

Not sure why you are not using vanitygen to filter your results even more for you.  Why only 3 characters?  Why are you not using an exact match on say the first 7 or 8 characters?

As you add more and more characters to your exact match criteria vanitygen will give you some idea of how long you are going to have to wait just to get something with those first characters - let alone a perfect match.  Just keep adding characters and that will give you a feel for how long it is going to be even get a match that is "close", and by "close" I mean a worthless partial match that is not really close and does not get you any closer to finding a match.

You probably know my opinion by now but just in case:  EK's approach will not work.  

I don't think you can generate and check addresses faster than vanitygen on a video card.

I can do some maths after my nap if someone else has not done it.

[FiatKiller]

I feel for you Ritual. I would retire or at least move now if I had 199 BTC.  lol

It's bad policy to ever throw out a harddrive without at least opening it and destroying the platters.

Never thrown one out yet.

[BurtW]

As the designer of cryptographically secured disk drives I can assure you that if you properly configure a TCG or other FDE drive you can just pull it out of your system and toss it.  Your data is safe.

For sure your comment does apply to standard disk drives and even more imporantly devices such as copiers that have unsecured disk drives in them.  Get an old junked copier and pull the disk drive.  Wala!  Thousands of documents to look at.

[piotr_n]

I want is for one of the mathematicians on the forum to explain why EKs approach is any more efficient than mine.

Because he uses (some kind of) math to vastly increase a probability that a number he's trying would be the one he's looking for.
Your approach is just looking blind

[itod]

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.

I can guarantee you one thing: you can stop vanitygen efforts, there's no chance you'll ever get any results with it. As somebody pointed out, you may as well search for the whole address with it, just to see how improbable that method is.

On the other hand, you maybe have a chance to recover it because she used a brainwallet. If she once knew the phrase, she
may eventually remember it, so why doesn't she try (don't laugh) hypnosis? I've read that experts can make you recover any memories. It's sure worth a try if the reward is 150.000US$.

[Ritual]

Not laughing. But I don't agree with piotr either.

Sure I may never ever hit. I'm well aware of the size of the namespace.

But I don't see that my efforts to reduce the search space are any less effective than EK's. And that's the whole point here.

I've reduced 31^58 to 29^58, and more, against a certain range of addresses.

He's trying rendezvous points on the curve with VERY NARROW nets on them.

It's exactly the same thing, although his hardware is better than mine.

To whoever asked: I go with 12* because any more than that takes longer to calculate (on my machine) than is worth it. i.e. it takes more than 58 times as long to calculate the third digit, and more than 58 times again the 4th one. I'm not likely to ever hit anyhow, but there you go. "Reasoning" hehe

Seriously, everything that I read about elliptic curves tells me that my approach is every bit as valid. It's a brute force against a narrow sliver of the namespace, as opposed to a rainbow table attack against the whole thing.

Anyone care to analyse? Rather than tell me to give up I mean

Ritual.

[piotr_n]

Ok.
Do you want to take place in competition for a bounty on breaking any of the gmaxwell's addresses?
Maybe we should make like a fund to get it done faster.
Though I'd rather prefer to generate my public keys by myself
Anyway, feel free to steal all my money- let it be my part of the bounty
I do reuse addresses sometimes - just get them from the chain.

[Ritual]

Ok.
Do you want to take place in competition for a bounty on breaking any of the gmaxwell's addresses.
Maybe we should make like a fund to get it done faster.
Though I'd rather prefer to generate my public keys by myself
Anyway, feel free to steal all my money- let it be my part of the bounty
I do reuse addresses sometimes

With all the respect I can grant you for your comment, which is fuck all....

Don't be so fucking ridiculous.

I'm well aware of what I am doing, and I'd bet a banjo to a barndance that I understand the mathematics behind this better than you do.

I wasn't putting myself up for a challenge, you utter utter moron, I was pointing out that ANY attack on the elliptic curve is futile, as long as it centers on isolating a section of the namespace.

Do you understand now? Or should I draw this in fat crayons for you and then post a picture of it? Or is fingerpaint better?

Try READING sometimes. It helps immensely with comprehension. Really.

Rit./

[piotr_n]

Don't get so upset. I didn't mean to offend you.
I only mean that if you cannot show me how you crack actual keys, then don't waste my time.
Please

[Ritual]

If you're mistaking me for the OP, then I forgive you. That only means that you can't read. Not your fault.

If you're under the impression that I am laying down some sort of challenge, then you're stupid. And that is also not your fault. But it means I won't bother with you.

Which is it?

Now before you answer, I'd like you to consider the following: I HAVE NEVER EVER CLAIMED TO HAVE CRACKED A KEY OR FOUND ANY WEAKNESS IN THE CURVE. This is not my thread.

Rit.

[Chimsley]

I am not a math wiz on this but while we are comparing futile efforts to "win the lottery" with bitcoin I am curious if someone can work out this math.

Is it possible to calculate how many addresses in the keyspace will start with a certain prefix. For example the address 1933phfhK3ZgFQNLGSDXvqCn32k2buXY8a has over 100k bitcoins on it.  If your using vanitygen or some other such tool and generating keys with a target of 1933 how big is that subset of addresses that will begin with that prefix?  Are we talking only 2 lifetimes of the universe instead of 10?

Just curious, this is interesting stuff.

[Phrenico]

BurtW - you misunderstand me.

I am simply creating billions of addresses with their private keys using Vanitygen. Then checking them against a stored list. I am not trying to go backwards, or break any kind of encryption. I'm just hoping for a match at some point. In my lifetime, preferably.

Point is, I am "reducing" the name space I am searching by specifying:

1) The first 3 chars of the address: 12g
2) The range of addresses I want to match.

It's not much of a reduction, and I'll have to be lottery-winning lucky, but you know what? It runs on my machine 24/7, and it's fine. If it hits, it hits.

What I want is for one of the mathematicians on the forum to explain why EKs approach is any more efficient than mine. As far as I can see, he can only compare a few million keys from a rendezvous point. He can do it very quickly, I grant that, but give me better hardware and I can generate more keys in Vanitygen too

Anyhow, mine is the crudest possible type of attack.

But I still don't see much of a difference between this and EKs. And when you get into the numbers, I'll bet that the advantage he has is microscopically insignificant. Anyone care to calculate it?

Rit./

Vanitygen just generates private keys randomly, which are converted deterministically to pub keys and addresses. Unless those hashes and ECC were broken, you're not reducing your search space by specifying that you want Vanitygen to store the addresses that start with 1xyzabc. In other words, there's no way to tell Vanitygen to "only make priv keys that get you addresses near 1xyzabc...".

Unfortunately for your wife, yours is just a brute-force method. Definitely ask her to tell you every possible number, phrase, and character that she may have used for her brain wallet. There's no other way about it.

I am not a math wiz on this but while we are comparing futile efforts to "win the lottery" with bitcoin I am curious if someone can work out this math.

Is it possible to calculate how many addresses in the keyspace will start with a certain prefix. For example the address 1933phfhK3ZgFQNLGSDXvqCn32k2buXY8a has over 100k bitcoins on it.  If your using vanitygen or some other such tool and generating keys with a target of 1933 how big is that subset of addresses that will begin with that prefix?  Are we talking only 2 lifetimes of the universe instead of 10?

Just curious, this is interesting stuff.

You're misunderstanding Vanitygen in the same way that Rit is. There's no way of knowing which private key will get you address that starts with a preordained string of characters.

For example, observe how different the addresses are even of very closely related private keys in this list:

http://www.directory.io/

That's the point of the cryptography; you get no information about where to look for the private key if you're only given the address.

[Phrenico]

I am not a math wiz on this but while we are comparing futile efforts to "win the lottery" with bitcoin I am curious if someone can work out this math.

Is it possible to calculate how many addresses in the keyspace will start with a certain prefix.

To answer your question more directly, it is certainly possible to calculate how many addresses start with a certain prefix. That's just 2^(160-x) where x is the length of the prefix.

The problem is there's no way of knowing which private keys get you that prefix, so you're no better off.

[weedoge]

I think the connection stability could use some tweaking.

At the moment, if I go offline for 30 seconds I drop to 90%, and 20 minuten later i'm back up to 100%. It's more accurate if it is correctly balanced over the last 24 hours to get a nice 99.99% stability.

You talking about the server for the rendezvous point thing?

The new c++ script queues them instead of chucking them away when they can't be sent.

[BurtW]

Maybe understanding exactly how vanitygen works will clear up some confusion:

Use vanitygen to search for the Bitcoin address

1) Create a totally random private key over the entire private key space (random Key_private)
2) Calculate the public key from the private key (ECC Key_public = Key_private * G)
3) Calculate the Bitcoin address (Address = Encode(HASH(HASH(HASH(Key_public)))))
4) Compare the randomly generated Bitcoin address to the regular expression given to vanitygen when you started it
5) If this randomly generated Bitcoin address matches the pattern then print and quit (or continue, depending on flags)
6) Go to 1)

So now maybe you can understand why setting your search pattern to only two or three characters and then doing the rest of the comparison yourself is not better (and is probably slower) than just setting vanitygen to do more or all of the pattern match.

Vanitygen generates one key pair at a time, calculates the Bitcoin address, then compares it to the pattern.  It does not magically generate only the Bitcoin addresses that match your pattern.  That is why the longer your pattern the more time it takes to find one.

Sorry if you already knew this.  Others might not have.

[BurtW]

Ritual,  Now I have a question for you:

Please give me the transaction id of the transaction where you spent the 1 BTC from your long lost BTC stash.

[User705]

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./

Not sure why you felt it smart to post part of your brainwallet and now if you post your address there will be quite a few people trying to crack it although you won't see any of it.  Anyways if you search the forums there was a somewhat reliable guy that can help you crack your brainwallet.

[BurtW]

If you are worried about it do not post the transaction or address involved.

[itod]

Not sure why you felt it smart to post part of your brainwallet and now if you post your address there will be quite a few people trying to crack it although you won't see any of it.  Anyways if you search the forums there was a somewhat reliable guy that can help you crack your brainwallet.

Don't worry you posted two words here, you could have posted two more and be safe, there would be 4-8 unknown words in your 8-12 words passphrase. Even if it is only 4, and even if those 4 are from reduced english vocabulary of commonly used of words of 17,000 words, there's 17,000^4 = 83,521,000,000,000,000 combinations left. You would have to reduce it to only 3 unknown words for anyone to have a chance to crack it.

[itod]

Itod the system at http://bitprobing.com has just found the first birthday collisions in the address space. This is a huge issue in my humble opinion which allows implications on the randomness of the address space.

I've seen it, watching the other thread, I've posted the things we should double-check before we can point to ECDSA.

TL:DR; for those who are not watching the other thread: We a getting a shitload of doubles (collisions) in public keys generated from different machines. I'm running 3-4 Linux machines each generating more than 100.000 keys/sec [Edit: each finding about 250 keys/hour which meet EK criteria], and others a doing this also on the massive level. This is, to my knowledge the first massive address generation here where the results a submitted to the central database and checked. We should check now if the lack of entropy has anything to do with this.

[phlogistonq]

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.

If it is any help, you misspelled that pretty severely. Provided your GF did not also do that and your misspelling it here was not intentional to make it slightly more difficult for others to try and find your passphrase, make sure you spell it correctly if you are using it to narrow the search space:

2,4-dinitrophenylhydrazine

(with or without capital "D" for "Dinitro" as per her habits)

[FiatKiller]

Maybe Brady is one of the words?  ;-)

[toknormal]

Folks.

This whole argument is purely theoretical nonsense.

The practical reality is that there is not one single 3rd party generated key that Evil can crack with his software. The flaw in the hypothesis is the point that "it has to be a weak address".

The word "weak" here does not mean "weak" as in "not strong". It is a misnomer. By deliberately generating a "weak" address you are basically telling the software what the private key is (relatively to feeding the hacking software a random address).

Public private key encryption security is based on ** probabilities **. Please put the word "weak" out of your heads and instead consider the fact that you are drastically modifying the solution domain for the address generation algorithm. This changes the nature of the key because it impacts on the probability of solution.

The correct measure of whether a weakness has been found is being able to crack *any* address with a significant probability, not "pre selected" addresses that happen to suit your particular hack algorithm. As Evil said himself in response to my analogy with sandgrains, it's like sending 100,000 people to all the beaches looking for a blue ball. Well that works if you know they have to go to a beach, but the fact is that you don't. Evil's algorithm **assumes** this by arbitrarily picking the rendezvous points.

Watch Evil's video at 0:20. http://www.youtube.com/watch?v=TC43aOdsf4g&hd=1

He says:

my random address generator is... "just generating bitcoin addresses that are potentially weak". The word "weak" here is used as if those addresses have some kind of hackability about them. Whereas what in fact has happened is that Evil has generated addresses deliberately close to the rendezvous points, thereby "telling" the hacking software where the solution domain is. It's a bit like me telling my password cracker that my password contains the letters "t, e, w, y, s, a and r" and then saying - "hey look - it cracked it" ! Well obviously because I basically told the hacking software what the password was, it just had to re-arrange the letters.

i.e. What evil is doing is modifying the data to fit the required result. He is not finding weaknesses in bitcoin addresses, he is creating a set of locks and then creating a set of keys that fit those locks.

[Ritual]

Just wanted to address a couple of things here about how I seem to be coming accross in this thread....

Firstly, I'm not EK - this is not my experiment, nor do I claim to really understand what he is doing very well.

Secondly, I am not claiming that I have cracked any addresses, or know how to. I simply mentioned that I have been throwing various brute force methods at an address known to me. None have been effective, and I have had no results. This is exactly as I expected, but I'm not yet ready to quit.

This is the reason that I have been showing alot of interest in this thread (and the other thread). If a technique does become known, then I have a vested interest in it.

I pointed out a couple of times that based on the size of the numbers involved that I did not believe any simple brute force technique was going to produce a result, except by accident. However, I do not claim that this is what EK is actually trying. It may be utterly different, and in fact, seems to be a completely different angle.

In short, I don't pretend to understand EKs experiment, I am not trying to argue for or against it, and I am certainly not trying to say that I know better. I most emphatically do not know better

Anyhow, just wanted to clear that up, because I felt that the thread was getting mildly derailed in a couple of places, and I felt this is my fault.

Still watching developments with interest.

Rit.

[toknormal]

This is the reason that I have been showing alot of interest in this thread (and the other thread). If a technique does become known, then I have a vested interest in it.

You're interested in cryptography "weaknesses" ? R.O.T.F.W.L. !

Well, you've come to the right place. Don't bother with the worlds greatest computer science labs, PHD research or reading military grade specifications - those folks are clueless. Bitcointalk is the bleeding edge and any new developments will ONLY appear on here !! (Specially when it's supplied by a raving Youtube researcher who thinks he's cracked Elliptic Curve DSA cryptography and can't get hs point across for swearing at his telly   )

Seriously though, EK's software is PISH. It couldn't crack an egg without being given the answer to start with.

It's main design objective is not to create history but to create 2 bitcoins from unsuspecting wide eyed victims *.


(Small Print)
* although I'm having a bit of fun with EK and don't wish him any genuine malice, he is fair game since a) he's trying to claim that he's discovered a phenomenon called "weak address space" which actually only exists within the definitions of his own software and b) he's trying to scam people out of 2 bitcoins for a piece of PISH software and that's actually quite a lot of money these days

[Ritual]

This is the reason that I have been showing alot of interest in this thread (and the other thread). If a technique does become known, then I have a vested interest in it.

You're interested in cryptography "weaknesses" ? R.O.T.F.W.L. !

Well, you've come to the right place. Don't bother with the worlds greatest computer science labs, PHD research or reading military grade specifications. Bitcointalk is the bleeding edge and any new developments will ONLY appear on here !! (Specially when it's supplied by a raving Youtube researcher who thinks he's cracked Elliptic Curve DSA cryptography and can't get hs point across for swearing at his telly  )

Seriously though, EK's software is PISH. It couldn't crack an egg without being given the answer to start with.

It's main design objective is not to create history but to create 2 bitcoins from unsuspecting wide eyed victims *.


(Small Print)
* although I'm having a bit of fun with EK and don't wish him any genuine malice, he is fair game since a) he's trying to claim that he's discovered a phenomenon called "weak address space" which actually only exists within the definitions of his own software and b) he's trying to scam people out of 2 bitcoins for a piece of PISH software and that's actually quite a lot of money these days

When you've finished rolling on the floor with laughter (are you really? really?), I'll point out my earlier comments on this thread, to do with a lost wallet containing a reasonable number of bitcoins. There's my vested interest. To clarify - I'm not in the least interested in general cryptography, the mathematics surrounding it, or finding weaknesses in the elliptic curve. If I was, then I would certainly be checking out alot of different resources.

I visit these forums casually, and this thread caught my attention, so I am following it. That OK with you? Or is that "pish" as well?

Rit

[FiatKiller]

If you check-out this link: http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

apparently some hardware wallets have crappy "random" numbers that are not random at all(a very common problem
with code)

another reason I prefer to just stick with the official client

[Ritual]

Fiatkiller - yep, I posted that link on the other thread. I was wondering if EKs research was related, and it seems it probably is, although I lack the knowledge about the subject to see the link.

[toknormal]

I visit these forums casually, and this thread caught my attention, so I am following it. That OK with you? Or is that "pish" as well?

No. it is not "pish" as well and I am genuinely sorry you lost your coins. It's not a pleasant experience to be robbed.

At the same time, there is a huge amount of fearmongering drama surrounding the whole security issues of bitcoin and for that matter other cryptocurrencies. It leaves everyone paranoid, convinced that they have been victims of whatever security "hole" is currently under discussion. You've just been caught up in the crossfire of this and I didn't mean to patronise you, even in jest, so for that I apologise.

Regarding the security "fearmongering" though, it's a bit like everyone being paranoid about terrorism when they've actually got nil chance - practically - of ever being a terrosism victim, while at the same time not caring 2 hoots about thousands of road deaths that go on all around them every day.

We need to separate things out. First of all, Nils Schneider's post (http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html ) is dealing with a very different phenomenon than Evil Keneivil's.  The Schneider phenomenon is basically to do with wallets that don't comply fully with the address generation specification (by repeatedly using the same random number to generate addresses). So it's a problem of the wallet, not the mathematics. It's basically leaving the door unlocked and can be put down to "faulty wallet" design.

On the other hand, EK is claiming that there are certain "legitimate" addresses that are somehow "weak" or "more hackable" than others.

My point is that it is irrelevant because his definition of "weakness" is pre-biased to fit his test of hackability. A bit like if I write down a number between 1 and 10, then ask you do guess it. Then you guess the correct number, I can then retrospectively define my chosen number as having been "weak". The reality is that any other number would have been equally secure by probability.

That's why I say that the only test that matters regarding EK's software is to crack an arbitrary, specification compliant bitcoin public key, which he will not be able to do.

(By the way could you point me to your thread where you discuss your coin loss ?)

[escrow.ms]

Folks.

This whole argument is purely theoretical nonsense.

The practical reality is that there is not one single 3rd party generated key that Evil can crack with his software. The flaw in the hypothesis is the point that "it has to be a weak address".

The word "weak" here does not mean "weak" as in "not strong". It is a misnomer. By deliberately generating a "weak" address you are basically telling the software what the private key is (relatively to feeding the hacking software a random address).

Public private key encryption security is based on ** probabilities **. Please put the word "weak" out of your heads and instead consider the fact that you are drastically modifying the solution domain for the address generation algorithm. This changes the nature of the key because it impacts on the probability of solution.

The correct measure of whether a weakness has been found is being able to crack *any* address with a significant probability, not "pre selected" addresses that happen to suit your particular hack algorithm. As Evil said himself in response to my analogy with sandgrains, it's like sending 100,000 people to all the beaches looking for a blue ball. Well that works if you know they have to go to a beach, but the fact is that you don't. Evil's algorithm **assumes** this by arbitrarily picking the rendezvous points.

Watch Evil's video at 0:20. http://www.youtube.com/watch?v=TC43aOdsf4g&hd=1

He says:

my random address generator is... "just generating bitcoin addresses that are potentially weak". The word "weak" here is used as if those addresses have some kind of hackability about them. Whereas what in fact has happened is that Evil has generated addresses deliberately close to the rendezvous points, thereby "telling" the hacking software where the solution domain is. It's a bit like me telling my password cracker that my password contains the letters "t, e, w, y, s, a and r" and then saying - "hey look - it cracked it" ! Well obviously because I basically told the hacking software what the password was, it just had to re-arrange the letters.

i.e. What evil is doing is modifying the data to fit the required result. He is not finding weaknesses in bitcoin addresses, he is creating a set of locks and then creating a set of keys that fit those locks.

+1 Couldn't say better.

[Ritual]

I visit these forums casually, and this thread caught my attention, so I am following it. That OK with you? Or is that "pish" as well?

No. it is not "pish" as well and I am genuinely sorry you lost your coins. It's not a pleasant experience to be robbed.

At the same time, there is a huge amount of fearmongering drama surrounding the whole security issues of bitcoin and for that matter other cryptocurrencies. It leaves everyone paranoid, convinced that they have been victims of whatever security "hole" is currently under discussion. You've just been caught up in the crossfire of this and I didn't mean to patronise you, even in jest, so for that I apologise.

Regarding the security "fearmongering" though, it's a bit like everyone being paranoid about terrorism when they've actually got nil chance - practically - of ever being a terrosism victim, while at the same time not caring 2 hoots about thousands of road deaths that go on all around them every day.

We need to separate things out. First of all, Nils Schneider's post (http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html ) is dealing with a very different phenomenon than Evil Keneivil's.  The Schneider phenomenon is basically to do with wallets that don't comply fully with the address generation specification (by repeatedly using the same random number to generate addresses). So it's a problem of the wallet, not the mathematics. It's basically leaving the door unlocked and can be put down to "faulty wallet" design.

On the other hand, EK is claiming that there are certain "legitimate" addresses that are somehow "weak" or "more hackable" than others.

My point is that it is irrelevant because his definition of "weakness" is pre-biased to fit his test of hackability. A bit like if I write down a number between 1 and 10, then ask you do guess it. Then you guess the correct number, I can then retrospectively define my chosen number as having been "weak". The reality is that any other number would have been equally secure by probability.

That's why I say that the only test that matters regarding EK's software is to crack an arbitrary, specification compliant bitcoin public key, which he will not be able to do.

(By the way could you point me to your thread where you discuss your coin loss ?)

Fair enough, tok, thanks - apologies to you too if I went off a bit at you.

Wrt the coin loss, it wasn't a theft. The missus had mined some coins way back in the day on her laptop and the wallet was lost when the machine was binned. We know the address but have no means of accessing it. That's all it is. Probably will never see the light of day again, but when EK started this thread, it immediately caught my interest for that reason.

Anywho, thanks for clarifying that it's not related to the Nils Scneider post. Like I said, I'm not at all well-versed in any of this stuff. Just reading along

Rit.

[BurtW]

You said you had 300 BTC and then spent 1 BTC.  During the spend of the 1 BTC the public key for the address contaiing the 300 BTC would have been entered into the blockchain.  So if either:

The address the 1 BTC came from still has the 299 BTC or
The change was sent back to the same address

then you have the public key for the 299 BTC.  If you do then the brute force search for the private key can be sped up somewhat.  Note however that even with this speed up finding the private key with a brute force search is still impossible.

Just for educational purposes, remember the algorithm for finding a Bitcoin address I gave a while back is:

Use vanitygen to search for the Bitcoin address

1) Create a totally random private key over the entire private key space (random Key_private)
2) Calculate the public key from the private key (ECC Key_public = Key_private * G)
3) Calculate the Bitcoin address (Address = Encode(HASH(HASH(HASH(Key_public)))))
4) Compare the randomly generated Bitcoin address to the regular expression given to vanitygen when you started it
5) If this randomly generated Bitcoin address matches the pattern then print and quit (or continue, depending on flags)
6) Go to 1)

If you know the public key then you no longer need the three hashes and the encoding shown in step 3) that step can be totally eliminated.  The new algorithm would be:

Use a new program to search directly for the key pair

1) Create a totally random private key over the entire private key space (random Key_private)
2) Calculate the public key from the private key (ECC Key_public = Key_private * G)
3) Calculate the Bitcoin address (Address = Encode(HASH(HASH(HASH(Key_public)))))
4) Compare the randomly generated public key to the desired public key
5) If they match you are done!
6) Go to 1)

[prezbo]

If you know the public key then you no longer need the three hashes and the encoding shown in step 3) that step can be totally eliminated.  The new algorithm would be:

Use a new program to search directly for the key pair

1) Create a totally random private key over the entire private key space (random Key_private)
2) Calculate the public key from the private key (ECC Key_public = Key_private * G)
3) Calculate the Bitcoin address (Address = Encode(HASH(HASH(HASH(Key_public)))))
4) Compare the randomly generated public key to the desired public key
5) If they match you are done!
6) Go to 1)

Using this algorithm would require 2^255 tries on average. Using Shanks' algorithm would require only 2^128 tries (along with O(2^128) space), worst case, currently no better algorithm is known. However, without knowing the public key the dlp-breaking algorithms can't be used, so the only thing that can be done is randomly searching through the whole space, like your first algorithm.

[cr1776]

Can you pm the private key for this one:

1F1tAaz5x1HUXrCNLbtMDqcw6o5GNn4xqX


 

[Ritual]

Hah!

Me first me first

[Sukrim]

[serious] Is there a way to visualize distribution of public keys somehow? It might be worthwhile to analyze pubkeys on Bitcoin and other Altcoin block chains that all use the same curve and look for anomalies.

As far as I get this project, it is kinda close to vanitygen and will only find keys that are by _very_ bad luck close to some predefined checkpoints. The question is now if it might be possible to find checkpoints that are close (maybe a bit similar to: http://www.youtube.com/watch?v=IuSnY_O8DqQ) to a lot of generated keys, because there might be a bias in how they are generated - or worse, in the underlying mathematics that forces them closer together than necessary.

This will ONLY work if keys are actually NOT uniformly distributed, something which the OP claims has not really been looked into so far.

[Ritual]

[serious] Is there a way to visualize distribution of public keys somehow? It might be worthwhile to analyze pubkeys on Bitcoin and other Altcoin block chains that all use the same curve and look for anomalies.

As far as I get this project, it is kinda close to vanitygen and will only find keys that are by _very_ bad luck close to some predefined checkpoints. The question is now if it might be possible to find checkpoints that are close (maybe a bit similar to: http://www.youtube.com/watch?v=IuSnY_O8DqQ) to a lot of generated keys, because there might be a bias in how they are generated - or worse, in the underlying mathematics that forces them closer together than necessary.

This will ONLY work if keys are actually NOT uniformly distributed, something which the OP claims has not really been looked into so far.

That appears to be exactly what the OP is investigating in this thread: https://bitcointalk.org/index.php?topic=433522.0;topicseen

I'm not familiar enough with the mathematics of it to really understand the conclusions, but there was a lot of talk about collisions at one point. I don't know how that reflects on the veracity of the program offered in this thread though.

Rit

[Sukrim]

Well, not exactly, what he's doing there is (as far as I understand it) to set a few thousand checkpoints, then create keys and check if they are close to these points - if they are close enough, report them to get paid.

The idea is that you'd get about the same number of keys close to any of these points (as long as they are equally spaced I guess). It's kinda the opposite of what I suggested - not looking at existing keys and see if they show some non-uniform behaviour but creating keys and trying to see how close they are to some points.

[preshing]

For Evil-Knievel's demonstration to work, you need to use his pseudorandom number generator (PRNG): https://bitcointalk.org/index.php?topic=421842.msg4746108#msg4746108

His PRNG only generates from a set of 2560000000 possible values: https://bitcointalk.org/index.php?topic=437220.msg4809894#msg4809894

Meanwhile, there are 45231284858326638837332416019018714005014673546513634524455141852155 115792089237316195423570985008687907852837564279074904382605163141518161494337 possible Bitcoin keypairs.

The probably of his tool cracking a real public key, in the wild, is virtually zero. You are more likely to have a meteor land directly on your house, on the same day, four years in a row.

Evil-Knievel is insulting everyone's intelligence, wasting our time, and trying to con somebody out of 2 BTC.

[Sukrim]

Meanwhile, there are 45231284858326638837332416019018714005014673546513634524455141852155 possible Bitcoin keypairs.

Do you have mathematic proof for this or are you just guessing that really every point on that curve can be reached?

[prezbo]

Meanwhile, there are 45231284858326638837332416019018714005014673546513634524455141852155 possible Bitcoin keypairs.

Do you have mathematic proof for this or are you just guessing that really every point on that curve can be reached?

The group order is known and is equal to FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 in hex form, however I don't know if that's equal to 45231284858326638837332416019018714005014673546513634524455141852155.

edit: it's actually 115792089237316195423570985008687907852837564279074904382605163141518161494337, which is very close to 2^256.

[BurtW]

Meanwhile, there are 45231284858326638837332416019018714005014673546513634524455141852155 possible Bitcoin keypairs.

Where did you get this number?  It looks wrong to me.

[preshing]

Where did you get this number?  It looks wrong to me.

Sorry, you're right. Copy/paste error from a Python shell! prezbo gave the correct number.

The number I posted is the total number divided by 2560000000 -- in other words, 1 over this number gives you the probability of ever finding one of Evil-Knievel's so-called "weak" Bitcoin addresses in the wild. Practically speaking, these addresses are just never gonna happen.

[Evil-Knievel]

This message was too old and has been purged

[BurtW]

At least Evil-Knievel and prezbo got the same number...

Evil, can you sumarize what you have found with all of your "mining".   There was rumors of collisions then nothing.  What is happening there?

[Evil-Knievel]

This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[itod]

I do not want to disclose too much,
but imagine the whole search space as a two dimensional space.

Instead of testing every single point of the search space, you just have to define a pivot point (and its modular inverse).
Then you move from two points (one random point and one private key point) in gradients to one of the pivot points.
All you have to do is, wait until the lines cross! Then you can use simple linear algera to recover the private key.

Let's summarize what's public about this approach:

1. The explanation above.

2. We know that Baby-step / giant-step method is used, witch is described here:

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).

3. Evil-Knievel is gathering massive number of known private/public keypairs, with 32 least significant bits of the x coordinate are matching predefined rendezvous-points. For instance, let's say if one of his predefined 32 bits are 0xe8c4cd13, and attacked public key with matching bits is:

public 04a8177aa6808d93b480f4627faff680632f1a90a017562a6f765182f6e8c4cd13ec108158c14b43ffca30c0d400c91c652eab7f659470f1f29fd3ff46a888170e
secret ?

and, for instance, 10 gathered public keys with known private keys are (can have thousands, or millions of them):

public 04d75aaf9cfef2f8322a20b72333693253d241d8a46169b8e0e5521f85e8c4cd133f41d60134196b58e6420d6e89f1bd7077113b9a6d040c03ea3ffb418c430ad0
secret 378c918ea10ce56c0b9a4a63f92d62c65b8a24e03934bfb3a34589811ccf56ec

public 0452fc595fcfc00c83a7931bf1f2aa1e354957d7e2e49365c1caecdfede8c4cd133143ce2f82a69e1428dc5a586173a66ada8698103d2c76a2a5fb224bf46818ee
secret b0233294c24b09b448348afb589b484010d5273f200eec231cbd818e7aae0280

public 0448389e36eefae47d05f18cd899ebe40f731676c2e6213d7588171c79e8c4cd13178291bdbc3cf088b853a7fd25b89a6ec321659f189f96646ef783e1e0baebeb
secret 6983dbd427787f8622c0ab0a18fd19c459a9fd8e78ea6512187750a2cdb60673

public 045bffe58a37b10ccd6b0c959809780647a941815aa6c673e294499e28e8c4cd135eafe089336ef75141a2c88f21f4b7a2b11e2a92794206d1820f81ef5584b1df
secret db47a70e12f4eaae590e8da6c3568602e4320bec60ea3812366617f96c950945

public 04a97656f1865c8dc4f969bc3480360eec8123d1fc2cefe67bb85ca97ee8c4cd139bb1d221cd90ea60034748fc0b87e8155858d1dd5c3b4e3c0320f15aa8412fc5
secret d69d3f4fa3b3199b084d0c4bea9b9a4c061e0296b5d4d7ea88c94ec7013ffc86

public 049054c05d5b9d5541b548f6bb26728b8f08b7b712e64b36f2c3b3acc0e8c4cd13da5faf23df4ce55a60bc9b6b55795e121c51b3220737c57ec97f61694ced30ac
secret 5d822497642b85eb1b76351ada43ea812963c5b9c45421cffe645df0bda3c81c

public 043169d25764343f122b9bee026f58ad654c73bff74f6b54a60c55a20ae8c4cd1339cebff780ba3654d1e9637d9a44d1faa1aa68a0468547ccd480483d1d48f1da
secret ccbf26b0d68ae6ca372aed9edd38f17d4fe886abb506b866a7b427c7506b6beb

public 04a3bccc214b53fec3a2aa1ec8d7b0e61d0033856c4f1520a06baa3dffe8c4cd137315b361e64d41f56e40c5055cfde75108ceb0c9d3bffd2b4085e5e4d3aec49f
secret 8bd7bdf8db2cbb9989474f8017ce33ff5ea27a56a7ad38fce3b24b247ea96f63

public 04f1a597f7acf407b5dfc31af461bfc0cce2edaced7ad9c01d36a5db7be8c4cd13ff1d9d7f9b6f9bea7608d27f634d1140dac078538df188b2740275111e7678c4
secret fd440695cf90e0879136bd47461f597c1bc87a902cb4ededc8f0b53dd2eacffa

public 04196f0100280e4fb61a97c6f382e049941b3ac2064255bd9a57674752e8c4cd131546ff51bcd6fcb6b422b11f002d155111a35f64e5c68d3bc9733175cefe5e51
secret a384d6afe2844ac705f8f7735b92293d887ce3d60873bc51651a1be5f467e71b

Is there any cryptographer here to whom all this makes sense? How can Baby-step / giant-step be combined with these common 32 bits and the that graphical explanation?

[jaesyn]

Is there any cryptographer here to whom all this makes sense? How can Baby-step / giant-step be combined with these common 32 bits and the that graphical explanation?

I'm not a cryptographer, but trying to understand things like the behavior of finite fields and [now] ECDLP are a quirky hobby of mine.

The 32-bit number is just to know when your client has found a potential hit.  It's exactly like a share when mining, where it may not be the solution, but at least shows that you're working towards it. 

In his code (https://github.com/gh2k/rpoints/blob/master/main.cpp), the client starts with a random i*G point, and continuously adds numbers to it (so you're calculating i*G + j*G).  There's logic that attempts to skip around a bit, trying 100 sequential numbers for j, then adding a big random number to it to make a big jump, and then resuming with another 100 sequential numbers attempt. 

All the while, it keeps track of i+j, so that if you find a share, it submits the point's X,Y and the i+j, which is the private key for that point.  The server presumably has the full key's value on it, and it is able to tell if your share was an actual point of interest, or just noise.

What I haven't figured out is what exactly the points of interest are. My first guess was that they're public keys, but spot checking the list against some from the Top 100 list didn't provide any matches for the lower 32-bits of known public key X values.  I also tried some of the unclaimed Satoshi-mined blocks that were paid to a public key, but no hits in the blocks that I checked.  I don't have a full database of known public keys available to query, so my tests were inconclusive.

As far as this code on Github is concerned, EK's intersection diagram has no relevance. I think he provided it to show that given constraints, you can narrow the search scope considerably.  But, I also think his diagram is flawed because it assumes that proximity of EC points correlates with proximity of their scalar multipliers, which I have not been able to observe myself.

[OracionSeis]

Did you just create a program which cracks and steals every bitcoin  address?

[FiatKiller]

Did you just create a program which cracks and steals every bitcoin  address?

time will tell, but he has an ongoing research project at bitprobing.com but most seem to think it will
not work

[OracionSeis]

Did you just create a program which cracks and steals every bitcoin  address?

time will tell, but he has an ongoing research project at bitprobing.com but most seem to think it will
not work

He has a script that runs with your CPU. I never used it but my fellas did. I don't trust this guy somehow ^^ Maybe the people's addresses who did run his script is in danger? Is not it possible?

[itod]

I don't trust this guy somehow ^^ Maybe the people's addresses who did run his script is in danger? Is not it possible?

No, the script is clean, but we are in danger to waist a lot of time.

[OracionSeis]

I don't trust this guy somehow ^^ Maybe the people's addresses who did run his script is in danger? Is not it possible?

No, the script is clean, but we are in danger to waist a lot of time.

I am following this thread i wonder what will come up ^^

[Supercomputing]

I do not want to disclose too much,
but imagine the whole search space as a two dimensional space.

Instead of testing every single point of the search space, you just have to define a pivot point (and its modular inverse).
Then you move from two points (one random point and one private key point) in gradients to one of the pivot points.
All you have to do is, wait until the lines cross! Then you can use simple linear algera to recover the private key.

You are very entertaining and I admire your enthusiasm. I hope you do realized that the above diagram has absolutely nothing to do with solving the ECDLP. Your only hope is to come up with a new mathematical model to solve the lifting problem. But first, you need to understand why the existing methods do not work:

http://mathsci.ucd.ie/~gmg/ECC2007Talks/ECC4FacesOfLifts.pdf

I will be looking forward to see what mathematical models that you discover to help solve the lifting problem.

[Ritual]

@Supercomputing...

There are alot of us watching this, with many different goals. I do not claim to speak for all, but I'd say most don't have the mathematical whatsit to interpret this.

Clearly EK is working hard towards some sort of conclusion, but I for one would dearly love to know what it is

Could you take the time to write a dummies guide to what EK is doing? I for one would be happy to tip - although considering my pathetically low BTC atm, it might not be much

Thanks,

Rit.

[Supercomputing]

@Ritual

I sure will this evening after I get off from work.

[Ritual]

Much appreciated mate, and thanks for your time. Be sure to PM me your BTC address after you post - I'll send what I can your way.

Rit.

[Evil-Knievel]

This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[Ritual]

EK: That's OK I think by now most of us have realised that you're a mathematician rather than a teacher

No offense, but you're operating at a level higher than alot of us on this thread. We need a baby-level explanation, particularly if you're asking 2 BTC for this!

Having said that, you seem to be intelligent, organised and energetic about it, which gives me faith.

Please don't take this as a criticism of any kind - I kinda consider you my last hope for the missus' wallet!

Rit.

[Evil-Knievel]

This message was too old and has been purged

[FiatKiller]

What are the valid characters for a wallet password? Are specials allowed like "&%$!"?
I used to use alt-codes a lot to be a smarta**, like alt-255 which looks like a space, but isn't.
EDIT: found the list: (no zero, lowercase L, uppercase "oh", uppercase I)
“123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

EK, great explanation. I'm not clear on G though. Is it a fixed value?

[BurtW]

You do realize that the point n*G and the next point (n+1)*G are not physically close to each other on the curve, right?

Going through the sequence n*G, (n+1)*G, (n+2)*G, etc. results in a psuedorandom sequence of points on the curve.

What you decribed above is searching the psuedorandom point space hoping to run across one of your randomly placed marker points.

Or did I miss something?

Now to put some numbers on what you are attempting you said you want to generate about 10¹¹ points and test against those points.

To make the math easier let's give you 2⁴⁰ points and round up to 2²⁵⁶ possible points.

So for every one of your 2⁴⁰ known points there are 2^(256-40) = 2²¹⁶ unknown points.

Plus every time through your loop P_next = P_prev + G you have to check the generated result P_next against all 2⁴⁰ of your known points in order to see if you got lucky.  That will take some time no matter how clever you are.

[BurtW]

EK, great explanation. I'm not clear on G though. Is it a fixed value?

Yes G is a constant in the specification Bitcoins uses.  From the specification:

The base point G in compressed form is:

G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
 
and in uncompressed form is:

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

[Evil-Knievel]

This message was too old and has been purged

[BurtW]

So you are clever in your point selection in order to make your comparison a bit faster.  

The smaller you make the common bits the more collisions you will get that require a time consuming full comparison, the larger you make your common bits the more costly your initial comparison.  Somewhere between 2²⁵⁶ and 2⁸ bits lies an optimal number of bits given how much you want to spend on your FPGA or ASIC hardware.

I already granted you the comparison can be done is a clever way to speed it up a bit.

This still boils down to a brute force attack.  A clever brute force attack but a brute force attack never the less.

[Ritual]

BurtW - well, that's kinda the point, isn't it? People want to know if the basic, impossible brute force-attack (20 billion years or whatever) can be reduced to something reasonable (say, a few months).

Is this the case here?

Rit

[BurtW]

All you need are these two numbers:

The number of known points (2⁴⁰ in the example so far)

The amount of time needed (on average, given a clever implementation) to compare the result of the N = P + G calculation to all the known points.

I think we can bascially neglect the time it takes to calculate N = P + G but that does take some time to do.

Given these two numbers we can calculate the time needed to crack any key.  The notion of "weak keys" is silly and is just introducing "luck" into the equation for no reason.

[BurtW]

BTW Evil-Knievel,

Are you going to pay this promised bounty:

https://bitcointalk.org/index.php?topic=427712.msg4902522#msg4902522

[itod]

All you need is these two numbers:

The number of known points (2⁴⁰ in the example so far)

Excuse if this is silly question because my understanding of this is very limited - but 2⁴⁰ is not a very big number, it's around 1 Terra. Since, to my understanding, Y coordinate is not very important because it is binary determined by the X coord and the sign +1/-1, there's only 32 bytes * 1 Terra = 32TB of data to check, which is well within range of todays disk arrays. This shouldn't be hard to check against, should it?

So, is this the correct explanation of the attack method:
- You need 2⁴⁰ X coordinates which have the 32 least significant bits matched to the X coord of the attacked public key, and all 2⁴⁰ with known private keys. That's what we've been doing in the other thread, collected 8 million of them in a few days
- You go through the sequence n*G, (n+1)*G, (n+2)*G ... (n+k)*G and check only those 32 bits for a match
- If you find a match, you check the X coord against the 32TB of data with known private keys
- If you find a match there you calculate found secret - k to get unknown private key
- If not you add 1 to k and repeat the process

Is this the correct attack vector? It looks too simple to me, I've must have misunderstood something.

[BurtW]

I think you got it.  That is my understanding also.

Assuming for now 2⁴⁰ known keypairs all we need is an estimate for the average comparison time given that some of them will be a short quick comparison as you suggested and others will be very long, having to do full comparisons.

Then we can easily calculate how long, on average, to crack a key pair.

[BurtW]

Storage needed for the public keys:

257 bits, 256 for the X coordinate + one bit for the sign of the Y coordinate BUT the bottom 32 bits are the same for all keys so we really just need a total of 257 - 32 = 225 bits each

Storage needed for the private keys:  256 bits each

So realistically we still need 64 bytes to store each known key pair

2⁴⁰ * 64 bytes is exactly 64 binary terabytes of data that needs to be stored - no big deal by today's standards.

But, have you ever tried to read 64 Tibytes of information from a disk drive?  Be sure to use SSDs for this as HDDs will be too slow for the full comparison operation

[itod]

So realistically we still need 64 bytes to store each known key pair

I disagree on that, you don't exactly need private keys to be handy, you need them only in the very rare occasion the attack was successful for the final printout of the found private key. They can be on the tape or something. Only the 1/2 of the data, 32TB with X coordinates have to be on the fast RAID.

[onzoom]

So realistically we still need 64 bytes to store each known key pair

I disagree on that, you don't exactly need private keys to be handy, you need them only in the very rare occasion the attack was successful for the final printout of the found private key. They can be on the tape or something. Only the 1/2 of the data, 32TB with X coordinates have to be on the fast RAID.
[/quote

32 TB on tape ? ]

[itod]

So realistically we still need 64 bytes to store each known key pair

I disagree on that, you don't exactly need private keys to be handy, you need them only in the very rare occasion the attack was successful for the final printout of the found private key. They can be on the tape or something. Only the 1/2 of the data, 32TB with X coordinates have to be on the fast RAID.

32 TB on tape ?

DAT 160 = 80 GB uncompressed (160 GB compressed)
DAT 320 = 160 GB uncompressed (marketed as 320 GB assuming 2:1 compression)

Cheep and ultra-reliable, you need less than 100 of them for this database. Whoever tries this in practice won't have a problem to buy 100 tapes.


Edit:
Just found out there are 6TB models now:
http://www8.hp.com/us/en/products/tape-drives-enclosures/index.html#!view=column&page=1
Had no idea that technology advanced so far in a few years.

[BurtW]

I was only giving total storage requirements.

Yes, you put the public keys in about 32 Tb of SSD and the private keys on 32 Tb of HDD.  32 Tb of HDD is not that much in the grand scheme of cracking ECC so forget the tape.

[jaesyn]

I think you got it.  That is my understanding also.

Assuming for now 2⁴⁰ known keypairs all we need is an estimate for the average comparison time given that some of them will be a short quick comparison as you suggested and others will be very long, having to do full comparisons.

Then we can easily calculate how long, on average, to crack a key pair.

Is the assumption here is that you can find 2⁴⁰ keypairs all with the same lower 32-bits to use in a rainbow table? I think that task alone is equivalent to O(N).

[Supercomputing]

@Ritual

Evil-Knievel is attempting to implement a variation of Pollard's kangaroo algorithm. The best known implementation that I know of can be accessed from the link below:
http://eprint.iacr.org/2010/617.pdf


We need to use what is known as "distinguished points" to implement a parallel version of the algorithm, please see the above link. Evil-Knievel is focused on small intervals, which is what the above algorithm does.The only limitation with this approach is that you need to know beforehand, the search interval that contains the solution. I am afraid setting random traps (rendezvous points) is not going to work for a 256-bit prime field.

If the goal is to recover an ECDSA key as used in Bitcoin, then the best approach will be to study the Hidden Number Problem. I have successfully used it in a lab environment to recover some keys that would otherwise be almost impossible to recover through pure brute force methods. I will explain more on this subject later.
http://www.iacr.org/archive/crypto2009/56770333/56770333.pdf

[kjj]

This is a scam.  This has been known to be a scam since post #125, nearly a week ago now.  Why are you still talking about it?

There is no statistical project.  There are no rendezvous points.  There is no algorithm.  He isn't washing Pollard's jockstrap, much less trying to implement any actual math.  His script generates keys from a tiny, tiny keyspace, and then his "cracker" searches that same tiny keyspace.

Also, Ritual is almost certainly the same person as Evil-Knievel.  Re-read the whole thread and watch out for posts from both accounts that appear to be in the other character's voice.

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.

[itod]

This is a scam.  This has been known to be a scam since post #125, nearly a week ago now.  Why are you still talking about it?

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.

[Supercomputing]

Also add that gmaxwell is willing to lose 50 BTCs because of this thread - it got my attention. Though very unlikely, but still possible that he may lose 50 BTCs.

[Ritual]

Also, Ritual is almost certainly the same person as Evil-Knievel.  Re-read the whole thread and watch out for posts from both accounts that appear to be in the other character's voice.

This is the second time some cretin has suggested this. Why not read my post history? And read EKs as well. Totally different boards, topics, interests. As I've stated before, I'm from Ireland. I'm not sure where EK is from, but it sure isn't here. Also, if you read the thread, you'll see that I have not always agreed with EK in it. And lastly, why in the world of sport would I ask for an explanation about this if I was him? If this is a scam, it's not in his interests to have any explanations which might show that?

So in short, kjj, if you don't like the thread, or if your tin-foil hat has slipped off, or nobody has come down to your basement with hot pockets for too long or whatever, then piss off.

Clear?

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

@kjj: There's always that one person ready to stir things up  In this thread, it's you!
Also, my project is no "scam" - the weak key generator (which was advertised as such) is a proof of concept to actually see that the program is able to crack private keys. People wan't to try, experiment, see results - that's why thy need keys that will show the "proof-of-concept" pretty quickly. But why am I telling you anyway, you seem to have no idea about anything that I was writing in this post.

I personally think YOU are the scam here

You are the scam, you are using FUD to push your product which doesn't clearly state what it is actually doing.

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

Noooo, now we must interrupt our scientific talk to argue with the trouble makers.

@gweedo: The program does exactly what it described here! If you still disagree then you certainly have not understood anything.
I would suggest going to university and attending some math classes.

I have a math degree and I understand your math. It is preying on FUD.

[Evil-Knievel]

This message was too old and has been purged

[Mitchell]

My housekeeper (and I think the trash collector too) have a math degree as well. Doesn't mean they understand anything though  .
Okay serously guys, how can I make this topic moderated to keep out those stress-makers?

You can't. You will have to lock this one, create a new topic and enable "Self-moderated" under "Additional Options...".

[gweedo]

My housekeeper (and I think the trash collector too) have a math degree as well. Doesn't mean they understand anything though  .

LMAO you have a house keeper, your mom doesn't count as a house keeper js. I have a math degree from an Ivy league school and I have been working on cryptographics for over 10yrs. I understand the bitcoin protocol and the code. Your code wasn't hard to follow and figure out. But you are using FUD to create a panic that you have found a flaw, and that is untrue. The flaw you found was with random generators not addresses.

[gweedo]

My housekeeper (and I think the trash collector too) have a math degree as well. Doesn't mean they understand anything though  .
Okay serously guys, how can I make this topic moderated to keep out those stress-makers?

You can't. You will have to lock this one, create a new topic and enable "Self-moderated" under "Additional Options...".

Don't tell him how to do it. If he is insulting the intelligence of other people let him use his mind and figure it out.

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

If he is insulting the intelligence of other people

.... which I do because you are insulting me as a scammer.

But you are a scammer...

To defraud; swindle.

You are defrauding people by saying that their is a flaw in bitcoin address which is untrue, so you are a scammer.

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

You are defrauding people by saying that their is a flaw in bitcoin address which is untrue, so you are a scammer.

Please quote the posting where I said that. I think you are doing FUD here.
I recall that I wrote that certain addresses are a lot easier to crack if others.

Clearly I am making the FUD and plus you edited the OP heavy.

Price:
I am asking you 2 BTC for the whole package. It has taken me lots of time to research everything and implement it cleanly. And who knows, this tool is giving you good chances to get one of these lost 10 MILLION US$ accounts 

[Sukrim]

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.

[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.

[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?

[Renaldas123]

So this guys wants $1000+ from every single person who wants to buy this? Well thats me out.

[BurtW]

So this guys wants $1000+ from every single person who wants to buy this? Well thats me out.

If anyone buys it then I have a bridge I want to sell them.

[foggyb]

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?

Yes he can, but it the complexity. Such difficult. Much hard. Rendezvous points & shit.

Btw rendezvous really just means a spot. So addresses in between the green spots are being cracked so hard. Such crack.  

Send him cash.

[virbbbq]

Proof of Concept Video:
- Working on real bitcoin network with real addresses and real coins.
- All transactions can be verified on blockchain.info
- Randomly generated Bitcoin Adresses are used (however they are all special-weak). This again shows you that there is an infinite number of weak bitcoin addresses.
- Sorry for all the cursing: It has been a long day 
http://www.youtube.com/watch?v=TC43aOdsf4g&hd=1

What is up to sale:
After 18 days of excessive work, I have today finished my hobby project:
It's a ECDSA private key cracker for the secp256k1 curve which is for example used in bitcoin.

What does this tool make better than others:
Existing Bitcoin Private Key crackers go through the whole palette of algorithms that are used in bitcoin - to mention some we have ECDSA, sha256, ripemd160 and base58 encoding.
Actually, we do not need to do most of them at all. My tool bases on elliptic curve cryptography only.
A known bitcoin public key has to be converted to hexadecimal and embedded into the software - then using elliptic curve mathematic only it can quite efficiently search through the search space.

Exact functioning:
- Keyspace is reduced in a precomputation phase by calculating several thousand rendezvous points (they are hardcoded in the software but may be changed at any time).
- This precomputation phase is inspired by the "Baby-Step-Giant-Step" algorithm.
- The target public key is then (using ecdsa arithmetic) reduced subseqentially until hitting one of the rendezvous point. Given G is the generator point, and  R=x*G the rendezvous point (which private key is known),
  we then may get the original privatekey by just taking PrivKey=x+iterations where iterations equals to the number of decrements were needed to hit R.

Open CL Extras:
- Kernel currently works with a global work size of 81920 (value can be adjusted for your graphics card). Meaning in every iteration step 81920 reductions can be made to the public key you try to crack.
- Given the rendezvous point table of size 768 (may be extended anytime) we can do 81920*768 = 62914560 key comparisons per cycle.
- Rendezvous-Table checks are based on just 32bit of x-coordinate to keep it fast! If a collision is found a local verification is performed on the CPU to see if its just a partial collision or a full match. This relaxes the GPU
- Midpoint Feature - So even when your computer shuts down or gets restarted - the work you have already done is remembered
- my HD7970 is at the moment capable of doing 150 MEGAKEYS per second - just a question of time until a rendezvous is being hit
- Speedup is possible with a better Modular-Multiplication. Currently implemented as Double and Add, you could use Montgomery or FFT to get tremendous speedups

Is it for beginners?
No! You should be exactly know what your doing. Even though the code is straight forward, you need to know what is being done exactly and where you need to manipulate parameters if you want to change something.

Documentation and Source Code?
Included (as a QT Project buildable on linux and windows)

Price:
I am asking you 2 BTC for the whole package. It has taken me lots of time to research everything and implement it cleanly. And who knows, this tool is giving you good chances to get one of these lost 10 MILLION US$ accounts  

Disclaimer:
This project is for research purpose only, or to recover lost private keys. It may not be used for any illegal activities and I cannot be held responsible for anything you do with it.

http://imageshack.com/a/img854/1821/qlf9.png

http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

http://key.btc123.com/

[mtwelve]

Not bashing, but besides recovering lost private keys, what legal activities can you do with this?

[Evil-Knievel]

This message was too old and has been purged

[mtwelve]

What kind of science?

[virbbbq]

What kind of science?

technology (science) development, it not affect any one because there are lot of keys, each and every address you open all most contain 0 balance, some............ so don't worry feel free

bitcoin one kind of technology (science) like the same

by virbbbq

[virbbbq]

Not bashing, but besides recovering lost private keys, what legal activities can you do with this?

Science 

Evil-Knievel are you sale the product or not, I send the message your not replay, what ever your work is good

by virbbbq