We had already looked at RSA back in this article for Diffie Helman Key Exchange in TLS. Let us understand other modern approaches in this space, namely Elliptic curve and Post Quantum Cryptography. Also let us look at Digital Signatures and how the PS3 private keys were stolen because of a nonce reuse.
Elliptic Curve Cryptography[3]
What are Elliptic Curves?
The elliptic curve over Zp, p > 3, is the set of all pairs (x,y) ∈ Zp which fulfill y² ≡ x³+a · x+b mod p together with an imaginary point of infinity O, where a,b ∈ Zp and the condition
4 · a³ +27 · b² != 0 mod p.
The above curve is symmetric around the x axis as solving it for y will give you two roots.
There are two geometric operations which are done on Elliptic Curves.
It gives us another way to solve the Discrete Logarithm Problem which was introduced here.
What do these operations give us?
Let’s take a point G and add it to itself x times to produce another point P via the addition operation we defined. We can write that as P = G + ··· + G (n times) or use some mathematical syntactic sugar to write that as P = nG, which reads n times G.
The elliptic curve discrete logarithm problem (ECDLP) is to find the number n from knowing just P and G.
Algebraically, the addition and Doubling looks like below.
The Elliptic curve construction itself can be illustrated as below..
ECDH Domain Parameters
1. Choose a prime p and the elliptic curve
E : y^2 ≡ x^3 +a · x + b mod p
2. Choose a primitive element P = (xP,yP)
The prime p, the curve given by its coefficients a,b, and the
primitive element P are the domain parameters.How does this work?
- Alice generates an ephemeral private key a and public key A = [a]G
- Bob generates an ephemeral private key b and a public key B = [b]G.
- Alice and Bob exchange keys. Alice Computes aB=a[b]G and Bob computes bA = b[a]G.
- Both parties compute the same result, namely the point (ab)P. This can be done algebrically using our equations. (or even geometrically for smaller values of a and b for learning purposes)
- If an attacker Oscar wants to break the ECDH, he has the following information: E (Curve), p (prime), P(Base point), A(Public key of Alice), and B(Public key of Bob).
- Oscar has to do the following calculations to find the private keys which is infeasibly hard.
To give an example of a real world elliptic curve, the parameters are generally quite large.
max: 115792089210356248762697446949407573530086143415290314195533631308867097853951
curve: y² = x³ + ax + b
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291Note in practice ECC is preferred to RSA as it accomplishes the same level of security with shorter Key Lengths.
Post Quantum Cryptography (KYBER CRYSTALS)
Let us build this up with a few concepts.
Key Encapsulation mechanism
In this approach, The sender encapsulates the symmetric key within a cipher-text using the recipient’s public key. Upon receiving the cipher-text, the recipient then decapsulates and retrieves the symmetric key using their private key.
The Learning With Errors (LWE) Problem
Let us assume we have a public key which is a matrix A as given below.
A = [[3, 1] [4, 2]]
Secret vector S which forms the private key is equal to
s = [2, 1]
An error vector equal to
e = [1, -1]
Then if we compute c=As+e we get c=[8,9]
Now, let’s say an adversary is given the matrix A and the vector c, and the task is to recover the secret vector s.
This is where the LWE problem comes in. The adversary needs to solve for the secret vector s given the noisy vector c.
In this simple example, it’s quite easy to see that given c and A, an adversary can compute s directly because the error term e is small and the matrix A is simple. However, in real-world scenarios, the matrix A would be much larger and the error term e would be much more significant, making it computationally difficult to recover the secret vector s without knowledge of the error distribution and specialized algorithms for solving LWE.
CRYSTALS Kyber in Practice
The private key of a Kyber key pair consists of polynomials with small coefficients
Let us assume the public key and error term look like the below.
Assume we have an irreducible polynomial for modulo as given below.
Then (A*s + e ) modulo f will become
t = (16x³ + 15x² + 7, 10x³ + 12x² + 11x + 6)
We now have a Kyber key pair with:
- Private key: s
- Public key: (A,t)
The trick is that it is a hard problem to recover s from (A, t). In fact, recovering s would require an attacker to solve the module-learning-with-errors (MLWE) problem, on which this system is built. The MLWE problem is expected to be hard even for quantum computers, which is why it is used in PQC.
Encryption
As in every public key encryption system, we can encrypt a message using the public key. Decryption can only be done by parties in possession of the private key. The encryption procedure uses an ephermal error and a randomizer polynomial vector e1 and r and an error polynomial e2.
In our example we’ll use:
r=(−x³+x²,x³+x²−1)
e1=(x²+x,x²)
e2=−x³−x²
Now, to encrypt a message, we have to turn it into a polynomial. We For example, we want to encrypt the number 11. Eleven has a binary representation of 1011=(1011)2. Our message encoded as binary polynomial therefore is:
mb=1x³+0x²+1x¹+1x⁰=x³+x+1
Before encryption we have to scale this polynomial. We upscale mb by multiplying it with ⌊q/2⌉, i.e. the integer closest to q/2. In our example with q=17, ⌊q/2⌉=9. Our final ready-to-be-encrypted message therefore is:
m=⌊q/2⌉⋅mb=9⋅mb=9x³+9x+9
We encrypt m using the public key (A,t). The encryption procedure calculates two values (u, v).
In our example, those values are:
u = (11x³+11x²+10x+3,4x³+4x²+13x+11)
v = 7x³+6x²+8x+15
Kyber ciphtertexts consist of those two values: (u,v). A polynomial vector u and the polynomial v.
Decryption
Given the private key s and a ciphertext (u,v), the decryption is straightforward. First, we compute a noisy result mn.
This result is noisy, because the computation actually does not yield the original message m. By looking at the equations we can see that:
Now it becomes apparent why we needed to scale m by making its coefficients large. If you recall, all other terms in the equation were chosen to be small. So the coefficients of mn are either close to ⌊q/2⌉=9 implying that the original binary coefficient of mb was a 1 or close to 0 implying the original binary coefficient was 0.
In our example we have mn=7x³+14x²+7x+5. We can recover the original scaled message m by going through the coefficients of mn and check if they are closer to ⌊q/2⌉=9 or 0 (or equivalently q).
So, let’s do that for all coefficients:
- 7, closer to 9 than 0 or q, round to 9
- 14, closer to q than 9, round to 0
- 7, closer to 9 than 0 or q, round to 9
- 5, closer to 9 than 0 or q, round to 9
Our rounded polynomial is 9x³+9x+9, which is the scaled polynomial that we encrypted! We can now simply recover the the original binary polynomial mb by scaling down with factor 1/9:
mb=1/9*(9x³+9x+9)=(x³+x+1)
From mb we can just read the bits of the original message, which are (1011) which is 11 in decimal.
Considering the parameters,
- n: maximum degree of the used polynomials
- k: number of polynomials per vector
- q, modulus for numbers
These are the values typically used.
Hybrid ECC and Post Quantum Cryptography[2]
Chrome supports a Hybrid version of the above mechanisms for key exchange called X25519Kyber768 for TLS.
This is how it works.
- The client generates its X25519 and Kyber key pairs.The server only generates the X25519 Key pair.
- The client transmits its X25519 public key and Kyber public key A(within the ClientHello request) to the server.
- Upon receiving the ClientHello request, the server utilizes the client’s Kyber public key A to generate a Kyber shared key and its encapsulation using the above mechanism of generating u and v.
- The server then sends its own X25519 public key along with the encapsulated Kyber shared key (in the ServerHello response) to the client.
- The client, upon receiving the ServerHello response, computes the X25519 shared secret using its X25519 private key. Additionally, the client decapsulates the encapsulated Kyber shared secret utilizing its own Kyber private key.
- The Shared Key is the concatenation of the X25519 shared secret and the Kyber Shared Secret
Digital Signatures
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents and uses an asymmetric key pair.
For encryption and decryption, the person who creates the digital signature uses a private key to encrypt signature-related data. The only way to decrypt that data is with the signer’s public key.
If the recipient can’t open the document with the signer’s public key, that indicates there’s a problem with the document or the signature. This is how digital signatures are authenticated.
The public keys are generally created through a trust chain similar to certificates. So the public key of the sender might be digitally signed by another Trusted Authority all the way to a root authority.
ECDSA : Elliptic Curve Digital Signature Algorithm
Let us go through an example of how digital signatures work with ECDSA.
So how do you sign a file/message ? First, you need to know that the signature is 40 bytes and is represented by two values of 20 bytes each, the first one is called R and the second one is called S.. so the pair (R, S) together is your ECDSA signature.. now here’s how you can create those two values in order to sign a file.. first you must generate a random value ‘k‘ (of 20 byes), and use point multiplication to calculate the point P=k*G. That point’s x value will represent ‘R‘. Since the point on the curve P is represented by its (x, y) coordinates (each being 20 bytes long), you only need the ‘x‘ value (20 bytes) for the signature, and that value will be called ‘R‘. Now all you need is the ‘S‘ value.
To calculate S, you must make a SHA1 hash of the message, this gives you a 20 bytes value that you will consider as a very huge integer number and we’ll call it ‘z‘. Now you can calculate S using the equation :
S = k^-1 (z + a* R) mod pNote here the k^-1 which is the modular multiplicative inverse of k… it’s ’s a number such that (k^-1 * k ) mod p is equal to 1. (For example 3*5 mod 7=1 so 3 and 5 are modular multiplicative inverse inverses of each other)
Now that you have your signature, you want to verify it, it’s also quite simple, and you only need the public key (and curve parameters of course) to do that. You use this equation to calculate a point P :
P= S^-1*z*G + S^-1 * R * AIf the x coordinate of the point P is equal to R, that means that the signature is valid, otherwise it’s not.
Pretty simple, huh? now let’s see why and how… and this is going to require some mathematics to verify :
We have :
P = S^-1*z*G + S^-1 * R *A
but A = a*G, so:
P = S^-1*z*G + S^-1 * R * a*G = S^-1 (z + a* R) * G
But the x coordinate of P must match R and R is the x coordinate of k * G, which means that :
k*G = S^-1 (z + a * R) *G
we can simplify by removing G which gives us :
k = S^-1(z + a * R)
by inverting k and S, we get :
S = k^-1 (z + a *R)
and that is the equation used to generate the signature..
You can note that you need both ‘k‘ (random number) and ‘a‘ (the private key) in order to calculate S, but you only need R and A (public key) to validate the signature. And since R=k*G and A = a*G and because of the trap door function in the ECDSA point multiplication (explained above), we cannot calculate a or k from knowing A and R, this makes the ECDSA algorithm secure, there is no way of finding the private keys, and there is no way of faking a signature without knowing the private key.
The ECDSA algorithm is used everywhere and has not been cracked and it is a vital part of most of today’s security.
How the Sony PS3 ECC Private Keys were stolen?
Sony made a huge mistake in their implementation, they used the same value for ‘k‘ everywhere, which means that if you have two signatures, both with the same k, then they will both have the same R value, and it means that you can calculate k using two S signatures of two files with hashes z and z’ and signatures S and S’ respectively :
S — S’ = k^-1 (z + a*R) — k^-1 (z’ + a*R) = k^-1 (z + a*R — z’ -a*R) = k^-1 (z — z’)
So : k = (z — z’) / (S — S’)
Once you know k, you can solve for the private key a:
S= k^-1 (z + a*R).
S*k = z+ a*R
a = (S*k — z) / R
What about Post Quantum digital signatures?
To learn that, let us go through a few concepts.
Zero Knowledge Proofs
Here is an example which uses Bertie Bott’s every flavored beans (of Harry Potter fame) as an example. [4]
So let’s assume there are two beans which look same but one of them tastes like chocolate and the other one tastes like spinach. Your cousin claims that he can distinguish them just by looking at the beans. You don’t believe him, but he doesn’t want to tell you which one is which, so there is still a chance that you eat the spinach one.
Instead you hide them both behind your back and randomly choose one of them and show it to your cousin. You then put it back and choose randomly again in a way that allows you to know whether you picked the same bean or not (like swapping the beans x times). You then again show it to your cousin who will have to tell you whether it’s the same bean as the one you showed before. Repeat this process until you are sure that he is indeed able to distinguish the beans (or that he’s not).
You now know that your cousin is able to tell the beans apart while you still do not know which bean is the tasty one.
Let us now look at a Post Quantum Signature scheme called DILITHIUM.
DILITHIUM
Similar to Kyber except that the error is also kept as a private key e generate two random vectors s1 and s2
t = As1+s2
t and A are the public keys.
To sign, Alice uses a sigma protocol which is a 3 step process.
Alice, the prover sends a commitment to Bob. In our case Alice generates a commitment of two random vectors y1 and y2 by sending Ay1+y2.
The verifier Bob then sends a challenge c to Alice. In case of a non interactive version where we want to avoid the round trip from Bob back to Alice, Alice generates a challenge for herself by Hashing the earlier commitment Ay1+y2 to generate c. This is also called a Fiat Shamir Transformation.
Alice then calculates z1 =cs1+y1 and z2=cs2+y2. This is also called as a Hidden withness.
Bob then checks if Az1+z2-ct = Acs1+Ay1+cs2+y2-ct= c(As1+s2)+Ay1+y2-ct= ct+Ay1+y2-ct =Ay1+y2 is same as the earlier commitment.
As you can see this is a Zero Knowledge Proof, as Alice has proved she knows the secrets s1 and s2 without revealing them to Bob.
Also similar to ECC2519Kyber hybrid mechanisms may be used where a portion of the signature could be using ECC and a portion using DILITHIUM
