Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 5A46FC07FF for ; 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 ; 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 ; 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 ; Sat, 21 Mar 2020 20:29:38 +0000 (UTC) Received: by mail-wm1-f41.google.com with SMTP id a9so7130902wmj.4 for ; 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: In-Reply-To: From: Marko Bencun Date: Sat, 21 Mar 2020 21:29:26 +0100 Message-ID: To: Tim Ruffing , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
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>
Mitigating key generation attacks would be very desirabl= e, 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.linux= foundation.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-pr= eproceedings.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<= br> > 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<= br> of HW to protect against fault attacks, we can additionally let SW
compute and send the challenge hash e=3DH(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<= br> signature verification, this technique does not hurt at least.=C2=A0

[Scheme 7: synthetic nonce, two interactions, stateless using MAC,
verifying e]

First interaction:
=C2=A0* SW generates a random t, computes h=3DH(t), and requests the R0 poi= nt
=C2=A0 =C2=A0that HW would use by sending (Q,m,h) to HW.
=C2=A0* HW uses a global counter c (or fresh randomness c), and computes =C2=A0 =C2=A0k0=3DH(d,m,c,h), R0=3Dk0G, mac=3DH'(d,m,c,h) and sends R0,= c,mac to SW.

Second interaction:
=C2=A0* SW computes R=3DR0+tG, e=3DH(R,Q,m) and requests a signature by sen= ding
=C2=A0 =C2=A0(Q,m,t,e,c,mac) to HW
=C2=A0* HW verifies mac=3DH'(d,m,c,H(t)), recomputes k0=3DH(d,m,c,H(t))= , k=3Dk0+t,
=C2=A0 =C2=A0computes R=3DkG, verifies e=3DH(R,Q,m), and if all is good com= putes
=C2=A0 =C2=A0s=3Dk+H(R,Q,m)d and sends s to SW.
=C2=A0* SW verifies that sG=3DR+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)=3DH(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=C2=A0 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/mail= man/listinfo/bitcoin-dev
--000000000000bf49fd05a1634216--