Lecture 6 - Key Exchange and Public-Key Cryptography

Diffie-Hellman Key Exchange

• Alice and Bob can have a public conversation to derive a secret shared key

Procedure

1. use public (often from standards) parameters:
   • p: a large prime (e.g. 2048-bits)
   • g: a primitive root modulo p (usually small)
2. Alice generates a random secret value $0 < a < p$ Bob generates random secret value $0 < b < p$ Alice computes $A := g^a \mod p$ and shares it with Bob Bob computes $B := g^b \mod p$ and shares it with Alice
3. Alice computes $s := B^a \mod p$ Bob computes $s := A^b \mod p$ Alice and Bob each obtain the same value: $B^a \mod p = g^{ba} \mod p = g^{ab} \mod p = A^b \mod p$ Mallory is not able to derive in polynomial time either $a$ or $b$

Security of Diffie-Hellman

• passive eavesdropping fails
  • Eve knows $p,g,g^a \mod p, g^b \mod p$
  • Eve wants to compute $s := g^{ab} \mod p$
  • best known approach: find $a$ or $b$, then compute $s$
  • finding $x$ given $g^x \mod p$ is an instance of the discrete logarithm problem, which is believed to be intractable for 2048-bit $p$
• active MITM attack succeeds
  • Alice does DH with Mallory, ends up with $u := g^{ab'} \mod p$
  • Bob does DH with Mallory, ends up with $v := g^{a'b} \mod p$
  • Alice and Bob think they’re talking to each other, but really they’ve computed a separate secret key shared with Mallory
• DH dives you a shared secret, but you don’t know who it’s shared with

Issues About Keys

Defending DH from MITMs Approaches:

1. trust-on-first-use - hope there’s no attacker the first time, but detect if keys change later (SSH)
2. have users communicate out-of-band - ask people to meet or call each other to verify they have the same $k$ (Signal)
3. rely on proximity to limit MITMs - attacker must be nearby, or in contact (IoT devices)
4. use digital signatures - what HTTPS websites do Important Goal: forward secrecy

• we usually want to communicate repeatedly
• pitfall - adversary could record all the ciphertexts, then later steal our key
• solution - for each session, use DH to generate a temp session key; use separate long-term key to authenticate it
• benefits - compromising long-term key would allow future impersonation but not retrospective decryption (assuming attacker can’t break DH)

RSA - Public-Key Cryptography

• since antiquity, encryption key = decryption key “symmetric key crypto”
• breakthrough - keys can be distinct

“Textbook” RSA

key generation (in secret):

1. generate large random primes $p$ and $q$ (say, 2048 bits each)
2. compute “modulus” $N := pq$ (say, 4096 bits)
3. pick small “encryption exponent” $e$ (say, 65537) must be relatively prime to $(p-1)(q-1)$
4. compute “decryption exponent” $d$ such that $ed \equiv 1 \mod (p-1)(q-1)$

• yields RSA key pair: - public key - $(e,N)$ - private key - $d,N)$
• public key encryption:
  • encrypt - $c := m^e \mod N$
  • decrypt - $m := c^d \mod N$
• digital signatures:
  • sign - $s := m^d \mod N$
  • verify: $m = s^e \mod N$

Facts about RSA

• RSA can be used for confidentiality and/or integrity+authenticity
• confidentiality - public-key encryption
  • Alice encrypts $m$ using Bob’s public key to get $c$
  • Bob decrypts $c$ using Bob’s private key to get $m$
• integrity/sender authenticity - digital signatures
  • Alice signs $m$ using Alice’s private key to get $s$
  • Bob verifies $m,s$ using Alice’s public key
• both properties - use both, with two key pairs
  • Alice encrypts $m$ using Bob’s public key to get $c$, then Alice signs $c$ using Alice’s private key to get $s$
  • Bob verifies $c,s$ using Alice’s public key, then Bob decrypts $c$ using Bob’s private key to get $m$

Security

• best known way to compute $d$ from $e$ is factoring $N$ into $p$ and $q$
• best known algorithm - number field sieve
• believed intractable for 4096-bit $N$

Drawbacks

• 1000x slower than AES

• messages must be shorter than $N$
• keys must be relatively large

Alternative - Elliptic-Curve Cryptography (ECC)

• elliptic curves are a mathematical alternative for constructing key exchange, signing, encryption
• pros: attacks (hoped) harder, so key can be shorter
• ex: ECDH, ECDSA, Ed25519

Subtle Attacks on Textbook RSA