In [3]:

```
from hashlib import sha256
import base58
```

Generating a valid bitcoin address that shares most of the characters with another address is not difficult for an attacker if they don't care about having the private key. This allows an attacker to cause you to lose funds with a relatively trivial amount of work. **I can only recommend that bitcoin users verify every character in every address they interact with.**

At it's most difficult, you can generate a different valid non-segwit address by changing any 6 non-sequential characters in 10's of hours using this notebook and a standard laptop. If you fix the last 4 characters and up to the first 25 charaters, it it significantly easier (~2-3min to generate a valid malicious address). Fixing the final 6 characters is equivalent to the most difficult case.

For segwit addresses, the manipulation is easier. Modifying non-sequential characters only affect the final 6 characters instead of all characters to the right of the modification. Finding a malicious address that matches the last 4 characters and most of the other characters only takes a minute via this notebook.

The goal of this post is to demonstrate why it’s important to verify every character in an address, not just the first and last few values, by showing how easy it is for an adversary to generate an address that looks similar to a valid address generated by your wallet. While such an attack couldn’t be used to steal funds, it would still result in lost bitcoin.

I’ll also cover some of the most important mechanics behind bitcoin address serialization, including Base58 encoding, Bech32 encoding and checksums.

All code for this post is written in python. You can run it yourself from the jupyter notebook, available on GitHub here.

**NOTE:** For this example, I will be using this address: `1HU1LDBXUg73f2ro2e2dB3XY8cFoYLFgZZ`

, it was randomly grabbed from a
block explorer, apologies if it is yours.

Before I explain address serialization, I must first explain Base58, and give some examples of converting between bases.

When we talk about the “base” of a number, what we’re referring to is the formatting used to represent that data. This is also known as Positional Notation. Most recognize the term “binary”, which is how we can understand computers to interpret data. Binary is a base 2 representation, i.e. 1s and 0s (bi - two numbers). The decimal system is base 10 (deci - ten, i.e. 0-9) and hexadecimal is base 16 which uses the numbers 0-9 and letters A-F, generally used to present data in a more human readable format.

Base58 uses 58 characters:
(`123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz`

)

In contrast to Base32 or Base64, the digits of the encoding do not line up well with byte boundaries of the original data. For this reason, the method is well-suited to encode large integers, but not designed to encode longer portions of binary data.

Because 58 is not a power of two, the characters in base58 don't correspond to a fixed number of bytes. Decimal has the same problem, one byte has 256 values, but that can require 1, 2, or 3 decimal characters.

Because of this, when converting a number to base58 from any other standard base, it may be impossible to know what the least significant digits will be, as they are dependent on all the digits in the input. (Unfortunately I couldn’t find a reference for this, so if any readers can help verify it would be greatly appreciated.)

The most significant digits, however, are not dependendent on all the digits, only the most significant ones. If you’re curious to learn more about what we’re talking about when we reference most and least significant digits, the best way is to learn about “Endianness” which you can see here.

An example might help explain this:

In [4]:

```
a_big_number = 1234567890
```

In [6]:

```
print("Decimal: ", a_big_number, " Length: ", len(str(a_big_number)))
a_big_hex_number = str(hex(a_big_number))[2:]
print("Hexidecimal: ", a_big_hex_number, " Length: ", len(a_big_hex_number))
a_big_byte_number = a_big_number.to_bytes(4,byteorder='big')
print("Bytes:", list(a_big_byte_number), " Length: ", len(a_big_byte_number))
a_big_base58_number = base58.b58encode(a_big_number.to_bytes(4,byteorder='big'))
print("base58: ", a_big_base58_number.decode('ascii'), " Length: ", len(a_big_base58_number))
a_big_base58_number = base58.b58encode_int(a_big_number)
print("base58 from int: ", a_big_base58_number.decode('ascii'), " Length: ", len(a_big_base58_number))
```

`0`

), and see what happens.

In [7]:

```
a_big_number = 1234567891
print("Decimal: ", a_big_number, " Length: ", len(str(a_big_number)))
a_big_hex_number = str(hex(a_big_number))[2:]
print("Hexidecimal: ", a_big_hex_number, " Length: ", len(a_big_hex_number))
a_big_byte_number = a_big_number.to_bytes(4,byteorder='big')
print("Bytes:", list(a_big_byte_number), " Length: ", len(a_big_byte_number))
a_big_base58_number = base58.b58encode(a_big_number.to_bytes(4,byteorder='big'))
print("base58: ", a_big_base58_number.decode('ascii'), " Length: ", len(a_big_base58_number))
```

Let’s next change one of the most significant digits (on the left side) and see what the result is.

In [10]:

```
a_big_number = 1334567890
print("Decimal: ", a_big_number, " Length: ", len(str(a_big_number)))
a_big_hex_number = str(hex(a_big_number))[2:]
print("Hexidecimal: ", a_big_hex_number, " Length: ", len(a_big_hex_number))
a_big_byte_number = a_big_number.to_bytes(4,byteorder='big')
print("Bytes:", list(a_big_byte_number), " Length: ", len(a_big_byte_number))
a_big_base58_number = base58.b58encode(a_big_number.to_bytes(4,byteorder='big'))
print("base58: ", a_big_base58_number.decode('ascii'), " Length: ", len(a_big_base58_number))
```

In [12]:

```
print('hex', ' bytes', ' binary', ' decimal')
hex_number = "4f8be3d2"
print(hex_number, list(bytes.fromhex(hex_number)), "{0:b}".format(int(hex_number,16)), int(hex_number,16))
hex_number_2 = "5f8be3d2"
print(hex_number_2, list(bytes.fromhex(hex_number_2)), "{0:b}".format(int(hex_number_2,16)), int(hex_number_2,16))
```

Now let's talk about bitcoin addresses. A bitcoin address has three components:

- The version byte
- The data
- The Checksum

The version byte gives us information about the context of the address.

0x00 for P2PKH addresses on the main Bitcoin network (mainnet)

0x6f for P2PKH addresses on the Bitcoin testing network (testnet)

0x05 for P2SH addresses on mainnet

0xc4 for P2SH addresses on testnet

This gives wallets and other related software the ability to check that the address is being used where it’s expected. For example, if you paste in an address with the version byte `0x6f`

into a mainnet wallet, the wallet will be able to show an error, letting you know that you probably don’t want to send funds to an address meant for testnet.

This will depend on the type of address you’re generating, but for a P2PKH address, the data portion of an address is the hash (actually hashed twice: RIPEMD(SHA256(pubkey))) of a public key.

Bitcoin Addresses are actually Base58Check encoded, **not** simply Base58.

A checksum is used in computing for data validation. For an address, this can detect typos by comparing the data to the checksum and making sure we get what we expected.

In Base58Check, you first double-hash the version byte and data with sha256. You take the first 4 bytes of the resulting hash and append it to the data, and then you convert the full (version byte + data + checksum) byte array into Base58.

By only taking the first 4 bytes of the hash, the checksum field is far from immune to collisions. SHA256 properly generates any even distribution of outputs. 4 bytes can only encode $256^4$ values (4,294,967,296), so if you want to find a hash collision, you only need to try an expected 4.3 Billion values per collision. This is important for this discussion, but it isn't the end of the story.

You might think at this point, "Cool, so if I want to create a malicious bitcoin address, I'll just decode it to bytes, and start changing bytes until I find a checksum collision, and I'm set!" But you'd be wrong. If you skimmed the Base58 discussion above, maybe take a closer read. **If you change some bytes in the middle of an address, when you go to encode it in base58, all of the lower significant digits are modified in base58.**

So now you might think: "Shit, so I have to modify the data, find a checksum collision, and then hope it encodes to the same last 4 digits? I'm screwed, bitcoin addresses are hard."

It's true, bitcoin addresses are confusing, but no, it's not that difficult to create a malicious address, and that's because while the checksum has to be *valid*, it doesn't have to be the *same* checksum of the original address.

Let's start simple. Let's say you want a valid bitcoin address with the same $A$ number of characters at the beginning, and the last digit to be the same. Let's assume that the resulting addresses will have an even distibution of final characters, since we're going to be changing a bunch of digits (some in the data, and all of the checksum).

If it's an even distribution, for each value we try, we have a 1-in-58 probability that it will be the correct value. Let's give it a try!

We'll try every value in one byte, that's 256 values, but the last character can be only one of the 58 characters in Bse58, so we should expect to see 256/58 = 4.4 matches

In [15]:

```
# Note for the nerds: I'm not optimizing the code, instead I'm favoring readability.
def cycle_through_one_byte(ver, data, digit, match):
dataarray = bytearray(data)
for i in range(256):
# Change a byte
dataarray[digit] = i
# Compute the double sha256 hash and take the first 4 bytes
check1 = sha256(sha256(ver+dataarray).digest()).digest()[:4]
# convert to base58
addr = base58.b58encode(ver+dataarray+check1)
# Check the last digit
if (addr[-1:] == match):
print('found: ', addr.decode('ascii'))
```

In [16]:

```
original_address ='1HU1LDBXUg73f2ro2e2dB3XY8cFoYLFgZZ'
k = base58.b58decode(original_address)
verbyte, data, check0 = k[0:1], k[1:-4], k[-4:]
```

In [17]:

```
cycle_through_one_byte(verbyte, data, 19, b'Z')
```

In [18]:

```
cycle_through_one_byte(verbyte, data, 19, b'1')
```

In [19]:

```
%time cycle_through_one_byte(verbyte, data, 19, b'2')
```

In [20]:

```
cycle_through_one_byte(verbyte, data, 10, b'Z')
```

Notice how the addresses look significantly different from each other when not changing the least significant byte.

But if we want the last digit to be a `1`

there’s only one match.

In [22]:

```
cycle_through_one_byte(verbyte, data, 10, b'1')
```

found: 1HU1LDBXUg73f2sgs9f2GtSEnq6YQ4sgH1

Though maybe that's just statistics being fun.

Let's move on to 2 digit matches. With 2 digits we have $58^2$ so 3,364 options, But if we cycle through all values in 2 bytes, that's $256^2$ or 65,536. So we should expect to see, 19.5 matches

In [27]:

```
def cycle_through_two_bytes(ver, data, match):
total_matches = 0
dataarray = bytearray(data)
for i in range(256):
# Change a byte
dataarray[19] = i
for j in range(256):
dataarray[18] = j
# Compute the double sha256 hash and take the first 4 bytes
check1 = sha256(sha256(ver+dataarray).digest()).digest()[:4]
# convert to base58
addr = base58.b58encode(ver+dataarray+check1)
# CHeck the last two digits
if (addr[-2:] == match):
total_matches+=1
print('found: ', addr.decode('ascii'))
print("Total Matches:", total_matches)
```

In [28]:

```
cycle_through_two_bytes(verbyte, data, b'ZZ')
```

In [29]:

```
cycle_through_two_bytes(verbyte, data, b'aZ')
```

In [30]:

```
%time cycle_through_two_bytes(verbyte, data, b'11')
```

Pretty solid so far. Notice that I'm changing only the least significant byte in the data section. This means the whole first section of address is unchanged.

Let's move on to 3 digits.

With 3 digits we have $58^3$ so 195,112 options, But if we cycle through all values in 3 bytes, that's $256^3$ or 16,777,216. So we should expect to see, 86 matches

In [31]:

```
def cycle_through_three_bytes(ver, data, match):
total_matches = 0
dataarray = bytearray(data)
for i in range(256):
# Change a byte
dataarray[19] = i
for j in range(256):
dataarray[18] = j
for k in range(256):
dataarray[17] = k
# Compute the double sha256 hash and take the first 4 bytes
check1 = sha256(sha256(ver+dataarray).digest()).digest()[:4]
# convert to base58
addr = base58.b58encode(ver+dataarray+check1)
# CHeck the last digit
if (addr[-3:] == match):
total_matches+=1
#print('found: ', addr)
print("Total Matches:", total_matches)
```

In [32]:

```
print(original_address)
```

1HU1LDBXUg73f2ro2e2dB3XY8cFoYLFgZZ

In [33]:

```
%time cycle_through_three_bytes(verbyte, data, b'gZZ')
```

Total Matches: 79 CPU times: user 4min 45s, sys: 422 ms, total: 4min 46s Wall time: 4min 46s

Let's move on to 4 digits. Which for some reason is a standard, "check the first and last 4". This is probably due to misunderstanding the checksum field. 4 base58 digits can only encode 3 bytes worth of data $(58^4 < 256^3)$, and as mentioned earlier, you can't decode the least significant digits only, you need the full value to decode.

With 4 digits we have $58^4$ so 11,316,496 options, But we could cycle through all values in only 3 bytes because that's $256^3$ or 16,777,216. So we should expect to see, 1.5 matches.

We can modifed a fourth byte, but instead of using all 256 available values, just use 4 values. This will boost the expect matches to 6 (scanning over $256^3 * 4$ or 67,108,864 values) while expecting ~20min execution time.

In [21]:

```
def cycle_through_four_bytes(ver, data, match):
total_matches = 0
dataarray = bytearray(data)
for i in range(4):
# Change a byte
dataarray[19] = i
for j in range(256):
dataarray[18] = j
for k in range(256):
dataarray[17] = k
for l in range(256):
dataarray[16] = l
# Compute the double sha256 hash and take the first 4 bytes
check1 = sha256(sha256(ver+dataarray).digest()).digest()[:4]
# convert to base58
addr = base58.b58encode(ver+dataarray+check1)
# Check the last four digits
if (addr[-4:] == match):
total_matches+=1
print('found: ', addr.decode('ascii'))
print("Total Matches:", total_matches)
```

In [22]:

```
print(original_address)
```

1HU1LDBXUg73f2ro2e2dB3XY8cFoYLFgZZ

In [23]:

```
%time cycle_through_four_bytes(verbyte, data, b'FgZZ')
```

Now what about fixing the last 5 digits?

Now we have $58^5$ = 656,356,768, which is 40x more than 3 bytes, but still well less than the full $256^4$ (4,294,967,296). That'll be roughly 3 hours of execution to generate one, which, while being more than feasible using off-the-shelf hardware, is more than I’m willing to put my computer through at the moment, so we'll leave that as an exercise for you to try at home if you’re interested.

And what about 6 or 7 digits?

6 digits gives us a 1 in 38,068,692,544 chance to find a valid address. That's interesting because now we're above $256^4$ which is the hash-collision scale. At this point, I think it will be faster to invert this process.

Instead of searching for matches to our base58 pattern, let's search through base58 address values to find valid addresses. A given base58 string should have a 1-in-4,294,967,296 chance of being valid $(256^4)$.

Based on my earlier benchmarks, that should take roughly 20 hours of execution (4200M tries per collision / 3M tries per minute $\approx$ 20hrs) . To get to that number of options, you would need to be able to change 6 digits of the address, and I don't think they need to be contiguous.

If any readers want to try this, I'd love to see the results.

In [23]:

```
import bech32
import itertools
```

Here is the list of characters used in Bech32 encoding.

In [24]:

```
print(''.join(sorted(list(bech32.CHARSET))))
```

023456789acdefghjklmnpqrstuvwxyz

In [25]:

```
an_address = 'bc1pw508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7k7grplx'
```

Like non-segwit addresses, segwit addresses contain several pieces of information:

This is analogous to the version bytes in a non-segwit address. `bc`

for mainnet addresses, `tb`

for testnet addresses. The Bech32 spec allows for many different values here, but only these two options are currently used for bitcoin addresses.

This is the number `1`

. Note that `1`

isn't part of the Bech32 encoding character set. This means that the data part will not contain the number `1`

.

The data part of the address starts with the 'witness version' character, followed by the characters that actually determine the address. Currently, that is 20 bytes of data for single signature addresses or 32 bytes for script adddresses (which includes multi-sig addresses). These bytes are first converted to 5-bit chunks so that they can be encoded with the base32 character set.

Like non-segwit addresses, a checksum is appended to the end of the address. Bech32 addresses use a 6-character checksum that is defined in the BIP. So the last 6 characters in a segwit address are the checksum.

I'll follow the same approach that I used above for non-segwit addresses, but this time it's easier because modifying one character only changes that character and the last 6 characters that are the checksum. So I'll cycle through the 32 values for a particular character and see if the last character or two in the checksum matches the original address

In [30]:

```
def cycle_through_one_char_and_match_one(address, digit):
hrp, data = bech32.bech32_decode(an_address)
checksum = bech32.bech32_create_checksum(hrp, data)
for i in range(32):
# Change a byte
data[digit] = i
# Compute the checksum
check1 = bech32.bech32_create_checksum(hrp, data)
# Check the last digit
if (check1[-1:] == checksum[-1:]):
print('found: ', bech32.bech32_encode(hrp, data))
def cycle_through_two_char_and_match_one(address, digits):
hrp, data = bech32.bech32_decode(an_address)
checksum = bech32.bech32_create_checksum(hrp, data)
for values in itertools.product(range(32), repeat=2):
# Change the bytes
for indx, digit in enumerate(digits):
data[digit] = values[indx]
# Compute the checksum
check1 = bech32.bech32_create_checksum(hrp, data)
# Check the last digit
if (check1[-1:] == checksum[-1:]):
print('found: ', bech32.bech32_encode(hrp, data))
```

In [31]:

```
print(an_address)
%time cycle_through_one_char_and_match_one(an_address, 8)
```

It shouldn't be a surprise that we don't get any modified matches when cycling through one character. There is a 1/32 chance of getting checksum with the same last digit, and we only tried 32 values (and found the original address).

We should expect if we cycle through a second character and only match on the last character that we will find 32 matches:

In [32]:

```
print(an_address)
%time cycle_through_two_char_and_match_one(an_address, [8, 10])
```

And 32 matches is what we find! And notice that only the two characters I chose to modify have changed, along with the five character before the last character (after the 'k').

Now for cycling through 3 characters looking for matches of the last two characters:

In [35]:

```
def cycle_through_three_char_and_match_two(address, digits):
hrp, data = bech32.bech32_decode(an_address)
checksum = bech32.bech32_create_checksum(hrp, data)
for values in itertools.product(range(32), repeat=3):
# Change the bytes
for indx, digit in enumerate(digits):
data[digit] = values[indx]
# Compute the checksum
check1 = bech32.bech32_create_checksum(hrp, data)
# Check the last two digits
if (check1[-2:] == checksum[-2:]):
print('found: ', bech32.bech32_encode(hrp, data))
```

In [36]:

```
%time cycle_through_three_char_and_match_two(an_address, [8, 10, 12])
```

And now we cycle through 4 characters matching the last 3 characters:

In [37]:

```
def cycle_through_four_char_and_match_three(address, digits):
hrp, data = bech32.bech32_decode(an_address)
checksum = bech32.bech32_create_checksum(hrp, data)
for values in itertools.product(range(32), repeat=4):
# Change the bytes
for indx, digit in enumerate(digits):
data[digit] = values[indx]
# Compute the checksum
check1 = bech32.bech32_create_checksum(hrp, data)
# Check the last digit
if (check1[-3:] == checksum[-3:]):
print('found: ', bech32.bech32_encode(hrp, data))
```

In [38]:

```
%time cycle_through_four_char_and_match_three(an_address, [8, 10, 12, 14])
```

In [39]:

```
def cycle_through_five_char_and_match_four(address, digits):
hrp, data = bech32.bech32_decode(an_address)
checksum = bech32.bech32_create_checksum(hrp, data)
for values in itertools.product(range(4), range(32), range(32), range(32), range(32)):
# Change the bytes
for indx, digit in enumerate(digits):
data[digit] = values[indx]
# Compute the checksum
check1 = bech32.bech32_create_checksum(hrp, data)
# Check the last four characters
if (check1[-4:] == checksum[-4:]):
print('found: ', bech32.bech32_encode(hrp, data))
```

In [14]:

```
%time cycle_through_five_char_and_match_four(an_address, [6, 8, 10, 12, 14])
```

Extrapolating out, looks like it would take ~45min to do a full run of 5 alterations and we should expect ~32 addresses with the same last 4 characters.

it would take ~24 hours to do a full run of 6 alterations and we would expect to see ~32 addresses with the same last 5 characters, and this would be the same timescale to find collisions of the full last 6 characters. And unlike base58Check, the least significant digits in a bech32 address won't have changed when we do this brute-force algorithm, so once the checksum matches, we can loop over any arbitrary set of characters in the data section of the address.

To illustrate why the exercises above matter, imagine you’re trying to send your bitcoin from an exchange to your hardware wallet. While none of what we produced in the scripts above would allow an attacker to steal your bitcoin, it could let an attacker destroy that bitcoin, if you don’t check the full address. When you get that address from your wallet's interface, you might copy-paste it in to the exchange website. If the attacker has gained access to your system’s clipboard, this is an opportunity to replace that address with one that looks extremely similar to the valid address you pasted in. To a user who only verifies the first and last few characters, these will look identical.

The code presented here was run on a standard laptop using unoptimized code, but this type of code is trivial to parallelize, and would be simple to optimize for speed. I do not doubt that the most difficult address manipulation could happen during the time it takes for a page to load. Because of this, **I can only recommend that bitcoin users verify every character in every address they interact with.**