Second-guessing Satoshi: ECDSA and Bitcoin (part II)

[continued from part I]

There are ways to improve confidence in the correct operation of a blackbox ECDSA implementation that has bee tasked with signing transactions with our private key. One approach suggested in the original paper is choosing the jointly between blackbox and external client requesting signatures. There is an inherent asymmetry here, because the two sides can not complete such a protocol on equal terms. Because knowledge of the nonce used to a particular signature allows private-key recovery, the client can not learn the final value that will be used to compute the signature. But we can still defeat a kleptographic system by guaranteeing that the blackbox can not fully control choice of nonce either.

  • Blackbox chooses its own nonce k and commits to it, for example by outputting a hash of the curve point that would have resulted from using that nonce eg P = k∗G
    where G is the generator of the group. (Recap: first half of an ECDSA signature is the x-coordinate of the point on the elliptic-curve that is obtained by “multiplying” the generator with the nonce.)
  • Client returns a random scalar value r.
  • Blackbox opens the commitment to reveal its chosen point P— but not the scalar k— and then proceeds to compute the signature using Q = r ∗ (k∗G).
  • Before accepting the signature, client verifies that the final point Q and original choice P are related as Q = r∗P.

This guarantees that even if a kleptopgraphic implementation chose “cooked” k values to leak information, that signal is washed away when those choices are multiplied by random factors. In fact  multiplication is not the only option. The protocol is equally effective with addition and using (r+k) ∗ P as final value. But an extra point-multiplication for both sides can not be avoided because each side still has to compute r∗P on its own. They can not accept a result precomputed by the other side.  (It does make it easier to for the client to verify expected result by a simple point addition instead of the more expensive multiplication.)

Main challenge for this protocol is the interactivity— it changes the interface between the ECDSA implementation and client invoking a signature operation by requiring two round-trips. But it need not require changes to the client software. For cryptographic hardware such as HSMs, there is already a middleware layer such as PKCS#11 that translates higher-level abstractions such as signing into low-level commands specific to the device. This abstraction layer could hide the extra round-trip. Alternatively the round-trip can be eliminated by a stateful client. Suppose that after every signature the HSM outputs a commitment to the nonce it will use for the next signature and client caches this value. Then each signature request can be accompanied by client’s own random contribution and each signature response can be verified against the commitment cached from previous operation.

We can extend that further to come up with a different mitigation: suppose that the blackbox ECDSA implementation is asked to commit to thousands of nonces ahead of time. The client can in turn specify a single seed value that will be used to influence every nonce in the list according to a pseudo-random function of that random seed. (We can’t simply add/multiply every nonce with the same random value. That would fail to mask patterns across multiple nonces chosen by a kleptographic implementation.) In this case no interactivity is required for signature operations, since both blackbox and client contributions to the final nonce are determined ahead of time. One caveat: a kleptographic implementation can try to cheat by faking a malfunction and outputting invalid responses in order to skip some values in the sequence, leaking information based on which ones were omitted. Meanwhile the client can’t insist that blackbox sign with previous nonce, because reusing nonces across different messages also results in private-key disclosure.

As a side-note: precomputing and caching nonces can also serve as a performance optimization, by leveraging the online/offline nature of ECDSA. Such signature schemes have the unusual property that a significant chunk of the required computation can be done without seeing the message that is being signed. For ECDSA the generation of the first half of the signature fits the bill: multiply a fixed point of the elliptic-curve by a random nonce that is chosen independent of the message. That point multiplication is by far the most expensive part of the signature. Front-loading that and computing nonces ahead of time reduces perceived latency when it is time to actually emit a signature.

One problem not addressed in the original paper is that of key generation. If the objective is guarding against a kleptographic blackbox ECDSA implementation, then it can not be trusted to generate keys either. Otherwise it is much simpler to “leak” private keys directly by using a subverted RNG whose output is known to the adversary. Ensuring randomness of nonces used when signing will not help in that situation; the private key is already compromised without signing a single message. But the same techniques used to randomize the nonce can be applied here, since an ECDSA public-key is also computed as a point-product of the secret private key and fixed generator point. The blackbox can commit to its choice of private-key by outputting a hash of the public-key, and the client can provide additional random input that causes final chosen key to be distributed randomly even if the blackbox was dishonest.

All of this complexity raises a different question: why is Bitcoin using ECDSA in the first place? As pointed out, RSA signing does not suffer from this problem of requiring “honest” randomness for each signature. But that is simply one criteria among many considerations. A future post will compare RSA and ECDSA side-by-side for use in a cryptocurrency such as Bitcoin.



Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s