Topic: This message was too old and has been purged - page 3. (Read 50756 times)
This message was too old and has been purged
@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
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.
This message was too old and has been purged
Quote
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?
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.
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.
@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
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
I think you got it. That is my understanding also.
Assuming for now 240 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 240 keypairs all with the same lower 32-bits to use in a rainbow table? I think that task alone is equivalent to O(N).Assuming for now 240 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.
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.
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.
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.
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
? ]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.
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
240 * 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
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
240 * 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
I think you got it. That is my understanding also.
Assuming for now 240 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.
Assuming for now 240 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.
All you need is these two numbers:
The number of known points (240 in the example so far)
The number of known points (240 in the example so far)
Excuse if this is silly question because my understanding of this is very limited - but 240 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 240 X coordinates which have the 32 least significant bits matched to the X coord of the attacked public key, and all 240 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.
BTW Evil-Knievel,
Are you going to pay this promised bounty:
https://bitcointalksearch.org/topic/m.4902522
Are you going to pay this promised bounty:
https://bitcointalksearch.org/topic/m.4902522
All you need are these two numbers:
The number of known points (240 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.
The number of known points (240 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 - 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
Is this the case here?
Rit
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 2256 and 28 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.
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 2256 and 28 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.
Jump to: