[bitcoin-dev] Overview of anti-covert-channel signing techniques

[bitcoin-dev] Overview of anti-covert-channel signing techniques

[Pieter Wuille]

Hi all,

Given the recent activity and attention [1,2] around anti-covert channel
signing schemes, I decided to create this overview of the various techniques
that I know of, their trade-offs, and the various issues they protect against.
Most of this is based on various schemes by a number of authors, and credit
goes to them. I'm putting this together into something hopefully more
comprehensive, but mistakes and omissions in this writeup are likely mine.

I don't believe we have security proofs for any of the schemes, or for any of
the claims I make about the mitigation techniques below. I hope that having
all properties written up in one place makes it easier to eventually get those.

1) Security model
-----------------

When talking about signing with covert channels, we consider 3 parties:
* HW, the hardware wallet (or other offline signing device) with secret data
  (a private key, or a seed from which the private key is derived).
* SW, the software wallet (or whatever communicates with HW and the network).
* OO, the outside observer who is trying to learn information about HW's
  secret data.

We consider two distinct attack models:
* MSW, "malicious software wallet", but with honest HW. OO and SW are the
  same party here, so this models the usual scenarios hardware wallets are
  designed for, including side-channel attacks if those are considered to be
  part of the threat model.
* MHW, "malicious hardware wallet", but with honest SW and no malicious party
  being able to communicate with HW directly. OO and HW may have shared secret
  information that SW (or anyone else) is unaware of. SW's job is trying to
  prevent HW from using this to leak any information about its secret.

When both the HW and the SW are compromised, clearly no security is possible,
as all entities are controlled by the same party in that case.

In case HW uses a deterministic algorithm, it is possible to protect against
the MHW case by spot checking HW's behavior, by using an externally known
secret/seed. However, we'd like to have better than just spot checking
security, and for protection against side-channel attacks we may want
something that keeps working even when randomness is used by HW.

To keep the scope limited, we assume SW has no secret key of their own. This
rules out solutions like using 2-of-2 MuSig between HW and SW, which work, but
come with their own complications (like needing secure storage for that
secret).

2) Issues and solutions
-----------------------

In this section I will go over the various issues that exist in the MHW and MSW
models, the known mitigation techniques, and the resulting schemes.

I'm assuming a Schnorr-like signature protocol, though everything should apply
equally to ECDSA, and to a lesser extent probably also to multisignature
schemes. These variable names are used:
* H is a hash function.
* G is the curve generator.
* m is the message to be signed, known to and agreed upon by SW and HW.
* d is HW's secret key, with corresponding public key Q=dG.
* k is the secret nonce k, with corresponding public nonce R=kG.

The simplest protocol is naive Schnorr with deterministic nonce generation,
where SW only verifies that a signature created by HW is valid:

[Scheme 1: deterministic nonce, no tweak]
* SW requests a signature by sending (Q,m) to HW.
* HW computes k=H(d,m), R=kG, s=k+H(R,Q,m)d, and sends (R,s) to SW.
* SW verifies sG=R+H(R,Q,m)Q, and publishes sig (R,s) in case of success.

2.a) Predictable k value

There is a simple attack against Scheme 1 that will leak the entire private
key undetectably using a single signature, under MHW. Assume HW and OO both
have access to a shared secret a, unknown to anyone else. HW computes
k=H(a,Q,m) instead, which SW cannot distinguish from the honest k=H(d,m) as it
knows neither a or d. OO can compute k using the same formula, and thus
recover the private key as d=(s-k)/H(R,Q,m).

The general strategy to avoid this is by letting SW provide entropy that is
included into the nonce computation. A very naive (and ineffective) way of
doing that would be:
* SW generates random t, and requests a signature by sending (Q,m,t) to HW.
* HW computes k0=H(d,m,t), R0=k0G, k=k0+t, R=kG, s=k+H(R,Q,m)d, and sends
  (R0,R,s) to SW.
* SW verifies sG=R+H(R,Q,m)Q, R=R0+tG, and publishes sig (R,s) if all is good.

This does not help as HW can still choose k directly, and retroactively
compute R0 as R-tG, satsifying SW's requirements. To address that, there are
two options:
* Turning R into a binding commitment to R0 and t (see Scheme 2).
* Only revealing t after HW has revealed their R0 (see Scheme 3).

The first approach is based on making R a commitment to R0 and t using
R=R0+H(R0,t)G. When applied to public keys this is known as pay-to-contract
(and is the basis for Taproot); when applied to the R point in signatures it's
known as sign-to-contract [3]. These are generally useful approaches to make
public keys and signatures commit to/timestamp external data, but using this
to protect against covert channels in signatures was first discussed by Greg
Maxwell [4]:

[Scheme 2: deterministic nonce, S2C tweak]
* SW generates random t, and requests a signature by sending (Q,m,t) to HW.
* HW computes k0=H(d,m,t), R0=k0G, k=k0+H(R0,t), R=kG,
  s=k+H(R,Q,m)d, and sends (R0,R,s) to SW.
* SW verifies sG=R+H(R,Q,m)Q, R=R0+H(R0,t)G, and publishes sig (R,s) if all
  is good.

The second approach is adding a round, and only revealing the tweak t after HW
has revealed their R0:

[Scheme 3: deterministic nonce, tweak revealed after nonce]
* SW requests a signature by sending (Q,m) to HW.
* HW computes k0=H(d,m), R0=k0G, and sends R0 to SW.
* SW generates a random t, and sends it to HW.
* HW computes k=k0+t, R=kG, s=k+H(R,Q,m)d, and sends (R,s) to SW.
* SW verifies sG=R+H(R,Q,m)Q, R=R0+tG, and publishes (R,s) if all is good.

2.b) Replay attacks

Scheme 3 introduces another problem however, this time under MSW. SW can ask
HW to sign the same message twice, but then pick distinct values for t (t and
t'). The resulting R points will be R=(k0+t)G and R'=(k0+t')G, and the s
values will be s=k0+t+H(R,Q,m)d and s'=k0+t'+H(R',Q,m)d. This allows SW to
compute d=(s'-t'-s+t)/(H(R',Q,m)-H(R,Q,m)). A similar problem would also exist
in Scheme 2 if t wasn't included in the formula for k0.

The problem is that SW is allowed to change their tweak while the nonce
only undergoes a linear function known to SW. There are again two ways to
address this problem:
* Making k0 generation non-repeating by including a counter or randomness
  in it (Scheme 4).
* Making SW commit to their tweak before revealing it as well (Scheme 5).

[Scheme 4: counter/random nonce, tweak revealed after nonce]
* SW requests a signature by sending (Q,m) to HW.
* HW uses a global counter c, or fresh randomness b, and computes k0=H(d,m,c)
  or k0=H(d,m,b), R0=k0G, and sends R0 to SW.
* SW generates a random t, and sends it to HW.
* HW computes k=k0+t, R=kG, s=k+H(R,Q,m)d, and sends (R,s) to SW.
* SW verifies sG=R+H(R,Q,m)Q, R=R0+tH, and publishes (R,s) if all is good.

A variant of Scheme 4, but with multiplicative tweak rather than additive,
and only revealing H(R0) rather than R0 immediately, was suggested by Sergio
Demian Lerner in [5].

[Scheme 5: deterministic nonce, precommited tweak revealed after nonce]
* SW generates a random t, computes h=H(t), and requests a signature by
  sending (Q,m,h) to HW.
* HW computes k0=H(d,m,h), R0=k0G, and sends R0 to SW.
* SW sends t to HW.
* HW verifies h=H(t), and if so, computes k=k0+t, R=kG, s=k+H(R,Q,m)d, and
  sends (R,s) to SW.
* SW verifies sG=R+H(R,Q,m)Q, R=R0+tG, and publishes (R,s) if all is good.

Scheme 5 is the one suggested by Stepan Snigirev in [2,6]. A variant with
S2C tweaking instead of additive tweaked was suggested by Andrew Poelstra
in his talk [7], with transcript by Bryan Bishop in [8].

2.c) k0 grinding

So far Schemes 2, 4, and 5 protect against predictable k values and replay
attacks. Predictable k values are however not the only way MWH can leak
secrets.

If we imagine HW has significant computational power, in Scheme 2 it can try
many different k0 values (by deviating from k0=H(d,m,t)), and observe what the
resulting (R,s) signature will be. For example, by iterating on average 256
times, it can choose 8 bits in (R,s) that convey information about k, d, or
whatever seed or master key they are derived from. Using forward error
correction (FEC) schemes, this channel of a few bits per signature may be
enough to leak an entire seed over enough signatures. Using a shared secret a
between HW and OO those bits can again be made undetectable to anyone else.

Schemes 4 and 5 are not vulnerable to this problem, as they force HW to commit
to its R0 before knowing the resulting R. One might think that Scheme 4 merely
shifts this problem to MSW, where SW can grind t to make R biased in a similar
way. We assumed that SW does not have access to any secrets however, so this
is harmless.

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.

One possibility is sticking with our "best one-round" Scheme 2, and accepting
that that implies the k0 grinding vulnerability.

There is another possibility, namely splitting Scheme 5 into two independent
interactions with HW, where no memory between them is needed on the HW side:

[Scheme 6: deterministic nonce, precommitted tweak revealed separately]
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 computes k0=H(d,m,h), R0=k0G, and sends R0 to SW.
Second interaction:
* SW requests a signature by sending (Q,m,t) to HW
* HW computes k0=H(d,m,H(t)), k=k0+t, R0=R0k, R=kG, s=k+H(R,Q,m)d, and sends
  (R0,R,s) to SW.
* SW verifies that R0 matches the earlier R0 it received, and that
  sG=R+H(R,Q,m)Q, R=R0+tG, and publishes (R,s) if all is good.

A variant of Scheme 6, with S2C tweaking instead of additive tweaking, is what
is being worked on by Jonas Nick [9] and Marko Bencun [10] for the
libsecp256k1 library.

The same technique cannot be applied to Scheme 4, as HW inherently needs state
to keep the counter c, or to remember the randomness b between interactions
there.

2.e) Failure bias

There is yet another, and even weaker, leak that is available in MHW: whenever
HW learns what the eventual signature (R,s) will be, it could pretend to fail
and go offline, or return some kind of error. In theory, this is enough to
introduce a similar bias, though it would come at possibly enormous failure
rates. If HW is allowed to fail 255 times out of 256, it can introduce an
8-bit bias, and employ similar techniques (FEC and shared HW/OO secret).
The obvious solution is showing a big warning to the user whenever any kind of
failure occurs (including device going offline, or returning invalid
responses) that the device is failing, and that if this happens frequently, it
should be treated as malicious.

Interestingly, Scheme 6 can be adapted to reduce this (already very weak)
channel further. The observation is that HW cannot predict during the first
interaction what (R,s) is going to be, as t is not known. This means it can
only fail during the second interaction when the result is already committed
to. Thus, if failure occurs during the second interaction, SW can simply
retry it with the same t value. If that succeeds, either a glitch occurred and
was safely retried, or the device's attempt to bias was prevented. If the
failure persists, the user should still be warned - as restarting with a
different k would reintroduce the possibility for bias.

2.f) Side-channel attacks

As a last consideration, let's see if these schemes have an impact on
potential resilience against side-channel attacks. I say potential, because
these classes of attacks are in general hard to protect against and model,
as they depend on implementation details and hardware protections. Still,
there are some general observations possible.

A significant amount of time in HW is likely spent on the EC multiplications
to obtain R0 and R from k0 and k. As s=k+H(R,Q,m)d, an variation of the replay
attack is possible here. In schemes with deterministic nonces, SW can ask for
the same signature twice, but use a fault injection to hopefully (only) cause
an error in R, R'. This would reveal (R,s) and (R',s') to SW, where s' is
k+H(R',Q,m)d, which would let them compute d=(s'-s)/(H(R',Q,m)-H(R,q,m)).
There is an easy solution against this, namely verifying the final signature
(R,s) in HW before sending it to SW, as almost certainly the result of such
a fault would not result in a valid signature. This comes at an extra
computational cost, though.

For other side-channel attacks like different power analysis, research [11]
shows that introducing fresh randomness in the right place may be helpful.
This approach is called "synthetic nonces" [12]. Unfortunately usage of these
rules out the deterministic approach from Scheme 6. A variant of Scheme 5
with fresh randomness in the k0 computation can be used, though.

3) Summary
----------

Six different issues of various levels of severity were discussed:
  (a) Predictable k: (MHW) a single signature leaks the entire private key.
  (b) Replay attacks: (MSW) a single signature leaks the entire private key.
  (c) k0 grinding: (MHW) the HW can leak n bits with 2^n work.
  (d) Statefulness: HW has to correctly maintain state, complicating things.
  (e) Failure bias: (MHW) a selective failure rate of (2^n-1)/2^n can be used
      to leak n bits of secret per signature.
  (f) Side-channel attacks: (MSW) physical access to HW can help extracting
      secrets.

It seems any reasonable solution should at least protect against (a), (b), and
(c), but it seems no solution can be optimal for all of (d), (e), and (f) too.

If statelessness and protection against failure bias are prioritized, Scheme 6
seems best. Its additive tweaking can be replaced with S2C (or multiplicative)
tweaking too. S2C in particular may be desirable to unify with support for
S2C-based timestamping.

If resistance against side-channels is prioritized, solutions with synthetic
nonces seem best; either Scheme 4, or Scheme 5 with randomness added to the
k0 computation. Again, any tweaking approach can be chosen.

If the 2-round approaches for Schemes 4, 5, and 6 are really unacceptable,
Scheme 2 (with S2C tweaking) could be used, but in that case protection
against k0 grinding is reduced to spot checking. If randomness is additionally
added for side-channel resistance, the ability to spot check disappears
entirely.

4) References
-------------

  [1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017649.html
  [2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017655.html
  [3] https://blog.eternitywall.com/2018/04/13/sign-to-contract/
  [4] https://bitcointalk.org/index.php?topic=893898.msg9861102#msg9861102
  [5] https://bitcointalk.org/index.php?topic=893898.msg9841502#msg9841502
  [6] https://medium.com/cryptoadvance/hardware-wallets-can-be-hacked-but-this-is-fine-a6156bbd199
  [7] https://youtu.be/j9Wvz7zI_Ac?t=640
  [8] https://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2019-02-04-threshold-signatures-and-accountability/
  [9] https://github.com/bitcoin-core/secp256k1/pull/590
  [10] https://github.com/bitcoin-core/secp256k1/pull/669
  [11] https://eprint.iacr.org/2017/985
  [12] https://moderncrypto.org/mail-archive/curves/2017/000925.html

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing]

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.

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 1172 bytes --]

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

> Hi Pieter,
>
> 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.
>

Public keys are deterministic and can be spot checked.  In fact, AFAIU if
hardened HD key derivations are not used, then spot checking is very easy.

While spot checking isn't ideal, my original concern with the synthetic
none standard proposal was that it is inherently non-deterministic and
cannot ever be spot checked.  This is why anti-covert signing protocols are
so important if we are going to use synthetic nonces.

[-- Attachment #2: Type: text/html, Size: 1588 bytes --]

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing]

On Sat, 2020-03-21 at 12:59 -0400, Russell O'Connor wrote:
> Public keys are deterministic and can be spot checked.  In fact,
> AFAIU if hardened HD key derivations are not used, then spot checking
> is very easy.
> 
> While spot checking isn't ideal, my original concern with the
> synthetic none standard proposal was that it is inherently non-
> deterministic and cannot ever be spot checked.  This is why anti-
> covert signing protocols are so important if we are going to use
> synthetic nonces.

If spot checking means checking a few instances, then I think this is a
pretty weak defense. What if the device starts to behave differently
after a year?

On Sat, 2020-03-21 at 21:29 +0100, Marko Bencun wrote:
> 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.
> 

How do you know that the device really uses your seed? This can only be
done by comparing the public keys output by the HW with a second
computation. Even if you use only non-hardened derivation, you need to
check the master (root) public key and that means you need compute the
master root public key once from the seed. You can't do this manually
on a sheet of paper after you rolled a few dice to generate your seed.
So you need to store the seed on a second device (if only for a short
time). And I think this defeats the purpose of a HW wallet.

And even if assume that spot checking and importing the seed works, the
problem is not solved. We still need a clearly specified full protocol
that we can analyze. 

Best,
Tim

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 1753 bytes --]

On Sun, Mar 22, 2020 at 5:43 AM Tim Ruffing <crypto@timruffing.de> wrote:

> On Sat, 2020-03-21 at 12:59 -0400, Russell O'Connor wrote:
> > Public keys are deterministic and can be spot checked.  In fact,
> > AFAIU if hardened HD key derivations are not used, then spot checking
> > is very easy.
> >
> > While spot checking isn't ideal, my original concern with the
> > synthetic none standard proposal was that it is inherently non-
> > deterministic and cannot ever be spot checked.  This is why anti-
> > covert signing protocols are so important if we are going to use
> > synthetic nonces.
>
> If spot checking means checking a few instances, then I think this is a
> pretty weak defense. What if the device starts to behave differently
> after a year?
>

I agree, which is why there perhaps is merit in using a non-hardered
derivation path so that the software side of a hardware wallet can check
the pubkey. Though I understand there are some disadvantages to the
non-hardened paths.

However, spot checking can even be done retroactively (and thoroughly).
Again, I agree that this is less than ideal, but does let you take some
action once you notice a deviation.

Your claim is that if we don't fix the pubkey issue there is no point in
fixing the signature issue.  I disagree.  While I think both issues need to
be fully addressed, the issues around the original proposed
non-deterministic signature scheme are far more severe. The proposal would
move us from a deterministic scheme, where spot checks are possible, with
all the caveats that entails, to a non-deterministic scheme where spot
checks are impossible.  My hope is that we can standardise a scheme that
has the advantages of non-determinism without the threat of covert channels.

[-- Attachment #2: Type: text/html, Size: 2262 bytes --]

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing]

On Sun, 2020-03-22 at 11:30 -0400, Russell O'Connor wrote:
> Your claim is that if we don't fix the pubkey issue there is no point
> in fixing the signature issue.  I disagree.  While I think both
> issues need to be fully addressed, the issues around the original
> proposed non-deterministic signature scheme are far more severe. The
> proposal would move us from a deterministic scheme, where spot checks
> are possible, with all the caveats that entails, to a non-
> deterministic scheme where spot checks are impossible.  My hope is
> that we can standardise a scheme that has the advantages of non-
> determinism without the threat of covert channels.

I think we agree that both issues should be addressed, and this is all
what matters in the end. Now that we have a proposal for Schnorr
signatures, it's indeed a good time to work on these issues.

Tim

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Marko Bencun]

[-- Attachment #1: Type: text/plain, Size: 6055 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 7206 bytes --]

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Dustin Dettmer]

[-- Attachment #1: Type: text/plain, Size: 1030 bytes --]

Excellent write up, thanks for putting it together.

On Tue, Mar 3, 2020 at 1:47 PM Pieter Wuille wrote:

> When both the HW and the SW are compromised, clearly no security is
> possible,
> as all entities are controlled by the same party in that case.
>
While all SW being compromised can’t be stopped, splitting the SW over two
stages can dramatically increase your security if both HW & SW are
compromised. You can do that by:

1) When you setup your storage solution (whatever it may be), export the
xpub(s) and verify the receiving addresses match xpubs with external
software before receiving.
2) Generate and export withdrawal transactions offline
3) Verify transactions against the same xpub(s) using external software
4) Upload transactions

This mitigates, I believe, all leak vectors besides k/R hacking and
prechosen entropy.

I made an external tool to just that here:
https://github.com/koinkeep/gatekeeper

Would love to add k commitments when (if?) we settle on best practices for
it.

[-- Attachment #2: Type: text/html, Size: 1574 bytes --]

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing]

Hi Dustin,

That sounds interesting but I can't follow your email to be honest.

On Mon, 2020-03-23 at 07:38 -0700, Dustin Dettmer via bitcoin-dev
wrote:
> This mitigates, I believe, all leak vectors besides k/R hacking and
> prechosen entropy.

Hm, so what vectors is this supposed to mitigate? Leaking through the
generated public keys? Anything else?

Here are a few questions:
 - What are you trying to achieve? You seem to describe how you get
from the setup to the goal in four steps but I don't understand what
the setup is or what the goal is. (What's a storage solution?)
 - "all SW being compromised" do you mean "SW and HW compromised"? Note
that SW and HW are parties in Pieter's writeup, not just abbreviations
for software and hardware. 
 - Where are the two stages? You mention four steps.
 - Where do you run the external software? On a second SW? Is this the
second stage?
 - Do you use unhardened derivation?
 - What's a k commitment?


Best,
Tim

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Dustin Dettmer]

[-- Attachment #1: Type: text/plain, Size: 1997 bytes --]

Hi Tim,

Hm, so what vectors is this supposed to mitigate? Leaking through the
> generated public keys? Anything else?


The main thing it’s protecting against is the stealing of your funds by
malicious hardware & software. There are some side benefits as well though.

 - What are you trying to achieve? You seem to describe how you get
> from the setup to the goal in four steps but I don't understand what
> the setup is or what the goal is. (What's a storage solution?)


“Storage solution” is however you’re storing bitcoins today. Could be 12
words on some paper plus a computer running electrum. Could be a Ledger +
computer. Point is this technique works regardless of how you’re storing
your bitcoin.

 - "all SW being compromised" do you mean "SW and HW compromised"? Note
> that SW and HW are parties in Pieter's writeup, not just abbreviations
> for software and hardware.


Yeah — if you split the SW party into two, “generator” and “validator” some
interesting and useful security properties emerge.

 - Where are the two stages? You mention four steps.


“Generator” and “validator”. The generator creates and passes on receiving
addresses and withdrawal transactions (while remaining offline). The
validator double checks everything the generator did..

It works best if the validator is written entirely independently of the
generator.

 - Where do you run the external software? On a second SW? Is this the
> second stage?


Yes

 - Do you use unhardened derivation?


It’s an open ended solution — it would work with a (presumably
non-trivial/random) unhardened derivation just fine.

 - What's a k commitment?


It is one of the proposed solutions presented (collected?) by Peter in this
thread. As I understand it k is used to generate R in the signature. By
committing to some k value the hardware wallet can’t “sneak out” your
private key(s) in the R value.

Best,
Dustin

>

[-- Attachment #2: Type: text/html, Size: 3604 bytes --]