Title: Solving partial WIF with two missing parts Post by: albert0bsd on January 19, 2022, 06:56:05 AM Well i want to open this topic to ask and share a little of my experience with this kind of "edge/estrange" cases of WIF with missing characters.
Example: Code: Partial WIF: L1dU****d4NTd7******6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t With an Public key Available my approach will be the next - Brute force all the first 4 missing characters - Calculate the the second part (6 Missing characters) with BSGS - Use a mixed mode (Brute force / BSGS ) to solve all parts together. For the user PawGo maybe this will be your Hybrid method with some changes ( Not this case in specific, but maybe some ideas on it). Question: How fast this can be solved for the public programs with CPU? I made a small script SINGLE-thread with a lot of possible improvements, the program solve this in some 3 hours, it is not a general program it need to be adapted to each case. Note: 10 11 and 12 Missing characters together in the same part at the beginning can be solved in minutes with CPU if you have the public key, without it is an impossible task. Maybe I'm missing something and this specific problem/case can be solved more easily or faster but I don't know. Title: Re: Solving partial WIF with two missing parts Post by: PawGo on January 19, 2022, 10:06:58 AM The problem with middle part is that any change has impact on checksum and compression flag. And that's good! Try to increment 6 characters and see if they produce correct flag 01. It would give you a subset of correct possibilities (not 58^6).
PS: I work on migrating WifSolver to CUDA, early beta version will be available soon (today/tomorrow). Title: Re: Solving partial WIF with two missing parts Post by: albert0bsd on January 19, 2022, 02:01:20 PM Yes you are right, seems if i implement the correct increment i can solve this in less than half hour with CPU even less i need to make some test
L1dU1111d4NTd71111116zCyXqGyWXhXTa16dNWXZs7cpdk6en2t 80 8391fe958e6543b739b52db45eb396b672fc42d48472ee321f50b150cd4f8c33 84 07d5b039 L1dU1111d4NTd7zzzzzz6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t 80 8391fe958e6543b73a1667b0dbc3b3c8fe91fb939a818d5e0f8de094de4432a7 43 07d5b039 I'm solving the 6 missing chars with BSGS and that part is solved instantly and doesn't matter if the byte encode is over written or not, but maybe i can do that part faster with your hint Title: Re: Solving partial WIF with two missing parts Post by: albert0bsd on January 21, 2022, 10:27:07 PM I try to find an easy/faster/efficient way to get what is the next valid WIF in this case finding the next 01 in the Encode byte, but seems that it require more operations that my current method, so i will pass that approach. PawGo if you know an easy way to calculate it please tell us.
NOW I will post here one example of what I'm doing in my program, step by step and i will show you guys the public key operations that i do to the public key in order to get a new "Transformed Public key" and how i solve the problem with that new public key. The target public key is: Code: 02FEE659ACF67F63F13AB4A7D676782F89EF8C51FCC9077A8709831FCEABFE261F Lets to suppose that the only missing characters are the second chunk of 6 characters at the middle. Code: L1dU1111d4NTd7******6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t I know that the key is not there, but lets to suppose that for the first example and at the end i will show you the real location and how to solve it with keyhunt. (Since you already know how to solve it with bitcrack and kangaroo). So lets to calculate the start range and the End range for this example: Code: Start: L1dU1111d4NTd71111116zCyXqGyWXhXTa16dNWXZs7cpdk6en2t Code: End: L1dU1111d4NTd7zzzzzz6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t If we remove the Encode bytes and the check sum the range in hexadecimal is: Code: Start: 8391fe958e6543b739b52db45eb396b672fc42d48472ee321f50b150cd4f8c33 So if we are sure that the target public key is there we can assume that the private key start by: Code: 8391fe958e6543b7000000000000000000000000000000000000000000000000 Lets to call it "Base Private key" It's public key is: Code: 02d1132913ea23066aeb2c862e74781cae270d06861eff13a224966dffa760a979 In that case we can substract to our target public key the value of the base publickey: Code: 02FEE659ACF67F63F13AB4A7D676782F89EF8C51FCC9077A8709831FCEABFE261F - Call the Result "PublickeyStep1" Now, as PawGo mention in this post and others of his post the problem with middle missing characters is tha they usually overwrite the encode byte 01 and others (not this case) the checksum part. In this case the full base58 stride is: Code: Stride: 211111111111111111111111111111111 If we see the hexadecimal part the last 4 bytes (8 hexadecimal characters) are 0 so in this case the Checksum is not overwritten so we can remove those not overwritten bytes and work only with the encode byte overwritten. New Stride hex: Code: Hex: 0af820335d9b3d9cf58b911d87035677fb7f5281 So, to work with our actual public key "PublickeyStep1" we need to add to it one extra byte, this can be done multiplying it by 256 Code: 035ba75d3476e534fc7c5f356236eac0da7a7a1285a13e2fa36725927228fa64d2 x 256 Call the Result: PublickeyStep2 Also we need add 1 to the PublickeyStep2 because we expected that the valid Target (Unknow Private key) have an 0x01 value in the Encode byte Code: 03813771bcfdb1f531273698c62adb3ed1a02693cf53e9ed1358350e8bf3ded880 + 1 Now with that extra byte set to ONE we can work with the current stride. You remember that we substract to the target publickey the "Base Public key" value? well now is time to subtract to the "PublickeyStep3" the value of the remainder of the of the base publickey in this case is the value of: Code: 0x39b52db45eb396b672fc42d48472ee321f50b150cd4f8c3384 Please check the value include the extra encode byte, but with the overwritten value 0x84 Code: 02019eedafe6ffa5ccc19cbc2d547edadfcfc2dc1cd1cc096794e9c2ebbbd994a3 - Call the result PublickeyStep4, I know, is getting a little complicated to follow, but it is only because the results are publickey in a ECC Operations and those operations are not in our day to day. Now if the partial WIF is valid, I can guaranty you that the "PublickeyStep4" is perfectly divisible by our stride. Code: 0361835cf65529916765ac4a5830f0ce0896312b5c0ab32e565cef0b3d0e6212a7 / 0x0af820335d9b3d9cf58b911d87035677fb7f5281 This result is now our Expected "Transformed Public key" and it will be in the range from 1 to 58^6 1 to 38068692544 or in hexadecimal from 0x01 to 0x08DD122640 that is 36 bits and it can solve instantly with almost all the programs mentioned above. Summary: PublickeyStep1 = Target Public key - Base Public key (This last value change if we change the original first 4 missing characters) PublickeyStep2 = PublickeyStep1 x 256 (This part add and extra "blank byte to the current public key") PublickeyStep3 = PublickeyStep2 +1 (We add the public key of G to the current public key) PublickeyStep4 = PublickeyStep3 - Base Public key remainder with extra overwritten byte Transformed Public key = PublickeyStep4 / Stride Real example: Code: Partial WIF: L1dUm2Fzd4NTd7******6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t Now we find the Transformed Public key with any of our tools in the range from 0x01 to 0x08DD122640 Code: albertobsd $ time ./keyhunt -m bsgs -f target.txt -q -r 1:1000000001 -S -n 0x100000000 In case of found one of those public keys you only need to do the inverse Operations in reverse way in order to get the Target privatekey PrivatekeyStep4 = Transformed Privatekey x Stride PrivatekeyStep3 = PrivatekeyStep4 + Base Private key remainder with extra overwritten byte PrivatekeyStep2 = PrivatekeyStep3 - 1 PrivatekeyStep1 = PrivatekeyStep3 / 256 Target Privatekey = PrivatekeyStep1 + Base Private key Code: 0x61111eefd x 0x0af820335d9b3d9cf58b911d87035677fb7f5281 Obviously this need to be automatically to avoid errors, also remember that the first missing part is 4 characters length, this mean that we need to repeat all those operations almost 58^4 times this is 11316496 times Title: Re: Solving partial WIF with two missing parts Post by: PawGo on January 22, 2022, 11:22:06 AM I try to find an easy/faster/efficient way to get what is the next valid WIF in this case finding the next 01 in the Encode byte, but seems that it require more operations that my current method, so i will pass that approach. PawGo if you know an easy way to calculate it please tell us. Yes, I was interested in that subject. I based one of my algorithms on that, but at the end I concluded it is not 100% sure solution and abandoned that. Code: https://github.com/PawelGorny/WifSolver/blob/master/src/main/java/com/pawelgorny/wifsolver/WorkerJump.java I have tried to calculate the step which would produce the correct checksum. The problem I found was that it works only for missing characters on very limited range (close to limit which changes stride, I do not remember exactly but I had good results for range 2-3 characters to the right of character which stops changing checksum). If I moved right, I was not able to find the stable jump. In my post https://bitcointalk.org/index.php?topic=5265788.msg54905327#msg54905327 I showed the example where I was able to find the proper jump, but then I realized that method is not 100% sure and I did not work on that anymore. |