Dice wallet with a twist of regret

[thelongcoin]

Back in 2013, I got interested in the hype a got a bitcoin from Coinbase.  Thinking I was being extra cautious, I created a "paper dice wallet" by rolling a six-sided dice 99 times per the instructions at bitaddress.org.  

From their website :  An important part of creating a Bitcoin wallet is ensuring the random numbers used to create the wallet are truly random. Physical randomness is better than computer generated pseudo-randomness. The easiest way to generate physical randomness is with dice. To create a Bitcoin private key you only need one six sided die which you roll 99 times. Stopping each time to record the value of the die. When recording the values follow these rules: 1=1, 2=2, 3=3, 4=4, 5=5, 6=0. By doing this you are recording the big random number, your private key, in B6 or base 6 format. You can then enter the 99 character base 6 private key into the text field above and click View Details. You will then see the Bitcoin address associated with your private key. You should also make note of your private key in WIF format since it is more widely used.

So I wrote down the original 99 rolls as 1330540124221 and so forth.  I have the public address, and then sent the BTC to the paper wallet.  Then, in a stroke (of genius), I transposed some of the digits (i.e. moved three consecutive digits to another location in the string of numbers) to obfuscate them, thinking if some sophisticated attacker were to gain access to my dice rolls, they would be unable to spend them.  Maybe I was too paranoid.   I've forgotten which digits I 'cut and pasted' and how many ( I strongly think its 3 to 5).  I actually kinda remember the area where the cut happened, not the paste.   How screwed am I?  Any chance to recover this bitcoin?

[furyo87]

There is a mathematical answer to your question but I am too lazy to compute it (800k+ solutions)

In any case what you need to start doing is a list of the possible solutions and start trying. It will take time but likely pay off.

[thelongcoin]

I know a fair amount of python and have already attempted this.  If the cut and paste was three consecutive numbers:  There are 97 different three number groups. 

1) 1st,2nd,3rd digits
2) 2nd,3rd,4th


96)  96th, 97th,98th digits
97) 97th,98th, 99th digits


Assuming that cut number has to go somewhere else, there are 96 spots for it to be inserted.  97*96 = 9312 possibilities

With four digits   96*95 = 9120
Assuming 5 digits  95*94 = 8930

Its trivial to write a python script to test all these possibilities, then convert the Base 6 number to the corresponding public/private key pair and test if there is a match. 


Conclusion:
Either I'm not good enough at python, python is the wrong tool, or the cut and paste was too big to brute force.

[furyo87]

ok, my bad, thought you had moved groups of 3 digits 3 to 5 times.
I agree with your math.

Assuming you have already tried those 30k private keys my next set would be to try strings of 2 characters and 1 character.

[KingZee]

I know a fair amount of python and have already attempted this.  If the cut and paste was three consecutive numbers:  There are 97 different three number groups. 

1) 1st,2nd,3rd digits
2) 2nd,3rd,4th


96)  96th, 97th,98th digits
97) 97th,98th, 99th digits


Assuming that cut number has to go somewhere else, there are 96 spots for it to be inserted.  97*96 = 9312 possibilities

With four digits   96*95 = 9120
Assuming 5 digits  95*94 = 8930

Its trivial to write a python script to test all these possibilities, then convert the Base 6 number to the corresponding public/private key pair and test if there is a match. 


Conclusion:
Either I'm not good enough at python, python is the wrong tool, or the cut and paste was too big to brute force.

This sounds reasonable, what's your problem? Have you successfully coded the "dice roll to private key" part?

[thelongcoin]

I've tried 2 digit and 1 digit transposes as well.  No luck.  So I believe I cut 3/4/5 consecutive digits somewhere and then inserted 3/4/5 other digits.  The difference possible combinations start to explode towards infinity and I fear I've lost the coin forever.  Does any recovery service exist to write code that tries to recreate all this possibilities?  I know most of the private key, but do I know enough?

[o_e_l_e_o]

I know most of the private key, but do I know enough?

The problem here is that I don't think you actually know any of the private key. Let's take a simple pattern for the sake of illustration.

Code:

123450123450 = 1F1E7D36

If you move the first digit to the end, you get:

Code:

234501234501 = 38F7DF45

If you instead move the second digit to the end, you get:

Code:

134501234502 = 23580746

Even the tiniest change in what you cut and pasted will result in a vastly different private key, so I don't think you can say with any certainty that you know any of the private key.

If you have tried every cut and paste of 1, 2, 3, 4, and 5, consecutive digits, then you might as well try 6+ consecutive digits, since the number of possibilities gets progressively smaller and it is trivial to try. The next thing might be to consider if instead of cut and pasting, you actually swapped two different sets of numbers.

Also, be sure you are checking both the compressed and uncompressed address, as bitaddress.org generates both.

[DannyHamilton]

I've tried 2 digit and 1 digit transposes as well.  No luck.  So I believe I cut 3/4/5 consecutive digits somewhere and then inserted 3/4/5 other digits.

I haven't tried the math yet, but this feels possible.

Can you make some intelligent assumptions about what you did?

For example:

• Definitly didn't grab digits starting at the very first digit?
• Second?
• Third?
• etc?
• Definitely didn't grab digits ending at the very last digit?
• Second to last?
• Third to last?
• Etc?
• Definitely grabbed consecutive digits?
• Definitely pasted those cut digits consecutively?
• Definitely pasted to the *right* (or definitely to the left?) of the cut?
• Definitely pasted at least 1 digit away from the cut?
• Two digits?
• Three digits?
• etc

Any little detail helps significantly reduce the number of possibilities that need to be checked.

Also, we humans are creatures of habit far more than we realize, and we are horrible at creating our own randomness.

Go through the steps..  Generate a list of 99 digits from 0 through 5 (preferably by dice roll exactly as you did before). Take a look at it. Then decide... If you were TODAY going to cut and paste digits for a similar purpose, how many digits would you cut and paste? Where in the string of digits would you cut them from?  Where would you paste them?

Now take a look at your decision.  Did you happen to choose a sequence that starts and/or ends with a particular digit for the cut? Did you happen to choose a particular pair of digits to paste in between?  How far from the ends did you cut? How far from the ends did you paste?  In choosing the sequence to cut, did you look for any particular digits (or patterns) to exist (or not exist) in (or before, or after) the sequence?Whatever "feels about right" currently, probably "felt about right" back then.

[thelongcoin]

I did leave myself a cryptic message that was supposed to serve as a reminder as to what the transposition was ...  I wrote this message the day I did the transpose, so it stands as the best clue on how to get the bitcoin back.  I believe it jogs my memory on where in the 99 digits the cut occurred, but not sure on how to interpret the message as to what the paste was and where the paste occurred.  But your questions have given me fresh thoughts on how to solve it.

[pooya87]

Conclusion:
Either I'm not good enough at python, python is the wrong tool, or the cut and paste was too big to brute force.

This may sound obvious but have you tried to actually test the code you wrote with an example? The problem may be in your code.
Choose some of the variations (with 1, 2, 3, ... transposition) at random and generate their addresses then enter that address in your code and start the search to see if it can find the correct answer. This way you can be sure that your code is fine.

[KingZee]

Conclusion:
Either I'm not good enough at python, python is the wrong tool, or the cut and paste was too big to brute force.

This may sound obvious but have you tried to actually test the code you wrote with an example? The problem may be in your code.
Choose some of the variations (with 1, 2, 3, ... transposition) at random and generate their addresses then enter that address in your code and start the search to see if it can find the correct answer. This way you can be sure that your code is fine.

This is what I meant, or share the code you used. Sorry if it sounds a bit rude but all we have is your word that "it doesnt work", have you really tested your code correctly and verified that even after iterating through all the options it didnt work? Are you sure you're generating the seed using the same method bitaddress.org uses? Are you sure you're checking the address using the right derivation? There's so many things you have to double check to see if your code is correct that I'm more inclined to believe it's something wrong on your end, not the dice roll or the cut.

[NotATether]

I've tried 2 digit and 1 digit transposes as well.  No luck.  So I believe I cut 3/4/5 consecutive digits somewhere and then inserted 3/4/5 other digits.  The difference possible combinations start to explode towards infinity and I fear I've lost the coin forever.  Does any recovery service exist to write code that tries to recreate all this possibilities?  I know most of the private key, but do I know enough?

I wouldn't give up yet. You're only trying to find a standalone private key and one derived from some seed phrase, and this makes the programming task much easier.

I know some Python so I'll look for some old code of mine that creates a private key WIF from hex and I'll apply it to this problem.

Python is actually the right tool for this job given the extreme easiness to convert a arbitrary base to a number. You just take the string of digits as input and then pass it to int() along with the base [after you turn the 6 digits into 0]. Most other languages don't have such a function so you'd waste some more time trying to write one.


Do you have a GPU? I have a feeling this search can be hardware-accelerated, and it's probably easier to write GPU code in Python than in C.

[LoyceV]

I did leave myself a cryptic message that was supposed to serve as a reminder as to what the transposition was ...

I like puzzles, can you share it (without sharing the 99 numbers)?

[NotATether]

As promised I made a script for this. It is currently single threaded and doesn't use a GPU but if this turns out to be useful I can add that functionality too.

Code:

import math
import hashlib
import codecs
import sys

def main():
    s = input("Enter the dice numbers: ")
    group = input("Enter the number of digits moved in one group: ")
    group = int(group)
    fil = input("path to output file: ")

    # Ensure that we have a 256-bit number
    digit2 = math.floor(math.log(6*len(s))/math.log(2) + 1)
    if digit2 > 256:
        raise ValueError("Number greater than 256 bits")
    f = open(fil, "w")
    # Try all combinations
    print("generating all combinations")
    transpose_s(sixtozero(s), group, f)

def transpose_s(s, n, f):
    combs = []
    i = 0
    l = len(s)
    j = min(n, l)
    if j - i < n:
        raise ValueError("dice number length is smaller than number of digits to transpose")
    while j < len(s):
        slice = s[i:j]
        ss = s[:i] + s[j:]
        # l-n is length of ss
        ll = l-n
        for k in range(0,ll):
            t = ss[:k] + slice + ss[k:]
            combs.append(t)
        i+=1
        j+=1
    cc = len(combs)
    
    print("{} possible transposes found".format(cc))
    print("converting to int")
    for ii in range(0,cc):
         combs[ii] = to_int(combs[ii])

    print("converting to hex")
    for ii in range(0,cc):
         combs[ii] = hex_no0x(combs[ii])

    print("converting to privkey WIF")
    privkeys = []
    for ii in range(0,cc):
        privkeys.append(construct_privkey(combs[ii]))

    for ii in range(0,cc):
        privkeys[ii] = base58(privkeys[ii])

    lines = "\r\n".join(privkeys)
    f.write(lines)
    f.close()
    print("Finished")
    sys.exit()

def hex_no0x(i):
    return hex(i)[2:]

# https://gist.github.com/Jun-Wang-2018/3105e29e0d61ecf88530c092199371a7
def construct_privkey(PK0):
    PK0 = '{:0>64}'.format(PK0)
    PK1 = '80'+ PK0
    PK2 = hashlib.sha256(codecs.decode(PK1, 'hex'))
    PK3 = hashlib.sha256(PK2.digest())
    checksum = codecs.encode(PK3.digest(), 'hex')[0:8]
    PK4 = PK1 + str(checksum)[2:10] 
    return PK4

# Define base58
def base58(address_hex):
    alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
    b58_string = ''
    # Get the number of leading zeros
    leading_zeros = len(address_hex) - len(address_hex.lstrip('0'))
    # Convert hex to decimal
    address_int = int(address_hex, 16)
    # Append digits to the start of string
    while address_int > 0:
        digit = address_int % 58
        digit_char = alphabet[digit]
        b58_string = digit_char + b58_string
        address_int //= 58
    # Add ‘1’ for each 2 leading zeros
    ones = leading_zeros // 2
    for one in range(ones):
        b58_string = '1' + b58_string
    return b58_string


def sixtozero(s):
    l = list(s)
    for i in range(0,len(s)):
        if s[i] == "6":
            l[i] = "0"
    return "".join(l)

def to_int(s):
    si = int(s, 6)
    return si

if __name__ == "__main__":
    main()

This will make a file with all possible private keys, one on each line. For example, the dice sequence "123" and one character transposed, makes the private keys:

Code:

5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreGRmRFDZ
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreKnSXYds
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreKnSXYds
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreGRmRFDZ

There are some duplicates, probably because some transposes are equivalent like swapping positions 1-2 and 2-1.

The next step after retrieving all these private keys is to use LoyceV's list of addresses with a balance to see which ones are inside both lists.

edit: fixed error in sixtozero()