[bitcoin-dev] Analysis of Bech32 swap/insert/delete detection and next steps

[bitcoin-dev] Analysis of Bech32 swap/insert/delete detection and next steps

[Pieter Wuille]

Hi all,

I've made a writeup on Bech32's detection abilities, analysing how it
behaves in the presence of not just substitution errors, but also
swapping of characters, and insertions and deletions:
https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb

It shows that the "insert or delete a 'q' right before a final 'p'" is
in fact the only deviation from the expected at-most-1-in-a-billion
failure to detect chance, at least when restricted to the classes of
errors analyzed with various uniformity assumptions. There is some
future work left, such as analyzing combinations of insertions and
substitutions, but I would be surprising if additional weaknesses
exist there.

It also shows that changing one constant in Bech32 would resolve this
issue, while not affecting the error detection properties for other
classes of errors.

So my suggestion for the next steps are:
* Update BIP173 to include the insertion weakness as an erratum, and
the results of this analysis.
* Amend segwit addresses (either by amending BIP173, or by writing a
short updated BIP to modify it) to be restricted to only length 20 or
32 (as fixed-length strings are unaffected by the insertion issue, and
I don't think inserting 20 characters is an interesting error class).
* Define a variant of Bech32 with the modified constant, so that
non-BIP173 uses of Bech32 can choose a non-impacted version if they
worry about this class of errors.
* Later, if and when we expect a need for non-32-byte witness programs
in the medium term, define an updated segwit address scheme that uses
the modified Bech32 variant.

I believe that the impact on production systems will be minimal using
the above, as many wallets already do not accept unknown witness
versions in outputs, and it gives us probably years to adapt.

What do people think?

Cheers,

-- 
Pieter

Re: [bitcoin-dev] Analysis of Bech32 swap/insert/delete detection and next steps

[ZmnSCPxj]

Good morning Pieter,

> Hi all,
>
> I've made a writeup on Bech32's detection abilities, analysing how it
> behaves in the presence of not just substitution errors, but also
> swapping of characters, and insertions and deletions:
> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb
>
> It shows that the "insert or delete a 'q' right before a final 'p'" is
> in fact the only deviation from the expected at-most-1-in-a-billion
> failure to detect chance, at least when restricted to the classes of
> errors analyzed with various uniformity assumptions. There is some
> future work left, such as analyzing combinations of insertions and
> substitutions, but I would be surprising if additional weaknesses
> exist there.
>
> It also shows that changing one constant in Bech32 would resolve this
> issue, while not affecting the error detection properties for other
> classes of errors.
>
> So my suggestion for the next steps are:
>
> -   Update BIP173 to include the insertion weakness as an erratum, and
>     the results of this analysis.
>

To clarify, this step does not modify anything about the implementation of BIP173, only adds this as an additional erratum section?

> -   Amend segwit addresses (either by amending BIP173, or by writing a
>     short updated BIP to modify it) to be restricted to only length 20 or
>     32 (as fixed-length strings are unaffected by the insertion issue, and
>     I don't think inserting 20 characters is an interesting error class).

To clarify, this refers to all SegWit address versions from 1 to 15, as this restriction exists for SegWit address v0?

>
> -   Define a variant of Bech32 with the modified constant, so that
>     non-BIP173 uses of Bech32 can choose a non-impacted version if they
>     worry about this class of errors.
>

Okay, this probably needs to be raised in lightning-dev as well, for invoice formats, as well as planned offers feature.

By my understanding, best practice for readers of Bech32-based formats would be something like the below:

1.  Define two variants of checksum, the current Bech32 checksum and the modified Bech32 checksum.
2.  Support both variants (software tries one first, then tries the other if it fails).
3.  Flag or signal some deprecation warning if current Bech32 checksum was detected.
4.  At some undefined point in the future, drop support for the current Bech32 checksum.

> -   Later, if and when we expect a need for non-32-byte witness programs
>     in the medium term, define an updated segwit address scheme that uses
>     the modified Bech32 variant.


Okay, so we will only use the modified Bech32 if and only if we expect to need a non-32-byte witness program for a particular non-0 SegWit version.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] Analysis of Bech32 swap/insert/delete detection and next steps

[Pieter Wuille]

> > So my suggestion for the next steps are:
> >
> > -   Update BIP173 to include the insertion weakness as an erratum, and
> >     the results of this analysis.
> >
>
> To clarify, this step does not modify anything about the implementation of BIP173, only adds this as an additional erratum section?

Correct - just documenting the issue.

> > -   Amend segwit addresses (either by amending BIP173, or by writing a
> >     short updated BIP to modify it) to be restricted to only length 20 or
> >     32 (as fixed-length strings are unaffected by the insertion issue, and
> >     I don't think inserting 20 characters is an interesting error class).
>
> To clarify, this refers to all SegWit address versions from 1 to 15, as this restriction exists for SegWit address v0?

Right, for v0 there is an inherent restriction to size 20 or 32
already, so this would only semantically change anything for version 1
through 16 (not 15).

> > -   Define a variant of Bech32 with the modified constant, so that
> >     non-BIP173 uses of Bech32 can choose a non-impacted version if they
> >     worry about this class of errors.
> >
>
> Okay, this probably needs to be raised in lightning-dev as well, for invoice formats, as well as planned offers feature.

It seems BOLT11 already doesn't care very much about the error
detection properties, as it's using Bech32 outside its design
parameters (max length 90 characters).

> By my understanding, best practice for readers of Bech32-based formats would be something like the below:
>
> 1.  Define two variants of checksum, the current Bech32 checksum and the modified Bech32 checksum.
> 2.  Support both variants (software tries one first, then tries the other if it fails).
> 3.  Flag or signal some deprecation warning if current Bech32 checksum was detected.
> 4.  At some undefined point in the future, drop support for the current Bech32 checksum.

I think it depends on the application and their tolerance to this sort
of errors. In some cases, these insertions may be detected already
with high probability (e.g. because of length restrictions, or the
fact that it adds random unstructured symbols at the end of the data
part).

> > -   Later, if and when we expect a need for non-32-byte witness programs
> >     in the medium term, define an updated segwit address scheme that uses
> >     the modified Bech32 variant.
>
> Okay, so we will only use the modified Bech32 if and only if we expect to need a non-32-byte witness program for a particular non-0 SegWit version.

Exactly.

-- 
Pieter