From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 64D8CC0881 for ; 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 ; 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 ; 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 ; Mon, 9 Dec 2019 22:31:25 +0000 (UTC) Received: by mail-oi1-f171.google.com with SMTP id c16so7958779oic.3 for ; 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 Date: Mon, 9 Dec 2019 14:31:13 -0800 Message-ID: To: Bitcoin Dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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