RSA Key Generation and Authentication Protocols - Prof. A.U. Shankar, Exams of Computer Science

Download RSA Key Generation and Authentication Protocols - Prof. A.U. Shankar and more Exams Computer Science in PDF only on Docsity! CMSC 414 S09 Exam 1 Page 1 of 6 Name:____________________________________ ____________________________________________________________________________________________________ Total points: 55. Total time: 75 minutes. 6 problems over 6 pages. No book, notes, or calculator 1. [10 points] Are n=221 and d=35 valid numbers for RSA. Explain. If you answer yes, obtain the corresponding e. _____________________________________________________________________ Solution There are two requirements: • n must be a product of two primes • e must be relatively prime to φ(n) (so that d, which equals e−1 mod-n, exists) First requirement [2 points] n = 221 = 13·17. 13 and 17 are primes. So this holds. Second requirement [2 points] If n =p·q where p and q are distinct primes, then φ(p⋅q) = (p−1)⋅(q−1) So φ(221) = (13−1)⋅(17−1) = 12·16 = 192 gcd(35, 192) = 1 [because 35 = 7·5 and 192 = 2 6 .3, so they have no factors in common] So e=35 is valid. So d = 35 −1 mod 192 [2 points] Obtaining d [4 points] We want integers a and b such that 1 = a·192 + b·35 (then b will be e). We can do trial and error or use Euclid’s algorithm, as shown below. [Below, rows n = −2 and n = −1 are initialization. rn ← remainder (rn-2/rn-1); qn ← quotient ( rn-2/rn-1 ); un ← un-2 − qn⋅un-1; vn ← vn-2 − qn⋅vn-1; ] n qn rn un vn −2 192 1 0 −1 35 0 1 0 5 17 1 −5 1 2 1 −2 11 2 17 0 From row n=1, we have rn = gcd(35, 192) = 1 (which we already knew), and 1 = (−2)·(192) + (11)·35 [ = -384 + 385 ] So d = 11 mod 192 = 11. _____________________________________________________________________ CMSC 414 S09 Exam 1 Page 2 of 6 Name:____________________________________ 2. [6 points] Every day X talks to Y via nodes A1, A2, B2, B1, as shown above: X sends a msg of 56 octets; A1 attaches a header of “A1,A2”; B1 puts the entire packet in another packet with header “B1,B2”; B2 undoes B1’s wrapping; A2 undoes A1’s wrapping. Addresses A1, A2, B1, B2 are each 32 bits. One day, X and Y decide to encrypt their communication with a secret key J (i.e., X and Y share J), and B1 and B2 decide to integrity-protect their communication with a secret key K (i.e., B1 and B2 share K). Both pairs use DES in CBC mode. Give the size of A1-B1 packet and the size of the B1-B2 packet. Explain your answers briefly. _____________________________________________________________________ Solution DES operates on 8-octet (64-bit) data blocks. CBC requires an IV of the encryption block size, so this too is 8 octets. A1, A2, B1, B2 are each 32 bits, which is 4 octets. • X-A1 pkt = J{msg} [2 points] pkt size = IV + msg.size = 8 + 56 octets = 64 octets • A1-B1 pkt = [A1,A2, J{msg}] [1 point] pkt size = 4 + 4 + 64 = 72 octets • MAC{[A1-A2 pkt]} = IV + CBC residue [2 points] mac size = 8 + 8 octets • B1-B2 pkt = [B1, B2, [A1-A2 pkt], MAC{[A1-A2 pkt}] [1 points] pkt size = 4 + 4 + 72 + 8 + 8 = 96 octets [3 points for the A1-B1 pkt and 3 points for the B1-B2 pkt.] [−1 point for each missing IV] [−1 point for missing residue] _____________________________________________________________________ A1 X B1 A2 B2 Y [msg] [A1,A2,msg] [B1,B 2,[A1,A2,msg]] [A1,A2,msg] [msg] CMSC 414 S09 Exam 1 Page 5 of 6 Name:____________________________________ c. 5. [5 points] The same protocol as in problem 4 except that J is now a high-quality key, B can handle muliple clients at a time, and the different instances of B do not communicate with each other. client A (has J) server B (has J) generate random CA NA ← encrypt CA with key J send [A, B, conn, NA] // msg 1 receive [A, B, conn, NA] RA
decrypt NA with key J SA
encrypt (RA+1) with key J generate random CB NB ← encrypt CB with key J send [B, A, SA, NB ] // msg 2 receive [B, A, SA, NB] TA
decrypt SA with key J if TA = CA+1 then B is authenticated else abort RB
decrypt NB with key J SB
encrypt (RB+1) with key J send [A, B, SB ] // msg 3 receive [A, B, SB ] TB
decrypt SB with key J if TB= CB+1 then A is authenticated else abort Consider an attacker who can only spoof A. Can this attacker impersonate A to B. If you answer no, explain briefly. If you answer yes, describe the attack. __________________________________________________________________________ Solution To impersonate A to B, the attacker must deliver a suitable msg 3 to B, [1 points] i.e., one that has SB equal to the correct response for NB Because B can handle multiple clients at the same time, the attacker obtain J{NB} via a reflection attack: - request another connection to B with msg 1 set to [A, B, conn, NB] [4 points] - the msg 2 response from this instance of B will have SA equal to J{NB} So the attacker can impersonate A to B. 0 points for password-guessing attack (not possible because J is high-quality key) 0 points if no explanation provided __________________________________________________________________________ CMSC 414 S09 Exam 1 Page 6 of 6 Name:____________________________________ 6. [10 points] Server B, which supports many clients, is attached to the Internet at a well-known (not secret) <TCP port, IP addr> y. Each client shares a password-dervied key with B. So B has for, each client, an entry consisting of the client id and key. The clients and server also share Diffie-Hellman parameters g and p (not secret). B has so many clients that it can decrypt ciphertext encrypted with a client key only if it already knows the client id; i.e., it is not feasible for B to try all the client keys until it finds one that results in sensible plaintext. Write down an authentication protocol so that a client A attached at an Internet <TCP port, IP addr> x can connect to B without disclosing its id (i.e., “A”) to an attacker that can only eavesdrop (i.e., hear messages in transit but cannot intercept messages or send messages with somebody else’s sender id). Cliearly identify the operations done at each side and the messages exchanged. __________________________________________________________________________ Solution 1. A attaches to x and requests TCP connnection to y [3 points] 2. After connection is established, A initiates DH exchange with B [3 points] 3. After DH exchange, A sends its id encrypted with DH key and authentication nonce, etc [4 points] A at x (has g, p and secret key K) B at y (has g, p and a [client id, key] entry for each client) Part 1 (x establishes TCP connection with y) attach to x; request TCP connection to y accept connection request become open to x become open to y Part 2 (A and B establish DH key) gen a TA ← g a mod p send [x, y, TA] (i.e., send TA as data on TCP connection) gen b TB ← g b mod p send [x, y, TB] JB ← (TA) b mod p // DH key JA ← (TB) a mod p // DH key Part 3 (A initiates authentication with B using K) gen NA send [x, y, JA{“A”, K{NA}}]] extract “A”, K{NA} using JB RA ← 1 + decrypt K{NA} using K gen NB send[y, x, JB{RA, K{NB}}] extract RA, K{NB} using JA if RA = NA + 1 then B authenticated RB ← 1 + decrypt K{NB} using K send[x, y, JB{RB}] extract RA, K{NB} using JA if RB = NB + 1 then A authenticated At most 1 point if part 1 missing. (Without part 1, A and B cannot authenticate without exposing A’s id.) 0 points if A or B sends messages with “A” exposed in part 2 (e.g., send [A, B, TA]). __________________________________________________________________________