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

From: Marko Bencun <mbencun@gmail•com>
To: Tim Ruffing <crypto@timruffing•de>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques
Date: Sat, 21 Mar 2020 21:29:26 +0100	[thread overview]
Message-ID: <CAOkeP8tn42PQvnSy_5BZ4H54F9myBODqsYFrGHDs=sncyohYfA@mail.gmail.com> (raw)
In-Reply-To: <de7bd393327015a5b97ffff0d15a7c90d2d2196a.camel@timruffing.de>

[-- 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 --]