Message-ID: <de7bd393327015a5b97ffff0d15a7c90d2d2196a.camel@timruffing.de>
From: Tim Ruffing <crypto@timruffing.de>
To: Pieter Wuille <bitcoin-dev@wuille.net>, Bitcoin Protocol Discussion
 <bitcoin-dev@lists.linuxfoundation.org>
Date: Sat, 21 Mar 2020 14:34:14 +0100
In-Reply-To: <VZTbLR9RlkkyNg6mOOIxedh7H0g8NGlaCmgBfCVXZ4RNfW3axefgoTqZGXjAQZFEuekujVGjRMv8SifDIodZ6tRGaaXQ_R63rFa03SGS6rg=@wuille.net>
References: <VZTbLR9RlkkyNg6mOOIxedh7H0g8NGlaCmgBfCVXZ4RNfW3axefgoTqZGXjAQZFEuekujVGjRMv8SifDIodZ6tRGaaXQ_R63rFa03SGS6rg=@wuille.net>
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques
Precedence: list

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.