A deep dive into Elliptic Curve Cryptography
Long Overdue
For work these past few weeks, I’ve had to dive deep back into learning cryptography. While I’ve mostly had a solid grasp of all topics, I haven’t been satisfied with my ability to articulate to both non-technical and technical colleagues both why ECC is the better choice and how to implement.
Why is ECC better than RSA
Essentially - over the past two decades, progress has been made in cutting down the time to factor very large numbers to find two primes. This is the underpinning security of RSA in what’s known as a trap door function. Easy to do one way (multiply two large primes together) hard to reverse (factor that very large number).
So while RSA isn’t insecure, its security has weakened over time due to it’s core trapdoor function effectiveness diminishing based on more powerful hardware and factoring technique advancements.
ECC’s trap-door function relies on the elliptic curve discrete logarithm problem, which has not had its trap-door effectiveness weakened over time (yet). ECC is also better for speed - faster key generation, smaller key sizes. While these may not be enormous differences for web content - it does make a difference in embedded contexts. Microchip has a good write-up on the speed improvements made.
The downside is that ECC and its crypto libraries/implementations are a bit more complex than RSA - and require someone who’s familiar with cryptography to think a little bit differently.
ECDH - Elliptic Curve Diffie-Hellman
The replacement for regular Diffie-Hellman key exchange (DHKE). ECDH is used to generate a shared secret between two parties.
It comes down to a mathematical in ECC point multiplication - similar to modular exponentiation used in DHKE.
Essentially:
ECDH is the preferred key exchange mechanism in most modern TLS configurations and is probably the most common usage of ECC crypto.
ECDSA - Elliptic Curve Digital Signature Algorithm
ECDSA involves a ton of complicated math that I will forgo explaining to focus on a high level overview. In RSA, signing meant encrypting something with the private key - normally a hash. Verifying a signature meant decrypting the signed hash with the known public key, and then comparing it to the calculated hash of the message.
The same general steps are taken, but the implementation looks quite different. ECDSA’s elliptic curve signing calculation still taken in a private key and a message. But the signature is a pair of coordinates along the curve that act as proof the signer knows what the private key is.
ECDSA is used all over the place as a signing algorithm. Substack’s website uses ECDSA as the signing algorithm for certs that are issued to it!
ECIES - Elliptic Curve Integrated Encryption Scheme
ECIES is fundamentally performing an ECC encrypt. Except - this isn’t like RSA, I can’t simply perform some prime number multiplication to encrypt. That same operation doesn’t translate over to ECC. So what I have to do is use a hybrid encryption scheme to share a secret over ECDH, then use that to generate a key to encrypt messages.
ECIES involves selecting three different components: the elliptic curve public key calculations, the key-derivation function, and the symmetric cipher to be used.
Let’s diagram this.
I start out with the classic Alice and Bob. They each have their ECC public and private key pair. We will assume Bob is acting as the server and Alice the client.
Alice will send over her public key, along with a nonce of random data used to seed some of the numbers used in subsequent calculations. Bob will then take Alice’s public key, along with his private key, and generate a shared secret a la ECDH.
Bob then uses that shared secret as an input to a key-derivation function (KDF) to produce a symmetric key. The KDF can be a hashing function like SHA-256.
Finally, the message Bob wants to send to Alice is encrypted with that symmetric key, producing the cipher text.
That cipher text is sent over with Bob’s public key.
Alice now performs the same steps that Bob did. She uses her private key with Bob’s public key to produce the shared secret, which is then hashed to produce the symmetric key. That key is then used to decrypt the ciphertext and the message is received.
When should the public/privacy keys be ephemeral?
The normal recommendation for ECIES is for both parties to use ephemeral keys. While this is standard, there are scenario where it doesn’t make sense.
In general, I would say the client can almost always use ECIES. In a peer-to-peer scheme, I think the certificates possessed by each client should be identifying certs, issued by a common trusted source. This way, the validity of the certs can be checked by each other.
If I am the server and am trying to manage a fleet of devices, each with their own issued certificate. I can use ECIES to pass a secured token and verify that the device has a signed certificate from a trusted source. In this case, I, as the server can use ephemeral key but the client would not.
It’s been a very long week for me, and I will be taking a long weekend of relaxation. I still got this one in on time. I have a topical analysis planned for two weeks from now I’m excited to get started on.