Since its introduction to cryptography more than 25 years ago, the elliptic curve cryptography (ECC) is increasingly gaining ground in the public-key cryptography protocol instantiation. Today it is most notably used in the implementation of Bitcoin crypto-currency, where all of the public key cryptography is done in ECC. Transport layer security (TLS) protocol, secure shell (SSH) protocol and others include elliptic curves as viable options. The advantages of ECC over other widely used public-key ciphers include smaller cryptographic key sizes and more efficient implementation, whilst offering the same level of security.
Public-key or asymmetric cryptography provides methods to encrypt and decrypt messages, as well as authenticate them using not one, but two different keys: one is used for encryption of a plaintext (public key), another for decryption of the ciphertext (private or secret key). The security of deployed cryptographic schemes relies on the assumed hardness of certain mathematical problems such as integer factorization (given a sufficiently large integer, what are the two prime numbers that are the factors of the integer in question) and discrete logarithm problem (given a sufficiently large integer and the base of a logarithm, what is the exponent resulting in the integer in question modulo some prime number).
However, as a recent example of the Heartbleed bug in OpenSSL implementation shows, most often cryptographic vulnerabilities do not stem from weaknesses in aforementioned mathematical problems, but rather from the manner in which they are implemented. Software bugs, design flaws as well as side-channel attacks – those attacks that collect information on the encrypted message or the encryption key from emission of “additional” signals such as noise produced by the computer, electromagnetic waves, etc. – are a number one threat to today’s cryptographic implementations on which we rely in our everyday use of the internet.
Researchers have surveyed several major implementations of ECC and performed a cryptographic “sanity check” – an audit that analyzed whether several known implementation-related attacks are applicable in ECC setting. More than 46 million public keys used in Bitcoin crypto-currencry transactions were extracted into a single 26GB file. It was discovered that only about a third of these were unique, putting the randomness employed in cryptographic key generation to doubt.
What is unsettling is that public-key cryptographic protocols have suffered from weaknesses in key generation in the past. Several years ago RSA, one of the most widely used public-key cryptosystems, suffered from poor randomness on certain machines, most notably in Debian GNU/Linux operating system (the weakness has been fixed by now), which allowed attackers to extract secret keys used for decryption and thus render encryption useless. ECC uses different methods for key generation and is not liable to the same kind of attacks RSA is.
Also, repeating public keys in Bitcoin protocol may be caused by multiple uses of the same Bitcoin address by the same user. However, researchers have also discovered that ECC signatures also repeat. The difference between public keys and signatures is that the latter are randomly generated per-message, hence it is impossible for the same user to reuse them multiple times. Researchers have found no explanation for the repeating elliptic curve signatures, suggesting that there is a chance that they suffer from poor randomness and are liable to attacks of similar kind.
It was also confirmed that the same nonces (“numbers used once”) were employed in generating several distinct Bitcoin public keys, further encouraging the hypothesis that poor randomness is an issue in some ECC implementations. Repeating nonces in different public keys were also discovered in TLS audit. 20 distinct nonces were found to be used more than once. 19 of them were used by different machines. The authors claim: “For servers than happen to always duplicate a server random, it is clear that there is an implementation problem to be fixed. However, for servers that only occasionally produce the same server random, it is indeed more troubling.”
The cryptographic sanity check on large datasets confirmed that even though ECC is mathematically as sound and computationally more efficient than other known public key cryptographic systems, it is not immune to known implementational vulnerabilities such as poor entropy in key generation as well as software bugs.
Elliptic Curve Cryptography in Practice. JW Bos, JA Halderman, N Heninger, J Moore, M Naehrig, E Wustrow – Microsoft Research. November, 2013, source link