How does the bech32 length-extension mutation weakness work? 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:


issue raised against bech32 repo
mailing list post
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 &quot;1&quot; 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 &quot;q&quot; means 0, &quot;p&quot; means 1, &quot;3&quot; means 17, and &quot;l&quot; 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 &quot;3qlp&quot; corresponds to the polynomial 17x3 + 31x + 1. As &quot;q&quot; 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 &quot;q&quot;) at the end, this would let anyone accidentally mutate valid Bech32 strings into distinct valid Bech32 strings by simply appending a &quot;q&quot;.
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 &gt; 0 is also valid. If p(x) happens to end in a &quot;p&quot;, 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 &quot;q&quot; characters in the penultimate position (just before the final &quot;p&quot;).
Similarly, if p(x) happens to end in a &quot;qp&quot;, it can be written as xi⋅e(x) + 1 for some e(x) and i &gt; 1. In this case, xj⋅e(x) + 1 where j &lt; i is also a valid string. In string form, this corresponds to removing &quot;q&quot; character in the penultimate position (just before the final &quot;p&quot;).