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 >