|
Title: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 07, 2020, 08:45:07 PM Hi, everybody!
You know that CPU XEON 2680v2 can brute-force public key (secp256k1 curve) at speed 55TH/s per thread :o Totaly double CPU can do 2.2PH/s !!!! 8) ->>40 threads with 55TH/s each. http://i.piccy.info/i9/c5490ee8cd06bbe127be69b5ce06ad0b/1586290519/8791/1371731/Untitled_1_240.jpg (http://piccy.info/view3/13745440/2438ce1ff1fc4096295567fc051637aa/)http://i.piccy.info/a3/2020-04-07-20-15/i9-13745440/240x136-r/i.gif (http://i.piccy.info/a3c/2020-04-07-20-15/i9-13745440/240x136-r) I mean that if you have public key and you whant to get private key of this public key, than you can do brute-forcing at this speed on CPU. The indicated speed requires 32GB of RAM memory. Each doubling of memory leads to a 2-fold increase in speed. At 128GB you can get a speed of 10PH/s and so on.. For example: You whant get private key from public key 0xa1eb046a8c225e0e173965a0ff7a4a899f745a3e2b3d21f926f4d59c955b4324bbd92c53c53c1 7404810a4c44ee82b5cdcebc1e62a56c4714c6c193ef10344a8 If you limit the memory to 4GB, you will get speed around 400TH/s at CPU XEON 2680v2 If starting private key will be 0x0000000000000000000000000000000000000000000000000000000000000001 Private key for this public key is 0x0000000000000000000000000000000000000000000000000013fea895f7b601 Totaly you need brute-force 5628024581502464 private keys. At speed 400TH/s you can do this in 14s -> 5628024581502464 / 400000000000000 Of course the number 2 ** 256 is incredibly huge and even such a speed is dust ;D Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: gmaxwell on April 07, 2020, 11:29:52 PM Hi, everybody! That CPU cannot do *any* operation at that speed, not even a single 32-bit multiply. Your post is an outright untruth.You know that CPU XEON 2680v2 can brute-force public key (secp256k1 curve) at speed 55TH/s per thread :o Totaly double CPU can do 2.2PH/s !!!! 8) ->>40 threads with 55TH/s each. My guess is that you intend to trick people into running malware or just rip them off selling them cracking software that lies about its performance. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 08, 2020, 06:09:52 AM Hi, everybody! That CPU cannot do *any* operation at that speed, not even a single 32-bit multiply. Your post is an outright untruth.You know that CPU XEON 2680v2 can brute-force public key (secp256k1 curve) at speed 55TH/s per thread :o Totaly double CPU can do 2.2PH/s !!!! 8) ->>40 threads with 55TH/s each. My guess is that you intend to trick people into running malware or just rip them off selling them cracking software that lies about its performance. I'm not going to post programs, source codes or algorithms. It's just a fact. But any way i can prove speed in easy way ;) You can make private in range from 0x0000000000000000000000000000000000000000000000000000000000000001 to 0x00000000000000000000000000000000000000000000000031f5c4ed27680000 than make public key(64bytes) from this private key and show me this public key. Total points in this range 3600000000000000000, so i will limit speed to 1Ph/s and i my CPU should brute-force this range in 1hour. If i find private key that you make i will post him. But if I fail, you must show your private key so that I can verify it with the public key you specify. If i win, you should remove malware warning from topic, if i fail you can delete this topic. ok? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 08, 2020, 08:02:33 AM Hello,
Even if you solve ECDLP for a 64bits key, that does not prove the speed you announce. You can use variant of the DP method on a reduced subset of private keys and get a complexity of O(2^32). I wrote a GPU program that looks for partial collision on addresses (not the same process but the method is similar) It founds 64bits collision in few minutes on a GTX 1050 Ti. So post the code and we will see. https://github.com/JeanLucPons/BTCCollider Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 08, 2020, 09:16:22 AM Hello, Even if you solve ECDLP for a 64bits key, that does not prove the speed you announce. https://github.com/JeanLucPons/BTCCollider There is no reference to 64 bits.. The desired private key can be located anywhere in the allowed range from 0x01 to 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 The only question is the time spent finding this key, and the speed from this will not change. Only processor power affects the speed, the number of threads and the amount of allocated memory for searching. Ok, programm used many optimizations and i can open 2 of them: 1 optimization>> For ex. we start brutforce from key 0x01 We make public key from this privatkey -> 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 After this we add in loop only G-point to this public key. And 1 to privatekey. So that in the cycle our private key and public match. Each addition of a G-point gives the same effect as if adding 1 to private key and again getting a public key from it. With this optimization we get rid of unnecessary conversions from the private key to the public key 2 optimization>> if you now bottleneck in addplt function is inverse function that take many cpu time, so.. Instead of adding a G-point to the public key each time and spending a lot of time on it. We can create an array of points that starts at point is G and each subsequent point is equal to the previous +G For ex. we create array of 1000points. so we can get diiferents for each point and our public key and in the and of array we will get total diiferents of this points make 1time inverse for total diiferents value and after this we can calculate inverse for each point in array in simple way. After this optimization you make 1 inverse for 1000 points enstead of 1000inverse. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Jean_Luc on April 08, 2020, 09:34:00 AM You can make private in range from 0x0000000000000000000000000000000000000000000000000000000000000001 to 0x00000000000000000000000000000000000000000000000031f5c4ed27680000 than make public key(64bytes) from this private key and show me this public key. You specify this range to prove your speed which is a 62bits range (not 64bits you're right). If you want to prove your speed, post your code. Solving ECDLP on sepck1 for a reduced priv key range does not prove the speed you announce. The speed of a method depend first on the complexity of the used algorithm not only on the speed of the hardware. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 08, 2020, 09:54:05 AM You can make private in range from 0x0000000000000000000000000000000000000000000000000000000000000001 to 0x00000000000000000000000000000000000000000000000031f5c4ed27680000 than make public key(64bytes) from this private key and show me this public key. You specify this range to prove your speed which is a 62bits range (not 64bits you're right). If you want to prove your speed, post your code. Solving ECDLP on sepck1 for a reduced priv key range does not prove the speed you announce. The speed of a method depend first on the complexity of the used algorithm not only on the speed of the hardware. This range was chosen only so that I could show that I can bruteforce this range in 1 hour this range can be for ex. from 0x0000000000000000000000000000000000000000000000000013fea895f7b601 to 0x0000000000000000000000000000000000000000000000000027fd512bef6c02 any way total point will be 3600000000000000000 if i start with 0x0000000000000000000000000000000000000000000000000013fea895f7b601 if i start with 0x0000000000000000000000000000000000000000000000000000000000000001 i will need 2hour Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 08, 2020, 10:14:26 AM You will just prove that you are able to solve ECDLP for a subset of priv key of a size near 2^62 in one hour.
But we have no proof of the algorithm used which can be in O(2^31). Why you don't want to post your code ? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Tamarindei on April 08, 2020, 10:31:55 AM Hi. It sounds like generic ECDLP "Baby step giant step" algorithm to me.
It's useful when you know the interval of the targeted privatekey only. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: gmaxwell on April 08, 2020, 11:01:57 AM But any way i can prove speed in easy way ;) You can make private in range from 0x0000000000000000000000000000000000000000000000000000000000000001 to 0x00000000000000000000000000000000000000000000000031f5c4ed27680000 than make public key(64bytes) from this private key and show me this public key. Total points in this range 3600000000000000000, so i will limit speed to 1Ph/s and i my CPU should brute-force this range in 1hour. That isn't impressive at all and wouldn't prove your claim. Because you fix a range, you could simply have a table of 2^31 entries (1G, 2G, 3G) based on X-only, you step by twice the size of your table, checking only the X to get a positive and negative offset, and find the match in one hour at a terribly slow rate of 1.2 million keys a second. At that speed you are missing even the most basic optimizations. Go away scammer. Or come back with a private key who's pubkey x coordinate begins with >=68 zero bits within two days... (other than the one with pubkey 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63). Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 08, 2020, 11:20:59 AM But any way i can prove speed in easy way ;) You can make private in range from 0x0000000000000000000000000000000000000000000000000000000000000001 to 0x00000000000000000000000000000000000000000000000031f5c4ed27680000 than make public key(64bytes) from this private key and show me this public key. Total points in this range 3600000000000000000, so i will limit speed to 1Ph/s and i my CPU should brute-force this range in 1hour. That isn't impressive at all and wouldn't prove your claim. Because you fix a range, you could simply have a table of 2^31 entries (1G, 2G, 3G) based on X-only, you step by twice the size of your table, checking only the X to get a positive and negative offset, and find the match in one hour at a terribly slow rate of 1.2 million keys a second. At that speed you are missing even the most basic optimizations. Go away scammer. Or come back with a private key who's x coordinate begins with >=68 zero bits within two days... (other than the one with pubkey 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63). And if you do not understand the topic, you do not need to call everyone scammers. I did not post any files.. Give me public key what ever you whant and give me start private key with whom I can find public key for 1 day with speed 1Ph/s this will drop options with tables 2 ^ 31 If i win you clear all the charges and apologize publicly for calling me a scammer. Have you agreed? If i failed you post private key from your public key, we compare him and and check if it falls outside the range of 1 day.. I can spend 1 day CPU resources to prove to you that you are wrong! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 08, 2020, 11:22:04 AM And it is clear test with other CPU.
I will use a slower processor I7 3770 (4core,8 threads) and the memory limit will be 8GB I generate random private key in range from 0x0000000000000000000000000000000000000000000000000000000000000001 to 0x00000000000000000000000000000000000000000000000031f5c4ed27680000 my private key turned out to 0x0000000000000000000000000000000000000000000000002022f3ed27580c00 the public key of this private key is 0x284e5d2ed67c10aa8be9ff03aa56969d3acfa3b5f4cf145617ce883f16c97bb4ad9c7b2da401a fb1bc49f96bf57ca58f9dd8a6de4bda706559ee23147de8c047 We give this public key to the program. Note! It does not know about the private key. Data preparation took about 10 minutes. Each thread give 35TH/s, total 250TH/s Brutforcing was completed in: 8411seconds Total points that program brutforced: 2315681358314736639 Average speed: 275313GH/s http://i.piccy.info/i9/41437376d8ef7413c28f3c4ac64b7872/1586344089/4839/1371731/Untitled_1_240.jpg (http://piccy.info/view3/13746137/a54758bbce6485b949a84771b93da927/)http://i.piccy.info/a3/2020-04-08-11-08/i9-13746137/240x127-r/i.gif (http://i.piccy.info/a3c/2020-04-08-11-08/i9-13746137/240x127-r) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: gmaxwell on April 08, 2020, 11:38:56 AM I think yo do not understand what are you talking... Clearly you're looking to fool people who don't, sadly for you I'm not one of them. Though the fact that you don't recognize that I do is odd...Quote Give me public key what ever you whant and give me start private key with whom I can find public key for 1 day with speed 1Ph/s This is exactly the same as what you offered above-- you just offset the starting position of the interior step.In what you describe, I choose x and y so that their difference is 60-ish bits. Then I give you y and xG. You would compute yG - xG and begin adding steps of the 2 x table_size * G to it and looking up the result in the table. Once you find a hit, you add the table position, the loop offset, and the y value to yield x. What I described to you -- finding a private key whos pubkey begins with a long fixed string is an actual test of performance. To make it a better test, instead of zeros (which you could have precomputed over weeks or months) it would be better to use the hash of a recent block hash to bound the starting time. :) But zeros would be good enough for the discussion here. I'm sure if you got anywhere near a 68 bit chosen prefix in two days you'd be setting a world record in "purebasic" computation for sure. :) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 08, 2020, 11:53:42 AM @Etar
Your tests does not prove anything. If you want to prove your key rate, follow the test given by gmaxwell. If you manage to get 275313 GKey/s , you should be able to find a public key (and its corresponding private key) with a X starting with ~60 zero bits in 1 hour, (~64 bits in 1 day) And to be sure that you didn't make any precomputation we should choice a random starting key. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 08, 2020, 12:01:29 PM I think yo do not understand what are you talking... Clearly you're looking to fool people who don't, sadly for you I'm not one of them. Though the fact that you don't recognize that I do is odd...Quote Give me public key what ever you whant and give me start private key with whom I can find public key for 1 day with speed 1Ph/s This is exactly the same as what you offered above-- you just offset the starting position of the interior step.In what you describe, I choose x and y so that their difference is 60-ish bits. Then I give you y and xG. You would compute yG - xG and begin adding steps of the 2 x table_size * G to it and looking up the result in the table. Once you find a hit, you add the table position, the loop offset, and the y value to yield x. What I described to you -- finding a private key whos pubkey begins with a long fixed string is an actual test of performance. To make it a better test, instead of zeros (which you could have precomputed over weeks or months) it would be better to use the hash of a recent block hash to bound the starting time. :) But zeros would be good enough for the discussion here. I'm sure if you got anywhere near a 68 bit chosen prefix in two days you'd be setting a world record in "purebasic" computation for sure. :) I talk about brutforce (you know what is this?) and you are trying to impose a search for an incomprehensible pubkey that I can look for years. look at fist post, i talk about brutforce speed, i am not talking that i can found ANY public key for 1hour or 1day and what does 60 bit have to do with it? 1 day with speed 1ph it is 10^15*86400 points total = 86400000000000000000 2^60 it is 1152921504606846976 you see difference between numbers? 86400000000000000000 79 times bigger than 2^60 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 08, 2020, 12:13:40 PM 1Ph/s speed is roughly 2^66 per 24 hours.
There is a bitcoin address with 0.64BTC and 64bit private key. You need 2^63 operations to bruteforce it. If you have real speed 2^66 per 24 hours, so you can perform 2^63 operations juts for 24/(2^3)=3 hours. So, welcome to prove your speed: just take 0.64BTC from this address: https://www.blockchain.com/btc/address/16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN The private key for this address is in the range: 0x8000000000000000 - 0xffffffffffffffff (64bit key, i.e. with 192 leading zeros) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: gmaxwell on April 08, 2020, 12:18:55 PM 1Ph/s speed is roughly 2^66 per 24 hours. Man, why you gotta tell me this at 5am when I'm too tired to go actually attempt collect it. I'm going to guess the pubkey isn't available, or otherwise this would have already been solved. :PThere is a bitcoin address with 0.64BTC and 64bit private key. You need 2^63 operations to bruteforce it. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 08, 2020, 12:20:21 PM 1Ph/s speed is roughly 2^66 per 24 hours. Give me public key of this address (64bytes)There is a bitcoin address with 0.64BTC and 64bit private key. You need 2^63 operations to bruteforce it. If you have real speed 2^66 per 24 hours, so you can perform 2^63 operations juts for 24/(2^3)=3 hours. So, welcome to prove your speed: just take 0.64BTC from this address: https://www.blockchain.com/btc/address/16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN The private key for this address is in the range: 0x8000000000000000 - 0xffffffffffffffff (64bit key, i.e. with 192 leading zeros) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: gmaxwell on April 08, 2020, 12:22:43 PM Seems you realy do not understand)) No I am talking about finding the private key for ANY pubkey which matches a particular criteria: one where the first 60 bits are zero, so that it will take on average 2^60 operations to find it.I talk about brutforce (you know what is this?) and you are trying to impose a search for an incomprehensible pubkey that I can look for years. Quote look at fist post, i talk about brutforce speed, i am not talking that i can found ANY public key for 1hour or 1day Your first post said a speed of 2.2 PH/s.Quote and what does 60 bit have to do with it? And I suggested two days.1 day with speed 1ph it is 10^15*86400 points total = 86400000000000000000 2^60 it is 1152921504606846976 you see difference between numbers? 86400000000000000000 79 times bigger than 2^60 You should be able to find a key matching the property I described in about 2 days at 2.2PH/s. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 08, 2020, 12:24:47 PM 1Ph/s speed is roughly 2^66 per 24 hours. There is a bitcoin address with 0.64BTC and 64bit private key. You need 2^63 operations to bruteforce it. If you have real speed 2^66 per 24 hours, so you can perform 2^63 operations juts for 24/(2^3)=3 hours. So, welcome to prove your speed: just take 0.64BTC from this address: https://www.blockchain.com/btc/address/16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN The private key for this address is in the range: 0x8000000000000000 - 0xffffffffffffffff (64bit key, i.e. with 192 leading zeros) Funny challenge :) but the public key is not exposed there ? If no, you need to hash... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 08, 2020, 12:33:05 PM Seems you realy do not understand)) No I am talking about finding the private key for ANY pubkey which matches a particular criteria: one where the first 60 bits are zero, so that it will take on average 2^60 operations to find it.I talk about brutforce (you know what is this?) and you are trying to impose a search for an incomprehensible pubkey that I can look for years. I told that programm can brutforce keys to find public key with speed 2.2Ph on xeon. if you know public key than YES program can found private key from this public key after some time... But this time depends only how far the starting private key from the desired.. Do you see the difference in your task and what I write? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: MrFreeDragon on April 08, 2020, 12:38:40 PM -snip- I told that programm can brutforce keys to find public key with speed 2.2Ph on xeon. -snip- Can you please explain pelease what kind of operation you mean by 1 hash? 2.2Ph/s means 2,200,000,000,000,000 h/s So what is your "one operation"? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: gmaxwell on April 08, 2020, 12:41:28 PM I am not talking that programm can found public key with criteria like 192 leading zeros or something. If your program could actually do what you claimed-- evaluate 2.2 petakeys per second, then it could find keys whos pubkeys have 60-bit leading zeros quite quickly. Quote Read carefully! I told that programm can brutforce keys to find public key with speed 2.2Ph on xeon. if you know public key than YES program can found private key from this public key after some time... But this time depends only how far the starting private key from the desired.. Do you see the difference in your task and what I write? But instead you demand a starting point _and_ a public key (rather than, e.g. a key hash). Which means you cannot actually do what you claim, because you need to compute a point difference in order to use a precomputed table. One we consider that, instead what you claim is not impressive-- it is outright slow. Assuming that the pubkey isn't available for that challenge payment-- go solve it. It's worth several thousand dollars, so if you could actually operate at the speed you could you wouldn't be wasting my time, you'd be collecting the bounty. Or go start at key 1, within 2^64 operations you will find a pubkey that begins with 60 zero bits with very high likelihood. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 08, 2020, 12:42:25 PM -snip- I told that programm can brutforce keys to find public key with speed 2.2Ph on xeon. -snip- Can you please explain pelease what kind of operation you mean by 1 hash? 2.2Ph/s means 2,200,000,000,000,000 h/s So what is your "one operation"? And you will understand what "one operation" mean. Thanks! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: MrFreeDragon on April 08, 2020, 12:50:51 PM -snip- I told that programm can brutforce keys to find public key with speed 2.2Ph on xeon. -snip- Can you please explain pelease what kind of operation you mean by 1 hash? 2.2Ph/s means 2,200,000,000,000,000 h/s So what is your "one operation"? And you will understand what "one operation" mean. Thanks! Not clear from that post, sorry. Is your "one operation" the EC calculation of the public key for one private key or EC points addition? It looks like you just overestimate your calculation power adding the operations that are not really performed. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: NotATether on April 08, 2020, 02:08:06 PM There is no computer processor in existence that has a rate of Petahertz per second, because of Moore's law. All modern processors today have a max turbo speed of around 5GHz per thread and even that can only be sustained for a short amount of time and then it reverts to it's base speed of around 2.5 GHz per thread. Since you're assuming this can be done on personal computers, even if you have say 8 cores then that's only a combined base speed of a little more than 16GHz per second.
And even then these numbers are just for CPU instructions, the process of finding a SHA256(SHA256(x)) hash has severely lower rates than what I posted. Look at this table here https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison (https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison). Look at the Mhash/s column, every processor listed only has megahash speed. You know that CPU XEON 2680v2 can brute-force public key (secp256k1 curve) at speed 55TH/s per thread No, it doesn't. According to the link I just posed, double Xeon E5-2690 processors (in the same family as 2680, since 2680 isn't on the list) has a listed hashrate of 66 Mhash/s. So it's safe to assume a single Xeon E5-2680 can do 33 Mhash/s for the entire processor. This screenshot looks like you hacked up a visual basic program and coded it to print sketchy results. 55 TH/s sounds very dodgy, like you're using an Antminer S17 with 56 TH/s as the mining source instead. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 08, 2020, 02:13:18 PM Not clear from that post, sorry. Is your "one operation" the EC calculation of the public key for one private key or EC points addition? It looks like you just overestimate your calculation power adding the operations that are not really performed. I will give a final explanation of how this works. *************************************** Imagine a house with 5 rooms. Each room has 200 people. All people have different non-repeating names. Your task is to find David. You can go around every room, go up to every person and ask his name David or not. In this way, you will find David by tomorrow's best. Or you can do otherwise. Shout the whole name David to the whole room; if David responds, then he is found; if not, then go to another room. For example, you spent 1 second on the first, second, third and fourth rooms and there was no David anywhere. You go to the fifth room, shout out a name and get a response from David. in 1 second A total of 5 seconds of time was spent. 1 second per room. there were a total of 1000 people. V=1000/5=200person/s *************************************** Resul the same in both way - We found Devid. in first way in a day, in second way in 5s. If you do not agree, then write what speed for the second example according to your You can tell anything, that this speed is impossible and so on. I say that if we need found private key of known public key than my algoritm will fast than algorithm where hashrate of 66 Mhash/s )) in millions times. And that is final explanation ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 08, 2020, 02:37:24 PM There is no computer processor in existence that has a rate of Petahertz per second, because of Moore's law. All modern processors today have a max turbo speed of around 5GHz per thread and even that can only be sustained for a short amount of time and then it reverts to it's base speed of around 2.5 GHz per thread. Since you're assuming this can be done on personal computers, even if you have say 8 cores then that's only a combined base speed of a little more than 16GHz per second. And even then these numbers are just for CPU instructions, the process of finding a SHA256(SHA256(x)) hash has severely lower rates than what I posted. Look at this table here https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison (https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison). Look at the Mhash/s column, every processor listed only has megahash speed. You know that CPU XEON 2680v2 can brute-force public key (secp256k1 curve) at speed 55TH/s per thread No, it doesn't. According to the link I just posed, double Xeon E5-2690 processors (in the same family as 2680, since 2680 isn't on the list) has a listed hashrate of 66 Mhash/s. So it's safe to assume a single Xeon E5-2680 can do 33 Mhash/s for the entire processor. This screenshot looks like you hacked up a visual basic program and coded it to print sketchy results. 55 TH/s sounds very dodgy, like you're using an Antminer S17 with 56 TH/s as the mining source instead. Move away from gigahertz, look more abstractly... if you need, for example, to get 2^2 and then 2^3 .. you can of course go by adding or multiplying or even raising to a power)) and spend a lot of processor time on it. Or you can just shift the bit to the left. In both case you get the same result. but spend a miserable resource on it. And ofcourse i will say that second way will much more efficiency and speed is faster! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 08, 2020, 02:41:52 PM Etar, you are funny person.
Yes, you just overestimate the rate. It is known that due to pollard kanagaroo method it is possible to perform less bruteforce operations. And roughly it is square root from the total length. You just count the operations which are not actually performed. You use the method which is good due to birthday paradox. However, due to this methond you just need less operations. So, your actual speed is not 2.2Ph/s but the square root from this amount, i.e. approx. 47 Mh/s in total. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 08, 2020, 02:47:05 PM Etar, you are funny person. You can write your vision of speed in example#2 in https://bitcointalk.org/index.php?topic=5238719.msg54181362#msg54181362Yes, you just overestimate the rate. It is known that due to pollard kanagaroo method it is possible to perform less bruteforce operations. And roughly it is square root from the total length. You just count the operations which are not actually performed. You use the method which is good due to birthday paradox. However, due to this methond you just need less operations. So, your actual speed is not 2.2Ph/s but the square root from this amount, i.e. approx. 47 Mh/s in total. If we start from private key 0x01 with my algorithm and you with your algorithm where hashrate is 66Mg/s than i found same public key in million times faster than you. Do you agree with me? V=S/t If i passed the range S in 2315681358314736639 privatkey values and T=8411seconds i can easy get V = 2315681358314736639/8411 = 275315819559474 keys/s Or you have a different vision of this formula, different from the rest of the world Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 08, 2020, 02:47:44 PM Etar, you are funny person. Yes, you just overestimate the rate. It is known that due to pollard kanagaroo method it is possible to perform less bruteforce operations. And roughly it is square root from the total length. You just count the operations which are not actually performed. You use the method which is good due to birthday paradox. However, due to this methond you just need less operations. So, your actual speed is not 2.2Ph/s but the square root from this amount, i.e. approx. 47 Mh/s in total. This is what we try to explain since the beginning of this post. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: NotATether on April 08, 2020, 06:31:33 PM It is known that due to pollard kanagaroo method it is possible to perform less bruteforce operations. And roughly it is square root from the total length. This is actually an interesting concept so I looked it up. It basically computes two sets of numbers, one set for each side of the xy = m equation. Later elements in the set are derived from earlier elements, and sometimes this will not find a collision between two elements in the same position of the two sets. I wonder if the regions/domains of x that will be missed is known, or at least if there have been studies about this. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Tamarindei on April 08, 2020, 09:21:35 PM I also think it is unfair to say its malware or scam with warning so early.
Maybe Etar can say what his intentions are for creating this topic here? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: gmaxwell on April 09, 2020, 01:50:06 AM I also think it is unfair to say its malware or scam with warning so early. Maybe Etar can say what his intentions are for creating this topic here? Perhaps, but quite a few times people have shown up with "cracking" tools that turned out to be a scam. It's a pretty standard MO. In particular several of the more recent ones have setup making these seemingly pointless "advertising posts" then nailing people who PM them, e.g. by sending them the software privately where other people can't call it out for being malware. I guess they feel better about robbing people because they imagine they're robbing other thieves. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: odolvlobo on April 09, 2020, 03:05:19 AM [Give me public key what ever you whant and give me start private key with whom I can find public key for 1 day with speed 1Ph/s this will drop options with tables 2 ^ 31 1015 checks/s for 1 day is 8.64x1019 (4AF0A763BB1C0000016) checks. If you can actually do that, you should be able to check all private keys between 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000 and 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff in less than 6 hours. But, I'll give you a whole day to find the private keys for these 16 public keys. The private keys are randomly distributed in the above range. If you can do that, I'll be impressed. I don't think that you can find 4. Code: 0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 09, 2020, 06:16:19 AM I also think it is unfair to say its malware or scam with warning so early. Maybe Etar can say what his intentions are for creating this topic here? Perhaps, but quite a few times people have shown up with "cracking" tools that turned out to be a scam. It's a pretty standard MO. In particular several of the more recent ones have setup making these seemingly pointless "advertising posts" then nailing people who PM them, e.g. by sending them the software privately where other people can't call it out for being malware. I guess they feel better about robbing people because they imagine they're robbing other thieves. I had heard about him before, but did not delve into the gist of it. This algorithm is very similar to the one I use. I just thought that I was the first one to think of this, but it turns out that something similar was invented before)) You can delete the topic if you want. All the same, I will not publish the source code. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Etar on April 09, 2020, 06:18:10 AM [Give me public key what ever you whant and give me start private key with whom I can find public key for 1 day with speed 1Ph/s this will drop options with tables 2 ^ 31 1015 checks/s for 1 day is 8.64x1019 (4AF0A763BB1C0000016) checks. If you can actually do that, you should be able to check all private keys between 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000 and 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff in less than 6 hours. But, I'll give you a whole day to find the private keys for these 16 public keys. The private keys are randomly distributed in the above range. If you can do that, I'll be impressed. I don't think that you can find 4. Code: 0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8 As i understand all of this public keys is in range of private keys: from 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000 to 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff ok i will try to do this. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 09, 2020, 06:54:30 AM Yesterday, I read in detail about the giant baby steps algorithm. I had heard about him before, but did not delve into the gist of it. This algorithm is very similar to the one I use. So you have use this algorithm which is in O(sqrt(n)) for both memory and time where n is the size of the range. Starting with an offset does not prevent to use this algorithm. That means that the key rate (or group operation) you announced is wrong. Do not waste time in solving the above problem, solving it will just prove that you have correctly implemented this known algorithm. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 09, 2020, 06:59:09 AM Yesterday, I read in detail about the giant baby steps algorithm. I had heard about him before, but did not delve into the gist of it. This algorithm is very similar to the one I use. So you have use this algorithm which is in O(sqrt(n)) for both memory and time where n is the size of the range. Starting with an offset does not prevent to use this algorithm. That means that the key rate (or group operation) you announced is wrong. Do not waste time in solving the above problem, solving it will just prove that you have correctly implemented this known algorithm. I did not write that CPU can do 2.2 P operations of addiding points/s i say 2.2Ph/s mean 2.2Pkeys/s. This mean that CPU can brutforce range of 2.2*10^15 points in 1/s if range is 1000 points and you check this range in 1seconds than you can say that speed is 1000points/s no matter how you do that whith comparsation or addiding or in other way! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 09, 2020, 07:42:23 AM This is well know since the beginning of elliptic curve usage in crypto.
But we count the number of group operation really performed (not the size of the range divided by time). For instance in my BTCollider which use the DP method (also in O(sqrt(n))), I get 27.9 Mips (GeForce GTX 1050 Ti) for 80bit collision search. That means that I really compute 27.9M group operation and hash per second. It solves 80bit collision in 14h30 (in average). Note that in that case, it have to compute an EC mult for each group operation. https://github.com/JeanLucPons/BTCCollider Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 09, 2020, 09:12:15 AM 0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED8 87AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
1 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4 in 6285s 04A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD3E48440249D6B C78BC928AA52B1921E9690EBA823CBC7F3AF54B3707E6A73F34 2 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eb5abc43bebad3207 in 5720s 0404A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3BD05357CAF834 0CB041B1D46C5BB6B88CD9859A083B0804EF63D498B29D31DD1 3 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e5698aaab6cac52b3 in 2923s 040B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D1D18283AF4955 6CF33E1EA71A16B2D0E31EE7179D88BE7F6AA0A7C5498E5D97F 4 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e59c839258c2ad7a0 in 2884s 04837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493E46726DE04352 832790FD1C99D9DDC2EE8A96E50CAD4DCC3AF1BFB82D51F2494 5 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e765fb411e63b92b9 in 3820s 040ECDB6359D41D2FD37628C718DDA9BE30E65801A88A00C3C5BDF36E7EE6ADBBAD71A2A535FCB5 4D56913E7F37D8103BA33ED6441D019D0922AC363FCC792C29A 6 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e7d0e6081c7e0e865 in 3851s 0422DD52FCFA3A4384F0AFF199D019E481D335923D8C00BADAD42FFFC80AF8FCF038F139D652842 243FC841E7C5B3E477D901F88C5AB0B88EE13D80080E413F2ED 7 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ec737344ca673ce28 in 6434s 04DB4F1B249406B8BD662F78CBA46F5E90E20FE27FC69D0FBAA2F06E6E50E536695DF83B68FD0F3 96BB9BFCF6D4FE312F32A43CF3FA1FE0F81DF70C877593B64E0 8 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e38160da9ebeaecd7 in 1777s 043BD0330D7381917F8860F1949ACBCCFDC7863422EEE2B6DB7EDD551850196687528B6D2BC0AA7 A5855D168B26C6BAF9DDCD04B585D42C7B9913F60421716D37A 9 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e79d808cab1decf8d in 3884s Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: bigvito19 on April 09, 2020, 10:41:06 AM Where is the program or is this person trying to sell it as usual?
Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 09, 2020, 11:37:39 AM Where is the program or is this person trying to sell it as usual? Nobody sells anything here. Here is a discussion about how speed is measured. :) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: NotATether on April 09, 2020, 12:45:49 PM All the same, I will not publish the source code. Will you at least tell us why you don't want to publish the source code? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 09, 2020, 04:02:30 PM Etar, I write it one more time: you just OVERestimate your actual power.
You use "square root method", but count the whole range. It is not correct. Your example with 5 rooms x 200 people each and only one David among them: if you ask the whole room you perform ONLY one operation, but not 200 operations. Yes, it is better not to ask every person in every room, but ask once per room. This is efficient way. But it does not mean that you actually ask everybody. This will be overestimation. Most famous Square root methods: - Baby-step Gian-step - Pollard's Rho algorithm - Pollard's kangaroo algorithm Have a look this link as well: https://www.embeddedrelated.com/showarticle/1093.php Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 09, 2020, 05:39:43 PM Etar, I write it one more time: you just OVERestimate your actual power. You use "square root method", but count the whole range. It is not correct. Your example with 5 rooms x 200 people each and only one David among them: if you ask the whole room you perform ONLY one operation, but not 200 operations. Yes, it is better not to ask every person in every room, but ask once per room. This is efficient way. But it does not mean that you actually ask everybody. This will be overestimation. Most famous Square root methods: - Baby-step Gian-step - Pollard's Rho algorithm - Pollard's kangaroo algorithm Have a look this link as well: https://www.embeddedrelated.com/showarticle/1093.php You guys are so smart here, I even feel awkward. Then answer me 3 simple questions: #1 Question . Let's imagine and take for the fact that I have a RAM for storing 2 ^ 255 public keys And I make a table of baby steps by this size. Those it’s enough for me to take 2 Giant steps to break the entire range 2 ^ 256 in 1second. What speed will I have in that case? If you answer 2hashes/s. I will call the orderlies and will laugh for a long time. ;D #2 Question . For example, I have a very small table of baby's steps. Let it be 10 values. And I take 100 giant steps per second. What speed will be in this case? #3 Question . There are 2 factories that produce cars. The first factory does everything .. from wheels to the trunk and engine. And the second one does only large-assembly cars. The first plant will produce 100 cars per month. The second is also 100 cars. Those due to the fact that the second factory does not make a car from atoms, but of large parts, we can’t say that it makes 100 cars a month? :D Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: odolvlobo on April 09, 2020, 11:00:51 PM Congratulations on finding those private keys. They are correct. I am impressed. However, ...
You guys are so smart here, I even feel awkward. Then answer me 3 simple questions: #1 Question . Let's imagine and take for the fact that I have a RAM for storing 2 ^ 255 public keys And I make a table of baby steps by this size. Those it’s enough for me to take 2 Giant steps to break the entire range 2 ^ 256 in 1second. What speed will I have in that case? If you answer 2hashes/s. I will call the orderlies and will laugh for a long time. ;D #2 Question . For example, I have a very small table of baby's steps. Let it be 10 values. And I take 100 giant steps per second. What speed will be in this case? #3 Question . There are 2 factories that produce cars. The first factory does everything .. from wheels to the trunk and engine. And the second one does only large-assembly cars. The first plant will produce 100 cars per month. The second is also 100 cars. Those due to the fact that the second factory does not make a car from atoms, but of large parts, we can’t say that it makes 100 cars a month? :D You are not doing 2.2 PH/s. You aren't even doing hashes. The problem here is with your terminology:
#1 The "speed" 1 one key per second. #2 The "speed" is 100 steps per second. #3 Yes Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 09, 2020, 11:23:29 PM @etar
The BSGS algotrithm has a complexity in time and in memory. You can have time in O(sqrt(n)) and memory in O(sqrt(n)). n is the search space size. But you can also have time in O(1) and memory in O(n) If you have n memory available and memory already filled, it makes no sense to give a key rate. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 10, 2020, 04:47:25 AM Congratulations on finding those private keys. They are correct. I am impressed. However, ... Totaly i found And i spent about 30-40 minutes on each new public key to prepare the data But probably I will find 1 more key maximum. I have question about the formula O (sqrt (n)), it means that the time spent is equal to (sqrt (n)) for the range from 1 to n so if for example n=64 than to break this range i need time sqrt (n) = 8s ? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 10, 2020, 06:56:41 AM O(sqrt(n)) in time means that you need to perform sqrt(n) group operations (addition here) in the worst case.
If you have n=2^64 (like the above problem), you need to perform sqrt(n) = 2^32 EC additions but to achieve this you also need to store in memory 2^32 "baby steps" and perform 2^32 additions to fill the memory. In total, 2*sqrt(n) group operation (worst case). If you have less memory, of course, you will have to perform more operations, O(sqrt(n)) is the best time/memory tradeoff for this method. I don't know your code but to solve the 16 keys given by odolvlobo, yon can fill only once the memory and then process the 16 keys. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 10, 2020, 07:46:49 AM Let's decide what kind of algorithm I came up with, and which of the known ones it looks like.
Step by step how I do bruteforce: For example, we need to find the private key from known the public key: 0x68d552d7a9d3fcd453fa080f7e9f3ff5536a287b058c9fe72ebbf3dbc1ec4caab7d1c060acd4a 0b57b6edd70d283fbba557c62e87b31eaff6f615732fe4f675d We need to make hashtable, for example, we will have a table of 10 values of X-coordinates First we need make variable ADDPUBG that equil table size but represent this value like point on curve. ADDPUBG = tablesize = 10 = 0xa0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7893aba425419b c27a3b6c7e693a24c696f794c2ed877a1593cbee53b037368d7 After that we can fill hashtable: Add Gpoint to public key 0x68d552d7a9d3fcd453fa080f7e9f3ff5536a287b058c9fe72ebbf3dbc1ec4caab7d1c060acd4a 0b57b6edd70d283fbba557c62e87b31eaff6f615732fe4f675d and we get new point 0xcb1e2f09dbff52b977bcf9b5820823dfc89f1621efb1e0f009246542edb2459479eea84c69408 3e4cd06d7c13ca35ca2494d374871f6bd31327c1651d941efe4 Cut only X-coordinat 0xcb1e2f09dbff52b977bcf9b5820823dfc89f1621efb1e0f009246542edb24594 and set to the table Then Add 2G to 0x68d552d7a9d3fcd453fa080f7e9f3ff5536a287b058c9fe72ebbf3dbc1ec4caab7d1c060acd4a 0b57b6edd70d283fbba557c62e87b31eaff6f615732fe4f675d Cut only X-coordinat and set to the table until it is full. After that we sort hashtable to use binarysearch in the shortest time! With the table finished now we take the starting private key with which we start brute force. let it be 0x01 Now we need to get the public key from the start key. It is 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 Now in the cycle we checks our x-coordinat of start public key with the keys in the table using binary search. if we not found key we can add to start public key table size ADDPUBG (ofcourse via addplt method) 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 + 0xa0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7893aba425419b c27a3b6c7e693a24c696f794c2ed877a1593cbee53b037368d7 = 0x774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cbd984a032eb6b5 e190243dd56d7b7b365372db1e2dff9d6a8301d74c9c953c61b And so on, until the starting public key becomes equal to one of the hash tables. I don’t know what famous algorithm suits mine. Because I use a sorted table. Can you tell me? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 10, 2020, 08:00:17 AM Read this, page 7:
https://www.math.u-bordeaux.fr/~aenge/ecc2015/documents/galbraith.pdf Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 10, 2020, 08:20:46 AM Read this, page 7: So I came up with an existing one BSGS algorithm? ???https://www.math.u-bordeaux.fr/~aenge/ecc2015/documents/galbraith.pdf Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 10, 2020, 08:25:24 AM Yes
Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 10, 2020, 12:10:03 PM @odolvlobo i have a question.
You gave me public keys whose private keys are in the range 8000000000000000:ffffffffffffffff So those you previously brute force this range. if you have all keys in this range why you do not take transaction #63 from bitcoin pazle? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Fortuna33 on April 10, 2020, 12:20:05 PM @Etar , anyway good work!
Could you send pm to me? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 10, 2020, 12:51:50 PM Dear moderators, how do you think, could you remove malware warning from this post?
Question by question, actually we understood that the TC just created "the wheel" but did not know that this wheel was already known to the community. Instead of walking by foot Etar used the wheel and could go faster and longer, so declared this high speed. However received the negative feedback for this: gmaxwell Reference - Physically impossible claims about key cracking performance, probably trying to trick people into running malware. It is grandiosely if Etar came to this method (already known) by himself. Just wow! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Jean_Luc on April 10, 2020, 01:47:19 PM That isn't impressive at all and wouldn't prove your claim. Because you fix a range, you could simply have a table of 2^31 entries (1G, 2G, 3G) based on X-only, you step by twice the size of your table, checking only the X to get a positive and negative offset, and find the match in one hour at a terribly slow rate of 1.2 million keys a second. gmaxwell posted this method in the beginning of this topic, (an optimized version using negation), without a starting offset in that case but easy to add one. It took 3 pages to etar to understand. BSGS is quite a very simple and intuitive algorithm and there are plenty of possible optimizations to speed it up. gmaxwell is right, according to the "attracting" title of this topic and to the refusal of Etar to post his code, to add this warning. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: MrFreeDragon on April 10, 2020, 02:00:09 PM That isn't impressive at all and wouldn't prove your claim. Because you fix a range, you could simply have a table of 2^31 entries (1G, 2G, 3G) based on X-only, you step by twice the size of your table, checking only the X to get a positive and negative offset, and find the match in one hour at a terribly slow rate of 1.2 million keys a second. gmaxwell posted this method in the beginning oh this topics, (an optimized version using negation), without a starting offset in that case but easy to add one. It took 3 pages to etar to understand. BSGS is quite a very simple and intuitive algorithm and there are plenty of possible optimizations to speed up it. gmaxwell is right, according to the "attracting" title of this post and to the refus of Etar to post his code, to add this warning. Ok, noted. Agree. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 11, 2020, 05:37:18 PM Yes No. This is not BSGS algorithm.because: - baby-step giant-step is a "meet in the middle" algorithm! - BSGS algoritm has a limit on N due to memory lack! So BSGS can`t be launched with n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 My algorithm can be run with any amount of memory, the amount of memory will only affect the size of the subgroup. Compare https://bitcointalk.org/index.php?topic=5238719.msg54191839#msg54191839 BSGS algorithm subtracts mP from Q unlike mine which adds mG to start point. ->>> I create a table of public keys that are in front of a known public key. And after that I am incrementing by the size of the tables to the starting public key. Those the algorithm rather catches up than meets in the middle. So we can say that there is something from the BSGS algorithm, but this is not it. (I think). Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: odolvlobo on April 11, 2020, 06:22:23 PM @odolvlobo i have a question. You gave me public keys whose private keys are in the range 8000000000000000:ffffffffffffffff So those you previously brute force this range. if you have all keys in this range why you do not take transaction #63 from bitcoin pazle? I didn't brute-force the private keys. I generated them randomly and gave you their public keys. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 11, 2020, 07:53:52 PM So BSGS can`t be launched with n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 You can use this algorithm with the memory you want. Of course, if you want to use it on the full range, you won't be able to get running time in O(sqrt(n)) because you won't have enough memory. BSGS is a simple time memory/tradeoff, if you have enough memory you can get the best complexity in O(sqrt(n)), if you don't have memory (you don't use a lookup table) then the algorithm get a complexity in O(n). For the basic BSGS, If x is the size of the lookup table, and n the search space size, the total number of needed group operations is x (to fill the memory) + n/x (to solve the key) and the minimum of this function is obtained when x = sqrt(n), then the total number of group operation is 2*sqrt(n). We neglect here the time spent by the search (or the insertion) in the lookup table which can be done very efficiently by combining hash table and binary search. Ex: for n=2^64, we see that the minimum is well at x=2^32 (~4.295E9) http://zelda38.free.fr/curve_bsgs.jpg Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 11, 2020, 08:52:54 PM ok, thanks for answers.
but BSGS moves back from a known public key. This algorithm, as I understand it, subtracts mP from Q. That is why it is called "meet in the middle" It is not the same.. if public key for example >2^254 than you will wait many-many time while mP will be in the table and you can’t influence it in any way. While my algorithm has a start public key. Of course, if it starts with private key at 0x01, then the residence time will be the same for both algorithms. But if I start with key 0x1000000000000000000000000000000000000000000000000000000000000000, for example, then I will quickly find the key Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 11, 2020, 09:14:32 PM "meet in the middle" is a generic term to design attack algorithm that makes time/memory tradeoff to reduce time complexity of basic brute force attack.
In that case, the best tradeoff brings O(sqrt(n)). The algorithm that I show you on the power point, is a basic one, lots of variants exist... since more than 50 years... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: gmaxwell on April 12, 2020, 07:28:55 AM One thing to keep in mind for these TMTO approaches is that the pre-computation size can be amortized across multiple problems. So, for example, on a 2TB ram (plus a few TB of disk) host you can build up a 2^38 ish-sized table and reuse it against multiple problems... and solve each additional 64-bit search with 2^25 operations each.
The optimizations to get low memory don't work quite as well for amortizing multiple problems, or at least are much harder to implement. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 15, 2020, 03:01:47 PM Just curious, I made a small program that does this. I used a 24bits hash table (no binary search) and a table of 2^30 point (~9GB), the hash table is not well optimized for insertion in order to save memory and to avoid fragmentation (not constant speed). It is obviously possible to make further optimizations to speed it up.
I ran this program on an old Xeon X5647 2.93GHz with 12GB of RAM. It takes 9min to fill the 2^30 baby step table and ~32min to browse the full 2^64 range so it can solve the 16 keys of odolvlobo in ~9h00 (max). I published the code: https://github.com/JeanLucPons/BSGS Here the key #10 and #11 of the odolvlobo set (expressed in compressed format) Code: BSGS v1.0 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: odolvlobo on April 15, 2020, 05:39:07 PM I have to say that this thread has been enlightening. I honestly had no idea how powerful these algorithms can be.
BurtW posted last summer about how he and his daughter were looking at the Pollard Kangaroo algorithm. The results they reported did not seem impressive, so I lost interest. https://bitcointalk.org/index.php?topic=5173445.0 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 15, 2020, 07:53:59 PM Much harder with the GPU.
Implementing binary search on a GPU is nearly impossible in the right way. For example my GPU can do 1.2G operation per second. I mean add point operation. But as soon as the BSGS algorithm is added and a search is made in the sorted table, the main hashrate drops sharply. Look at results.. GPU #0 1240MKey/s x1 GPU #0 499MKey/s x1048576 GPU #0 360MKey/s x4194304 GPU #0 113MKey/s x16777216 GPU #0 70MKey/s x33554422 Even 70 million giant steps multiplied by 32 million babys’s looks quite sad against the background of the CPU. When calculating on the CPU, the table size almost does not affect the main hashrate. Because the number of samples from the sorting table is Log2 of the size of the table. But with the GPU this does not work out. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 15, 2020, 08:56:59 PM How did you implement the binary search on the GPU ? Iterative or recursive ?
I already implemented binary searches on GPU without having such an issue. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MikeJ_NpC on April 16, 2020, 05:26:23 AM I think its rather interesting to say the least despite the non hashing attribute.
Furthermore, i have a nightmare with all the data applicable to solve, more than the basic set people tout, PK ranges Key-space, Nonce, etc etc in dec. So you want a puzzle you can do one that i need to resolve. I am at a impasse with my own attempts and have had a company with QC ability attempt which they came up short for a few reasons internally not in reference to my wallet. Hence, if Etar or Greg would like to take a look or anyone who can resolve this (requires experience) i would be god dam thankful... been years and im frankly fed up and heard it all. Send a PM.. If there is a need to solve a problem and validate this model, mine would be it... not going to have more data sets than this.... BUT this approach is one i haven't seen ... despite the rumblings from the elders ... i do concur more needs to be disclosed but not to the point where he ruins his time put into the model. anyways cheers... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 16, 2020, 05:43:08 AM How did you implement the binary search on the GPU ? Iterative or recursive ? I already implemented binary searches on GPU without having such an issue. I tried in different ways. Here is an example where the counter variable is used, which is responsible for the number of iterations over the sorted table. This is so that there are no branches. It should be the log2 of the size of the table. if table have size 2^20 than counter=20 With this approach, the key search is always the same in time and equal to the sampling time multiplied by counter Code: .func (.reg .b32 eq, .reg .b32 pos) FOUNDINSORT(.reg .b32 a0, .reg .b32 a1, .reg .b32 a2, .reg .b32 a3, .reg .b32 a4, .reg .b32 a5, .reg .b32 a6, .reg .b32 a7, .reg .b64 _arr, .reg .b32 beginrange, .reg .b32 endrange) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 16, 2020, 06:11:04 AM There is an horrible call in your loop. Try to remove it and implement the comparison locally.
Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 16, 2020, 06:20:37 AM There is an horrible call in your loop. Try to remove it and implement the comparison locally. I think that PTX compiler unroll function, but any way i unroll EQUILLESSMOREHALF function to main loop. Result the same as early.. I think that this issues in cuda driver api (specifically in their library cuda.lib). Because random access to memory is happening here. And I have already encountered this before (when the miner wrote for the ethereum. On Windows 7, the miner gave 24Mx with 1063 cards, and on Windows 10 only 4mx ???). On windows 7, random access to memory worked fine on windows 10 no. I then could not defeat it then. Code: .func (.reg .b32 eq, .reg .b32 pos) FOUNDINSORT(.reg .b32 a0, .reg .b32 a1, .reg .b32 a2, .reg .b32 a3, .reg .b32 a4, .reg .b32 a5, .reg .b32 a6, .reg .b32 a7, .reg .b64 _arr, .reg .b32 beginrange, .reg .b32 endrange) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 16, 2020, 06:37:09 AM I passed my hashtable to a hash size of 25bit (always 2^30 points inside), i win 20% of speed for a 500MB overhead.
Edit: Concerning GPU the access to global memory is slower than local memory but I'm surprised that it is so slow in your case. For other programs, i implemented binary search on global memory (millions of items) with very good performances. In that case a hashtable is better than binary search. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 16, 2020, 06:43:10 AM I passed my hashtable to a hash size of 25bit (always 2^30 points inside), i win 20% of speed for a 500MB overhead. Edit: Concerning GPU the access to global memory is slower than local memory but I'm surprised that it is so slow in your case. For other programs, i implemented binary search on global memory (millions of items) with very good performances. In that case a hashtable is better than binary search. It is clear that if you do not check all 32 bytes, but only 16 bytes or 8 bytes in general, then the speed will be higher. it is natural. Nevertheless, this does not justify such a sharp drop in the hashrate as the table grows. Indeed, in fact, a 2-fold increase in the table adds only 1 additional sample. Edit: if I correctly understood the logic of your code. That is when the public key is calculated. You look at the first 3 bytes of the key in the hash table. If 3 bytes of key are there, then you get offset of start private key>> add offset to start private key>>compute public key>> compare public keys. But 24 bits is very small - it is a lot of collisions Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 16, 2020, 07:17:15 AM This problem is typically a time memory trade off problem so the goal is to find all best time memory tradeoff.
I store only 40 bits for the generator index (so 2^40 key max in my hash table) and 24 (+ 25 bits) of the x value. 64 bits per items and an array of 2^25 pointers + 2 * 2^25 short arrays. So i get few false collisions (one every 2^(49-30) giant steps in average) that i need to check but I win lots of memory, my giant step is much larger. I'm able to browse the 64bit range in 24min with my 9 year old Xeon (12GB) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 16, 2020, 12:03:15 PM -snip- I store only 40 bits for the generator index (so 2^40 key max in my hash table) and 24 (+ 25 bits) of the x value. 64 bits per items and an array of 2^25 pointers + 2 * 2^25 short arrays. -snip- How and where can you store all 2^40 keys? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 16, 2020, 12:39:56 PM How and where can you store all 2^40 keys? I store only 49bits (25+24) per key (using a HASH_SIZE of 25 in https://github.com/JeanLucPons/BSGS/blob/master/HashTable.h). I accept to have few false collisions and to make little more calculations to handle them. Each item in the table is a 64bits item, 40 bit for the generator index and 24 bit for a part of the key. I choose this maximum of 40 bit (32+8) because more than 2^32 keys is possible but you're right 2^40 can be decreased and few bits can be used for the key and decrease the probability of false collision. This program is here to be modified and adapted... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 17, 2020, 05:52:02 PM I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM.
It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation. If I convert to the Etar's unit: It does 14.6 PKey/s. I posted the result in the readme of my program: https://github.com/JeanLucPons/BSGS/blob/master/README.md Thanks to odolvlobo to provide this challenge. Best wishes to Etar to optimize his program and fix his issue on GPU. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 17, 2020, 07:19:45 PM I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM. it was good thread i think.It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation. If I convert to the Etar's unit: It does 14.6 PKey/s. I posted the result in the readme of my program: https://github.com/JeanLucPons/BSGS/blob/master/README.md Thanks to odolvlobo to provide this challenge. Best wishes to Etar to optimize his program and fix his issue on GPU. I think that each of us received something instructive here. Can you make release of your program? i mean exe file for windows? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 17, 2020, 08:59:13 PM I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM. It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation. If I convert to the Etar's unit: It does 14.6 PKey/s. -snip- Nice job! Thank you. So, your total time for 16 keys is 216 minutes, including 9 minutes for 2^30 precomputations. That means that for 16 keys search you need 207 minutes, or approx. 13 minute per one 64bit key. As i saw from your results, the time per one 64 key varied from 2 min to 19 min. Avg time 13minute is very good. I guess it is faster than the result reqched by Pollard Kangaroo method sahred in BurtW topic. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Tamarindei on April 17, 2020, 09:54:07 PM I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM. It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation. If I convert to the Etar's unit: It does 14.6 PKey/s. I posted the result in the readme of my program: https://github.com/JeanLucPons/BSGS/blob/master/README.md Thanks to odolvlobo to provide this challenge. Best wishes to Etar to optimize his program and fix his issue on GPU. Thx. How long would it take you to solve 110 bit range key of puzzle transaction? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 18, 2020, 05:28:12 AM I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0 To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years ! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 18, 2020, 06:38:17 AM I published an exe file for Windows: Thanks a lot for release.https://github.com/JeanLucPons/BSGS/releases/tag/1.0 To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years ! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 18, 2020, 08:04:57 AM Nice job! Thank you. You're welcome :) So, your total time for 16 keys is 216 minutes, including 9 minutes for 2^30 precomputations. That means that for 16 keys search you need 207 minutes, or approx. 13 minute per one 64bit key. As i saw from your results, the time per one 64 key varied from 2 min to 19 min. Avg time 13minute is very good. I guess it is faster than the result reqched by Pollard Kangaroo method sahred in BurtW topic. If you look at the key who has been solved in 19min, you see that ...7D0E6081C7E0E865 is close to ...8000000000000000 (end range of thread #3) and that it requires a total of 2^33.86 giant steps (max 2^34) so we are close to the end of the range. It takes ~20 minutes to browse the full 2^64 range, so the theoretical average time to solve a key should be 10min without taking into account the baby step precalculation. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 18, 2020, 09:14:29 AM Nice job! Thank you. You're welcome :) So, your total time for 16 keys is 216 minutes, including 9 minutes for 2^30 precomputations. That means that for 16 keys search you need 207 minutes, or approx. 13 minute per one 64bit key. As i saw from your results, the time per one 64 key varied from 2 min to 19 min. Avg time 13minute is very good. I guess it is faster than the result reqched by Pollard Kangaroo method sahred in BurtW topic. If you look at the key who has been solved in 19min, you see that ...7D0E6081C7E0E865 is close to ...8000000000000000 (end range of thread #3) and that it requires a total of 2^33.86 giant steps (max 2^34) so we are close to the end of the range. It takes ~20 minutes to browse the full 2^64 range, so the theoretical average time to solve a key should be 10min without taking into account the baby step precalculation. I try to implement hashtable, because hashtable is more fast then binary search. So, i use 24bit mask, like in your implementation. total baby steps = 2^24 = 16777216. Just for test. In real usage it should more. and i get a lot of collisions when fill table: Code: ----------HashTable Info---------- there were unique 10604491 24 bit combinations from total of 16777216 combinations 24 bit combinations that has collision was 6172725 and maximum of collision was 10 on some of the hashes i think it is terrible result of collisions :o Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 18, 2020, 09:58:36 AM f you use a 24bit hashtable and 2^30 keys for baby step:
You will have (in average) a list of 2^(30-24) = 64 items per hash. Each items of this list contains the generator index and an additional part of the key. Code: typedef struct {The hash is 3 byte of MSB of the key. b0 is 3 byte of LSB of the key. So we store 48 bits of the key. p (offset) is the "generator index" corresponding to the key p.G Then to access it , you compute the hash (one simple & operation) and you have direct access to this small list. You can sort each list according to the part of key and you will need 6 operations (in average) to get the generator index. I did like this in HashTable::Get(). Then as I don't store the full X value of p.G, i have some false collision, than i need to check by a computePublicKey. A false collision happens every 2^(24+24 - 30) = 2^18 giant steps, that means that I need to perform an extra EC multiplication every 262144 giant steps. According to the memory you have, you may need to adjust the HASH size, and the number of bit of the key stored in the entry in order to have a minimum of false collision. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 18, 2020, 11:50:11 AM f you use a 24bit hashtable and 2^30 keys for baby step: Ah, I understand difference bettwen our hashtables.You will have (in average) a list of 2^(30-24) = 64 items per hash. Each items of this list contains the generator index and an additional part of the key. Code: typedef struct {The hash is 3 byte of MSB of the key. b0 is 3 byte of LSB of the key. So we store 48 bits of the key. p (offset) is the "generator index" corresponding to the key p.G Then to access it , you compute the hash (one simple & operation) and you have direct access to this small list. You can sort each list according to the part of key and you will need 6 operations (in average) to get the generator index. I did like this in HashTable::Get(). Then as I don't store the full X value of p.G, i have some false collision, than i need to check by a computePublicKey. A false collision happens every 2^(24+24 - 30) = 2^18 giant steps, that means that I need to perform an extra EC multiplication every 262144 giant steps. According to the memory you have, you may need to adjust the HASH size, and the number of bit of the key stored in the entry in order to have a minimum of false collision. When you make pubkey you compare pubkey (masked pubkey) with each of element of hashtable( in last optimisation you add sorting for this) But i try to use other way. i don`t need to compare pubkey with each elements becouse i have table of 2^24 In that case i need only 1 lookup to the table to get hash and i get result - hash exist or not and if exist get pointer to memory where stored G counter or few G counters if collision. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: 0zero0 on April 18, 2020, 01:14:24 PM From what I have learnt about bitcoin I can say that deriving a private key from a public key is not possible.
The public key of is derived from a private key but that functionality is not backward compatible according to what I have learnt. So deriving the private key from public key is not feasible in my opinion. P.S : I have read this in some article on have watched youtube videos which say the same. Also, if it is miraculously possible could you please explain it how, in Laymans terms. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 18, 2020, 02:09:06 PM Ah, I understand difference bettwen our hashtables. When you make pubkey you compare pubkey (masked pubkey) with each of element of hashtable( in last optimisation you add sorting for this) But i try to use other way. i don`t need to compare pubkey with each elements becouse i have table of 2^24 In that case i need only 1 lookup to the table to get hash and i get result - hash exist or not and if exist get pointer to memory where stored G counter or few G counters if collision. Ok, If I understand well your startegy, you face the birthday paradox problem. When you fill your hashtable, you will start to have collision around the sqrt(2^24)=2^12th insertion. So for 2^24 G counters, you will need a hashtable of ~2^48 entries to avoid collision. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 18, 2020, 06:57:01 PM -snip- Thanks a lot for release. Have you tested this release on your config? How is the progress compared with your code? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 19, 2020, 08:12:34 AM -snip- Thanks a lot for release. Have you tested this release on your config? How is the progress compared with your code? Because have big base hashrate. I mean for ex. base hashrate for i7 3770 is 14Mkey/s. I can`t get this speed on my program because i use simple language where big integer calculations used 3ty part library. In that case i have low base hashrate due to convertion for integers. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 19, 2020, 09:56:23 AM I published an exe file for Windows: https://github.com/JeanLucPons/BSGS/releases/tag/1.0 To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years ! Hello respected Jean !!! Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb. ? Thanks Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 19, 2020, 10:08:34 AM I published an exe file for Windows: https://github.com/JeanLucPons/BSGS/releases/tag/1.0 To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years ! Hello respected Jean !!! Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb. ? Thanks by default baby step = 2^30 = 40000000 in hex format you can use for ex. 2^28 = 10000000 in hex each step used 64bit of memory, so 2^28 need only 2Gb 2^29 around 4Gb Decrease the baby step counter will proportionally increase the brute force time. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 19, 2020, 11:22:05 AM -snip- Thanks a lot for release. Have you tested this release on your config? How is the progress compared with your code? Because have big base hashrate. I mean for ex. base hashrate for i7 3770 is 14Mkey/s. I can`t get this speed on my program because i use simple language where big integer calculations used 3ty part library. In that case i have low base hashrate due to convertion for integers. Jean_Luc also made the vanity search program, and some guy modified it to work with pollard kangaroo method. The code is here: https://github.com/alek76-2/vs-kangaroo-hybrid I beleive that this program should be faster. It uses GPU, not CPU. Of course it is not good to compare CPU and GPU, GPU will always be ahead. Also for proper work of BSGS method the RAM is required; the more - the better. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 19, 2020, 11:28:07 AM I published an exe file for Windows: https://github.com/JeanLucPons/BSGS/releases/tag/1.0 To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years ! Hello respected Jean !!! Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb. -snip- Etar already answered. I can confirm the same. Just use the smaller baby step table. It is the 1st line in in.txt file. By default it is 40000000 in hex format (2^30), and it requitres approx. 9Gb RAM. For your 8Gb memory you can use 20000000 (2^29), and in total you will need approx. 1 hour to find the private key for 64bit key. Jean tested with 12Gb RAM and 2^30 baby step and had approx 13 minutes. You will have 1 hour with your 8Gb RAM. Just test, and say the result if 1 hour prediction was correct. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 19, 2020, 11:47:38 AM I published an exe file for Windows: https://github.com/JeanLucPons/BSGS/releases/tag/1.0 To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years ! Hello respected Jean !!! Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb. -snip- Etar already answered. I can confirm the same. Just use the smaller baby step table. It is the 1st line in in.txt file. By default it is 40000000 in hex format (2^30), and it requitres approx. 9Gb RAM. For your 8Gb memory you can use 20000000 (2^29), and in total you will need approx. 1 hour to find the private key for 64bit key. Jean tested with 12Gb RAM and 2^30 baby step and had approx 13 minutes. You will have 1 hour with your 8Gb RAM. Just test, and say the result if 1 hour prediction was correct. Big thanx all members for yours answers. I will test today in the evening and show me results. I hope my PC without CUDA will can do something. Again - big thanx to all. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 19, 2020, 01:10:51 PM Is any method for add Windos ReadyBost to Release ? I was tern up readyboost but release code not used them. Have someone sny ideas ?
Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: sssergy2705 on April 19, 2020, 06:59:10 PM I published an exe file for Windows: https://github.com/JeanLucPons/BSGS/releases/tag/1.0 To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years ! Hello respected Jean !!! Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb. -snip- Etar already answered. I can confirm the same. Just use the smaller baby step table. It is the 1st line in in.txt file. By default it is 40000000 in hex format (2^30), and it requitres approx. 9Gb RAM. For your 8Gb memory you can use 20000000 (2^29), and in total you will need approx. 1 hour to find the private key for 64bit key. Jean tested with 12Gb RAM and 2^30 baby step and had approx 13 minutes. You will have 1 hour with your 8Gb RAM. Just test, and say the result if 1 hour prediction was correct. core i7 3770 8 RAM 28 mins Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 19, 2020, 08:01:10 PM core i7 3770 8 RAM 28 mins 28 min per key with 8Gb RAM ? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 19, 2020, 08:42:13 PM core i7 3770 8 RAM 28 mins 28 min per key with 8Gb RAM ? I try fined key from in.txt of reliase. Speed down to 0.01Mkey per second. Give me please examples what you use ? My ex is to hard for me. BabyStep:0x20000000 Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000 Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF Keys :1 This config is down on my i5 with 8Gb !!!😠 Thenx Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: sssergy2705 on April 20, 2020, 09:01:50 AM core i7 3770 8 RAM 28 mins 28 min per key with 8Gb RAM ? I try fined key from in.txt of reliase. Speed down to 0.01Mkey per second. Give me please examples what you use ? My ex is to hard for me. BabyStep:0x20000000 Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000 Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF Keys :1 This config is down on my i5 with 8Gb !!!😠 Thenx Code: root@system:~# ./bsgs in.txt in.txt Code: 20000000 https://imgur.com/gItX4Uh Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 21, 2020, 07:36:40 AM Jean_Luc also made the vanity search program, and some guy modified it to work with pollard kangaroo method. The code is here: https://github.com/alek76-2/vs-kangaroo-hybrid I beleive that this program should be faster. It uses GPU, not CPU. Of course it is not good to compare CPU and GPU, GPU will always be ahead. Just curious, I wrote a simple Kangaroo program, I didn't test the alek's one because I have a look in his code and see that basic optimizations (at least for CPU) are missed. Especially line 625 of Vanity.cpp Code: ph->Kp = secp->AddAffine(ph->Kp, Sp[pw]); // This requires a modular inversion which can be batched I published the code here: https://github.com/JeanLucPons/Kangaroo A comparison between BSGS and Kangaroo, (64bit search, on my old Xeon) : Kangaroo should end in 2^33 iterations (in average). I reached 18.18 MKey/s (here the DP method can be applied to speed up the hashtable and decrease drastically the needed memory, this method can be efficiently implemented on GPU). Code: Kangaroo v1.0 I'll post the full result for the 16 keys on github when ended. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 21, 2020, 09:15:52 AM Quote from: Jean_Luc link=topic=5238719.msg54267073#msg54267073 I published the code here: https://github.com/JeanLucPons/Kangaroo Jean_Luc, Anybodey can you make a exe file for windows ? My intel i5 without CUDA, and my manipulation with memory cash, arh, radyboosters etc. unsuccesful for me. I hope Kangoro will work for me more succesful Pleeeease. Br. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 21, 2020, 09:18:49 AM The Pollard's kangaroo has solved the 16 64bit keys in 3:07:38, so a bit faster than BSGS (03:35:53) and with a lot less memory.
https://github.com/JeanLucPons/Kangaroo/blob/master/README.md I will definitely add a GPU support for it. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 21, 2020, 09:20:35 AM Jean_Luc, Anybodey can you make a exe file for windows ? I re added it. Strangely github removed it ?!!! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 21, 2020, 09:22:19 AM Jean_Luc, Anybodey can you make a exe file for windows ? I re added it. Strangely github removed it ?!!! I was seen only sorces for Kongaroo, in github witout exe. 😩 Please reupload exe for Kangaroo to github, Jean_Luc ? Biiiiiig thank you !!! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 21, 2020, 09:28:38 AM https://github.com/JeanLucPons/Kangaroo/releases
You see it ? for me it seems ok. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 21, 2020, 10:08:23 AM https://github.com/JeanLucPons/Kangaroo/releases You see it ? for me it seems ok. May God protect you, you are a good man,Jean_Luc.👋 Biggest Thanks and Regards You. Oh now I see exe file. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 21, 2020, 10:15:32 AM https://github.com/JeanLucPons/Kangaroo/releases You see it ? for me it seems ok. May God protect you, you are a good man,Jean_Luc.👋 Biggest Thanks and Regards You Jean_Luc !!!!!!!!!!!! Oh Yes Yes Yes Yes, Now I see exe file. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 21, 2020, 10:54:30 AM 0 FFFFFFFFFFFFFF 02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305FEF82A ----- I solve now this in 1:54 min !!! I happy now !!! And file size 8.4 Mb, memory on my notebook not working like shet !!! :) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 22, 2020, 11:31:18 AM Please help.
What start and and key in Kangaroo config I will neede for this, for ex ETH public key ? Publick key 02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305FEF82A Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 22, 2020, 01:10:40 PM 1Ph/s speed is roughly 2^66 per 24 hours. Give me public key of this address (64bytes)There is a bitcoin address with 0.64BTC and 64bit private key. You need 2^63 operations to bruteforce it. If you have real speed 2^66 per 24 hours, so you can perform 2^63 operations juts for 24/(2^3)=3 hours. So, welcome to prove your speed: just take 0.64BTC from this address: https://www.blockchain.com/btc/address/16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN The private key for this address is in the range: 0x8000000000000000 - 0xffffffffffffffff (64bit key, i.e. with 192 leading zeros) Eter, hello. You was finded private key for this address ? I check all examples in this thread I apologise private key from this thread only for new wallets :( Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 22, 2020, 01:13:30 PM The Pollard's kangaroo has solved the 16 64bit keys in 3:07:38, so a bit faster than BSGS (03:35:53) and with a lot less memory. https://github.com/JeanLucPons/Kangaroo/blob/master/README.md I will definitely add a GPU support for it. Yes, Kangaroo method does not need memory. Can you please clarify: 1) Did you use the tame table for the subsequent keys? (I mean while you find the 1st key, you have some tame points - do you use them for the key2, key3, etc... ?) Wild points are not important anymore, but tame ones very helpful as all 16 keys are within the same range; and if you use them, the time needed for the subsequent key will be less, less and less. That means that for method evaluation it is better to perform several tests and confirm the average time for one key rather than the total time. 2) How much were your tame and wild tables? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 22, 2020, 01:45:32 PM 1) Did you use the tame table for the subsequent keys? (I mean while you find the 1st key, you have some tame points - do you use them for the key2, key3, etc... ?) Wild points are not important anymore, but tame ones very helpful as all 16 keys are within the same range; and if you use them, the time needed for the subsequent key will be less, less and less. No this optimization is not yet done. Reusing tame points will speed up thing by ~2 for others keys. Edit: I'm wondering if using wild point of solved key can be reused also, this should work... 2) How much were your tame and wild tables? I use the distinguished point method so it varies a lot according to the dpSize. I wrote few notes on it on an other project: https://github.com/JeanLucPons/BTCCollider/blob/master/README.md Anyway, first GPU release is coming: 16 keys (64bits) solved in 29:44, key by key, no reuse of old points. Code: C:\C++\Kangaroo\VC_CUDA10\x64\Release>Kangaroo.exe -t 0 -gpu ..\..\in.txt Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: dextronomous on April 22, 2020, 02:24:05 PM Great to have a Jean_Luc around all the time, thanks a lot for you'r great works.
Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 22, 2020, 02:48:40 PM 1) Did you use the tame table for the subsequent keys? (I mean while you find the 1st key, you have some tame points - do you use them for the key2, key3, etc... ?) Wild points are not important anymore, but tame ones very helpful as all 16 keys are within the same range; and if you use them, the time needed for the subsequent key will be less, less and less. No this optimization is not yet done. Reusing tame points will speed up thing by ~2 for others keys. Edit: I'm wondering if using wild point of solved key can be reused also, this should work... -snip- Wild points of slved keys will not be helpful. All the wild points are just connected with the exact public key - so every wild point is a unknown part (the same unknown as the public key). The other thing is with the tame points - you know the private key to every tame point. So the tame points you have - the better chances for meeting with wild :) I am imaging it like you have the "cord" to every tame kangaroo. "Cord" is the exact private key. As soon as the tame kangaroo meet with the wild one, you can easily retrieve the private key for the target address using your known "cord" and the known "jump" by the wild kangaroo (one adding/substraction operation). In the table of wild kangaroos you have the known jumps from the point of target address (target public key). As soon as you change the target address, all the wild points become useless. So, after changing the target address all the wild points should be cleared. They will just requre more time for comparator without real help. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 22, 2020, 02:57:36 PM A solved wild point become P1 + d1.G = (k1 + d1).G
A collision with a new wild point P2 + d2.G will give P2 + d2.G = (k1 + d1).G => P2 = (k1 + d1 - d2).G I think solved wild can be reused. We can say that a wild kangaroo trapped becomes a tame one ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 22, 2020, 03:24:02 PM A solved wild point become P1 + d1.G = (k1 + d1).G A collision with a new wild point P2 + d2.G will give P2 + d2.G = (k1 + d1).G => P2 = (k1 + d1 - d2).G I think solved wild can be reused. We can say that a wild kangaroo trapped becomes a tame one ;) Oh, yes yes and yes. You are right. If the key solved, all the wild points became tame... But the "cord" will not be direct... Yes, clear. I was wrong. You are right! EDIT: "We can say that a wild kangaroo trapped becomes a tame one": The whole troop of kangaroos become tame! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 22, 2020, 03:47:42 PM -snip- Anyway, first GPU release is coming: 16 keys (64bits) solved in 29:44, key by key, no reuse of old points. Very good job. I guess that the GPU code for Pollard Kanagaroo is now available for public. Thank you! I have just tested your code on Ubuntu 18.04, GPU only, GTX 1080ti, and it found 16 keys (64 bit) just for 16:11 minutes, so 1 minute per 64bit key on average :o Code: $ ./kangaroo -t 0 -gpu in16.txt PS. The code works faster if use ONLY GPU. If use GPU and CPU, the speed was slower (like 2-3 times slower). Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 22, 2020, 05:00:42 PM Anyway, first GPU release is coming Thanks for your work. You are really very good at algorithms. I tried to test the GPU version. But for some reason, loading the GPU and memory is extremely small. And the speed drops immediately from 350 to 100 Mkeys per second. http://i.piccy.info/i9/325822f18b5e64884080e0902e42e273/1587574888/5859/1371731/Untitled_1_240.jpg (http://piccy.info/view3/13768624/f8f17f15d64c762ec4d3eca6eb216c2a/)http://i.piccy.info/a3/2020-04-22-17-01/i9-13768624/240x134-r/i.gif (http://i.piccy.info/a3c/2020-04-22-17-01/i9-13768624/240x134-r) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 22, 2020, 05:08:07 PM -snip- I tried to test the GPU version. But for some reason, loading the GPU and memory is extremely small. And the speed drops immediately from 350 to 100 Mkeys per second -snip- I am not sure, but the speed is droping while changing the target key. The program is clearing the kanagroo points and setting up the new troops of wild kangaroos. With your 2080ti you should have a good performance. The 64bit is just very small for it, and the GPU spend more time for "preparation" rather than for actual finding. Try the code with higher key (for example 80bit key). I think that with your 2080ti you could solve 80bit key for 20-30 minutes. And also you will see your actual speed during this time. EDIT: Running GTX 2080 Ti for 64bit is like driving the sport car in small village. If you want to test the actual speed of your "car" you need to go to highway! ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 22, 2020, 05:27:24 PM Yes with a large number of thread and a small range (64bits) you face an overhead due to the DP method.
You can try to set by hand the dpSize using the -d option. C:\C++\Kangaroo\VC_CUDA10\x64\Release>Kangaroo.exe -t 0 -d 10 -gpu ..\..\in.txt You will get a warning but ignore it. As MrFreeDragon said, such a GPU will be much more efficient on 80bit search or more. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 22, 2020, 07:13:36 PM Yes with a large number of thread and a small range (64bits) you face an overhead due to the DP method. My setup and speed:You can try to set by hand the dpSize using the -d option. C:\C++\Kangaroo\VC_CUDA10\x64\Release>Kangaroo.exe -t 0 -d 10 -gpu ..\..\in.txt You will get a warning but ignore it. As MrFreeDragon said, such a GPU will be much more efficient on 80bit search or more. Range 2^64, DP-10, speed 500Mkeys/s Range 2^64, DP-11, speed 700Mkeys/s Range 2^64, DP-12, speed 900Mkeys/s, Time to find 16 keys is 15m30s (the time is about the same as for weaker cards, although the speed is higher) Range 2^80, DP - by default, speed 1100Mkeys/s but not a single key was found in 1 hour Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 22, 2020, 07:42:59 PM -snip- Range 2^80, DP - by default, speed 1100Mkeys/s but not a single key was found in 1 hour Good thing - now you know your exact speed as you tested the card "on highway" :) However it is strange you could not solve 80bit range for 1 hour. Actually for 80bit key the Pollard Kangaroo code should make on average 2^40 operations. So, with the speed 1100Mkey/sec you will need only 2^40/1100M seconds = 1000 seconds = 16-17 minutes. Check the range you use for the search. For 80bit key it is 0x80000000000000000000 - 0xffffffffffffffffffff (2^79 - 2^80-1). Or other in higher bit keys, but with the range length 80bit. EDIT: There is also possible that your key is out of the range you specify. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 23, 2020, 04:07:24 AM Range 2^64, DP-12, speed 900Mkeys/s, Time to find 16 keys is 15m30s (the time is about the same as for weaker cards, although the speed is higher) Yes having a too large DP size and too much threads create an overhead. You need more iterations. Range 2^80, DP - by default, speed 1100Mkeys/s but not a single key was found in 1 hour I will try to make a test with a 80bit key today and improve the creation of kangaroo which is slow. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 23, 2020, 07:11:43 AM Range 2^80, DP - by default, speed 1100Mkeys/s but not a single key was found in 1 hour I published a new release 1.2 with faster kangaroo creation. I'm trying to attack a 80bit key but on my hardware (115MK/s), it will take time ;) in.txt Code: 25FEEE926526B0B4F0085358DF14702F7F6F04E8EC2200000000000000000000 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 23, 2020, 11:09:53 AM My low cost hardware has solved the 80bit key is 03:52:25.
I will now work on endomorphism and symetry optimization. Code: Kangaroo v1.2 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 23, 2020, 01:40:14 PM My low cost hardware has solved the 80bit key is 03:52:25. My Hi-End GPU can`t find any key for 1h))Config txt the same like in example, just little increase range to 80bit, all public keys from example. Code:
Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 23, 2020, 01:52:03 PM My low cost hardware has solved the 80bit key is 03:52:25. With the 1st Kangarooo v1.1 my GPU 1080ti solved 80bit key for 35 minutes. This time seems reasonable as with the speed 436MKey 80bit key should be solved (2^40 operations) for 2^40 / 436M = 2521 sec = 42 minutes. With 2080ti at 1100MKey/sec the total time should be 15-20 minutes. Code: $ ./kangaroo -gpu -t 0 in80.txt For the test I used 80bit key from 100 bitcoin transaction challenge: Code: 80000000000000000000 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 23, 2020, 02:23:58 PM My Hi-End GPU can`t find any key for 1h)) That should work. For 80bit search, 2^41 is an average time, with a probability of ~50% to find the key. I will try this night. Many thanks to MrFreeDragon for testing the software ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 23, 2020, 02:46:51 PM 2h and nothing, speed drop to 267Mkey, GPU usage drop to 25%
Code: Kangaroo v1.2 there is txt file (the same like example, only 80bit range set) Code: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb4800000000000000000000 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 23, 2020, 02:50:00 PM 2h and nothing, speed drop to 267Mkey, GPU usage drop to 25% That's strange, may be a bug somewhere, the gpu usage drops may be because the HashTable becomes too big. I'll try Did you try with others key ? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 23, 2020, 02:55:31 PM My Hi-End GPU can`t find any key for 1h)) That should work. For 80bit search, 2^41 is an average time, with a probability of ~50% to find the key. I will try this night. Many thanks to MrFreeDragon for testing the software ;) Agree with this comment. The Pollard Kangaroo solves the problem with the less operations (square root from the total width), but with not 100% probability of course. Etar, if you had this: [1017.74 MKey/s][GPU 1017.74 MKey/s][Count 2^41.74][Dead 2][01:08:13][8578.7MB]. it means that you just was unlucky. However it does not mean that you should restart the code. Actually at this stage the code sould solve the key within the next every minute. Your 2080ti actually made 2^41 operations for 40 minutes (1h8min / 2^0.74) or 2^40 operations for 20 minutes. So everything works good. You just was unlucky with the probability to solve... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 23, 2020, 03:11:03 PM 2h and nothing, speed drop to 267Mkey, GPU usage drop to 25% That's strange, may be a bug somewhere, the gpu usage drops may be because the HashTable becomes too big. I'll try Did you try with others key ? I dont know how hashtable can be 13 gb in this reason. No, i did not try other keys. Only from example. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 23, 2020, 03:12:59 PM . Actually at this stage the code sould solve the key within the next every minute. I think the same but i was wait 2 h ???Your 2080ti actually made 2^41 operations for 40 minutes (1h8min / 2^0.74) or 2^40 operations for 20 minutes. So everything works good. You just was unlucky with the probability to solve... And it is not unlucky there should be other reason. I launch this config few times. And no one times not get result. I think that bsgs algoritm is more-more predicteble. You know how many memory you need for calculation. You know speed and you know how many time you need to check range. Kangaroo algorithm not used less memory as i see due to grow hashtable in time. Or if hashtable allocate in begining i dont know if i can allocate hashtable for range 2^255. And if i allways will get dead kangaroo how i will know that i solve range and there no key... So if range will be 128 bit so you dont know will you found key or you will get out of memory or all times wiil get dead kangaroo. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 23, 2020, 03:23:41 PM My gpu have only 11gb of memory I dont know how hashtable can be 13 gb in this reason. No, i did not try other keys. Only from example. The hash table is centralized and managed by the CPU. You have 7 dead kangaroo, a dead kangaroo is a collision in the same herd, and the kangaroo is re created. There is the same probability to get a dead kangaroo or to solve the key. Having 7 dead kangaroo without solving the key is like throwing 7 times a coin and having consecutively nine time "heads", bad luck ! On this key, i got 20 dead kangaroos ! ~2^35 , ~4 times more iterations needed compare to the average 2^33... [114.85 MKey/s][GPU 114.85 MKey/s][Count 2^34.98][Dead 20][05:41][1269.3MB] Key#11 Pub: 0x03D4E6FA664BD75A508C0FF0ED6F2C52DA2ADD7C3F954D9C346D24318DBD2ECFC6 Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EE3579364DE939B0C Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 23, 2020, 04:44:53 PM I have tried the same 80bit range as you:
Code: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb4800000000000000000000 Kangaroo v1.1, Range width 2^80, 16 keys from the example. For 2hours 30 minutes at speed 433Mkey the script performed 2^41.7 operations, killed 7 kangaroos, but did not solve the key. I have some idea but not sure if it is correct and could have the impact. For the range with leading zeros everything worked fine (I mena then I tried the 80bit key from the challenge example). But we are all killing kangaroos with the 16 key example.... and not solving them. Probably the kangaroos are jumping outside the range and make the width much wider. What if just adjust the range to the one with leading zeros and also adjust the public key to search. I mean "to substract 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb4800000000000000000000 from the range and from the public key as well. So the range will be 0x00000000000000000000 - 0xffffffffffffffffffff and the public key will be Q - kG , where Q is the target public key and k is the start of the range. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 23, 2020, 04:54:04 PM could have Probably the kangaroos are jumping outside the range and make the width much wider. Kangaroo cant jump outside because step is modulo nWhat if just adjust the range to the one with leading zeros and also adjust the public key to search. I mean "to substract 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb4800000000000000000000 from the range and from the public key as well. So the range will be 0x00000000000000000000 - 0xffffffffffffffffffff and the public key will be Q - kG , where Q is the target public key and k is the start of the range. If i will get all time dead kangaroo due to collision in the same tribe i cant see positive moment in this algorithm. Any way thanks for reseaching. You a very-very good programmer! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 23, 2020, 04:58:50 PM Yes I remarked that this first key of this set often generate dead kangaroos (even in 64bit range)
The fact that the startrange is not zero should not impact, it is just a translation. It is equivalent to what MrFreeDragon said. All kangaroos are uniformly distributed in the range and make random jumps form G up to 2*sqrt(k2-k1).G Even if kangaroos goes out of the range it is not really a problem. I will try to change the calculation on random jump to see if it improve something. [18.00 MKey/s][Count 2^34.40][20:47][Dead 10][20.2MB] Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 [115.23 MKey/s][GPU 115.23 MKey/s][Count 2^33.52][Dead 5][02:02][463.9MB] Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 23, 2020, 05:42:53 PM What if use many publick key from 1 adress ? Maby jrivate key will be 1 and private key search for many public adreses will get more trustwothy result ?
Can someone test this idea ? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 23, 2020, 09:55:16 PM Yes I remarked that this first key of this set often generate dead kangaroos (even in 64bit range) The fact that the startrange is not zero should not impact, it is just a translation. It is equivalent to what MrFreeDragon said. -snip- Finally I could solve the 80bit key from the 16key example for 3h14min. But I made the adjustment I wrote before. Changed the range in the following way: Code: Real ranges: And also made the corrsponding changes to the public keys: deducted the Point 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000*G from every Public key, so: Code: The initial pubic keys: And the result for the 1st key was found for 3:14 hours: Code: Start:0 Now we can retrieve the target private key: Final Priv = 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000 + 0xCB5EBB3EF3883C1866D4 = 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4 I know that these adsjutments should not affect the time to solve, however in my case without adjustments i could not solve the 1st 80bit from example for 4 hours, with the adjustments the 1st key was solved for 3:14 hours. If Etar could test that adjusted public keys with the adjusted ranges (with leading zeros) on his 2080ti it would be great. Etar should have the speed 2.5 times faster, so the 1st key should be solved for 1:15-1:30 hours. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 24, 2020, 02:47:22 AM During the night, I solved the key with the same config file as Etar in 2^41.59 iterations (09:06:32) and 1 dead kangaroo.
It seems normal. I will make further tests to see if changing the jumps can improve things a bit... Code: C:\C++\Kangaroo\VC_CUDA10\x64\Release>Kangaroo.exe -t 0 -gpu ..\..\in.txt Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: PietCoin97 on April 24, 2020, 08:01:08 AM Code: Kangaroo.exe -t 0 -gpu -gpuId 0,1,2,3,4,5 in.txt Jean luc does it work also with such an key space ? Start:8000000000000000000000001 Stop :FFFFFFFFFFFFFFFFFFFFFFFFE or should i give in all 64 bits ? and are my setting ok or can i get higher speed ? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 24, 2020, 08:07:43 AM I solved 20 times the following key (64bit range) and there was a strange 24 dead kangaroos event !? It seems that from times to times the algorithm has hard time to solve the key... Just a matter of probability ? My Mersenne twister fails ? I will make further tests...
Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 [115.22 MKey/s][GPU 115.22 MKey/s][Count 2^33.63][Dead 3][02:12][502.4MB] [115.22 MKey/s][GPU 115.22 MKey/s][Count 2^34.07][Dead 0][02:59][675.8MB] [115.22 MKey/s][GPU 115.22 MKey/s][Count 2^31.43][Dead 0][29s][113.4MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.70][Dead 1][02:19][525.5MB] [115.22 MKey/s][GPU 115.22 MKey/s][Count 2^35.20][Dead 24][06:31][1472.8MB] [115.22 MKey/s][GPU 115.22 MKey/s][Count 2^34.44][Dead 7][03:52][872.4MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.51][Dead 1][02:02][459.6MB] [115.22 MKey/s][GPU 115.22 MKey/s][Count 2^34.27][Dead 7][03:27][779.1MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.68][Dead 3][02:17][516.3MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.85][Dead 3][02:34][581.7MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.33][Dead 1][54s][206.9MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.40][Dead 0][57s][216.1MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.45][Dead 2][01:57][441.1MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.97][Dead 1][01:24][319.5MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^34.66][Dead 6][04:29][1012.6MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.12][Dead 0][47s][178.9MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^31.66][Dead 0][34s][131.5MB] [115.23 MKey/s][GPU 115.23 MKey/s][Count 2^33.32][Dead 3][01:47][403.6MB] [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^34.00][Dead 2][02:52][647.1MB] [115.22 MKey/s][GPU 115.22 MKey/s][Count 2^33.68][Dead 2][02:17][516.5MB] Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 24, 2020, 08:10:11 AM Jean luc does it work also with such an key space ? Start:8000000000000000000000001 Stop :FFFFFFFFFFFFFFFFFFFFFFFFE or should i give in all 64 bits ? and are my setting ok or can i get higher speed ? Yes it should work. Your setup looks good. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 24, 2020, 11:10:09 AM Tried to use Kangaroo v1.2 on Ubuntu and searched for 2^80 range width. The 1st key was solved for the same tim 3h15min, the 2nd for 4h and the 3d for 4h13min. Here are the results:
Code: input 5 public keys: I used the adjusted keys (deducted the start range from every point), but actually such adjustment does not make sense. Code: Kangaroo v1.2 The version 1.2 is faster by 2-3% compared with the version 1.1 I stoped the code and did not wait for the remaining 2 keys. We can see that for 2^80 range it needed 2^42.05, 2^42.39 and 2^42.47 operations, however on average 2^41 was enough. So the total time for every key was 2-3 times longer (!!!) For 2^80 range it makes big difference (1.5 hours vs 3 hours). But due to the tests made I can confirm that on GTX 1080ti (11Gb) the key in 2^80 range could be found for 3-4 hours, although 1.5 hours on average was expected. Jean_Luc, are all the wild kangaroos start from the one public key point? I guess that symmetry would halve the total time... We have to solve P = k.G, we know that k lies in the range [k1,k2]; So, (k2-k) also lies in the range [k1,k2]. How about starting the wild kangaroos not only from k, but from both k and (k2-k)? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 24, 2020, 11:52:00 AM Yes there is a problem with the spreading of wild kangaroo i think.
They should be spread with a -(k2-k1)/2 translation, the keys you solved are close to the upper bound, it explains the factor of 2. I will try this ASAP. Many thanks for the tests ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 24, 2020, 12:07:54 PM I solved 20 times the following key (64bit range) and there was a strange 24 dead kangaroos event !? It seems that from times to times the algorithm has hard time to solve the key... Just a matter of probability ? My Mersenne twister fails ? I will make further tests... Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 -snip- I tried to do the same (solved 20 times the same key as you). The total result was the same as test with 64bit before: average 1minute per 64bit range key (total 20:52 min for 20 keys). It seems that my GPU card is more friendly - maximum kangaroo kills was 8 times for the first time. [300.90 MKey/s][GPU 300.90 MKey/s][Count 2^34.32][Dead 8][01:06][3192.1MB] [347.36 MKey/s][GPU 347.36 MKey/s][Count 2^33.94][Dead 7][52s][2462.2MB] [456.28 MKey/s][GPU 456.28 MKey/s][Count 2^32.93][Dead 1][26s][1223.2MB] [415.46 MKey/s][GPU 415.46 MKey/s][Count 2^33.44][Dead 4][36s][1742.3MB] [350.83 MKey/s][GPU 350.83 MKey/s][Count 2^32.23][Dead 0][18s][754.4MB] [403.60 MKey/s][GPU 403.60 MKey/s][Count 2^33.52][Dead 2][38s][1837.3MB] [299.12 MKey/s][GPU 299.12 MKey/s][Count 2^31.98][Dead 0][16s][635.9MB] [458.32 MKey/s][GPU 458.32 MKey/s][Count 2^32.80][Dead 0][26s][1120.4MB] [280.27 MKey/s][GPU 280.27 MKey/s][Count 2^34.59][Dead 6][01:28][3846.3MB] [203.74 MKey/s][GPU 203.74 MKey/s][Count 2^30.73][Dead 0][10s][270.9MB] [296.67 MKey/s][GPU 296.67 MKey/s][Count 2^34.36][Dead 6][01:14][3301.0MB] [279.64 MKey/s][GPU 279.64 MKey/s][Count 2^31.67][Dead 0][14s][514.0MB] [324.70 MKey/s][GPU 324.70 MKey/s][Count 2^34.13][Dead 4][01:02][2811.4MB] [297.73 MKey/s][GPU 297.73 MKey/s][Count 2^34.38][Dead 7][01:14][3339.0MB] [426.65 MKey/s][GPU 426.65 MKey/s][Count 2^33.35][Dead 2][34s][1635.3MB] [408.92 MKey/s][GPU 408.92 MKey/s][Count 2^32.45][Dead 2][20s][875.8MB] [321.43 MKey/s][GPU 321.43 MKey/s][Count 2^34.17][Dead 4][01:02][2876.2MB] [250.27 MKey/s][GPU 250.27 MKey/s][Count 2^34.98][Dead 7][02:04][5059.6MB] [321.52 MKey/s][GPU 321.52 MKey/s][Count 2^34.16][Dead 2][01:02][2868.8MB] [353.13 MKey/s][GPU 353.13 MKey/s][Count 2^33.89][Dead 3][50s][2379.2MB] Done: Total time 20:52 That "dead" kangaroo case is the cycle running. Kangaroos running in cycles do not find new points, but slow down the algorithm and also might cause it to fail. This was described by Edlyn Teske in Computing discrete logarithms with theparallelized kangaroo method work (see 6.3): https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8520 EDIT: remove code tag from the 20 results to bold the maximum DEAD Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 24, 2020, 12:39:09 PM Thanks for the reading and the tests :)
The dead kangaroos are well handled, they are detected, deleted and recreated. Was quite a nightmare with the GPU and coalesced memory access :D The only things that might happen is that a kangaroo enter in a cycle without having a distinguished point in the cycle but it is rather unlikely. Handling this in the GPU (with a Floyd cycle detection) will just kill GPU performance. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 24, 2020, 01:13:32 PM Thanks for the reading and the tests :) The dead kangaroos are well handled, they are detected, deleted and recreated. Was quite a nightmare with the GPU and coalesced memory access :D The only things that might happen is that a kangaroo enter in a cycle without having a distinguished point in the cycle but it is rather unlikely. Handling this in the GPU (with a Floyd cycle detection) will just kill GPU performance. Jean_Luc, can you edit code for geting good resualt ? Please.... I very hope Kangaroo will can brute bitcoin... ?? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 24, 2020, 01:22:33 PM Jean_Luc, can you edit code for geting good resualt ? Please.... I very hope Kangaroo will can brute bitcoin... ?? I'm sorry, I do my maximum, but this algorithm is known from long time and it cannot break Secpk1. May be a flash of genius will hit a day me but for the moment nothing better than O(sqrt(n))... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 24, 2020, 01:35:37 PM Jean_Luc, can you edit code for geting good resualt ? Please.... I very hope Kangaroo will can brute bitcoin... ?? I'm sorry, I do my maximum, but this algorithm is known from long time and it cannot break Secpk1. May be a flash of genius will hit a day me but for the moment nothing better than O(sqrt(n))... Maybe ETH is more simple and resualtativ will be ??? Br !!!!! You are great coder and very good man Bro. I will hope you and Etar will psenesnt your enoter result and codes. Very inyresting !!!!! Etar, yours method is false resalt generated too, like Kangaroo? 😢 Btc not hacked. This is very bad news for me ((() Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 24, 2020, 02:18:58 PM They should be spread with a -(k2-k1)/2 translation, the keys you solved are close to the upper bound, it explains the factor of 2. I added the translation, looks like better. I published a new release https://github.com/JeanLucPons/Kangaroo/releases Thanks to test it :) I redid the test above: Code: [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.12][Dead 1][01:32][352.0MB] Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 24, 2020, 02:32:38 PM They should be spread with a -(k2-k1)/2 translation, the keys you solved are close to the upper bound, it explains the factor of 2. I added the translation, looks like better. I published a new release https://github.com/JeanLucPons/Kangaroo/releases Thanks to test it :) I redid the test above: Code: [115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.12][Dead 1][01:32][352.0MB] 😊😊😊😊Thaaaaank Yoooouu !!!! I wil buy my additional CUDA for testing codes. My first CUDA away from me now.... and aftef I will brute brute brute" brute the wolrld again". Biggest thanks Jean_Luc !!!! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 24, 2020, 05:05:24 PM They should be spread with a -(k2-k1)/2 translation, the keys you solved are close to the upper bound, it explains the factor of 2. I added the translation, looks like better. I published a new release https://github.com/JeanLucPons/Kangaroo/releases Thanks to test it :) Nice job! Seems we were right that the better spread of kangaroos should be applied. I made the quick test for 16 64bit range keys, and the total time now 10:23 min compared with 16 minutes earlier. Now it is 38-39sec per one 64bit range key! Code: $ ./kangaroo -t 0 -gpu in16.txt Kangaroo v1.3 has better performance for sure! And good thing for Green Peace as Kangaroo v1.3 goes to the target with less "dead animals" ;) PS. Later I will test these 16 keys for the wider 80bit range and let you know. Expect it will solve them for 1.5-2 hours instead of 4 hours as it was before. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 24, 2020, 06:48:28 PM Confirm that v1.3 has better perfomance! @Jean_Luc Thank you for job!
First key in range 2^80 found in [01:15:13] with 8 dead kangaroo. Code: Kangaroo v1.3 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 24, 2020, 08:18:43 PM Confirm that v1.3 has better perfomance! @Jean_Luc Thank you for job! First key in range 2^80 found in [01:15:13] with 8 dead kangaroo. Many thanks for testing, you should to decrease a bit your grid size, you have a too small dp for a 2^80 range and a large RAM usage. Could you try with -g 136,128 or -g 68,256 or even -g 68,128, thanks. This GPU should be quite good at 2^88 range with nominal settings ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 24, 2020, 10:13:16 PM Quote Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000 Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48FFFFFFFFFFFFFFFFFFFF Good night Supermans !!! My brain cant sleep becouse this megathread. :-) Please explain me, why always used this start-stop ranges ? This ranges, as I right ubdersta d NOT FOR ANY publick keys and if I will use publick key not from this thread I will be needed enother ranges Yes or .... ??? p.s. BEEEEEEEEEG THENKS FOR ALL OF YOU !!! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 24, 2020, 10:49:10 PM -snip- Please explain me, why always used this start-stop ranges ? -snip- We just use the same public keys and ranges in order to test different devices and help JeanLuc to develop his program. If we use different ranges and keys it will be a little bit difficult to undertand the real improvement of the program performance. The 16 public keys were generated by odolvlobo just for test purposes earlier in this topic: https://bitcointalk.org/index.php?topic=5238719.msg54184513#msg54184513 The initial range was only 2^64 width, and now we see that this range is too small for the program (the key is found just for 1 minute or less). So for test purposes Etar decided to make the key range wider up to 2^80 (just change the start and end range). And at the moment we use that enlarged ranges, together with the same 16 public keys. If you read that test post by odolvlobo you could find that he made a challenge: "I'll give you a whole day to find the private keys for these 16 public keys. ... If you can do that, I'll be impressed. I don't think that you can find 4". But, JeanLuc accepted this challenge and developed his own tool on CUDA, and after some days we see that all 16 keys in the range 2^64 could be found just for 10 minutes. There is no need 24 hours for it! This was the explanation why we use that ranges. However, answering on your question, of course you can use any ranges you want and public keys you want. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 25, 2020, 11:56:11 AM Tried v1.3 with 80bit ranges.
The speed increased by 5-7% in v1.3 compared to v1.2. BUt as the range wider, the "luck" is very important thing. First, i tried 16 keys with the same 80 bit ranges: Code: $ ./kangaroo -t 0 -gpu in16_80.txt The firt five keys were solved for 706 minutes, i.e 141 min per key (2h20min/key). The total time per key is very different and vary from 43 minutes to 4h29min. Then I tried the same keys but with adjustment to the range and public keys (deducted start range from everything): Code: $ ./kangaroo -t 0 -gpu in16_80adj.txt I stoped the process after 3 keys were solved. For 3 such keys it needed 292 minutes or 97min per key (1h37min / key). The average time was more predictable like 2 hours per key. I doubt again if such range/pubkey adjustments could improve the progress. May be the initial kangaroos allocation is more effecient in the adjusted ranges? But more tests are required in order to prove it (3 or 5 key are not enough...) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 25, 2020, 12:56:08 PM -snip- Please explain me, why always used this start-stop ranges ? -snip- We just use the same public keys and ranges in order to test different devices and help JeanLuc to develop his program. If we use different ranges and keys it will be a little bit difficult to undertand the real improvement of the program performance. The 16 public keys were generated by odolvlobo just for test purposes earlier in this topic: https://bitcointalk.org/index.php?topic=5238719.msg54184513#msg54184513 The initial range was only 2^64 width, and now we see that this range is too small for the program (the key is found just for 1 minute or less). So for test purposes Etar decided to make the key range wider up to 2^80 (just change the start and end range). And at the moment we use that enlarged ranges, together with the same 16 public keys. If you read that test post by odolvlobo you could find that he made a challenge: "I'll give you a whole day to find the private keys for these 16 public keys. ... If you can do that, I'll be impressed. I don't think that you can find 4". But, JeanLuc accepted this challenge and developed his own tool on CUDA, and after some days we see that all 16 keys in the range 2^64 could be found just for 10 minutes. There is no need 24 hours for it! This was the explanation why we use that ranges. However, answering on your question, of course you can use any ranges you want and public keys you want. Big Thank You Bro. I caryfuly reading all mesages. 😊 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 25, 2020, 12:59:06 PM Tried v1.3 with 80bit ranges. The speed increased by 5-7% in v1.3 compared to v1.2. BUt as the range wider, the "luck" is very important thing. First, i tried 16 keys with the same 80 bit ranges: Code: $ ./kangaroo -t 0 -gpu in16_80.txt The firt five keys were solved for 706 minutes, i.e 141 min per key (2h20min/key). The total time per key is very different and vary from 43 minutes to 4h29min. Then I tried the same keys but with adjustment to the range and public keys (deducted start range from everything): Code: $ ./kangaroo -t 0 -gpu in16_80adj.txt I stoped the process after 3 keys were solved. For 3 such keys it needed 292 minutes or 97min per key (1h37min / key). The average time was more predictable like 2 hours per key. I doubt again if such range/pubkey adjustments could improve the progress. May be the initial kangaroos allocation is more effecient in the adjusted ranges? But more tests are required in order to prove it (3 or 5 key are not enough...) Bro, can you explain more detailed how to modyfy publick key ? I was readyng all your messages but not understand, but I think this is very interesting method to -delet all not neede info from keys for improve calculation.... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 25, 2020, 01:15:04 PM Bro, can you explain more detailed how to modyfy publick key ? I was readyng all your messages but not understand, but I think this is very interesting method to -delet all not neede info from keys for improve calculation.... This is just due basic ECC calculations. But I am not sure it could be important here. Let's say that the public key Q is within the range [a, b] where a is minimum and b is maximum. I can adjust the range to [a-a, b-a] which is actually [0, b-a] and also adjust the Q in order "to solve the same problem", so the Qadj = Q - a*G where G is the basis Point. In other words I find the public key for the number a which is a*G and make the ECC substraction Q - a*G which is the Qadj. Now we try to solve adjusted public key Qadj within the range [0, b-a] and as soon as we find the key, we can easily retrieve the real target private key just adding a to the found one. If you are not familiar with ECC calculation, try to play with java made ECC calculator. It is not quick, but can make basic ECC calcualtions: point additions, point substraction, point multiplcation by a number, point division. That ECC calcualtor is here: https://bitcointalk.org/index.php?topic=5202064.0 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 25, 2020, 01:35:10 PM I doubt again if such range/pubkey adjustments could improve the progress. May be the initial kangaroos allocation is more effecient in the adjusted ranges? But more tests are required in order to prove it (3 or 5 key are not enough...) Many thanks for the tests ;) They looks very good ! The translation you did is equivalent to what the code do so the result should be equal. The new spreading of kangaroos gives more chance to a key in the middle of the range to be found. At first, a key close to the end of range was harder to find and a key near to the beginning was easier. It more logical to have a spreading from the middle. By expending the range of the odolvlobo's test to 80bit, all the 16 keys are very close to each others and near the end of the range (0xCB5E.....) We should make tests of uniformly distributed key in the range. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: PietCoin97 on April 25, 2020, 10:37:23 PM i let the new 72 bit test file run this is result (newest version of all kangaroo files)
Code: Kangaroo.exe -t 0 -d 20 -gpu -gpuId 0,1,2,3,4,5 in72_20.txt Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 26, 2020, 05:36:38 AM Many thanks for testing ;)
I added some information on expected number of operation and needed memory. On my test it gives: Avg Mem=188.0 MB (Theoretical 191.0MB) Avg Count=37.19 (Theoretical 2^37.25) Theoretical results are not so bad here, but when you increase the dp, theoretical values become too large because calculation are here done using the asymptotic 2.sqrt(n) + nbKangaroo.2^dp which becomes bad when dp increase. n is the range size. For instance of the test done by PietCoin97 (with dp=20), it gives: Expected operations: 2^42.52 (Measured 2^39.42) Expected RAM: 460.4MB (Measured 58.5MB) It is difficult to get the analytical expression of the theoretical values. If anyone can help to find the analytical expression, it would be great. To find the analytical expression , you have to consider that the extra operation due to dp (nbKangaroo.2^dp) also increase the number of points and increase the probability to find a collision due to the birthday paradox. So the analytical expression should be something like: 2.sqrt(n) + f(nbKangaroo,dp) where f(nbKangaroo,dp) is a function with an asymptotic equal to nbKangaroo.2^dp. Calculation of probability on the birthday paradox are rather complex :( Here are 2 loglog plots showing the asymptotic (in blue) for some dp and 40 bit search on a classical birthday paradox with a theoretical average of sqrt(PI/2)*sqrt(n) (instead of 2.sqrt(n) in the kangaroo case): Red plots are experimental plots (averaged on 1000 searches) https://raw.githubusercontent.com/JeanLucPons/BTCCollider/master/img/hash160_col40.jpg https://raw.githubusercontent.com/JeanLucPons/BTCCollider/master/img/hash160_col40_asymptote.jpg Code: Kangaroo v1.3 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: PietCoin97 on April 26, 2020, 09:35:05 AM Jean Luc i made a new test run with 72 bit file with db 16 !
here is result Code: Kangaroo.exe -t 0 -d 16 -gpu -gpuId 0,1,2,3,4,5 in72_20.txt I also try it with standard settings with no change and it was terrible (system use db 11 as standard ) Ram usage goes up really fast and speed decrease really fast Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 26, 2020, 11:34:02 AM -snip- The translation you did is equivalent to what the code do so the result should be equal. -snip- It late to read it, I have alreade compared initial ranges and the adjusted ranges for 16 keys in 75bit ranges. And yes, the result is more or less the same. See below. -snip- By expending the range of the odolvlobo's test to 80bit, all the 16 keys are very close to each others and near the end of the range (0xCB5E.....) We should make tests of uniformly distributed key in the range. -snip- Actually where is the key should not be important, we just should know the range. But for better test purposes I generated the 16 keys equally distributed within the range 2^75 width: - generated random 256bit number as the Start Range - generated 16 random 75bit numbers in the range [0, 2^75] - added the received 16 random numbers to the start range and received 16 numbers in the range [Start Range; Start Range + 2^75] - generated the corresponding public keys and made the tests with Kangaroo v1.3 For 16 keys in 75bit range I needed 5h43min, i.e. 21:27min per key. Code: $ ./kangaroo -t 0 -gpu in16_75.txt Then I made the adjustments and deducted Start Range from every key and the range as well, so now the range to search become [0, 2^75]. The total time to search for the adjusted keys was 5h23min, i.e. 20:10min per key. So the total time is more or less the same. The reason the 1st test was longer because 2 keys were found for 43 and 51 min (2 times longer than average) with 4-5 dead kangaroos comapred to average 0-1 dead kangaroos. So, just not lucky ones :) I think these are good results. The main thing here is the Count value for every key. All my keys were within the range 2^75 width, so the direct brutforce needed 2^75 operations. The expected average for pollard kangaroo method is (1.818 + o(1))SquareRoot(2^75) = 2^38.36 /* Why 1.818 square root? - see here https://arxiv.org/pdf/1501.07019.pdf */ Among the 32 total tests 24 keys were found for longer than 2^38.36 and 8 keys were found for less than 2^38.36. This results is very good I think. I did not expect 50%/50% for 32 tests. 8 keys found for less than the expected theoretical average number of operations is quite good. PS. The program says Range width: 2^76 for my range Start:0 - Stop :8000000000000000000, however it is exactly 2^75. The same shows for the 1st tests - 2^76 howver the range width is 2^75 only. I mention for the pruposes of direct brute force determination. For my ranges it is 2^75, and not 2^76. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 26, 2020, 12:49:05 PM May thanks again for all these tests ;)
I think these are good results. The main thing here is the Count value for every key. All my keys were within the range 2^75 width, so the direct brutforce needed 2^75 operations. The expected average for pollard kangaroo method is (1.818 + o(1))SquareRoot(2^75) = 2^38.36 /* Why 1.818 square root? - see here https://arxiv.org/pdf/1501.07019.pdf */ This result is for a "3 kangaroos non parallel method". 2 Wilds, one starting at (k2+k1)/2 and one starting at k1 - (k2-k1)/2 and a Tame stating at k1 + 3(k2-k1)/10, 10 divide k2-k1. Here we have a large number of Tames and Wilds, Tames start between k1 and k2 and wild starts between k1 - (k2-k1)/2 and (k2+k1)/2. I must says that I don't know the exact factor of sqrt(N), I assume it was 2 but it may be a bit less. PS. The program says Range width: 2^76 for my range Start:0 - Stop :8000000000000000000, however it is exactly 2^75. The same shows for the 1st tests - 2^76 howver the range width is 2^75 only. I mention for the pruposes of direct brute force determination. For my ranges it is 2^75, and not 2^76. Yes, the range is [Start,Stop] , so Start and Stop included, 2^75 + 1 will be rounded to 2^76. So for 0..8000000000000000000, you should specify 0..7FFFFFFFFFFFFFFFFFF Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 26, 2020, 02:39:57 PM -snip- Yes, the range is [Start,Stop] , so Start and Stop included, 2^75 + 1 will be rounded to 2^76. So for 0..8000000000000000000, you should specify 0..7FFFFFFFFFFFFFFFFFF Ok, noted. For large numbers (2^75+1) rounded to 2^76 makes very big difference (2 factor). This dos not affect the program speed, however there is no need to show the width range in integer power of 2. I guess that the range width lets say 2^75.01 also applicable. If take log2(Stop-Start) the width 2^75+1 will not be rounded to 2^76 but will be showed as 2^75 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 26, 2020, 03:20:42 PM Yes you're right but I have no conversion routine from int256 to double.
And the precision should be enough for the floor function, it is important that the program runs with the good range as it is use for the jump table. I will try to improve things. Still fighting with the memory and operation estimation... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: PietCoin97 on April 26, 2020, 05:06:59 PM Jean luc when do you add multi pub key search and how would it be work?
Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 26, 2020, 05:16:00 PM Jean luc when do you add multi pub key search and how would it be work? I would like first to finalize the calculation of estimated memory and operation (important to tune the dp) and the save/load/merge work. Then I will implement multiple key. The basic idea for multiple keys is to start wild kangaroos with different keys. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: PietCoin97 on April 26, 2020, 07:28:12 PM OK but can you maybe add first multi pub key search and after that you can optimize all together?
Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: dextronomous on April 26, 2020, 08:10:51 PM hi Jean_Luc.
was wondering if it was possible to have a verbose method available, to see a bit more details. about wich range or space it is at. thanks a lot great software very fast. especially 1.3 8) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 27, 2020, 06:06:19 AM OK but can you maybe add first multi pub key search and after that you can optimize all together? Helli. You have multi GPU balid. You can work from one to next target fine. Other members in this thread have only one GPU !!! I think this thread for no brain-less people with single GPU bitcoin miners ;) Have a nice day. P.s. Luc, please do not share code for multy key finder. In future year, after we are making all test s ;-)share sach code will be fine I thinck. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 27, 2020, 06:21:56 AM OK but can you maybe add first multi pub key search and after that you can optimize all together? What pubkey you interested ? Mining pubkey in very hard task I think, and very needed first. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 27, 2020, 06:26:02 AM Jean luc when do you add multi pub key search and how would it be work? I would like first to finalize the calculation of estimated memory and operation (important to tune the dp) and the save/load/merge work. Then I will implement multiple key. The basic idea for multiple keys is to start wild kangaroos with different keys. Beeeeeegest thank you Jean_Luc. I think your relise will be great again :))) like all your previous relises. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 27, 2020, 07:26:14 AM I did a test, wanting to know the average time of the birthday paradox when searching collision between 2 tables (like the kangaroo problem).
The kangaroo method is announced to be 2.sqrt(n) but this is for a simple 2 stages algorithm where: - you first travel a single tame kangaroo sqrt(n) steps to setup a trap - then you make steps with the wild until a collision occurs (it falls in the trap), this second stage is expected to end in sqrt(n) steps. The factor 2 comes from that. There no need of a hashtable there. I did a test on 1.000.000 searches (24bits) using a table: [ 999999] (2^12.825836) (Theoretical 2^12.825748) It ends in sqrt(PI).sqrt(n) ~= 1.772.sqrt(n) Note that the precision afer 1.000.000 trials is about 1/sqrt(1.000.000)=0.001 so 3 digits are expected to be good. 2^0.825836 = 1.77256 , sqrt(PI) = 1.77245 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 27, 2020, 11:48:06 AM -snip- It ends in sqrt(PI).sqrt(n) ~= 1.772.sqrt(n) Note that the precision afer 1.000.000 trials is about 1/sqrt(1.000.000)=0.001 so 3 digits are expected to be good. 2^0.825836 = 1.77256 , sqrt(PI) = 1.77245 Your empirical tests actually showed the results very closed to benchmark for Kangaroo known algorithm. Yes, the 2*sqrt(n) was for simple Kangaroo method. This is a very nice reading as well: https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch14.pdf For three-kangaroo it is 1.818*sqrt(n) - Excercise 14.5.11 in reading above For four-kkangaroo it is 1.714*sqrt(n) - Excercise 14.5.12 in reading above You are using herds of kangaroos, so it is not simple one. Can you please also have a look at the 14.6 section of the reading above? There is a Distributed Kanagroo Algorithm: let Np is the number of processors; [0, w] is the range. They divide the interval into Np sub-intervals of size w/Np and then run the kangaroo algorithm in parallel on each sub-interval. The solution is to use a herd of Np/2 tame kangaroos and a herd of Np/2 wild kangaroos. This gives an algorithm with running time O(sqrt(w/Np)). How do you tink, will it be faster? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 27, 2020, 12:35:28 PM Your empirical tests actually showed the results very closed to benchmark for Kangaroo known algorithm. Yes, the 2*sqrt(n) was for simple Kangaroo method. The test i did was a simple calculation on a classical birthday paradox on 2 tables instead of one. I draw alternatively a random number in [0..N[ in each table and look for collision between the 2 tables. This converges to sqrt(PI.N). sqrt(PI/2.N) on a single table. Now, I'm doing tests a in real situation, 1024 kangaroos, 10000 40 bit keys informally distributed, for the moment it seems to converge to 2.sqrt(N) + nbKangaroo.2^dp as expected, with dp=7 on 40bit search. In this situation (1024 << sqrt(N) - 2^dp), the approximation using the asymptote is good. How do you tink, will it be faster? Thanks for the reading. No I don't think it will be faster Example for Np=2, you have 2 ranges of w/2 so you perform a total of operation: 2.sqrt(w/2) + 2.sqrt(w/2) = 4/sqrt(2).sqrt(w) which is more than 2.sqrt(w) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 27, 2020, 05:24:49 PM I published an exe file for Windows: https://github.com/JeanLucPons/BSGS/releases/tag/1.0 Hi, I tested on my ubuntu 17.04 (and a mobile cpu: Intel(R) Xeon(R) CPU E3-1505M v6 @ 3.00GHz) your BSGS program (https://github.com/JeanLucPons/BSGS/) with a 64 bit key: Code: input file Results: Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 Done: Total time 22:49 Then I replaced only this function void void Int::ModMulK1(Int *a, Int *b) (https://github.com/JeanLucPons/BSGS/blob/master/SECPK1/IntMod.cpp#L856) with a my function and I get this result: Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 Done: Total time 20:00 Time ago I did a my version of the break-short (https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89) program: time ./break-short Build Hash Search Keys Error!!! False collision! Error!!! False collision! Build Hash Search Keys Error!!! False collision! Found private key 1: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4 real 11m58,270s A note: your program uses 9 GB RAM and 8 cores (for the giant steps), my version of break-short uses 8 GB RAM and only 1 core. ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- When I use 18 GB RAM: Code: input file your program: Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 Done: Total time 18:19 your program with my function: Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 Done: Total time 17:15 my version of break-short program (16 GB RAM): time ./break-short Build Hash Search Keys Error!!! False collision! Found private key 1: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4 real 5m54,964s If I could use parallel programming and exploit all my 8 cores, I think it would take probably less than 3 minutes to crack a 64 bit key only with a cpu. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 27, 2020, 06:01:44 PM Hi arulbero :)
The key you tested are ...7F2F1A1DDF3E9FF8 so near the worst case if you run with 8 thread. or ...BB3EF3883C1866D4 idem I didn't optimized this program up to the ninja level, I spend time on the Kangaroo one ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 27, 2020, 06:16:30 PM ./kangaroo -d 8 input
Kangaroo v1.3 Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000 Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF Keys :1 Number of CPU thread: 8 Range width: 2^64 Number of random walk: 2^13.00 (Max DP=17) DP size: 8 [0xff00000000000000] SolveKeyCPU Thread 4: 1024 kangaroos SolveKeyCPU Thread 1: 1024 kangaroos SolveKeyCPU Thread 5: 1024 kangaroos SolveKeyCPU Thread 2: 1024 kangaroos SolveKeyCPU Thread 3: 1024 kangaroos SolveKeyCPU Thread 7: 1024 kangaroos SolveKeyCPU Thread 0: 1024 kangaroos SolveKeyCPU Thread 6: 1024 kangaroos [16.09 MKey/s][GPU 0.00 MKey/s][Count 2^33.42][Dead 3][13:26][3423.9MB] Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 Done: Total time 13:44 with my function in IntMod.cpp: ./kangaroo -d 8 input Kangaroo v1.3 Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000 Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF Keys :1 Number of CPU thread: 8 Range width: 2^64 Number of random walk: 2^13.00 (Max DP=17) DP size: 8 [0xff00000000000000] SolveKeyCPU Thread 5: 1024 kangaroos SolveKeyCPU Thread 3: 1024 kangaroos SolveKeyCPU Thread 1: 1024 kangaroos SolveKeyCPU Thread 0: 1024 kangaroos SolveKeyCPU Thread 2: 1024 kangaroos SolveKeyCPU Thread 6: 1024 kangaroos SolveKeyCPU Thread 4: 1024 kangaroos SolveKeyCPU Thread 7: 1024 kangaroos [21.08 MKey/s][GPU 0.00 MKey/s][Count 2^32.47][Dead 0][05:16][1774.8MB] Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 Done: Total time 05:26 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 27, 2020, 06:37:16 PM I presume the main differences between your ModMul function (if it is still the same you give me) and mine are in:
imm_umul() where I use intrinsic functions and where you have used inline assembly. On windows it is not possible to do inline assembly, gcc support intrinsic functions so it should generate a good code. I really don't want to fight with inline assembly on Linux and this horrible AT&T syntax, i did few ones where no intrinsic exists, this was a nightmare... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 27, 2020, 08:09:46 PM I presume the main differences between your ModMul function (if it is still the same you give me) and mine are in: imm_umul() where I use intrinsic functions and where you have used inline assembly. On windows it is not possible to do inline assembly, gcc support intrinsic functions so it should generate a good code. I really don't want to fight with inline assembly on Linux and this horrible AT&T syntax, i did few ones where no intrinsic exists, this was a nightmare... Yes, you're right. Besides when I compile I get this message: warning: #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" [-Wcpp] #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" Maybe with a new version of gcc the performance of your function would be better on my system. I replaced ModSquareK1(Int *a) too: ./kangaroo -d 8 input Kangaroo v1.3 Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000 Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF Keys :1 Number of CPU thread: 8 Range width: 2^64 Number of random walk: 2^13.00 (Max DP=17) DP size: 8 [0xff00000000000000] SolveKeyCPU Thread 0: 1024 kangaroos SolveKeyCPU Thread 2: 1024 kangaroos SolveKeyCPU Thread 3: 1024 kangaroos SolveKeyCPU Thread 1: 1024 kangaroos SolveKeyCPU Thread 7: 1024 kangaroos SolveKeyCPU Thread 4: 1024 kangaroos SolveKeyCPU Thread 6: 1024 kangaroos SolveKeyCPU Thread 5: 1024 kangaroos [24.33 MKey/s][GPU 0.00 MKey/s][Count 2^33.42][Dead 2][08:56][3440.8MB] Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 Done: Total time 09:15 from 16 to 24 MKeys/s, +50% ... EDIT: 2**(33.42) keys / (13*60+44)s = 13.947.463 = 14 MKeys/s your program 2**(32.47) keys / (5*60+26)s = 18.248.465 = 18,2 MKeys/s ModMul replaced 2**(33.42) keys / (9*60+15)s = 20707585 = 20,7 MKeys/s ModMul+ModSqr replaced 2**(33.24) keys / (7*60+58)s = 21223116 = 21,2 MKeys/s ModMul+ModSqr+ModSub replaced from 14 to 21,2 MKeys/s: +50% Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 27, 2020, 08:34:31 PM Quote from: arulbero [/quote Hello Arulbero. Can you modyfi your break-short code for import pubkeys from .txt files ? This very hard recompile and edit code for run tests. Big thank you. Have a nice time in this thread. ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 27, 2020, 08:39:20 PM warning: #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" [-Wcpp] #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" Yes, do you remenber this ? We have fighting with a f.ck.ng bug when you have implemented the ModSqr function, i had to add a volatile to prevent gcc to perform optimization ! This volatile is not necessary for gcc > 7.3 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 27, 2020, 08:57:41 PM warning: #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" [-Wcpp] #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" Yes, do you remenber this ? We have fighting with a f.ck.ng bug when you have implemented the ModSqr function, i had to add a volatile to prevent gcc to perform optimization ! This volatile is not necessary for gcc > 7.3 Ok, I tried with "unsigned char c" (I removed the check): from 2**(33.42) keys / (13*60+44)s = 13.947.463 = 14 MKeys/s your program with volatile to 2**(32.18) keys / (4*60+12.0)s = 19.308.330 = 19,3 MKeys/s with unsigned char and the bug is still there, with unsigned char I get this error: ./kangaroo -d 8 input Kangaroo v1.3 ParsePublicKeyHex: Error invalid public key specified (Not lie on elliptic curve) input, error line 2: 0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED8 87AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8 Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000 Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF it's weird that the program doesn't stop, I think it should terminate in this case. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 27, 2020, 08:59:17 PM arulbero you giant-step code down then not enoth memory to ?
Title: nullius does >100 trillion operations per second on a 3.3 GHz CPU! Post by: nullius on April 29, 2020, 07:09:46 AM Etar, you are funny person. Yes, you just overestimate the rate. It is known that due to pollard kanagaroo method it is possible to perform less bruteforce operations. And roughly it is square root from the total length. You just count the operations which are not actually performed. You use the method which is good due to birthday paradox. However, due to this methond you just need less operations. So, your actual speed is not 2.2Ph/s but the square root from this amount, i.e. approx. 47 Mh/s in total. I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM. It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation. If I convert to the Etar's unit: It does 14.6 PKey/s. Newsflash: I, nullius, have written a very small shell script that can do over 100 trillion operations per second on a single core of an ancient 3.3 GHz CPU! Here is the source code, including a benchmark, on a Linux system (FreeBSD will be a bit different): Code: $ echo '1048576^1024' | time -p bc -sql Well, you see, I realized that an exponentiation is just a bunch of multiplications. In this case, 1024 multiplications—and each of those multiplications is 1,047,576 additions. Thus, I have done 1,073,741,824 additions in 0.01 seconds. But wait! If expressed in tally-style unary units, each operand of each of those additions is 1,048,576 additions of the number 1. Thus, in my units, this counts as 1,125,899,906,842,624 operations in 0.01 seconds. Ergo, >100 trillion operations per second on a CPU that is almost nine years old. A genius, am I. Sadly, I am still only in the “tera” range; but surely, if I were to play semantic games a bit more, I could boost myself into the “peta” range as OP did—or even beyond him, into the “exa” range. This is well know since the beginning of elliptic curve usage in crypto. But we count the number of group operation really performed (not the size of the range divided by time). Soooo... Let me get this straight: OP, who has a past history of prolific posting in shitcoin threads before some long post history gaps, suddenly “woke up” and started posting in Development & Technology with wild claims backed only by semantic games and insulting the intelligence of people who know far more than he does. I did not bother to read the whole thread, which is now nearly 10 pages. Did I miss anything? I will give a final explanation of how this works. *************************************** Extraordinary claims backed by poorly-written explanations riddled with semantic games are the mark of either a crackpot or a scammer. Take your pick. I think yo do not understand what are you talking... Clearly you're looking to fool people who don't, sadly for you I'm not one of them. Though the fact that you don't recognize that I do is odd...Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU Post by: Lauda on April 29, 2020, 07:51:23 AM Tagged this user named Etar for intellectual dishonesty/trying to fool newbies. Do not forget this:
Quote Trust summary for Etar This user recently woke up from a long period of inactivity. I think yo do not understand what are you talking... Clearly you're looking to fool people who don't, sadly for you I'm not one of them. Though the fact that you don't recognize that I do is odd...Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Etar on April 29, 2020, 09:25:50 AM @lauda, @ nullius
You are just bored and you decided to flood here? If you have not read the whole topic, or at least a few pages, then you should not write here. For people who have problems with trust in people and who see scam in any person, I will repeat I created the topic because I didn’t know that algorithms such as bsgs or kangaroos had existed for a long time. In fact, I just shared information and nothing more, and adequate people explained to me that this is not new, but long known. I did not publish codes, I did not upload releases, so that I could be accused of something. But it seems like some people just don’t have enough manners in communication. One reason why i still look here is to find out how things are going Jean_luc with his kangaroo algorithm. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Lauda on April 29, 2020, 09:28:24 AM In fact, I just shared information and nothing more, and adequate people explained to me that this is not new, but long known. I will rather consult monkeys from the local zoo before I consult you. Please do not post any more of your "information". Title: Re: nullius does >100 trillion operations per second on a 3.3 GHz CPU! Post by: odolvlobo on April 29, 2020, 09:37:49 AM I did not bother to read the whole thread, which is now nearly 10 pages. Did I miss anything? Yes, you did. The thread is 10 pages because there is stuff going on here, despite the ridiculous title. Tagged this user named Etar for intellectual dishonesty/trying to fool newbies. Do not forget this: You are wrong. You didn't bother to read the thread and you just copy-pasted gmaxwell's undeserved negative trust. Etar doesn't deserve the negative trust. He claimed rates that are clearly impossible, but that is because his measurement methodology is flawed. He was not lying or trying to misrepresent anything. He was just wrong. The fact that I challenged him to find 16 specific private keys in a 264 range and he succeeded clearly demonstrates that he has accomplished something. If you want to know the details, you'll have to read the thread. Title: Re: nullius does >100 trillion operations per second on a 3.3 GHz CPU! Post by: Lauda on April 29, 2020, 09:41:55 AM He claimed rates that are clearly impossible, but that is because his measurement methodology is flawed. He was not lying or trying to misrepresent anything. He was just wrong. Insisting that you are right or that you are providing knowledge when you have been proven wrong is malicious, therefore the rating.The fact that I challenged him to find 16 specific private keys in a 264 range and he succeeded clearly demonstrates that he has accomplished something. Yes, and I am Santa Claus.Don't try to teach me how to use the trust system, you have no idea what you are talking about in that aspect. Title: Re: nullius does >100 trillion operations per second on a 3.3 GHz CPU! Post by: nullius on April 29, 2020, 11:20:09 AM I did not bother to read the whole thread, which is now nearly 10 pages. Did I miss anything? Yes, you did. The thread is 10 pages because there is stuff going on here, despite the ridiculous title. If you have not read the whole topic, or at least a few pages, then you should not write here. University professors of the sciences regularly receive e-mails from cranks claiming to have invented perpetual motion machines, free energy devices, simple cures for cancer, etc., etc. (I know this, because I used to have someone forwarding those to me for my amusement.) Would you blame them for not wasting their time reading things that are facially incredible and, moreover, presented in the manner of arrogant ignorance? The topic title, “brute-forcing public keys at amazing speed 2.2 PH/s on CPU”, is not only ridiculous because of the “2.2 PH/s” claim that I parodied (https://bitcointalk.org/index.php?topic=5238719.msg54322014#msg54322014): Nobody who knows anything whatsoever about elliptic curve cryptography would ever talk about “brute-forcing public keys”. It is stunningly ignorant. I say that, having some history here of pointing out that Bitcoin’s secp256k1 has a 128-bit security level (https://bitcointalk.org/index.php?topic=2859033.0). I made that thread because I was sick and tired of people yammering about how long it would take to bruteforce a 2256 keyspace. If an attacker were to use a bruteforce attack, trying keys one by one, that would require on the order of 2256 work. (I here ignore the restrictions on valid secp256k1 keys, which reduces that to about 2255.5; the difference would be negligible in practical terms, and it’s anyway not here relevant.) However, no serious attacker would ever try to bruteforce elliptic-curve crypto. Rather, it is estimated that breaking Bitcoin’s 256-bit keys with the best known attacks should require around 2128 work [...] Although I didn’t read this whole thread, I skimmed Etar’s posts from his post history page. It is easy, because he has been exclusively posting in this thread since 2020-04-07 (https://bitcointalk.org/index.php?topic=5238719.msg54177213#msg54177213). Before that, his last post was in a shitcoin thread on 2019-02-06 (https://bitcointalk.org/index.php?topic=5104608.msg49616785#msg49616785). I also noticed what others here seem not to, at least not in the first few pages which I did read: Etar appears to have no history of posting in D&T, at least not that I could find on a cursory check. He used to post prolifically in shitcoin threads. In 2017–19, the account had several large posting gaps; then it was dormant for over a year. It seems to have the same style as before; but that is easy, when the style is basically gibberish. Anyway, the account suddenly woke up and immediately, exclusively started pushing this thread in a know-it-all belligerent manner. Let me get this straight: OP, who has a past history of prolific posting in shitcoin threads before some long post history gaps, suddenly “woke up” and started posting in Development & Technology with wild claims backed only by semantic games and insulting the intelligence of people who know far more than he does. @lauda, @ nullius You are just bored and you decided to flood here? Back at you. Post history is the kind of thing that Lauda would notice... Don't try to teach me how to use the trust system, you have no idea what you are talking about in that aspect. ...indeed. The fact that I challenged him to find 16 specific private keys in a 264 range and he succeeded clearly demonstrates that he has accomplished something. If you want to know the details, you'll have to read the thread. Eh... This is well know since the beginning of elliptic curve usage in crypto. But we count the number of group operation really performed (not the size of the range divided by time). For instance in my BTCollider which use the DP method (also in O(sqrt(n))), I get 27.9 Mips (GeForce GTX 1050 Ti) for 80bit collision search. That means that I really compute 27.9M group operation and hash per second. It solves 80bit collision in 14h30 (in average). Note that in that case, it have to compute an EC mult for each group operation. https://github.com/JeanLucPons/BTCCollider Most famous Square root methods: - Baby-step Gian-step - Pollard's Rho algorithm - Pollard's kangaroo algorithm Have a look this link as well: https://www.embeddedrelated.com/showarticle/1093.php You guys are so smart here, I even feel awkward. [...discussion continued right up to the top of this page.] So... after others drew him an introductory map of methods better than brute-force, Etar managed to find your challenge keys in a 264 range? It is manifestly unimpressive for someone with this attitude: ~ if you do not know how, this does not mean that it is impossible.I'm not going to post programs, source codes or algorithms. It's just a fact. ~ I think yo do not understand what are you talking...And if you do not understand the topic, But it seems like some people just don’t have enough manners in communication. You are not one to be lecturing others on “manners in communication”. Your rudeness is as bad as your conceited ignorance. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 29, 2020, 11:59:02 AM The topic started from one things, and continued with others. TC was wrong in some things, however he understood it. However he created a "marketing" name attracted JeanLuc developer and motivated him (i beleive) to continue his job with BSGS annd Kanagroo codes.
Here the message their Jean_Luc promissed to develop ECDLP solver: https://github.com/JeanLucPons/BTCCollider/issues/3 This topic helped to force that work, and JeanLuc finished his BSGS: https://github.com/JeanLucPons/BSGS and later Kangaroo on GPU: https://github.com/JeanLucPons/Kangaroo The last one (Kangaroo) is amazing. Many thanks to Jean_Luc! Jean_Luc, i suggest you to create a separate topic about your Kangaroo program and continue discussions there. We can collect some main things (method, tests, benchmarks, etc) and post them in the 1st message of new topic. What do you think about this? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 29, 2020, 12:04:04 PM Yes I agree to open an other topic, I'm still fighting to get the average running time in function of dp and nbKangaroo, this is quite complex and I got unexpected results but interesting ;)
I'll open the new thread when I ends my statistics. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: NotATether on April 29, 2020, 06:55:38 PM Yes I agree to open an other topic, I'm still fighting to get the average running time in function of dp and nbKangaroo, this is quite complex and I got unexpected results but interesting ;) I'll open the new thread when I ends my statistics. It's been very interesting seeing the results from doing kangaroo hops, so I support this decision. And then this thread should be locked since we seem to be getting derailed. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 29, 2020, 06:59:34 PM I did a test, wanting to know the average time of the birthday paradox when searching collision between 2 tables (like the kangaroo problem). The kangaroo method is announced to be 2.sqrt(n) but this is for a simple 2 stages algorithm where: - you first travel a single tame kangaroo sqrt(n) steps to setup a trap - then you make steps with the wild until a collision occurs (it falls in the trap), this second stage is expected to end in sqrt(n) steps. The factor 2 comes from that. There no need of a hashtable there. Hi, let's see if I have understood this Kangaroo algorithm: P=k*G, you know P and you know that a < k < b, for semplicity : 0 < k < a, for example: 0 < k < 2^64 (starting interval) you generate many sequence of 2 type of points: 1) tame: each sequence starts from a random point T0 that lies in the starting interval, then T0, T1, T2, …. the difference between 2 consecutive points is: G, or 2*G, or 4*G, or 8*G, …, or 2^32*G 2) wild: each sequence starts from P + r*G, where r*G is a random point with a random r private key between 0 < k < 2^31), then: W0, W1, W2, ….. the difference between 2 consecutive points is: G, or 2*G, or 4*G, …, or 2^32*G each jump towards the next point depends on the x coordinate (mod 33) of the current point; in this way if a tame kangaroo reach a points already reached from a wild kangaroo (or viceversa), you have a collision and then same path from there. In that case T = W -> t*G = w*G -> t*G = P + w*G -> t*G = k*G + w*G -> k = (t-w) mod n Besides you use distinguished points to detect this collision. In this example you generate about 2^32 points (T points) in the interval [1*G, (2^64+(2^32)(2^32))*G] and about 2^32 points (W points) in the interval [P+r*G, ((k+r)+(2^32*2^32))*G] let's say that both type of points have for sure their private keys in [1, 2^65] interval But can you treat these points like if they were random? Can you apply in this case the birthday paradox? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 29, 2020, 07:23:27 PM -snip- But can you treat these points like if they were random? Can you apply in this case the birthday paradox? The DP method (distinguished points) with a hashtable is used. That means that every subsequent jump is dependent from the x-coordinate of the current location. That means that pseudorandom walks are used for the kangaroos. No need to store all the visited points for this case. From here the definition (page 4, 1st par): https://eprint.iacr.org/2014/565.pdf a point is a distinguished point - if its representation exhibits a certain bit pattern, e.g., has the top 20 bits equal to zero. Whenever one of the parallel random walks reaches such a point it is stored on a central processor Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 29, 2020, 08:02:09 PM -snip- But can you treat these points like if they were random? Can you apply in this case the birthday paradox? The DP method (distinguished points) with a hashtable is used. That means that every subsequent jump is dependent from the x-coordinate of the current location. That means that pseudorandom walks are used for the kangaroos. No need to store all the visited points for this case. Yes, this is clear, but these points seem to me not to be really (pseudo)random. There is a order. You can move only forward (from private key's point of view). Therefor many collisions are just impossible to get (instead in the birthday paradox, each new distinguished point has the chance to produce a collision with any previous distinguished point, for example that happens in BTCCollider (https://github.com/JeanLucPons/BTCCollider), because in that case you can jump in any position, you go back and forth across the entire space) Example with only 2 sequences: If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure. Then how do you apply in this case birthday paradox? It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ... Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Tamarindei on April 29, 2020, 09:52:43 PM -snip- But can you treat these points like if they were random? Can you apply in this case the birthday paradox? The DP method (distinguished points) with a hashtable is used. That means that every subsequent jump is dependent from the x-coordinate of the current location. That means that pseudorandom walks are used for the kangaroos. No need to store all the visited points for this case. Yes, this is clear, but these points seem to me not to be really (pseudo)random. There is a order. You can move only forward (from private key's point of view). Therefor many collisions are just impossible to get (instead in the birthday paradox, each new distinguished point has the chance to produce a collision with any previous distinguished point, for example that happens in BTCCollider (https://github.com/JeanLucPons/BTCCollider), because in that case you can jump in any position, you go back and forth across the entire space) Example with only 2 sequences: If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure. Then how do you apply in this case birthday paradox? It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ... I think that's why the papers you find don't use the birthday paradox to analyze pollard kangaroo. Birthday paradox is used for the very similar gaudry schost algorithm. Gaudry schost algorithm sets the point to a new random location in the interval as soon as a distinguished point is found and saved. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: HardwareCollector on April 29, 2020, 10:51:52 PM Yes, this is clear, but these points seem to me not to be really (pseudo)random. There is a order. You can move only forward (from private key's point of view). Therefor many collisions are just impossible to get (instead in the birthday paradox, each new distinguished point has the chance to produce a collision with any previous distinguished point, for example that happens in BTCCollider (https://github.com/JeanLucPons/BTCCollider), because in that case you can jump in any position, you go back and forth across the entire space) Example with only 2 sequences: If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure. Then how do you apply in this case birthday paradox? It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ... Maybe the following links will help with understanding the motivations behind the Kangaroo method: https://web.northeastern.edu/seigen/11Magic/KruskalsCount/Kruskal'sCount.html https://web.northeastern.edu/seigen/11Magic/KruskalsCount/Pollard.pdf Pollard’s Rho method is based on the birthday paradox, but the Kangaroo method on the other hand is not. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 30, 2020, 01:29:12 AM -snip- If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure. -snip- I am not sure if I understand you correct. But T_101, T_102, ... etc are not the distinguished points, these are jump points. At the start only the jump point table is prepared. It is not possible to know all the distinguished points within the working range. Distinguished point is a property of point. As soon as the point meets this property, it goes to the hash table: if tamePosi is distinguished add (TAME,tamePosi,tamei) to hashTable if wildPosi is distinguished add (WILD,wildPosi,wildi) to hashTable The kangaroo (as wild so tame) will jump permanently by pseudorandom steps from the jump table while reach the Point with patterned X-coordinate (the distinguished point). As reach the distinguished point, this point just saved in the hashtable (kangaroo type, distance, Point) check for coliddion, and kangaroo continues to jump. -snip- It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ... The same kangaroo can not go back, but due to symmetry point it so not needed. P=k*G, you know P and you know that a < k < b. Actually Point P'=k'*G is also suitable for us if k' = b - (k-a) = b + a - k, which is also lies in the range a..b Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 30, 2020, 05:04:43 AM Yes the random walk with kangaroo is particular as the path cannot be truncated easily modulo n (n=range size). So the kangaroos can go outside of the range. This is not a problem as the 2 herds travel at the same average speed. The jumpDistane table has an average of sqrt(n) so after sqrt(n) jumps the kangaroos reach the end of the range. The points in the hastable 'older' than ~2.sqrt(n) jumps can be cleared (this is not done, but the collision should happen more or less at the same time).
As we don't know where is the private key, there is a worst case when this key is near the begining or the end of the range. The worst case correspond to 3sqrt(PI)/2.sqrt(n) and the best case to sqrt(pi).sqrt(n), so the average is 5.sqrt(pi)/4 which give an average time complexity of ~2.21.sqrt(n) (green curve) but the difficulty is to find the complexity according to the number of kangaroo and DP. I found an approximation of the asymptote when nbKangaroo goes to infinity which is ~ cubicroot( nbKangaroo.16.n.2^dp ) (blue curves) Red curve are experimental points each averaged on 1000 40bits searches with key uniformly distributed in the range. http://zelda38.free.fr/kang_stat1.jpg Edit: A zoom near the average: http://zelda38.free.fr/kang_stat2.jpg Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 30, 2020, 09:00:33 AM Hello everybodey !!! Please help me. I have access to hiend Tesla GPU what I will end in a same day later. I try to test Kangaroo on real pubkeys but unsoccesfull. Then I use DP=9 computation speed down from 500MKeys to 11MKeys/second (!!!!) I try use 68 Byte ranges etc. ALL THIS UNSUCCESFULL FOR ME. Please someone tall me what settings I will nedd for starting Kangarok( -d, greed size, etc) and what renges I need to use ??????? I veryh need help ASAP. Big thanks !!! Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 30, 2020, 09:06:37 AM This is examples from my today tests:
plazmosis.exe - is a renamed kangaroo.exe Quote The system cannot find the path specified. C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF Keys :13 Number of CPU thread: 0 Range width: 2^160 Number of random walk: 2^20.58 (Max DP=57) DP size: 15 [0xFFFE000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 10919.1ms [459.75 MKey/s][GPU 459.75 MKey/s][Count 2^33.49][Dead 0][30s][34.2MB] ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^160 Number of random walk: 2^20.58 (Max DP=57) DP size: 15 [0xFFFE000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... ^C C:\Plasmosis> C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFFFFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^80 Number of random walk: 2^20.58 (Max DP=17) DP size: 15 [0xFFFE000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFFFFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^80 Number of random walk: 2^20.58 (Max DP=17) DP size: 7 [0xFE00000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 7390.7ms Warning, 66588 items lost Hint: Search with less threads (-g) [135.88 MKey/s][GPU 135.88 MKey/s][Count 2^32.10][Dead 0][32s][1832.9MB] ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^52 Number of random walk: 2^20.58 (Max DP=3) Warning, DP is too large, it may cause significant overload. Hint: decrease number of threads, gridSize, or decrese dp using -d. DP size: 7 [0xFE00000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6336.7ms Warning, 65695 items lost Hint: Search with less threads (-g) [135.05 MKey/s][GPU 135.05 MKey/s][Count 2^31.65][Dead 507][25s][1335.4MB] ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^52 Number of random walk: 2^20.58 (Max DP=3) Warning, DP is too large, it may cause significant overload. Hint: decrease number of threads, gridSize, or decrese dp using -d. DP size: 7 [0xFE00000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6149.4ms Warning, 65678 items lost Hint: Search with less threads (-g) [332.32 MKey/s][GPU 332.32 MKey/s][Count 2^29.98][Dead 27][04s][417.1MB] ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^52 Number of random walk: 2^20.58 (Max DP=3) Warning, DP is too large, it may cause significant overload. Hint: decrease number of threads, gridSize, or decrese dp using -d. DP size: 7 [0xFE00000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6128.5ms Warning, 65678 items lost Hint: Search with less threads (-g) [251.78 MKey/s][GPU 251.78 MKey/s][Count 2^30.71][Dead 98][10s][704.4MB] ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^52 Number of random walk: 2^20.58 (Max DP=3) Warning, DP is too large, it may cause significant overload. Hint: decrease number of threads, gridSize, or decrese dp using -d. DP size: 15 [0xFFFE000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6148.2ms [460.02 MKey/s][GPU 460.02 MKey/s][Count 2^33.81][Dead 1050][37s][40.6MB] ^C C:\Plasmosis> C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^60 Number of random walk: 2^20.58 (Max DP=7) Warning, DP is too large, it may cause significant overload. Hint: decrease number of threads, gridSize, or decrese dp using -d. DP size: 15 [0xFFFE000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6501.1ms [459.77 MKey/s][GPU 459.77 MKey/s][Count 2^34.30][Dead 11][52s][53.5MB] ^C C:\Plasmosis> C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^68 Number of random walk: 2^20.58 (Max DP=11) Warning, DP is too large, it may cause significant overload. Hint: decrease number of threads, gridSize, or decrese dp using -d. DP size: 15 [0xFFFE000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 7050.7ms [459.78 MKey/s][GPU 459.78 MKey/s][Count 2^38.50][Dead 81][16:02][907.6MB] ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^68 Number of random walk: 2^20.58 (Max DP=11) DP size: 7 [0xFE00000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6794.7ms Warning, 65975 items lost Hint: Search with less threads (-g) [268.25 MKey/s][GPU 268.25 MKey/s][Count 2^30.81][Dead 0][10s][749.8MB] ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 9 -gpu -g 96,128 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^68 Number of random walk: 2^20.58 (Max DP=11) DP size: 9 [0xFF80000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6872.2ms [183.93 MKey/s][GPU 183.93 MKey/s][Count 2^35.38][Dead 0][03:25][6682.8MB] ^C C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 128,256 in.txt Kangaroo v1.3 Start:0 Stop :FFFFFFFFEBAAEDCE6 Keys :13 Number of CPU thread: 0 Range width: 2^68 Number of random walk: 2^22.00 (Max DP=10) DP size: 7 [0xFE00000000000000] GPU: GPU #0 Tesla T4 (40x64 cores) Grid(128x256) (393.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^22.00 kangaroos in 17993.3ms Warning, 393221 items lost Hint: Search with less threads (-g) [11.02 MKey/s][GPU 11.02 MKey/s][Count 2^36.33][Dead 0][22:28][12887.4MB] Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 30, 2020, 09:29:30 AM I published a pre-release with the new calculation for expected operation.
I also changed the jump Table size to make it multiple of power of 2 in order to avoid the modulo, this should brings little improvement on GPU. Thanks to test it ;) https://github.com/JeanLucPons/Kangaroo/releases/tag/1.4beta @COBRAS: do not use a Tesla on small range and if you don't know where is the private key (in a range) you have to specify the full range: 0 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 but in that case, your tesla will end its calculation when the earth will collapse on the sun ;) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: COBRAS on April 30, 2020, 11:29:15 AM Video with lincks for reading:
"Pollard-Kangaroo GPU CUDA & Quadratic sieve" https://youtu.be/kMevZQc7774 Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: HardwareCollector on April 30, 2020, 12:14:11 PM I published a pre-release with the new calculation for expected operation. I also changed the jump Table size to make it multiple of power of 2 in order to avoid the modulo, this should brings little improvement on GPU. Thanks to test it ;) https://github.com/JeanLucPons/Kangaroo/releases/tag/1.4beta @COBRAS: do not use a Tesla on small range and if you don't know where is the private key (in a range) you have to specify the full range: 0 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 but in that case, your tesla will end its calculation when the earth will collapse on the sun ;) While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively Code: ./kangaroo -t 0 -gpu -gpuId 0 in72.txt Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 30, 2020, 12:16:22 PM Yes the random walk with kangaroo is particular as the path cannot be truncated easily modulo n (n=range size). So the kangaroos can go outside of the range. This is not a problem as the 2 herds travel at the same average speed. The jumpDistane table has an average of sqrt(n) so after sqrt(n) jumps the kangaroos reach the end of the range. Ok. I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points). The speed should double. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: HardwareCollector on April 30, 2020, 12:27:30 PM I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points). The speed should double. Yes, it should be significantly faster when solving for multiple instances, since there’s no need to discard the previous distinguished points. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 30, 2020, 01:01:41 PM While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively Manu thanks for the test ;) Bad news for the lower speed :(. On my low cost GPU it is 10% faster. Will try to understand why ? I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points). I don't think it will change something (at least on single key search). You can may be win memory. In the above readings, a guy announced a speed slightly lower than 1.77sqrt(n) [1.73qrt(n)] but I must say that it is hard to believe his method can beat the birthday paradox. I didn't enter in details in its analysis and it is done on DLP not ECDLP. In any case, to beat the birthday paradox, you have to find a way to maximize the probability of natural random collision. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 30, 2020, 01:53:09 PM While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively As you compile by yourself, could you try to change In GPU/GPUEngine.h:24 #define NB_JUMP 64 to #define NB_JUMP 32 and tell me what is your key rate, thanks :) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: HardwareCollector on April 30, 2020, 02:49:48 PM While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively As you compile by yourself, could you try to change In GPU/GPUEngine.h:24 #define NB_JUMP 64 to #define NB_JUMP 32 and tell me what is your key rate, thanks :) With the above recommended changes to v1.4beta: Code: ./kangaroo -t 0 -d 13 -gpu -gpuId 0 in72.txt v1.3 stock with 13-bit distinguished point mask: Code: ./kangaroo -t 0 -d 13 -gpu -gpuId 0 in72.txt Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 30, 2020, 03:14:33 PM Thanks :)
So it seems a bit faster with 32 jumps. I will make tests to see if affects the average number of operation. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: MrFreeDragon on April 30, 2020, 03:23:13 PM Thanks :) So it seems a bit faster with 32 jumps. I will make tests to see if affects the average number of operation. Why it was faster with 32 jumps for him? Do you have the exaplanation? Also nice things you added: Expected operations: 2^37.15 Expected RAM: 1419.0MB What is the current formula you use for Expected operations? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 30, 2020, 04:08:59 PM Another idea:
do you use the symetrie? If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions. The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones. In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval. In other words : an interval of this type has only 2**(n-1) different x coordinates. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on April 30, 2020, 04:35:06 PM Another idea: do you use the symetrie? If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions. The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones. Yes i have to investigate, I already tested several things without improving things. Translating tame is like translating wild in the opposite direction. May be a brownian motion can be interesting (having positive and negative jump). Why it was faster with 32 jumps for him? Do you have the exaplanation? Probably cache usage. Also nice things you added: Expected operations: 2^37.15 Expected RAM: 1419.0MB Edit: Formula exposed above and for the memory , expected operation*sizeof(hash entry)/2^dp Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 30, 2020, 04:46:36 PM Another idea: do you use the symetrie? If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions. The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones. Yes i have to investigate, I already tested several things without improving things. Translating tame is like translating wild in the opposite direction. No. I meant: translate tame and wild. Not only tame. In a interval with 2^n points but only 2^(n-1) coordinates 'x' (instead of 2^n) to increase the probability to have a collision. If you do the same number of steps in a half space (from coordinates x point of view), the chance should be higher. Half number of x coordinates, half DP, same number of steps, more chance. Like I said before, a tame kangaroo and a wild kangaroo in this scenario collide not only if they fall in the same position but if they fall in 2 different positions (but symetric respect of the center of the interval) as well. If you instead translate this interval in any other position of the curve, when a tame kangaroo and a wild kangaroo fall in 2 positions symetric respect of the center of the interval, your current algorithm doesn't detect a collision, simply because it can't know (without more computation) the x coordinate of the symetric point (respect of (a+b)/2 * G) of any DP that lies in the hashtable (and a symetric point of a DP generally is not a DP) May be a brownian motion can be interesting (having positive and negative jump). My idea goes a little in that direction too, cause the jumps are always positive but the points generated go in both direction, exploiting the symetrie of the curve. Example: when a sequence starts from -k*G (negative part): -k*G, (-k + 2^17)*G, (-k +2^17 + 2^3)*G, .... forth --> but in this way you have too (for free) the x coordinates of : +k*G, (+k - 2^17)*G, (+k- 2^17 - 2^3)*G, .... <-- back the movement is like this: zero point (--> <--) extreme: -k*G, k*G (--> <--) extreme: (-k+2^17)*G, -(-k+2^17)*G (--> <--) extreme: (-k+2^17+2^3)*G, -(-k+2^17+2^3)*G when a sequence starts/arrives in the positive part: k*G, (k + 2^8)*G, (k +2^8 + 2^31)*G, .... forth --> -k*G, (-k - 2^8)*G, (-k -2^8 - 2^31)*G, .... <-- back zero point <-- ( )--> extreme: -k*G, k*G <--( )--> extreme: -(k+2^8)*G, (k+2^8)*G <--( )--> extreme: -(k+2^8+2^31)*G, (k+2^8+2^31)*G Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: HardwareCollector on April 30, 2020, 06:55:43 PM Another idea: do you use the symetrie? If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions. The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones. In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval. In other words : an interval of this type has only 2**(n-1) different x coordinates. I am not following the logic here. What is missing is, how will the paths converge after both the tame and the wild reach the same x-coordinate, assuming that it is the symmetry point? Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: HardwareCollector on April 30, 2020, 07:03:08 PM @Jean_Luc
Please start a new thread for your Pollard Kangaroo implementation discussion. :) Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: arulbero on April 30, 2020, 07:50:08 PM Another idea: do you use the symetrie? If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions. The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones. In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval. In other words : an interval of this type has only 2**(n-1) different x coordinates. I am not following the logic here. What is missing is, how will the paths converge after both the tame and the wild reach the same x-coordinate, assuming that it is the symmetry point? Good point! It is enough to modify slightly the way we generate the next jump: + jP[tamePosi.x % n]*G if y > p/2, - jP[tamePosi.x % n]*G is y <p/2 (then I will indicate 'y' if y > p/2, '-y' if y < p/2) in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision The tame and the wild will go on with 2 specular paths: Q -> Q + k*G -> Q + k*G -r*G -> ... -> DP (x,y) (x1,-y1) (x2,y2) (x0, y0) -Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP (x,-y) (x1,y1) (x2, -y2) (x0, -y0) until they reach 2 symetric DP, for both of which we know the private key. May be a brownian motion can be interesting (having positive and negative jump). I have created a sort of "brownian motion", my kangaroos keep jumping back and forth. Title: Re: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] Post by: Jean_Luc on May 01, 2020, 05:45:47 AM I opened a new thread.
https://bitcointalk.org/index.php?topic=5244940.0 |
