[SOLVED] CS algorithm Cryptography Basics Key exchange

Cryptography Basics Key exchange

Review
Integrity: prevent Mallory from tampering
v == MACk(m) k
Bob
k
Bob
p := Dk(c)
Message Authentication Code
Hashes -> HMAC
Use: SHA2, SHA3
k
m, v:= MAC (m) k
m, v
Confidentiality: prevent eavesdropper (Eve) from learning the (plaintext) message
Streamciphers
AES-CTR, ChaCha20
Block ciphers
AES-CBC (caution: padding oracles!)
k
c := E (p) k
Eve
Alice
Mallory
Best practice: Authenticated ciphers (e.g. AES-GCM) Encrypt,thenMAC
?

Sharing k Amazing fact:
Alice and Bob can have a public conversation to derive a shared key!
Diffie-Hellman (D-H) key exchange
1976: Whit Diffie, Marty Hellman
with ideas from Ralph Merkle
(earlier, in secret, by Malcolm Williamson of British intelligence agency)
Relies on a mathematical hardness assumption called discrete log problem (a problem believed to be hard)

3.
Computes x
= (gb mod p)a mod p =gba modp
Computes x
= (ga mod p)b mod p =gab modp
Diffie-Hellman protocol
D-H protocol
1. 2.
Alice and Bob agree on public parameters (maybe in standards doc*, or pick them) p: a large safe prime s.t. (p-1)/2 is also prime
g: a square mod p (but not 1)
Alice
Generates random secret value a.
a
b
Bob
Generates random secret value b.
(0 < b < p)(0 < a < p)gb mod pga mod p(Notice that x == x)Can use k := HMAC0(x) as a shared key. DH passive eavesdropping attack abga mod pEve wants to compute x = gab mod p Best known approach:ga mod pFind a or b, then compute xFinding y given gy mod p is an instance of the discrete log problem:gb mod p Best practice: Use large DH group size (e.g. 2048-bit primes)or a more secure group (Elliptic curve cryptography)[Breakout exercise: what about Mallory (active attacks)?]No known efficient algorithm*gb mod pMan-in-the-middle (MITM) attacka’ b’b aAlice does D-H exchange,really with MalloryBob does D-H exchange,ga modp gb’ mod pga’ modp gb mod pkBob = gab mod preally with MallorykAlice = gab mod p Alice and Bob each think they are talking with the other,but really Mallory is between them and knows both secretsBottom line:D-H gives you secure connection, but you dont know whos on the other end! Defending D-H against MITM attacks Cross your fingers and hope there isnt an active adversary. Rely on out-of-band communication between users. [Examples?] Rely on physical contact to make sure theres no MITM. [Examples?] Integrate D-H with user authentication.If Alice is using a password to log in to Bob, leverage the password:Instead of a fixed g, derive g from the password Mallory cant participate w/o knowing password. Use digital signatures. [More next week.]Public key encryptionCan Alice share a public key (ga mod p) and have anyone encrypt a message only she can read?Public key encryptionCan Alice share a public key (ga mod p) and have anyone encrypt a message only she can read? Diffie-Hellman doesnt allow this directly, but with some math:Alices public key is A= ga mod p and her private key is aBob has Alices public key, and a message m he wants to send her: Pick a random value r [0,p-2] Compute R= gr mod p ComputeS=m*Armodp Send Alice (R,S)To decrypt: Alice computes S*R-a mod p = m*Ar *gr(-a) mod p = m*gargr(-a) mod p = m*gar-ar mod p = m*g0 mod p = m