Popa and 2021
CS 161 Computer Security
Discussion 5
Cryptographic Hashes and MACs
Question 1 Crytographic Hashes () For each of the given functions H below, determine if it is one-way or not, and if it is collision- resistant or not.
Q1.1 H(x) = x2
(A) One way
(B) Collision resistant
(C) Both
(D) Neither
Q1.2 For this part you have access to a SHA-256 hash function. The notation [x : y] refers to a
Q1.3
slice of bytes x to y − 1.
H(x) = SHA-256(x[0 : len(x) − 1])
(G) One way
(H) Collision resistant
(I) Both
(J) Neither
H(x) = x3
(A) One way
(B) Collision resistant (C) Both
(D) Neither
Page 1 of 5
Question 2 MAC Madness (18 min) Evan wants to store a list of every CS161 student’s firstname and lastname, but he is afraid Mallory will tamper with his list.
Evan is considering adding a cryptographic value to each record to ensure its integrity. For each scheme, determine what Mallory can do without being detected.
Assume MAC is a secure MAC, H is a cryptographic hash, and Mallory does not know Evan’s secret key k. Assume that firstname and lastname are all lowercase and alphabetic (no numbers or special characters) and that usernames must be unique.
Q2.1 (3 points) H(firstname∥lastname)
(A) Mallory can modify a record to be a value of her choosing
(B) Mallory can modify a record to be a specific value (not necessarily of her choosing) (C) Mallory cannot modify a record without being detected
(D)
(E)
(F)
Q2.2 (3points) MAC(k,firstname∥lastname)
Hint: Can you think of two different records that would have the same MAC?
(G) Mallory can modify a record to be a value of her choosing
(H) Mallory can modify a record to be a specific value (not necessarily of her choosing)
(I) Mallory cannot modify a record without being detected
(J)
(K)
(L)
Q2.3 (3 points) MAC(k, firstname∥”-“∥lastname), where “-” is a hyphen character. (A) Mallory can modify a record to be a value of her choosing
(B) Mallory can modify a record to be a specific value (not necessarily of her choosing) (C) Mallory cannot modify a record without being detected
(D)
Discussion 5
Page 2 of 5 CS 161 – Fall 2021
(E) (F)
Q2.4 (3points) MAC(k,H(firstname)∥H(lastname))
(G) Mallory can modify a record to be a value of her choosing
(H) Mallory can modify a record to be a specific value (not necessarily of her choosing) (I) Mallory cannot modify a record without being detected
(J)
(K)
(L)
Q2.5 (3points) MAC(k,firstname)∥MAC(k,lastname)
(A) Mallory can modify a record to be a value of her choosing
(B) Mallory can modify a record to be a specific value (not necessarily of her choosing) (C) Mallory cannot modify a record without being detected
(D)
(E)
(F)
Q2.6 (3 points) Which of Evan’s schemes guarantee confidentiality on his records?
Discussion 5
Page 3 of 5
CS 161 – Fall 2021
(G) All 5 schemes
(H) Only the schemes with a MAC (I) Only the schemes with a hash
(J) None of the schemes
(K) (L)
Question 3 Confidentiality and integrity () Alice and Bob want to communicate with confidentiality and integrity. They have:
• Symmetric encryption.
– Encryption:Enc(K,m). – Decryption:Dec(K,c).
• Cryptographic hash function: Hash(m).
• MAC:MAC(K,m).
They share a symmetric key K and know each other’s public key.
We assume these cryptographic tools do not interfere with each other when used in combina- tion; i.e., we can safely use the same key for encryption and MAC.
Alice sends to Bob
1. c = Hash(Enc(K, m))
2. c = c1, c2 : where c1 = Enc(K, m) and c2 = Hash(Enc(K, m))
3. c = c1,c2 : where c1 = Enc(K,m) and c2 = MAC(K,m)
4. c = c1,c2 : where c1 = Enc(K,m) and c2 = MAC(K,Enc(K,m))
Q3.1 Which ones of them can Bob decrypt? 1 2 3 4
Q3.2 Consider an eavesdropper Eve, who can see the communication between Alice and Bob. Which schemes, of those decryptable in (a), also provide confidentiality against Eve?
1 2 3 4
Discussion 5 Page 4 of 5 CS 161 – Fall 2021
Q3.3 Consideraman-in-the-middleMallory,whocaneavesdropandmodifythecommunication between Alice and Bob.
Which schemes, of those decryptable in (a), provide integrity against Mallory? i.e., Bob can detect any tampering with the message?
1 2 3 4
Q3.4 Many of the schemes above are insecure against a replay attack.
If Alice and Bob use these schemes to send many messages, and Mallory remembers an encrypted message that Alice sent to Bob, some time later, Mallory can send the exact same encrypted message to Bob, and Bob will believe that Alice sent the message again.
How to modify those schemes with confidentiality & integrity to prevent replay attack?
⋄ The scheme providing confidentiality & integrity is Scheme . The modification is:
Discussion 5 Page 5 of 5 CS 161 – Fall 2021