[bitcoin-dev] Nonce blinding protocol for hardware wallets and airgapped signers

[Dustin Dettmer]

Stepan have you spent any time considering a scheme that could involve HD
keys, preregistering n (ie. 1000) preimages, or something similar to reduce
the number of rounds at time of signing?

Would a zero knowledge solution allow for a reduction in rounds?

On Wed, Feb 26, 2020 at 7:13 PM Stepan Snigirev via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:

> This topic appeared in the list a few times so I would like to discuss it
> in more detail and maybe push forward to standardization.
>
> We have to accept that any hardware wallet or an air-gapped computer we
> use to sign transactions can be compromised. It may happen via a supply
> chain attack or malicious firmware update.
>
> If the signer is isolated (faraday cage, airgap and so on), it still can
> leak private keys to the outside world by choosing nonces for signatures in
> a funny way such that the attacker can calculate our private keys. Back in
> the days, I wrote a small post [1] and a proof-of-concept demo [2] of this
> attack.
>
> Deterministic nonce generation can be verified only if we have private
> keys somewhere else. It doubles the attack surface - now we need to
> maintain two independent signers from different vendors that use the same
> private key and the same deterministic algorithm for a nonce generation. In
> addition to that, as Pieter mentioned in the Schnorr-BIP, deterministic
> nonces are vulnerable to glitch attacks [3].
>
> A simple way to fix it is by forcing the signer to use additional entropy
> from the host. This protocol takes away the privilege of picking nonce from
> the signer and doesn't require any secret material outside the signer.
>
> I suggest the following implementation of the protocol for signing a
> message `m`:
>
> 1. Host picks a random number `n` and sends its hash together with the
> message `m` to the signer.
> 2. Signer computes a nonce `k` it wants to use for signing. It can be
> either a deterministic scheme or using RNG. Signer commits to the chosen
> nonce by sending the corresponding point `R=kG` to the host.
> 3. Host sends the preimage `n` to the signer
> 4. Signer tweaks the nonce by this number `k'=k+n`, signs the message and
> sends back the signature (R',s)
> 5. Host verifies that the public point in the signature is tweaked by n:
> `R'==R+nG`
>
> ASCII-art:
>
>    Host                                Untrusted signer
> 1. Pick random n   --- sha256(n),m -->  calculate nonce k
> 2.                 <------ R=kG ------  commit to k
> 3. Send preimage   -------- n ------->  sign with nonce k'=k+n
> 4. Verify R'==R+nG <------- sig ------
>
> I believe this protocol solves the problem. A drawback of this scheme is
> that the number of communication rounds doubles, so it might be pretty
> inconvenient for air-gapped remotely located signers.
>
> I also suggest the following extensions that might be helpful for certain
> use-cases
>
> # Extensions
>
> ## Multiple hosts
>
> There are some use-cases where multiple hosts are involved in the setup
> and all hosts don't trust each other and the signer. So all of them want to
> give extra entropy to the signer and verify that it was included. At the
> moment I have exactly this scenario - our main MCU doesn't trust the
> proprietary closed-source secure element, and the computer doesn't trust
> the whole hardware wallet. We need a way to convince both of them that
> their entropy was used in the nonce.
>
> It can be solved by concatenating hashes and preimages:
>
> Host1 ------- h(n1) --> Host 2 -- h(n1) h(n2) --> Signer
>       <--- R+n2 G -----        <------- R -------
>       ------- n1 ----->        ------ n1 n2 ----> sign with k''=k+n1+n2
> Ver: R''==R'+n1 G       Ver: R''==R+n2 G + n1 G
>
> In this case, the first host doesn't even notice that the second host was
> also using this protocol and mixing in the entropy. And the signer only
> needs to add one extra number to the nonce.
>
> ## Stateless random signer
>
> If the signer wants to generate a nonce non-deterministically but doesn't
> have an ability to store a generated nonce it may send back to the host
> some meta-information that would help it to re-generate the same nonce
> later. It can be for example additional random data used in a deterministic
> scheme, either encrypted and authenticated or just as a plain text (I am
> more a fan of encrypted though).
>
> Generally, the host shouldn't care what this data is about - he just
> stores the data between rounds and sends it back to the signer with the
> next round.
>
> # Implementation for PSBT
>
> We can either use proprietary fields [4] or define key-value pairs and add
> them to the BIP-174. Depends if anyone else is interested in using this
> protocol or not.
>
> I would suggest the following key-value per-input pairs assuming multiple
> hosts want to mix in external entropy:
>
> 1. Key: {PSBT_IN_EXT_NONCE_HASH}|{pubkey}, Value:
> {sha256(n1)}|{sha256(n2)}|...
> 2. Key: {PSBT_IN_NONCE_COMMITMENT}|{pubkey}, Value: {33-byte R point}
> 3. Key: {PSBT_IN_NONCE_SIGNER_METADATA}|{pubkey}, Value: {anything}
> 4. Key: {PSBT_IN_EXT_NONCE_PREIMAGE}|{pubkey}, Value: {n1}|{n2}|...
>
> Then the signature from the signer is placed into existing
> PSBT_IN_PARTIAL_SIG. Combiner and Finaliser should verify that nonce in the
> signature includes external entropy and may remove their own entropy from
> the set. They should also verify that the values of the fields did not
> change between rounds.
>
> So, list, what do you think? Am I missing something? Would it be
> interesting to have this protocol standardized and deployed?
>
> # References
>
> [1]
> https://medium.com/cryptoadvance/hardware-wallets-can-be-hacked-but-this-is-fine-a6156bbd199
> [2]
> https://github.com/stepansnigirev/chosen_nonce_demo/blob/master/HD_key.ipynb
> [3]
> https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#alternative-signing
> [4]
> https://github.com/bitcoin/bips/blob/master/bip-0174.mediawiki#proprietary-use-type
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200302/7860629d/attachment.html>