Solving WIF in a ‘hybrid’ mode

The following content was written by PawGo on July 31, 2020, 07:57:23 AM in the thread Solving WIF in a ‘hybrid’ mode. All content is owned by the author of the bitcointalk.org post. (original)

---

Hello

I would like to share with you one thing I found recently – maybe you will give me a hint how to use it in the most effective way.
Recently I published my WIF Solver (https://github.com/PawelGorny/WifSolver) with several ways to ‘attack’ problem of missing characters. I would like to talk about method called JUMP. Please let me describe the method and then I will ask a question.
In the example in my project I use WIF L5EZftvrYaSud_____zTqLcHLNDoVn7H5HSfM9BAN6tMJX8oTWz6 (taken from a very helpful site learnmeabitcoin.com).
So, let’s take the WIF and replace missing characters by ‘1’, we will get:
L5EZftvrYaSud11111zTqLcHLNDoVn7H5HSfM9BAN6tMJX8oTWz6 and try to decode it. We will get a hex string, starting with ’80’ + priv key + compression flag + checksum. Lets call it hexInit
As we see, compression flag is incorrect – so something is wrong… Go on.
I focus on fact that for any correct WIF generated from the initial one, after decoding there must be a flag ’01’ and given checksum. Now, let’s jump to the first missing character on the right. We may say, that when we iterate Base58 characters in fact we increase our hex number (08+priv+01+checksum) by 58^34. But I realized that adding 58^34 to hexInit will change the last bytes – checksum and compression. I asked myself – is there a combination which will set ’01’ + expected checksum again (I mean not only in the real WIF which we look for?).
So I add 58^34 several times and yes! WIF: L5EZftvrYaSud1111uzTqLcHLNDoVn7H5HSfM9BAN6tMJX8oTWz6 produces desired ending.
(in fact I check existence of flag ’01’ and not the full checksum, but last 7 characters – I found that the 8th character from right could be different)
We have our WIF which we may use as a starter for calculations.
The other question is – is there a fixed length of jump? And question is again yes – for this case length is 64.
Which means that we may now forget about working on WIF and instead start working on ‘numbers’.
Let’s take number starter = 80ef235aacf90d9f4a9df7ba29006cad4ec1c6610833d3a8587b4d7c662e5ce97a0166557e53 and increase it, but not by 58^34 (like it would be in brute force method – just a next Base58 character) but by 64*(58^34) – we have our jump 240921c8be82fd68a2a77fba0089f71029354609c90000000000 – as we see last 10 characters are 0, so it will not change the end of ‘decoded’ hex string.
This way we save some time, because we do much less number of additions.
[By the way, I also checked what are then possible characters on 34th, 33rd, 32nd… position), and we may find that we have 29*29*29… correct combinations, which is much more optimistic that 58*58*…]

Now, my question is:
Replacing missing letters by 111 -> zzzz, +- with correction for a ‘valid’ starter/finish, we may find a target range [starter, finish]. And we know that we may use jump as a number to add, which makes our range not ‘continuous’ but sparse (we may think about it like about islands). Is there any method ‘smarter’ than brute-force iteration? We may make an assumption that we look for pubkey, not address if it helps.

Of course we may change our variables, remove unneeded characters and pass is to BitCrack (
it would have keyspace start=ef235aacf90d9f4a9df7ba29006cad4ec1c6610833d3a8587b4d7c662e5ce97a and stride=240921c8be82fd68a2a77fba0089f71029354609c9) and then search for address. But is there any better way?


start:
ef235aacf90d9f4a9df7ba29006cad4ec1c6610833d3a8587b4d7c662e5ce97a
end:
ef235aacf90d9f4ab3fedd0341bb04f1bd6de2b22006062c40d74b022f965fee
jump:
240921C8BE82FD68A2A77FBA0089F71029354609C9
(diff: 160722da414e57a2fba781a9ec325dd3c589ce9c01397674) – full range
diff/jump = 9c7cd4 – number of strides to do
result:
ef235aacf90d9f4aadd8c92e4b2562e1d9eb97f0df9ba3b508258739cb013db2
pubkey:
02b4632d08485ff1df2db55b9dafd23347d1c47a457072a1e87be26896549a8737

---

The following content was written by BrewMaster on July 31, 2020, 04:44:03 PM in the thread Solving WIF in a ‘hybrid’ mode. All content is owned by the author of the bitcointalk.org post. (original)

---

i have 2 problems with your method.
1) you skipped over explaining how you came up with 64 when you made the jump in 64*(58^34). looking at the binary representation of (58^34) i am guessing you were looking for enough bits to leave the 0x01 untouched hence the 6 bit shift.
but here is a question, how do you know that addition of more (58^n) between 1 and 63 is not going to give the same 0x01?
note that i said n and not 34 because the assumption should be that the missing character could be in different positions which brings me to second problem

2) if i understood your method correctly then it can not work in cases when (58^n) doesn’t even change 0x01 at the end. for example the following key since you can no longer make any jumps:
L5E______YaSudiozVRzTqLcHLNDoVn7H5HSfM9BAN6tMJX8oTWz6

---

The following content was written by PawGo on July 31, 2020, 05:54:46 PM in the thread Solving WIF in a ‘hybrid’ mode. All content is owned by the author of the bitcointalk.org post. (original)

---

yes, of course.


Maybe it was just a kind of luck that I get ‘unknown’ character on this position, which allowed me to make my experiments. Of course if we move problem into left side, it will stop giving us any gain.
Initially I asked myself if is there a way to find a value on unknown position which would give us the correct compression byte 01. All the time I was thinking in parallel in two systems – both in hex and in WIF – which could make my reasoning a bit confusing, so I am sorry for if something is not clear enough.
Anyway, I found that there is cycle (64 steps) and it produces 29 possible characters (on 34th position). And this is my algorithm – I take initial WIF, convert to number and try to find first ‘correct’ – with correct compression byte and checksum. I treat this distance as a initial jump. And then, from obtained number I try to find the cycle.

Set of characters on 34th position has size 29. On 33rd position it is already 58, BUT! set 33+34 is 841 = 29*29. And set 32+33+34 has size 29*29*29. This is one more interesting thing, because it allows us to pre-produce a list of possible combinations for last 4 or 5 characters and use it instead of 58*58*58.

I do not understand question
What do you want to add? On which position?

---

The following content was written by BrewMaster on July 31, 2020, 06:26:41 PM in the thread Solving WIF in a ‘hybrid’ mode. All content is owned by the author of the bitcointalk.org post. (original)

---

it seems to me that when you add 64*(58^34) to go to the next value and check the addition result, you are skipping a lot of values in between (the jump) and i am trying to figure out how can we be sure there isn’t any other valid values in that skipped space to check.

---

The following content was written by PawGo on July 31, 2020, 06:47:22 PM in the thread Solving WIF in a ‘hybrid’ mode. All content is owned by the author of the bitcointalk.org post. (original)

---

experimentally…

I would rather say that there is no sooner correct jump, but we maybe we may have false hits in the future – maybe combination of characters ‘on left side’ will change something, however I do not think so; I have not found any situation like that.

---