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 04D14C013E for ; Tue, 3 Mar 2020 21:46:06 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 018CF85EAA for ; Tue, 3 Mar 2020 21:46:06 +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 EhGU56vmOrQd for ; Tue, 3 Mar 2020 21:46:03 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail1.protonmail.ch (mail1.protonmail.ch [185.70.40.18]) by fraxinus.osuosl.org (Postfix) with ESMTPS id 8B24985E69 for ; Tue, 3 Mar 2020 21:46:03 +0000 (UTC) Date: Tue, 03 Mar 2020 21:35:55 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wuille.net; s=protonmail; t=1583271358; bh=gpaBBzHQDLxefQWN6EybL/H0ZF1U6GhN3OzZxOQNV1g=; h=Date:To:From:Reply-To:Subject:Feedback-ID:From; b=bhysmhL/Ov4U/olelzAAj6xsPkH+ki9ZvcOlWMQv2VnhRZnRYrU2CO6rTUDwt71pf RDAAufA02z8ukHKnUrpQS1ziilatHpqMMP39VD461ymFDvZWyxVnKegU1MxPIV37tc C7h9TD9T8Khb4MBl9Qea2TisYqUV1A/uSJy2TsCg= To: Bitcoin dev list From: Pieter Wuille Reply-To: Pieter Wuille Message-ID: Feedback-ID: 83p8XfQDlAVZaV1KZvKBP38DBJ-T0wAL9YhnBMePKqaSXpOMTTsq_oVBZ56Tdk3gbggb5Vx1OtLNo5RE2smj7w==:Ext:ProtonMail MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Mailman-Approved-At: Tue, 03 Mar 2020 21:47:34 +0000 Subject: [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: Tue, 03 Mar 2020 21:46:06 -0000 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 technique= s that I know of, their trade-offs, and the various issues they protect again= st. 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 th= ose. 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 dat= a (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 b= e part of the threat model. * MHW, "malicious hardware wallet", but with honest SW and no malicious par= ty being able to communicate with HW directly. OO and HW may have shared sec= ret 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 possibl= e, as all entities are controlled by the same party in that case. In case HW uses a deterministic algorithm, it is possible to protect agains= t 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. Thi= s 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 ap= ply 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=3DdG. * k is the secret nonce k, with corresponding public nonce R=3DkG. 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=3DH(d,m), R=3DkG, s=3Dk+H(R,Q,m)d, and sends (R,s) to SW. * SW verifies sG=3DR+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=3DH(a,Q,m) instead, which SW cannot distinguish from the honest k=3DH(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=3D(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=3DH(d,m,t), R0=3Dk0G, k=3Dk0+t, R=3DkG, s=3Dk+H(R,Q,m)d, a= nd sends (R0,R,s) to SW. * SW verifies sG=3DR+H(R,Q,m)Q, R=3DR0+tG, and publishes sig (R,s) if all i= s 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 ar= e 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=3DR0+H(R0,t)G. When applied to public keys this is known as pay-to-contra= ct (and is the basis for Taproot); when applied to the R point in signatures i= t's known as sign-to-contract [3]. These are generally useful approaches to mak= e public keys and signatures commit to/timestamp external data, but using thi= s to protect against covert channels in signatures was first discussed by Gre= g 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=3DH(d,m,t), R0=3Dk0G, k=3Dk0+H(R0,t), R=3DkG, s=3Dk+H(R,Q,m)d, and sends (R0,R,s) to SW. * SW verifies sG=3DR+H(R,Q,m)Q, R=3DR0+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=3DH(d,m), R0=3Dk0G, and sends R0 to SW. * SW generates a random t, and sends it to HW. * HW computes k=3Dk0+t, R=3DkG, s=3Dk+H(R,Q,m)d, and sends (R,s) to SW. * SW verifies sG=3DR+H(R,Q,m)Q, R=3DR0+tG, and publishes (R,s) if all is go= od. 2.b) Replay attacks Scheme 3 introduces another problem however, this time under MSW. SW can as= k HW to sign the same message twice, but then pick distinct values for t (t a= nd t'). The resulting R points will be R=3D(k0+t)G and R'=3D(k0+t')G, and the = s values will be s=3Dk0+t+H(R,Q,m)d and s'=3Dk0+t'+H(R',Q,m)d. This allows SW= to compute d=3D(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=3DH(d,= m,c) or k0=3DH(d,m,b), R0=3Dk0G, and sends R0 to SW. * SW generates a random t, and sends it to HW. * HW computes k=3Dk0+t, R=3DkG, s=3Dk+H(R,Q,m)d, and sends (R,s) to SW. * SW verifies sG=3DR+H(R,Q,m)Q, R=3DR0+tH, and publishes (R,s) if all is go= od. A variant of Scheme 4, but with multiplicative tweak rather than additive, and only revealing H(R0) rather than R0 immediately, was suggested by Sergi= o Demian Lerner in [5]. [Scheme 5: deterministic nonce, precommited tweak revealed after nonce] * SW generates a random t, computes h=3DH(t), and requests a signature by sending (Q,m,h) to HW. * HW computes k0=3DH(d,m,h), R0=3Dk0G, and sends R0 to SW. * SW sends t to HW. * HW verifies h=3DH(t), and if so, computes k=3Dk0+t, R=3DkG, s=3Dk+H(R,Q,m= )d, and sends (R,s) to SW. * SW verifies sG=3DR+H(R,Q,m)Q, R=3DR0+tG, and publishes (R,s) if all is go= od. 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 tr= y many different k0 values (by deviating from k0=3DH(d,m,t)), and observe wha= t 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 com= mit to its R0 before knowing the resulting R. One might think that Scheme 4 mer= ely shifts this problem to MSW, where SW can grind t to make R biased in a simi= lar way. We assumed that SW does not have access to any secrets however, so thi= s is harmless. 2.d) Statefulness We're left with Schemes 4 and 5 that protect against all listed issues. Bot= h 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 accepti= ng that that implies the k0 grinding vulnerability. There is another possibility, namely splitting Scheme 5 into two independen= t 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=3DH(t), and requests the R0 point tha= t HW would use by sending (Q,m,h) to HW. * HW computes k0=3DH(d,m,h), R0=3Dk0G, and sends R0 to SW. Second interaction: * SW requests a signature by sending (Q,m,t) to HW * HW computes k0=3DH(d,m,H(t)), k=3Dk0+t, R0=3DR0k, R=3DkG, s=3Dk+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=3DR+H(R,Q,m)Q, R=3DR0+tG, and publishes (R,s) if all is good. A variant of Scheme 6, with S2C tweaking instead of additive tweaking, is w= hat 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 st= ate 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: whene= ver HW learns what the eventual signature (R,s) will be, it could pretend to fa= il 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 committe= d 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 multiplication= s to obtain R0 and R from k0 and k. As s=3Dk+H(R,Q,m)d, an variation of the r= eplay attack is possible here. In schemes with deterministic nonces, SW can ask f= or the same signature twice, but use a fault injection to hopefully (only) cau= se 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=3D(s'-s)/(H(R',Q,m)-H(R,q,m)). There is an easy solution against this, namely verifying the final signatur= e (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 the= se 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 us= ed 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) t= oo. If statelessness and protection against failure bias are prioritized, Schem= e 6 seems best. Its additive tweaking can be replaced with S2C (or multiplicati= ve) 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 syntheti= c 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 additiona= lly 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=3D893898.msg9861102#msg986110= 2 [5] https://bitcointalk.org/index.php?topic=3D893898.msg9841502#msg984150= 2 [6] https://medium.com/cryptoadvance/hardware-wallets-can-be-hacked-but-t= his-is-fine-a6156bbd199 [7] https://youtu.be/j9Wvz7zI_Ac?t=3D640 [8] https://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2019-02-04-thres= hold-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