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 p ga mod p (Notice that x == x′) Can use k := HMAC0(x) as a shared key. DH passive eavesdropping attack a b ga mod p Eve wants to compute x = gab mod p Best known approach: ga mod p Find a or b, then compute x Finding 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 p Man-in-the-middle (MITM) attack a' b' b a Alice does D-H exchange, really with Mallory Bob does D-H exchange, ga modp gb' mod p ga' modp gb mod p kBob = ga’b mod p really with Mallory kAlice = gab’ mod p Alice and Bob each think they are talking with the other, but really Mallory is between them and knows both secrets Bottom line: D-H gives you secure connection, but you don’t know who’s on the other end! Defending D-H against MITM attacks ◦ Cross your fingers and hope there isn’t an active adversary. ◦ Rely on out-of-band communication between users. [Examples?] ◦ Rely on physical contact to make sure there’s 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 can’t participate w/o knowing password. ◦ Use digital signatures. [More next week.] Public key encryption Can Alice share a “public key” (ga mod p) and have anyone encrypt a message only she can read? Public key encryption Can Alice share a “public key” (ga mod p) and have anyone encrypt a message only she can read? Diffie-Hellman doesn’t allow this directly, but with some math: Alice’s public key is A= ga mod p and her private key is a Bob has Alice’s 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