MIME-Version: 1.0
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Mon, 9 Dec 2019 14:31:13 -0800
Message-ID: <CAPg+sBgdspmfK1qpG=9N9fAtVNkMDd+xym7yHdjq=zYnqeh5dA@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Subject: [bitcoin-dev] Analysis of Bech32 swap/insert/delete detection and
	next steps
Precedence: list

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