Recovering garbled Bitcoin addresses

April 23, 2024 TelegramThere are many code snippets in this blog post. You can download them from a repo. The finished project is available here.Once upon a time, there was a decentralized network called ZeroNet. Unlike popular content-addressed storage networks that came later (such as IPFS), ZeroNet enabled dynamic sites that could be updated by their owners in real-time, such as blogs and forums. As a consequence, sites could not be addressed by immutable hashes. The lead developer didn’t want to invent any new cryptography, though, so he made perhaps the smartest decision: sites were addressed by Bitcoin addresses, and their contents and updates were signed by that address.If you haven’t used Bitcoin, here’s what its addresses look like: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71. In comparison, a typical domain name on the web looks like this: purplesyringa.moe. The main difference is that Bitcoin addresses are case-sensitive, and people are used to addresses being case-insensitive. This has led to hacks like using http://zero/1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71 instead of http://1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71.zero, but mistakes still happened, and sometimes the only trail you had is a lower-cased address, like 1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71. And that’s how valuable information is lost.I was working on archiving ZeroNet back then, so any sort of information loss due to human error was a nuisance worth fixing. Have we really lost access to the site if we only know the lower-cased address? Can we recover the original address somehow?What’s an address?A common misconception is that a Bitcoin address is an encoding of a public key. This is not the case. Instead, an address contains an encoding of a hash of the public key. It is a UX decision: the hash is shorter than the public key and thus easier to use, but it is still long enough so that security is not affected.

It turns out that Satoshi made other UX considerations, too. A Bitcoin address encodes not only a hash of the public key but also a checksum. If someone makes a typo in the target address while transferring currency, the Bitcoin client will notice that and cancel the transaction. The protection is much more reliable than the one IBAN uses: the checksum is the first four bytes of SHA256(SHA256(key_hash)).The last important part is that the encoding is not your favorite base64 but base58. The difference is that base58 excludes the characters 0, O, I, and l from the encoding because they are easily confused, and + and / because they are not URI-safe (and potentially confusing), and = because padding is useless anyway.Here’s a neat illustration:A private key (random 32 bytes) maps via ECDSA magic to a public key (33 bytes). The public key is then hashed via SHA-256 and RIPEMD-160 to a 20-byte string. Prepending a 1-byte address type (0x00) to the hash produces a 21-byte payload. This payload is hashed via SHA-256 twice, and the first 4 bytes are used as the checksum. The payload and the checksum are then concatenated, resulting in a 25-byte decoded address. This address is then encoded with base58 to produce a human-readable string, about 34 characters long on average.A private key (random 32 bytes) maps via ECDSA magic to a public key (33 bytes). The public key is then hashed via SHA-256 and RIPEMD-160 to a 20-byte string. Prepending a 1-byte address type (0x00) to the hash produces a 21-byte payload. This payload is hashed via SHA-256 twice, and the first 4 bytes are used as the checksum. The payload and the checksum are then concatenated, resulting in a 25-byte decoded address. This address is then encoded with base58 to produce a human-readable string, about 34 characters long on average.First attemptCan we brute-force our way through all combinations of lowercase/uppercase and check if any is valid?

Let’s try just that.import base58 import itertools address_lowercase = "1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71" def try_both_cases(c): yield c if c.upper() != c: yield c.upper() for address in itertools.product(*map(try_both_cases, address_lowercase)): address = "".join(address) try: base58.b58decode_check(address) except ValueError: pass else: print("Found valid address:", address) $ time python3 attempt1.py ^CTraceback (most recent call last): File "/home/purplesyringa/btccaserestore/attempt1.py", line 16, in <module> base58.b58decode_check(address) File "/home/purplesyringa/.local/lib/python3.11/site-packages/base58/__init__.py", line 152, in b58decode_check result = b58decode(v, alphabet=alphabet, autofix=autofix) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/home/purplesyringa/.local/lib/python3.11/site-packages/base58/__init__.py", line 128, in b58decode acc, mod = divmod(acc, 256) ^^^^^^^^^^^^^^^^ KeyboardInterrupt real 1m47,770s user 1m47,301s sys 0m0,027s Second attemptYeah, using Python was a mistake. It’s probably not going to terminate before the heat death of the universe. Let’s rewrite it in Rust:use base58::FromBase58; use itertools::Itertools; use sha2::{digest::Update, Digest, Sha256}; fn main() { let address_lowercase = "1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71"; let addresses = address_lowercase .bytes() .map(|byte| { if byte.to_ascii_uppercase() !

= byte { vec![byte, byte.to_ascii_uppercase()] } else { vec![byte] } }) .multi_cartesian_product(); for address in addresses { let address = String::from_utf8(address).unwrap(); let Ok(decoded_address) = address.from_base58() else { continue; }; if decoded_address.len() != 25 { continue; } let round1 = Sha256::new().chain(&decoded_address[..21]).finalize(); let round2 = Sha256::new().chain(round1).finalize(); if decoded_address[21..] == round2[..4] { eprintln!("Found valid address: {address}"); } } } $ time cargo run --bin attempt2 --release Finished `release` profile [optimized] target(s) in 0.01s Running `target/release/attempt2` Found valid address: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71 real 0m34,296s user 0m34,275s sys 0m0,013s Yay! That’s precisely the address that we started with.Problem solved? Well, yeah, but in my case, address recovery was a part of an automated process. That means I’m not even sure if the input is total garbage.Can 1hell0w0rldd9cgdqo3htmtkv8lk4znx71 be restored to a valid Bitcoin address? Maybe! Does anyone actually use that address? I don’t know! They could have gotten lucky with Vanitygen.Should I spend my CPU time trying to recover 1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa? Probably not, but how should I check that automatically while avoiding false negatives?And that’s how the journey towards the fastest recovering algorithm started.Third attemptThe first step in the process is decoding base58. Let’s check out what the base58 encoding actually does to see if we can cut any corners.

We start with an arbitrary byte string, e.g. 00 d6 f6 4e e7 83 6a cf 6e 5a 93 7d 63 54 c3 a5 96 cd 24 2d fc 2f 78 fa 7c (represented in hex for simplicity).We interpret the byte string as a long number in big-endian: 5270856372487448678887896392566731007782045065082238990972.We then encode the number in radix-58: 19, 34, 35, 38, 49, 6, 50, 9, 16, 26, 12, 8, 11, 39, 36, 23, 46, 2, 16, 26, 20, 26, 43, 28, 7, 19, 18, 3, 32, 45, 30, 6, 0.This conversion process does not preserve the count of leading zero bytes (e.g. 00 ff and ff map to one radix-58 sequence, namely 4, 23), so we add all the leading zeroes from the byte string to the radix-58 representation. There was just one zero byte in the byte string, so we write 0, 19, 34, 35, 38, 49, 6, 50, 9, 16, 26, 12, 8, 11, 39, 36, 23, 46, 2, 16, 26, 20, 26, 43, 28, 7, 19, 18,

3, 32, 45, 30, 6, 0.Finally, we replace the numbers 0-57 with the corresponding characters from the sequence 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz. For instance, 0 maps to 1 and 57 maps to z: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71.Conversely, the decoding process is as follows:Replace the alphabet characters with numbers 0-57.Decode the long number from big-endian radix-58.Encode the long number into big-endian radix-256.Add however many leading zeroes there were in the radix-58 representation to the radix-256 representation.So, how does replacing a single character in the encoded string affect the byte string? For example, let’s replace A with a in the example address. On the first step, …, 6, 50, 9, 16, 26, … changes to …, 6, 50, 33, 16, 26, …. This is just adding 33 - 9 = 24 to a digit of a long number, which increases the long number from step 2 by 24⋅5825. In radix-256, this is still just addition with carry. Step 4 is a bit of a mouthful, but we can sidestep the complexity by abusing that Bitcoin addresses with a checksum are always 25 bytes long.So, how about we parse the address just once and then simulate flipping the case by adding or removing a constant (say, 24⋅5825 in the example above) from the byte representation of the address?

Let’s do just that:use itertools::Itertools; use num_bigint::BigUint; use num_traits::{One, Zero}; use sha2::{digest::Update, Digest, Sha256}; const BASE58_ALPHABET: &'static [u8] = b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"; fn main() { let garbled_address = "1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71"; let mut parsed_number: BigUint = Zero::zero(); let mut power_58_i: BigUint = One::one(); let mut possible_differences = Vec::new(); let mut base_address = vec![0u8; garbled_address.len()]; for (digit_index, byte) in garbled_address.bytes().enumerate().rev() { // Some letters, like L and o, are only valid base58 characters in one case; this // complicates the code a bit let digit1 = BASE58_ALPHABET .iter() .position(|&b| b == byte.to_ascii_uppercase()); let digit2 = BASE58_ALPHABET .iter() .position(|&b| b == byte.to_ascii_lowercase()); match (digit1, digit2) { (Some(digit1), Some(digit2)) if digit1 != digit2 => { // Two distinct variants are possible parsed_number += digit1 * &power_58_i; base_address[digit_index] = byte.to_ascii_uppercase(); // digit1 is uppercase, digit2 is lowercase, lowercase comes after uppercase in the // alphabet, so the difference is positive possible_differences.push((digit_index, (digit2 - digit1) * &power_58_i)); } (Some(digit), _) => { // Just the first variant is right parsed_number +=