A bech32 address ending with p can be modified be inserting or removing q characters immediately before the final p character to make a new valid bech32 address. Why does this work?
Are there any other similar mutation weaknesses in bech32?
References:
I'm going to provide a more algebraic explanation of the issue.
Every valid (and invalid) Bech32 string can be seen as a polynomial in the variable x, where the coefficients are elements of GF(32). I'm going to ignore the GF(32) part in what follows, so it suffices to say that they're simply numbers from 0 to 31 inclusive, with weird addition and multiplication rules that guarantee every operation always stays within the range 0-31.
The data part (which means the string excluding the human-readable part (HRP) and the "1" that follows it, but including the 6 checksum characters at the end) uses the character set that's included in BIP173 in table form. For example, a "q" means 0, "p" means 1, "3" means 17, and "l" means 31. Each of these characters forms the coefficient of the term of our polynomial. I'm going to ignore the human-readable part as well in what follows as it doesn't matter for the issue, but for completeness the HRP also encodes coefficients of the polynomial, but using a different (and slightly more complicated) translation.
For example, the string "3qlp" corresponds to the polynomial 17x3 + 31x + 1. As "q" represents 0, there is no x2 term.
Now, every valid Bech32 string corresponds to a polynomial p(x) that can be written as p(x) = f(x)⋅g(x) + 1 for some f(x), where g(x) = x6 + 29x5 + 22x4 + 20x3 + 21x2 + 29x + 18.
Why is that + 1 there? If it wasn't, then for every valid p(x) = f(x)⋅g(x), x⋅f(x)⋅g(x) = x⋅p(x) would also be a valid polynomial. As multiplying by x is simply adding a 0 (or "q") at the end, this would let anyone accidentally mutate valid Bech32 strings into distinct valid Bech32 strings by simply appending a "q".
However, it turns out that adding the + 1 does not fully solve this sort of issue. It isn't possible anymore to simply multiply by x, but it's still the case that for every valid p(x), xi⋅(p(x) - 1) + 1 for any i > 0 is also valid. If p(x) happens to end in a "p", it can be written as x⋅e(x) + 1 for some e(x). In this case, xi⋅e(x) + 1 is also a valid string, for every value of i. In string form, this corresponds to inserting "q" characters in the penultimate position (just before the final "p").
Similarly, if p(x) happens to end in a "qp", it can be written as xi⋅e(x) + 1 for some e(x) and i > 1. In this case, xj⋅e(x) + 1 where j < i is also a valid string. In string form, this corresponds to removing "q" character in the penultimate position (just before the final "p").
Pieter Wuille's comment gives a nice summary:
basically: take a bech32 string, xor a 1 into the last character, then push or pop as many 'q's as you like, and then xor a 1 into the last character again... should always give you a valid new bech32 string
Checksum code taken from Bitcoin Core is:
uint32_t PolyMod(const data& v)
{
uint32_t c = 1;
for (const auto v_i : v) {
uint8_t c0 = c >> 25;
c = ((c & 0x1ffffff) << 5) ^ v_i;
if (c0 & 1) c ^= 0x3b6a57b2;
if (c0 & 2) c ^= 0x26508e6d;
if (c0 & 4) c ^= 0x1ea119fa;
if (c0 & 8) c ^= 0x3d4233dd;
if (c0 & 16) c ^= 0x2a1462b3;
}
return c;
}
Basically, the checksum function has an internal variable that is modified with every 5-bit character, similar to SHA without padding and different sizes. What you should notice is that it both this and SHA are prone to length extension attacks, which means someone who doesn't know x but knows H(x) can calculate H(x || A), where A is any data sequence and || is the concat operator.
Called from:
data CreateChecksum(const std::string& hrp, const data& values)
{
data enc = Cat(ExpandHRP(hrp), values);
enc.resize(enc.size() + 6); // Append 6 zeroes
uint32_t mod = PolyMod(enc) ^ 1; // Determine what to XOR into those 6 zeroes.
data ret(6);
for (size_t i = 0; i < 6; ++i) {
// Convert the 5-bit groups in mod to checksum values.
ret[i] = (mod >> (5 * (5 - i))) & 31;
}
return ret;
}
In this function, simply the result of PolyMod is serialized, but the checksum's least significant bit is XOR'ed with 1. If you undo that, you can extend the checksum by feeding the PolyMod function (or the Initialize-Update-Finalize version of it) a number of five-bit zeros more, and if you XOR the least significant bit with 1 again, you'll get a valid checksum.
Why? Because a zero byte does not cause any if branch to run in the PolyMod function loop. c was zero, and it stays zero.
The reason XOR-1 was a part of the specification is (from my understanding) was to prevent adding an additional character at the end in a way that the checksum is still correct. Otherwise,
ii2134hk2xmat79tqqii2134hk2xmat79tqqqii2134hk2xmat79tqqqqwould all be correct, which is worse (even though there are length checks...)
In the CreateChecksum function, you'll see that to create a signature, 6 empty five-bits are appended (because it's how BCH works, checksum is set to empty before being calculated). Because PolyMod has no knowledge if the zeros are part of the input or the empty checksum, they're treated the same. Therefore you can:
1) Take any Bech32 address as a five-bit byte sequence
2) Xor the last byte with 1
3) Append arbitrary numbers
4) Add 6 empty bytes
5) Calculate PolyMod result
6) Xor the last byte with 1
7) Encode
The quirk described in the link given is when those "arbitrary numbers" in step 3 are zeros. The PolyMod requests a payload with 6 zeros appended to be checksummed (and trailing zeros make a difference in this case as c is nonzero), and the checksum should come just after the payload, if we want the checksum to be correct. You can add zeros to the end, and it'll stay correct. Only the XOR-1 thing has to be done.
Here's how the BCH checksum works and why it's unique:
If you give the PolyMod function a payload and 6 empty bytes (which is the length of the signature) it'll give you a value.
If you serialize this value in the place of the last 6 empty bytes and call the PolyMod function, it'll return zero. Whenever the checksum is correct, it returns zero. You can then discard the last 6 bytes and use the rest while decoding
Consider the PolyMod function's state after the payload and the checksum is processed. It returns zero, which is the value of the c variable (you can look at the code at the top). Same for c0. Since then, as long as v_i equals zero, c will stay zero. Therefore you can append zeros at the end without breaking the checksum. Or the converse, if you have a valid address, you can remove zeros at the end.
Plus some Xor-ing with 1, as I explained in the middle of the post. In Bech32 alphabet, p ^ 1 = q and q ^ 1 = p.
