From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 42EC5C002B for ; Mon, 20 Feb 2023 00:52:50 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 0B360405BD for ; Mon, 20 Feb 2023 00:52:50 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 0B360405BD Authentication-Results: smtp2.osuosl.org; dkim=pass (2048-bit key) header.d=blockstream-com.20210112.gappssmtp.com header.i=@blockstream-com.20210112.gappssmtp.com header.a=rsa-sha256 header.s=20210112 header.b=eyL96jrI X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.899 X-Spam-Level: X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id WzvuFbWTpXLh for ; Mon, 20 Feb 2023 00:52:48 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 9E7AE40291 Received: from mail-pg1-x536.google.com (mail-pg1-x536.google.com [IPv6:2607:f8b0:4864:20::536]) by smtp2.osuosl.org (Postfix) with ESMTPS id 9E7AE40291 for ; Mon, 20 Feb 2023 00:52:48 +0000 (UTC) Received: by mail-pg1-x536.google.com with SMTP id 20so746881pgq.8 for ; Sun, 19 Feb 2023 16:52:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream-com.20210112.gappssmtp.com; s=20210112; t=1676854368; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=qcM6dz4ONmQliizEC1eqRg6o3t2Jdsxhg1ot39zE8eA=; b=eyL96jrIStcQxvz+CjpfwEg4OBOwX9UZSvepRe8VI9MFl96HSbO/79blQz2b1XJiPR 8NuLt1HHevvj7YhkRFx+uucaleHsoiDMMR0l1tTQFGikFvphg1tvzElMgMmNe2WgmghC y9NdXdLvGWKl2WfgckCtAYpIzrE50JZOyo3qWuCzw3dSuV6X+FBu5GbFo3jXDhSflzYf +TiZVd12qP2l0HQoGKrpEao9KYmYWsHNU+82ESCE7aWOUo/xbYz6aMlFjob1BOKTPA2R GEZBr1p8Mu7UDlkunay7sZDakvjOsJjKMJiRC3y177Kxk1Tpf47GfvTbcNO4bpMhq1Fq XAVA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1676854368; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=qcM6dz4ONmQliizEC1eqRg6o3t2Jdsxhg1ot39zE8eA=; b=aq909mcPT0OB6Us/3C6ZTrBcgVxE2NrEjTYtEutNmXG5AjkleJ+C9/3UEzY4BdUE/W Trny6GSYN0M529skpgGyRktXHpSkYs547t3cXkbeDXJ4O9Q6aRwxS5cwCl6sZCO55Thq b516e/Bpd9kFiBrAT8wMNQO7HqUbKO6JMFknz5l3cDNl7N//UeSSNgPfOY1NrokBjyJA ost1vBwhByar5k2WkmoMME0yxiKAmKV3U4qAxLDjhWYigRZCmCaOLo1SPPZN409ZWZmi u1LegUqxJ/ZIkx83tyPofRUMhDaw1PvedsEHwqVxkbOIEriP6VM1IKLsG5XDYAIU3QAh 5QnA== X-Gm-Message-State: AO0yUKUy08f7rb6eXKxcuaOiXaU0cjeN4elE1zCwyAQWU4WPAXc3nOdC ZYHizg11wlY0s8YWr7pLH7LgHkVl3vUYRol70IwplA== X-Google-Smtp-Source: AK7set9EE6DVk7LrXAQFlDsxarkMph9MdgPf77mHOXyh7/DLz6tn17qG4Pl4T8cXsVEKXm+YqkmNIC9Jn8Yp5w2IQdI= X-Received: by 2002:a05:6a00:d49:b0:5a9:bbac:23c6 with SMTP id n9-20020a056a000d4900b005a9bbac23c6mr78624pfv.14.1676854367785; Sun, 19 Feb 2023 16:52:47 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: "Russell O'Connor" Date: Sun, 19 Feb 2023 19:52:36 -0500 Message-ID: To: Andrew Poelstra , "David A. Harding" , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000eeb19705f5171479" Subject: Re: [bitcoin-dev] Codex32 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, 20 Feb 2023 00:52:50 -0000 --000000000000eeb19705f5171479 Content-Type: text/plain; charset="UTF-8" On Sun, Feb 19, 2023 at 5:13 PM Andrew Poelstra via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > On Sun, Feb 19, 2023 at 10:13:33AM -1000, David A. Harding wrote: > > I'm curious about whether there's a way to prevent this attack without > > otherwise compromising the properties of the code? For example, some > > extra data that Bob can carry around (or memorize) for verifying the > > shares haven't changed, but which is not otherwise needed for recovery > > (so there's no problem if it's lost). > > > > Unfortunately not, as near as I can tell ... one way to think of this is > that Alice can flip a lot of random tiles then "error correct" it to get > a new valid, but incorrect, seed. So as long as we support error > correction it'll be possible to wreck seeds in this way. > > It's actually even worse than this ... as long as there's a clearly > defined "checksum" at the end of a share, Alice will be able to mangele > tiles and then just re-compute the checksum at the end. > > So what we really need to prevent this is something like a MAC: where > Bob has a secret value which gets input into the checksum somehow, which > Alice can't create valid checksums without knowing. Unfortunately I > don't see any way to do this with linear codes. With a hash-based > "checksum" a la BIP39 it would definitely be possible, but of course, > not hand-computable. > Speaking off the cuff and as a non-cryptographer (i.e do NOT rush off and do this without any vetting) but Christopher Allen once referred me to an cypher tile set called LS47 . If we set aside the cypertext, I suspect we can form a MAC by recording some random initial tile configuration, running the LS47 algorithm, and recording the final tile configuration. These records are not sensitive as (presumably!) the share data is not recoverable from just knowing these two configurations. So one can keep these records with you, digitally sign them or whatever, and then take them to your share on a regular basis to rerun the LS47 algorithm to see if you still get the same final state from the initial state. Perhaps something more specific to Bech32 could be designed, but otherwise this (alleged) MAC process isn't Codex32 specific. --000000000000eeb19705f5171479 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Sun, Feb 19, 2023 at 5:13 PM Andrew Poelstra via bitcoin-dev <= = bitcoin-dev@lists.linuxfoundation.org> wrote:
On Sun, Feb 19, 2023 at 10:13:33AM -10= 00, David A. Harding wrote:
> I'm curious about whether there's a way to prevent this attack= without
> otherwise compromising the properties of the code?=C2=A0 For example, = some
> extra data that Bob can carry around (or memorize) for verifying the > shares haven't changed, but which is not otherwise needed for reco= very
> (so there's no problem if it's lost).
>

Unfortunately not, as near as I can tell ... one way to think of this is that Alice can flip a lot of random tiles then "error correct" it= to get
a new valid, but incorrect, seed. So as long as we support error
correction it'll be possible to wreck seeds in this way.

It's actually even worse than this ... as long as there's a clearly=
defined "checksum" at the end of a share, Alice will be able to m= angele
tiles and then just re-compute the checksum at the end.

So what we really need to prevent this is something like a MAC: where
Bob has a secret value which gets input into the checksum somehow, which Alice can't create valid checksums without knowing. Unfortunately I
don't see any way to do this with linear codes. With a hash-based
"checksum" a la BIP39 it would definitely be possible, but of cou= rse,
not hand-computable.

Speaking off the cuff and as = a non-cryptographer (i.e do NOT rush off and do this without any vetting) b= ut Christopher Allen once referred me to an cypher tile set called LS47 <= ;https://gitea.blesmrt.net/e= xa/ls47>.=C2=A0 If we set aside the cypertext, I suspect we can form= a MAC by recording some random initial tile configuration, running the LS4= 7 algorithm, and recording the final tile configuration.=C2=A0 These record= s are not sensitive as (presumably!) the share data is not recoverable from= just knowing these two configurations.=C2=A0 So one can keep these records= with you, digitally sign them or whatever, and then take them to your shar= e on a regular basis to rerun the LS47 algorithm to see if you still get th= e same final state from the initial state.

Perhaps= something more specific to Bech32 could be designed, but otherwise this (a= lleged) MAC process isn't Codex32 specific.
--000000000000eeb19705f5171479--