Claim the coins challenge - The typo scenario

[joan]

This challenge is related to import/export of private keys and wallet and creating "off the radar" addresses.
I don't know if it can be done. (I still have the correct private key of course)

Scenario:
- I used a tool or the client to generate a completely off the radar address.
- I wrote the private key on a piece of paper and stored it in a safe.
- I secured some of my savings to the corresponding address.
- We are now some years later and I want to import it back and spend my savings.

Unfortunately, it looks like I made a typo while writing down the private key ! This is all the information that I have left :

privkey: 5JjNVWPaRTPg1i4etqfPHFnsDZ1Js5qBYXFH9G4jC2Drb6kERsm
addr: 18j6vJ39JFtHtgwNninSk4L61VzRhXBmoc (bbe)
balance: 0.10 BTC

hints:
- The address is valid, the privkey has a typo, the typo is not in the checksum bytes.

I don't know if this can be done due to the double SHA256 used for integrity check. Maybe we should have correcting codes instead (A non working destination address due to a typo is not very critical, but a non working privkey is).

Idea:
Maybe we could have a validateprivkey rpc call like there is a validateaddress. This way I might have checked earlier and realized the backup wasn't valid.

Reference threads
- Private key and wallet export/import
- Bitcoin Off The Grid (shell script to generate privkeys)

[ascent]

There's a big difference between the type of typo you're talking about here and a genuine typo. Typos are keying errors on keyboards, and thus you could try substitutions for each character with a nearby key on the keyboard. In the scenario you have illustrated, the first thing to check is to see if you left a character out, by counting the number of characters in the string. If so, you could try insertions between each character.

[bitlotto]

You could design a script that:
-checks letters/numbers that look the same eg. switch 2 and z
-try changing one letter at a time
-try changing two
-then try checking to see if it works

Pretty much like brute forcing a password but you know most of it already. I wouldn't be able to make the script but it would be retrievable.

If they used my script though, they would have to make multiple mistakes as they would have a hex version of the key too AND since they wouldn't have typed it out but wrote it down location of keys on keyboard wouldn't matter! It would probably be a L or 1 type thing!

[casascius]

I actually was planning on doing this very recently!  I'll take a whack at it.

[ius]

A single typo is trivial to correct, as the private key includes a checksum as well.

Warning: hackjob ahead

Code:

#!/usr/bin/python
import base58, hashlib

def sha_checksum(data):
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()[:4]

sec = '5JjNVWPaRTPg1i4etqfPHFnsDZ1Js5qBYXFH9G4jC2Drb6kERsm'

data = base58.b58decode(sec, 37)

checksum = data[-4:]
key = data[:-4]

for i in xrange(len(sec)):
    for c in base58.__b58chars:
        modkey = sec[:i] + c + sec[i+1:]
        decoded = base58.b58decode(modkey, 37)

        if decoded:
            if sha_checksum(decoded[:-4]) == checksum:
                print 'Found:', modkey
                print (6+base58.__b58chars.index(c))*' '+'^'

Code:

Output:Found: 5JjNVWPaRTPg1i4etqfPHPnsDZ1Js5qBYXFH9G4jC2Drb6kERsm
                                   ^

Hmm, no monospaced code font?

[patvarilly]

Here's a modification to PrivateKeys.java in BitcoinJ that does the trick:

Code:

ECKey key = null;
final String ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
Boolean solved = false;
for( int i = 0; !solved && i < args[0].length(); i++ )
{
	// Replace one character in the private key
	String before = args[0].substring( 0, i );
	String after = args[0].substring( i+1 );
	for( int j = 0; !solved && j < ALPHABET.length(); j++ )
	{
		String keyStr = before + ALPHABET.substring( j, j+1 ) + after;

		try {
			DumpedPrivateKey dumpedPrivateKey = new DumpedPrivateKey(params, keyStr);
			key = dumpedPrivateKey.getKey();
					
			System.out.println("Address from private key is: " + key.toAddress(params).toString());
			solved = true;
			break;
		} catch( AddressFormatException e ) {
		}
	}
}
if( !solved )
{
	System.out.println( "Could not correct private key!" );
	return;
}

You just need to try every single-letter change in the private key to see if it produces a valid public key (the public key is derivable from the private key in EC cryptography).  In your case, only a single valid public key comes out (because of the checksumming), but if there were more than one, you could check to see if the address that's generated is the address you have on file.

[joan]

Output:Found: 5JjNVWPaRTPg1i4etqfPHPnsDZ1Js5qBYXFH9G4jC2Drb6kERsm

Awesome! And thanks.
(And also D'Oh! but of course )

So if there is a single error and it's not in the checksum, we just test len(privkey)*58 candidates.
For 2 errors we would test (if I'm not mistaken…) [(len*(len-1))/2]*58, still under 100,000 candidates, nice.

[o]

From the code above, I have questions about the base58 used. I have search one base58.py in the google code (and elsewhere) which use the encoding:

"123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

but the C and java implementation of bitcoin use the the following encoding:

"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

So I want to know whether there is consensus about the use of base58?

[bitlotto]

I think they call it Satoshi Base58. 
({1..9} {A..H} {J..N} {P..Z} {a..k} {m..z})

[o]

I think they call it Satoshi Base58. 
({1..9} {A..H} {J..N} {P..Z} {a..k} {m..z})

With the success of bitcoin, it will be the only Base58. 

[ius]

From the code above, I have questions about the base58 used. I have search one base58.py in the google code (and elsewhere) which use the encoding:

"123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

but the C and java implementation of bitcoin use the the following encoding:

"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

So I want to know whether there is consensus about the use of base58?

If I recall correctly Flickr also uses/used a base58 encoding - with a different character set(!) - that's the one you probably found on Google code.

I forgot to link to the base58 module I used - I borrowed base58.py from Abe: https://github.com/jtobey/bitcoin-abe/blob/master/base58.py

[bitlotto]

From base58.h in Bitcoin:
123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
I'd go with that one! All Bitcoin stuff uses that one!