path: root/25/3a68a40b845ffb0c2ba04e8ef2835c3b828c7d

Return-Path: <mbencun@gmail.com>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 5A46FC07FF
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 21 Mar 2020 20:29:40 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by fraxinus.osuosl.org (Postfix) with ESMTP id 4CD638685E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 21 Mar 2020 20:29:40 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from fraxinus.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id KCfTy4ovw0gD
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 21 Mar 2020 20:29:39 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-wm1-f41.google.com (mail-wm1-f41.google.com
 [209.85.128.41])
 by fraxinus.osuosl.org (Postfix) with ESMTPS id D6E7E86362
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 21 Mar 2020 20:29:38 +0000 (UTC)
Received: by mail-wm1-f41.google.com with SMTP id a9so7130902wmj.4
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 21 Mar 2020 13:29:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=OqRcFarfXPC0dynS1L/Ul+0FOktvX70F1ra7ansG334=;
 b=j4doLpWitKwXawo7NjyYCKMBd9zXOmS0dMTRw6HzbnN1nDxwYIxaZhtFWQl46XX7nK
 5zGrrX7I9wNnquLqc2aA9f7RqoKqofZCrd+95o2kKmBiK2jMfbUUZeM3ZepxqONBDk84
 K/3jdHFXAAYX61pGhvzoxlCJWjiLAj7qNGAGrgvspLEyIQK1ygFqtnRTxNEeVfb84Etg
 UiAJ/IRXSFTu9tLI5qlfsGTDdYp4WOlDRwl5FjVlreEkKZfrCvo0g0YBlofawevYBm4S
 tFxA1XTyCJ8+oGCJEuIqNwnDIXYU89M5XH173a+Dyplnb7ImI/J8NpkTznYMYQlgBC27
 fuYA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=OqRcFarfXPC0dynS1L/Ul+0FOktvX70F1ra7ansG334=;
 b=tUo9RvQ/VmbBBpGSG7LkRUhHHeO2YUij7maZ92++eFvWrVHhCTAljFxV9G3YJRU7Ms
 XvTy63Mm0/4KXAfOKPWIQS8ePapeyEPKMO1JSzkJenJWC1SVloxUXIU7T/7MXzi2sVsm
 YCEe9LJpbbr7IxlSImwHgiAA34uJzSOoD3pDs+o9gJ5hWlRkOGsNjM7OW2umitSelNZf
 D75Lfqsih592JGkJ8n0MsbYznRSgCpbZIXJ4fYv/7DXrp95sV6lSrnWKGx6o8RzBlnQk
 YZB0lZ2eLqVmv9pE/GGd6nFu0cCnQctEHJXbngeZDp/ckgtENaxqKM1O6kP10e4U6JzB
 78AA==
X-Gm-Message-State: ANhLgQ1lduaeckchnRE+Mt1eMtm9M0E+4paubpFtlh5Eg/TMNohVej1u
 GnlN8S5i1QKGVGEq4wF35VFwzpICV5FuxJKIWs26GUsz
X-Google-Smtp-Source: ADFU+vukwOASz3E7vHW+jPSNoGvCXl9MY+Du80hwSElpTFzoqLUeaHTDdr1vD5eH5Yz1T5+7YFIi33LybDWAB2rWg9A=
X-Received: by 2002:a1c:9d09:: with SMTP id g9mr18238404wme.68.1584822577218; 
 Sat, 21 Mar 2020 13:29:37 -0700 (PDT)
MIME-Version: 1.0
References: <VZTbLR9RlkkyNg6mOOIxedh7H0g8NGlaCmgBfCVXZ4RNfW3axefgoTqZGXjAQZFEuekujVGjRMv8SifDIodZ6tRGaaXQ_R63rFa03SGS6rg=@wuille.net>
 <de7bd393327015a5b97ffff0d15a7c90d2d2196a.camel@timruffing.de>
In-Reply-To: <de7bd393327015a5b97ffff0d15a7c90d2d2196a.camel@timruffing.de>
From: Marko Bencun <mbencun@gmail.com>
Date: Sat, 21 Mar 2020 21:29:26 +0100
Message-ID: <CAOkeP8tn42PQvnSy_5BZ4H54F9myBODqsYFrGHDs=sncyohYfA@mail.gmail.com>
To: Tim Ruffing <crypto@timruffing.de>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000bf49fd05a1634216"
X-Mailman-Approved-At: Sat, 21 Mar 2020 20:33:38 +0000
Subject: Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques
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: Sat, 21 Mar 2020 20:29:40 -0000

--000000000000bf49fd05a1634216
Content-Type: text/plain; charset="UTF-8"

Practically speaking, most hardware wallets allow you to import your own
BIP39 seed, so you can work around key generation attacks today, with a one
time inconvenience at the start. However, with the signing nonce attacks, a
user today has no protection.

Mitigating key generation attacks would be very desirable, but I see it as
independent of anti nonce covert channel protection.

On Sat, Mar 21, 2020 at 5:46 PM Tim Ruffing via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Pieter,
>
> That's a really nice overview.
>
> Let's take a step back first. If we believe that malicious hardware
> wallets are big enough of a concern, then signing is only part of the
> problem. The other issue is key generation. The PRG from which the seed
> is derived can be malicious, e.g., just H(k_OO,counter) for a key k_OO
> chosen by the hardware manufacturer. I haven't seen an argument why
> attacks during the signing model should more realistic than attacks
> during key generation, so I'd be very hesitant to deploy anti-covert
> channel singing protocols without deploying protocols for key
> generation that are secure in the same attacker model.
>
> While there's a bunch of protocols for signing, there's not much
> research for key generation. One simple idea is a simple commit-and-
> reveal protocol to generate a master (elliptic curve) public key pair
> with entropy contributions from both HW and SW (similar to the
> protocols here for generating R). Then use BIP32 public derivation for
> all other keys in order to make sure that SW can verify the derivation
> of the public kyes. The corresponding master secret key would replace
> the seed, i.e., there's no "symmetric" seed. That idea comes with other
> drawbacks however, most importantly this is not compatible with
> hardened derivation, which creates a new security risk. If we want
> (something like) hardened derivation, zero-knowledge proofs of correct
> derivation could maybe used but they again come with other issues
> (efficiency, complexity).
>
> By the way, here's a paper that considers a similar setting where the
> hardware wallet is also malicious during key generation:
> https://fc19.ifca.ai/preproceedings/93-preproceedings.pdf
> This model goes a step further and assumes threshold signatures but
> interestingly here the human user (instead of the SW) is the trusted
> party interacting with the HW. In this model the human user has a low-
> entropy password.
>
> Now back to the signing process: I think yet another security property
> to look at is security against a malicious SW with parallel signing
> sessions. I think it's reasonable to restrict a single HW device to a
> single session but what if the same seed is stored in two or more HW
> wallets? That's plausible at least. Taking this additional security
> property into account, it appears that Scheme 4 is vulnerable to
> Wagner's attack because SW can influence R by choosing t after seeing
> R0. (This can be fixed, e.g., by using Scheme 5 instead.)
>
>
> On Tue, 2020-03-03 at 21:35 +0000, Pieter Wuille via bitcoin-dev wrote:
> > 2.d) Statefulness
> >
> > We're left with Schemes 4 and 5 that protect against all listed
> > issues. Both
> > need two interaction rounds, with state that needs to be kept by HW
> > between
> > the rounds (the k0 value). While not a problem in theory, this may be
> > hard to
> > implement safely in simple APIs.
>
> A generic way to make one party (HW in this case) stateless is to let
> it encrypt and authenticate its state, e.g., using AEAD. In our
> particular case I think that the state does not need to be
> confidential, and a simple MAC suffices. For simplicity let's assume we
> have another hash function H' (modeled as a random oracle) used as MAC.
> We can (ab)use d as a MAC key.
>
> If we don't want to spend an entire signature verification on the side
> of HW to protect against fault attacks, we can additionally let SW
> compute and send the challenge hash e=H(R,Q,m) and let HW only verify
> the computation of e. This helps against fault-attacks in the
> computation of R and e because now SW needs to commit to e, which is a
> commitment to the exact computation fault that HW will suffer from. But
> I'm not sure yet if this is weaker or stronger or incomparable to
> verifying the signature. I guess it's weaker [1]. If we don't drop
> signature verification, this technique does not hurt at least.
>
> [Scheme 7: synthetic nonce, two interactions, stateless using MAC,
> verifying e]
>
> First interaction:
>  * SW generates a random t, computes h=H(t), and requests the R0 point
>    that HW would use by sending (Q,m,h) to HW.
>  * HW uses a global counter c (or fresh randomness c), and computes
>    k0=H(d,m,c,h), R0=k0G, mac=H'(d,m,c,h) and sends R0,c,mac to SW.
>
> Second interaction:
>  * SW computes R=R0+tG, e=H(R,Q,m) and requests a signature by sending
>    (Q,m,t,e,c,mac) to HW
>  * HW verifies mac=H'(d,m,c,H(t)), recomputes k0=H(d,m,c,H(t)), k=k0+t,
>    computes R=kG, verifies e=H(R,Q,m), and if all is good computes
>    s=k+H(R,Q,m)d and sends s to SW.
>  * SW verifies that sG=R+eQ and publishes (R,s) if all is good.
>
> One last observation: Since the inputs to H and H' are the same, we
> could even use H'(x)=H(H(x)). Not sure if that's useful.
>
> Best,
> Tim
>
> [1] In the (admittedly weird) case that faults in two runs of the
> executions are independent and can be made highly likely (say
> probability almost 1), verifying e could indeed be stronger than
> verifying the signature: When verifying the signature, the fault attack
> is successful if  the *same* fault happens during signing and
> verification (birthday collision!). When verifying e instead, the
> attack is successful if the attacker predicts the fault correctly. But
> I guess if faults can be made very likely, there's no hope anyway.
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--000000000000bf49fd05a1634216
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div>Practically speaking, most hardware =
wallets allow you to import your own BIP39 seed, so you can work around key=
 generation attacks today, with a one time inconvenience at the start. Howe=
ver, with the signing nonce attacks, a user today has no protection.</div><=
div><br></div><div>Mitigating key generation attacks would be very desirabl=
e, but I see it as independent of anti nonce covert channel protection.<br>=
</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_=
attr">On Sat, Mar 21, 2020 at 5:46 PM Tim Ruffing via bitcoin-dev &lt;<a hr=
ef=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linux=
foundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" st=
yle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padd=
ing-left:1ex">Hi Pieter, <br>
<br>
That&#39;s a really nice overview.<br>
<br>
Let&#39;s take a step back first. If we believe that malicious hardware<br>
wallets are big enough of a concern, then signing is only part of the<br>
problem. The other issue is key generation. The PRG from which the seed<br>
is derived can be malicious, e.g., just H(k_OO,counter) for a key k_OO<br>
chosen by the hardware manufacturer. I haven&#39;t seen an argument why<br>
attacks during the signing model should more realistic than attacks<br>
during key generation, so I&#39;d be very hesitant to deploy anti-covert<br=
>
channel singing protocols without deploying protocols for key<br>
generation that are secure in the same attacker model.<br>
<br>
While there&#39;s a bunch of protocols for signing, there&#39;s not much<br=
>
research for key generation. One simple idea is a simple commit-and-<br>
reveal protocol to generate a master (elliptic curve) public key pair<br>
with entropy contributions from both HW and SW (similar to the<br>
protocols here for generating R). Then use BIP32 public derivation for<br>
all other keys in order to make sure that SW can verify the derivation<br>
of the public kyes. The corresponding master secret key would replace<br>
the seed, i.e., there&#39;s no &quot;symmetric&quot; seed. That idea comes =
with other<br>
drawbacks however, most importantly this is not compatible with<br>
hardened derivation, which creates a new security risk. If we want<br>
(something like) hardened derivation, zero-knowledge proofs of correct<br>
derivation could maybe used but they again come with other issues<br>
(efficiency, complexity). <br>
<br>
By the way, here&#39;s a paper that considers a similar setting where the<b=
r>
hardware wallet is also malicious during key generation: <br>
<a href=3D"https://fc19.ifca.ai/preproceedings/93-preproceedings.pdf" rel=
=3D"noreferrer" target=3D"_blank">https://fc19.ifca.ai/preproceedings/93-pr=
eproceedings.pdf</a><br>
This model goes a step further and assumes threshold signatures but<br>
interestingly here the human user (instead of the SW) is the trusted<br>
party interacting with the HW. In this model the human user has a low-<br>
entropy password.<br>
<br>
Now back to the signing process: I think yet another security property<br>
to look at is security against a malicious SW with parallel signing<br>
sessions. I think it&#39;s reasonable to restrict a single HW device to a<b=
r>
single session but what if the same seed is stored in two or more HW<br>
wallets? That&#39;s plausible at least. Taking this additional security<br>
property into account, it appears that Scheme 4 is vulnerable to<br>
Wagner&#39;s attack because SW can influence R by choosing t after seeing<b=
r>
R0. (This can be fixed, e.g., by using Scheme 5 instead.) <br>
<br>
<br>
On Tue, 2020-03-03 at 21:35 +0000, Pieter Wuille via bitcoin-dev wrote:<br>
&gt; 2.d) Statefulness<br>
&gt; <br>
&gt; We&#39;re left with Schemes 4 and 5 that protect against all listed<br=
>
&gt; issues. Both<br>
&gt; need two interaction rounds, with state that needs to be kept by HW<br=
>
&gt; between<br>
&gt; the rounds (the k0 value). While not a problem in theory, this may be<=
br>
&gt; hard to<br>
&gt; implement safely in simple APIs.<br>
<br>
A generic way to make one party (HW in this case) stateless is to let<br>
it encrypt and authenticate its state, e.g., using AEAD. In our<br>
particular case I think that the state does not need to be<br>
confidential, and a simple MAC suffices. For simplicity let&#39;s assume we=
<br>
have another hash function H&#39; (modeled as a random oracle) used as MAC.=
<br>
We can (ab)use d as a MAC key.<br>
<br>
If we don&#39;t want to spend an entire signature verification on the side<=
br>
of HW to protect against fault attacks, we can additionally let SW<br>
compute and send the challenge hash e=3DH(R,Q,m) and let HW only verify<br>
the computation of e. This helps against fault-attacks in the<br>
computation of R and e because now SW needs to commit to e, which is a<br>
commitment to the exact computation fault that HW will suffer from. But<br>
I&#39;m not sure yet if this is weaker or stronger or incomparable to<br>
verifying the signature. I guess it&#39;s weaker [1]. If we don&#39;t drop<=
br>
signature verification, this technique does not hurt at least.=C2=A0 <br>
<br>
[Scheme 7: synthetic nonce, two interactions, stateless using MAC,<br>
verifying e]<br>
<br>
First interaction:<br>
=C2=A0* SW generates a random t, computes h=3DH(t), and requests the R0 poi=
nt<br>
=C2=A0 =C2=A0that HW would use by sending (Q,m,h) to HW.<br>
=C2=A0* HW uses a global counter c (or fresh randomness c), and computes<br=
>
=C2=A0 =C2=A0k0=3DH(d,m,c,h), R0=3Dk0G, mac=3DH&#39;(d,m,c,h) and sends R0,=
c,mac to SW.<br>
<br>
Second interaction:<br>
=C2=A0* SW computes R=3DR0+tG, e=3DH(R,Q,m) and requests a signature by sen=
ding<br>
=C2=A0 =C2=A0(Q,m,t,e,c,mac) to HW<br>
=C2=A0* HW verifies mac=3DH&#39;(d,m,c,H(t)), recomputes k0=3DH(d,m,c,H(t))=
, k=3Dk0+t,<br>
=C2=A0 =C2=A0computes R=3DkG, verifies e=3DH(R,Q,m), and if all is good com=
putes<br>
=C2=A0 =C2=A0s=3Dk+H(R,Q,m)d and sends s to SW.<br>
=C2=A0* SW verifies that sG=3DR+eQ and publishes (R,s) if all is good.<br>
<br>
One last observation: Since the inputs to H and H&#39; are the same, we<br>
could even use H&#39;(x)=3DH(H(x)). Not sure if that&#39;s useful.<br>
<br>
Best,<br>
Tim<br>
<br>
[1] In the (admittedly weird) case that faults in two runs of the<br>
executions are independent and can be made highly likely (say<br>
probability almost 1), verifying e could indeed be stronger than<br>
verifying the signature: When verifying the signature, the fault attack<br>
is successful if=C2=A0 the *same* fault happens during signing and<br>
verification (birthday collision!). When verifying e instead, the<br>
attack is successful if the attacker predicts the fault correctly. But<br>
I guess if faults can be made very likely, there&#39;s no hope anyway.<br>
<br>
<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div></div>

--000000000000bf49fd05a1634216--