1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
Return-Path: <pieter.wuille@gmail.com>
Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 64D8CC0881
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 Dec 2019 22:31:26 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by whitealder.osuosl.org (Postfix) with ESMTP id 4208185DA4
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 Dec 2019 22:31:26 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from whitealder.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id FtOT3XqqxCDa
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 Dec 2019 22:31:25 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-oi1-f171.google.com (mail-oi1-f171.google.com
[209.85.167.171])
by whitealder.osuosl.org (Postfix) with ESMTPS id 674108461B
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 Dec 2019 22:31:25 +0000 (UTC)
Received: by mail-oi1-f171.google.com with SMTP id c16so7958779oic.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 09 Dec 2019 14:31:25 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to;
bh=jDOWxfdDOg/UF2UJ13e5ZGm/Di874GUlM0z/0/Xgon4=;
b=lGagX9pLkAFLN4TUI/U/FW0tTBl/Nn2rGkk+6iEWazmMvoS9MW9qzTM0v4AXUbbHVi
o9j2S2CGMFZU+mkwlBT3iAnWF9Z6H8pRGVltgR+J+tXaOfdxp/quw3irGJk7BmXYnxCY
SpsEiEJyIsr3btAxFGMlsaVbdDEN3yVNHWCXJdCRPoT9hyJZuTnccYD+07UatPiqE0oM
t6ltiqjHenIZMi84igRy+5gvv88ATNdv/Pj1HiGQJLTK5Aajstx/Gs2v9cl+7jY+j/iR
fSaEw8nq8dt3oVsIqugV4CVVs7ZpvW0VUh5VYG5UMfRJ7UEqZsG9etrXF1ceL/a2KlVC
2FvA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=jDOWxfdDOg/UF2UJ13e5ZGm/Di874GUlM0z/0/Xgon4=;
b=ELwcUkrG1fBZsr1mXX62ZOtHOzlPUYPef+upb79N3wU1MJCphg3ruvNwPUZi19DFRc
8bqlia77qs1okoA2pAMS6yN0pQoAiuxRNIzS7QDLAQlCXN6gE2206WpOtJq1ffUQzvCJ
4nI1ENbZRV2E49+DKnh9LUpgsTVePrnAOhvLo1TniKgjBRlhYbkc96Gwi6HRtNwQlL+H
StTHhJTGJ9Lrcy3naNb97f5N8gfyQFDNJggX31pkrRXqY90BpCWNLzzr7T5XJHUiwNcU
NPzGDroyli5MUvhWfZ43Xv3Rc6PYlSeH46heGELdGfQsuprR1nHYhnQ5bLQ07xgBW2TK
o+ZQ==
X-Gm-Message-State: APjAAAVDjk0KZCp8Jj93RqFUEVzLLY0gy73EoyHir+OYX8Z4J3EoV1EC
DIie7lQnpMBG7q/oUxeA1vqv2NYyUH79Iv+gam5r/jfUTvw=
X-Google-Smtp-Source: APXvYqy9ueKjam7cXyJ+Sx3S2+gO/rtQpiCht86KiiMnhtkeaISdl4s91nEWc2ICJW8FJBi2CyTXysJjjfNz3+D05y0=
X-Received: by 2002:a54:4117:: with SMTP id l23mr1262223oic.140.1575930684312;
Mon, 09 Dec 2019 14:31:24 -0800 (PST)
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 09 Dec 2019 22:31:26 -0000
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
|
