The common HTTPS key exchange algorithms are RSA and ECDHE.
Among them, RSA is a traditional key exchange algorithm. It does not have the nature of forward security, so it is rarely used by servers. ECDHE algorithm is widely used because of its forward security.
I have introduced the PROCESS of RSA handshake in the last article, this article will introduce the ECDHE algorithm “from theory to practice.”
Discrete logarithm
The ECDHE key negotiation algorithm is evolved from the DH algorithm, so we start with the DH algorithm.
DH algorithm is an asymmetric encryption algorithm, so it can be used for key exchange. The core mathematical idea of DH algorithm is discrete logarithm.
Are you scared to hear this math concept? I’m not going to tell you how the discrete logarithm goes, but I’m just going to tell you the math.
Discrete logarithm is a combination of two mathematical concepts of discrete plus logarithm, so let’s review logarithms first.
If you want to talk about logarithms, you have to talk about exponents, because they’re inverse functions of each other, exponents are exponents, and logarithms are inverse exponents.
For example, if base 2 is used, the formula for exponents and logarithms is as follows:
So for base 2, logarithm of 32 is 5 and logarithm of 64 is 6, and the calculation is as follows:
Logarithms can be continuous, discrete logarithms can’t be continuous, hence the name “discrete”,
Discrete logarithm is based on logarithm operation plus “modular operation”, that is, take the remainder, the corresponding programming language operator is “%”, can also be expressed by mod. The concept of the discrete logarithm is shown below:
In the figure above, the base a and module P are the common parameters of the discrete logarithm, which is to say public, b is the real number, and I is the logarithm. Now that you know the logarithm, you can use the formula above to compute the real number. On the other hand, knowing the real numbers makes it harder to extrapolate logarithms.
Especially when the modulus P is a large prime number, even if the base a and the real number B are known, it is almost impossible to calculate the discrete logarithm in the existing computer computing level, which is the mathematical basis of DH algorithm.
DH algorithm
Now that we know the discrete logarithm, let’s look at how the DH algorithm exchanges keys.
Now it is assumed that Hong and Ming agree to use DH algorithm to exchange keys. Based on the discrete logarithm, Hong and Ming need to first determine module and base as the parameters of the algorithm. These two parameters are public and are named by P and G.
Then, Xiao Hong and Xiao Ming each generate a random integer as a private key. The private keys of both parties should be kept strictly and cannot be leaked. Xiao Hong’s private key is called A, and Xiao Ming’s private key is called B.
Now that hong and Ming have both P and G and their private keys, they can calculate the public key:
- Red’s public key is denoted as A, A = G ^ A (mod P);
- Xiao Ming’s public key is denoted as B, B = G ^ B (mod P);
A and B are also open, because according to the principle of discrete logarithms, it is very difficult to compute logarithms A and B backwards from real numbers (A and B), at least with the computing power of existing computers, and if A quantum computer comes out, it will probably be cracked, and of course if A quantum computer comes out, Then the key negotiation algorithm is about to get a big upgrade.
After the TWO parties exchange their DH public keys, the red hand has five numbers: P, G, A, A, and B, and the Ming hand has five numbers: P, G, B, B, and A.
Then Red performs the operation: B ^ a (mod P), and the result is K. Since the power operation of discrete logarithms has commutative law, Ming performs the operation: A ^ B (mod P), and the result is also K.
This K is the symmetric encryption key used between Xiao Hong and Xiao Ming, which can be used as the session key.
It can be seen that during the whole key negotiation process, Xiao Hong and Xiao Ming disclosed four pieces of information: P, G, A, B, where P and G are parameters of the algorithm, A and B are public keys, and A and B are private keys kept by both parties. Hackers cannot obtain these two private keys, so hackers can only calculate discrete logarithms (private keys) from public P, G, A, and B.
According to the principle of discrete logarithm, if P is a large number, it is difficult to solve the problem of private keys A and B with the computing power of existing computers. If the private key cannot be solved, the session key cannot be calculated. Therefore, DH key exchange is secure.
DHE algorithm
Based on the private key generation mode, the DH algorithm can be implemented in two ways:
- Static DH algorithm, this is deprecated;
- DHE algorithm, now commonly used;
Static In the DH algorithm, the private key of one party is static. That is, the private key of one party is the same during key negotiation. Generally, the private key of the server is fixed, that is, A is constant, and the private key of the client is randomly generated.
Then, only the client’s DH exchange key public key is change, and the server public key is constant, so as time extended, hackers will be intercepted vast amounts of data of key agreement process, because some data is public key agreement process, hackers can brute force on the basis of these data out of the server’s private key, and then you can calculate the session key, Therefore, the intercepted encrypted data is cracked. Therefore, the static DH algorithm does not provide forward security.
Since the private keys of a fixed party are at risk of being broken, the DHE algorithm is simply ephemeral for each exchange of key communication, making the private keys of both parties randomly generated and temporary.
So, even if a good hacker breaks the private key of one communication process, the private key of the other communication process is still secure, because the private key of each communication process is independent, which ensures “forward security”.
ECDHE algorithm
In order to improve the performance of DHE algorithm, the ECDHE algorithm, which is now widely used in key exchange, was developed due to the poor calculation performance of DHE algorithm and the need to do a lot of multiplication.
Based on DHE algorithm, ECDHE algorithm utilizes ECC elliptic curve characteristics, which can calculate the public key and the final session key with less computation.
The process of Xiao Hong and Xiao Ming using ECDHE key exchange algorithm:
- Both sides decide in advance what kind of elliptic curve to use, and the base point G on the curve, and these two parameters are public;
- Both parties generate a random number as private key D and multiply it by base point G to obtain the public key Q (Q = dG). At this time, the public and private keys of Xiao Hong are Q1 and D1, and the public and private keys of Xiao Ming are Q2 and D2.
- The two parties exchange their public keys, and finally the little red calculation point (x1, y1) = d1Q2, and the little bright calculation point (x2, y2) = d2Q1. Since the multiplicative exchange and associative law can be satisfied on the elliptic curve, d1Q2 = d1d2G = d2d1G = d2Q1, so the x coordinates of the two parties are the same. So it’s a shared key, a session key.
In this process, the private keys of both sides are randomly and temporarily generated, and are not public. Even according to the public information (elliptic curve, public key, basis point G), it is difficult to calculate the discrete logarithm (private key) on the elliptic curve.
ECDHE handshake process
After knowing the basic principle of ECDHE algorithm, we will take a look at the actual situation.
Wireshark: TSL handshake using ECDHE key negotiation algorithm
If ECDHE is used, the client sends encrypted HTTP data before the fourth TLS handshake. However, in the RSA handshake, the application data must be transmitted only after the fourth TLS handshake is completed.
So, ECDHE saves a round trip of a message compared to the RSA handshake. This is called “TLS False Start”, similar to the “TCP Fast Open”, in which the application data is sent before the connection is fully established. This improves the efficiency of transmission.
Next, analyze each ECDHE handshake.
TLS first handshake
The Client will first send a “Client Hello” message, which contains the TLS version number used by the Client, the list of supported cipher suites, and the generated Client Random number.
TLS second handshake
After receiving the “Hello” from the client, the Server will return the “Server Hello” message, which contains the TLS version number confirmed by the Server and a Server Random number, and then selects an appropriate password suite from the list of password suites on the client.
However, the cipher suite selected is different from RSA. Let’s analyze the meaning of this cipher suite.
“TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384”
- The key negotiation algorithm uses ECDHE.
- The signature algorithm uses RSA.
- The communication after handshake uses AES symmetric algorithm, the key length is 256 bits, and the packet mode is GCM.
- The algorithm is SHA384.
Then, to prove its identity, the server sends a “Certificate” message, which is also sent to the client.
This step is very different from the RSA handshake. Because the Server uses the ECDHE Key negotiation algorithm, it sends the Server Key Exchange message after the certificate is sent.
The process server does three things:
- Select an elliptic curve named named_curve, select the elliptic curve is equivalent to the elliptic curve base point G, these will be exposed to the client;
- Generate a random number as the private key of the server elliptic curve and save it locally.
- The server’s elliptic curve public key is calculated based on base point G and the private key, which is exposed to the client.
To prevent the public key of the elliptic curve from being tampered with by a third party, the server uses the RSA signature algorithm to sign the public key of the elliptic curve on the server.
This is followed by a “Server Hello Done” message, in which the Server says to the client, “This is my information.
At present, the Client and Server share the following information through plaintext: Client Random, Server Random, elliptic curve used, elliptic curve base point G, and the public key of the Server elliptic curve. These information is very important and is the material for the subsequent generation of session keys.
TLS handshake for the third time
After receiving the certificate from the server, the client verifies whether the certificate is valid. If the certificate is valid, the server-side identity is valid. During certificate verification, the authentication is performed step by step through the certificate chain to verify the authenticity of the certificate. Then, the public key of the certificate is used to verify the signature. In this way, the identity of the server can be confirmed.
The Client generates a random number as the private Key of the elliptic curve of the Client, and then generates the public Key of the elliptic curve of the Client based on the information provided by the server, and sends the “Client Key Exchange” message to the server.
At this point, each side has the other’s public key of elliptic curve, its own private key of elliptic curve, and base point G of elliptic curve. Therefore, both sides calculate the point (x, y), where the x coordinate value is the same for both sides. In the previous ECDHE algorithm, x was said to be the session key, but in practice, x is not the final session key.
Remember the TLS handshake phase, when both the client and server generated a random number to pass to each other?
The final session key is generated using three materials: client random number + server random number + X (the shared key calculated by ECDHE algorithm).
The reason for this trouble is that TLS designers do not trust the reliability of client or server “pseudo-random numbers”. To ensure true randomness, mix three unreliable random numbers together and the degree of “randomness” is high enough for a hacker to calculate the final session key, which is more secure.
After calculating the session key, the client sends a Change Cipher Spec message to tell the server to use the symmetric algorithm to encrypt communication.
Then, the client sends the “Encrypted Handshake Message” Message to digest the previously sent data and encrypt it with the symmetric key. Then, the server performs authentication to verify whether the generated symmetric key can be used properly.
TLS for the fourth handshake
Finally, the server performs the same operation to send “Change Cipher Spec” and “Encrypted Handshake Message”. If both parties verify that encryption and decryption are ok, the Handshake is officially completed. Then, encrypted HTTP requests and responses can be sent and received normally.
conclusion
The differences between RSA and ECDHE handshake processes:
- The RSA key negotiation algorithm does not support forward secrecy, and the ECDHE key negotiation algorithm does support forward secrecy.
- Using RSA key negotiation algorithm, TLS can transmit application data after completing four handshakes. For ECDHE algorithm, the client can send encrypted HTTP data in advance without waiting for the server’s last TLS handshake, saving the round-trip time of a message.
- If ECDHE is used, the Server Key Exchange message is displayed during the second TLS handshake, but the message is not displayed during the RSA handshake.
Shoulders of giants
- zh.wikipedia.org/wiki/ Elliptic curve Diffie…
- zh.wikipedia.org/wiki/ elliptic curve
- zh.wikipedia.org/wiki/ Diffie Herman…
- Time.geekbang.org/column/arti…
- zhuanlan.zhihu.com/p/106967180