Elliptic Curve Cryptography in Practice

This week, in our study group, Dan P. looked at the paper "Elliptic Curve Cryptography in Practice". This paper tries to do for elliptic curve based cryptography what the following papers did for factoring based cryptography:

• Ron was wrong, Whit is right
• Mining your Ps and Qs
• Coppersmith in the wild    

All three of these papers managed to extract RSA private keys from a large corpus of published RSA public keys. The essential trick being that poor random number generation leads to RSA public keys which have a high probability of sharing a prime factor with another RSA public key. This is particularly a problem for low end devices which generate their own keys on start-up, when there is little available entropy to seed the random number generator.

The current paper aims to study how ECC is really used in the wild, and examine similar issues. As the first task the authors captured real world data. This was from four different applications.

• Bitcoin: Here the signing algorithm used to transfer bitcoins from one wallet to another is the ECDSA algorithm. Obtaining the full set of public keys for bitcoin, and the full set of issued digital signatures, is easy. All one needs to do is download the blockchain!
• TLS: ECC can be used in one of two places. Either via ECDH to derive the pre-master secret and/or using ECDSA to sign the Diffie-Hellman handshake. To obtain the data on TLS the authors scanned the internet to examine all IPv4 web addresses and see whether they answered a TLS handshake request, and with what.
• SSH: SSH is much like TLS, except the handshake algorithm is a lot simpler. Again one can use ECC in one of two ways; either to derive keys and/or to provide authentication.
• Austrian Citizen Card: The Austrian e-ID card can use ECDSA for signing; and all public keys are available via an LDAP database.

In terms of what the authors found, the deployment of ECC seemed quite sparse. For TLS, the most important protocol, only 1 in 10 servers supported ECC. Of these 98% supported curves of 256 bits, whereas 80 (resp. 70) percent supported curves of 384 (resp. 521) bits. Why servers would not support all bit sizes sparked some discussion in our group. But we could come up with no really rational reason.

An interesting aside would be to reconduct the experiment. Since the Snowden revelations last year many companies have moved to "forward secure" variants of TLS. Almost all forward secure variants of TLS require the use of ECC enabled Diffie-Hellman key agreement. Thus one would expect (hope maybe?) that the number of servers supporting ECC would now be larger than 10%.

Then the authors went on to examine possible weak failure points of implementations of ECDSA; similar to the weak entropy for RSA key generation mentioned at the start. There were a tiny number of  anomalies in Bitcoin transactions: 

• For 158 wallets (out of 47 million) one could recover the private key from the public signing data. Again this was due to poor random number generation.
•  A number of wallet addresses cannot (within reason) correspond to valid private keys (unless the Bitcoin hash function can be easily inverted). The authors reckon 75 BTC have been lost in this way.

The conclusions re the investigation for the other three cases studies revealed virtually no surprising results. So the study group closed for the week.