ECDSA

Rob Austein recently announced that cryptech has a software ECDSA signature and verification implementation which runs on the Novena using the Cryptech TRNG. This is another major milestone for the project and enables a whole set of new usecases for cryptech.

Rob goes on to say the following about the ECDSA implementation:

As with the RSA code, does just enough to support what PKCS #11 wants. Includes just enough ASN.1 code to generate signatures (which are small ASN.1 objects for ECDSA) and to save and restore ECDSA private keys using AES-Keywrap.

Internal structure of the code attempts to be modular in a way that should make it easy to drop in Verilog replacements in the obvious places (either for the low-level field arithmetic operators, or, as we’re currently contemplating, for the entire higher-level point multiplier).

Code is written with an eye towards (relative) simplicity, constant-time (to confound timing channel attacks), and an embedded environment (so no unnecessary use of dynamic memory, etcetera). Price tag for some of this is that some of the elliptic curve math algorithms are not the speediest possible; we hope that the Verilog portions will make this a moot point, if not, we’ll revisit.

Opinions vary on how critical constant-time is for ECDSA. On the one hand, every signature uses a new random number, and, since we think we have a pretty good TRNG, this doesn’t give an attacker much to work with. On the other hand, due to the structure of the ECDSA algorithm, an attacker who can guess the random number used for any particular signature can recover the private key, which is as bad as it gets. So we’re into analyzing (very_low_probability * very_bad_outcome), a kind of multiplication problem humans are notoriously bad at solving. I chose to err on the side of paranoia at the cost of speed.

Next steps is to integrate the new set of mechanisms into the PKCS#11 layer.