From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id A2578C07FF for ; Sat, 21 Mar 2020 13:34:24 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 990D8873FE for ; Sat, 21 Mar 2020 13:34:24 +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 Xc8xAry3yJ1N for ; Sat, 21 Mar 2020 13:34:22 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mout-p-201.mailbox.org (mout-p-201.mailbox.org [80.241.56.171]) by fraxinus.osuosl.org (Postfix) with ESMTPS id 81DCF873F3 for ; Sat, 21 Mar 2020 13:34:22 +0000 (UTC) Received: from smtp1.mailbox.org (smtp1.mailbox.org [80.241.60.240]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by mout-p-201.mailbox.org (Postfix) with ESMTPS id 48l1p34p7QzQl8k; Sat, 21 Mar 2020 14:34:19 +0100 (CET) X-Virus-Scanned: amavisd-new at heinlein-support.de Received: from smtp1.mailbox.org ([80.241.60.240]) by hefe.heinlein-support.de (hefe.heinlein-support.de [91.198.250.172]) (amavisd-new, port 10030) with ESMTP id xAiOYPXmxy8j; Sat, 21 Mar 2020 14:34:15 +0100 (CET) Message-ID: From: Tim Ruffing To: Pieter Wuille , Bitcoin Protocol Discussion Date: Sat, 21 Mar 2020 14:34:14 +0100 In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Sat, 21 Mar 2020 16:46:24 +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 13:34:24 -0000 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.