Background

The questions I want to answer:

  • How RSA and Diffie Hellman work? Pros and cons?
  • How TLS handshake works?
  • Why do we need both RSA and DP in TLS, when seem like we can use either of them to achieve a secret key exchange?
  • What is Perfect forward secrecy?
RSA
  • a public-key encryption that helps anyone can send a secret
    (encrypted) message to the receiver, without any prior contact, using publicly available info.

  • Mechanics:

    • the receiver generates 2 pairs of keys: public key PK = (e,n), secret key SK = (d,n). (I will not dig into the mathematics behind the scene of the e, n, d generating process). PK is public, everyone knows it, it is like the telephone number that anyone can look up in the yellow book. SK is kept secretly and only known by the receiver.
    • the sender then uses PK to encrypt the message m and sent it to receiver via a public channel. At this point, anyone can see the encrypted message c but cannot decrypt it.
      c = m^e % n
    • the receiver uses the SK to decrypt the message.
      m = c^d % n
  • Why RSA is secured: RSA's security is based on the fact that multiplying these two prime numbers is easy, but determining the original prime numbers from the product, that’s factoring, is considered infeasible due to the time it would take even using today’s super computers.

  • The disadvantage of RSA is it does not offer forward secrecy. If an attacker records all messages sent to the receiver then all of those messages can be decrypted if the SK is later on compromised. We, of course, can generate a new pair of keys for every communication session, but this will be an expensive procedure.

Forward secrecy
  • aka perfect forward secrecy (PFS)
  • a feature of specific key agreement protocols that gives assurances that session keys will not be compromised even if the private key of the server is compromised.
Authentication with RSA
  • Apart from a public key encryption, RSA can also be used as an authentication method:

    • confirming that a message has been sent by the entity who claims to have sent it, and proving that a message hasn’t been altered or tampered with.
  • Mechanics:

    • signer produces a digital signature by applying a hash function on a message m the sign it with the SK (d, n)
      signature = hash(m)^d % n
    • signer then sends the (m, signature, hash function) to verifier
    • verifier verifies by reproducing the message hash by PK**(e, n)**:
      hash(m)' = signature^e % n
    • then compare
      hash(m)' == hash(m)
    • the reason why we do not sign directly on m is that RSA operation can not handle messages longer than the modulus size. That means that if you have a 2048 bit RSA key, you would be unable to directly sign any messages longer than 256 bytes long => we need to hash the message to a fixed size.

Diffies Hellman (DH)

  • a key exchange algorithm

  • a method of securely exchanging cryptographic keys over a public channel. It allows the two parties to communicate over a potentially dangerous connection and still come up with a shared secret that they can use to make encryption keys for their future communications.

  • Mechanics:

    • sender and receiver each pick a large number x and y, and keep them secret from the public.
    • both sides agree on two more numbers, which anybody can know. We'll call them g and n. In practice
      • n is a large prime number
      • g is a relatively small number that is derived from a cyclic group (G) that is normally generated well before
    • sender calculates g^x % n and sends the result to receiver via public channel.
    • receiver calculates g^y % n and sends the result to sender via public channel.
    • the shared key is g^(x*y) % n = ((g^x % n)^y) % n = ((g^y % n)^x) % n
  • Why DH is secured:

    • DH's safety relies on the Diffie-Hellman problem, which assumes that under the right parameters, it is infeasible to calculate g^(x*y) % n from the separate values of g, g^x, g^y, n. There is currently no publicly known way to easily find g^(x*y) from the other values, which is why the Diffie-Hellman key exchange is considered secure, even though attackers can intercept the values g, n, g^x, g^y
  • Advantages of DH over RSA

    • It is faster than RSA
    • DH offers PFS
  • Problems of DH is that it provides no authentication because it has no means of verifying whether the other party in a connection is really who they say they are. Without any form of authentication, users may actually be connecting with attackers when they think they are communicating with a trusted party. => this is the reason why we usually use RSA and DP together in practice to have both PFS and authentication.

TLS handshake
  • What happens between client and server during TLS handshake:

    • specify the TLS protocol version they will use
    • decide the cipher suite they will use
    • client authenticates the identity of server via Certificate Authority (CA)
    • generate session keys to use symmetric encryption after the handshake is complete
  • Detail steps:

    1. Client sends Client Hello message to Server which include:
      • TLS version client supports
      • cipher suites client supports
      • a random bytes: client random
    2. Server sends Server Hello message to Client which include:
      • Server's SSL certificate
      • server's chosen cipher suites
      • a random bytes: server random
    3. Client confirms Server's identity (authentication) by checking the server's SSL certificate using RSA encryption:
      • SSL certificate contains:
        • domain name
        • person/ organization owns the certificate
        • which Certificate authority (CA) issued it
        • CA's digital signature
        • issue date
        • expiration date
        • server's PK (used later in key exchanges)
        • some other parameters ...
      • The whole identity authentication is based on the idea "You trust the CA, and they trust me, therefore you can trust me.":
        • the browser has a build-in list of all CA's public key
        • it uses CA's PK to decrypt the CA's digital signature
        • it confirms that the decrypted data is matched.
    4. Key Exchange: at this point, base on the cipher suite, the key exchange can be conducted differently:
      • RSA key exchange:
        • Client generates a random pre-master secret, encrypts it with the Server's public key (found in Server SSL's certificate), sents the result to Server
        • Server decrypts the pre-master secret using its secret key.
        • At this point, both Client and Server share the same pre-master secret. As mentioned above, RSA key exchange doesn't offer PFS, so it is abandoned in TLS v1.3, the key exchange algorithm in TLS v1.3 is Ephemeral Diffie-Hellman.
      • DH key exchange
        • Server calculates its DH parameters: (g, n, g^x % n), and sends to Client
        • Client calculates its DH parameter: (g^y % n), and sends to Server
        • At this point, both Client and Server can calculate the pre-master secret = g^(x*y) % n
    5. Both Client and Server generate session key from pre-master secret, client random, and server random. The purpose of client random and server random is to avoid replay attack.
    session_key = PRF(pre_master_secret, 
                    "master secret", 
                    ClientHello.random + ServerHello.random)
    
    1. Client is ready: The client sends a "finished" message that is encrypted with a session key.
    2. Server is ready: The server sends a "finished" message encrypted with a session key.
    3. Secure symmetric encryption achieved: The handshake is completed, and communication continues using the session key.

Ref: