[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 = ga’b 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 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 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 doesn’t allow this directly, but with some math:Alice’s public key is A= ga mod p and her private key is aBob 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