Full Name:
UCI ID Number: Sources:
Spring 2019
CS134: Computer and Network Security Homework 1
Due: 04/25/19: 11:59pm
Guidelines:
• Use any word processor (or handwrite and scan your answers). Upload your solutions in PDF
to Gradescope.
• No collaboration is allowed. The only people you may consult are the TA-s and the instructor.
• Looking up, paraphrasing or copying answers from the Internet or other sources is not allowed; doing so is a violation of academic honesty. You must cite any sources you use, e.g., reference books, Wikipedia, etc.
Warning: any submissions not following the above guidelines will receive a score of zero.
P1
P2
P3
P4
P5
Total
/20
/20
/20
/20
/20
/100
1
Problem 1: Encryption using a Hash Function
To communicate securely, Alice and Bob use the following encryption scheme:
IV0 =IV
IVi = H(IVi−1)
Ci = Pi ⊕ IVi
where IV is a b-bit secret value known to both Alice and Bob, Ci and Pi are b-bit ciphertext and plaintext blocks, respectively, and H is a cryptographically secure hash function that produces a b-bit output. (Assume that b ≥ 160).
(a) Is this scheme secure? If it is, explain your reasoning. If not, show what an adversary can learn.
(b) Consider a modified version of this scheme, where Ci = Pi ⊕ IVk−i and k is the number of blocks that Alice encrypts. As in question (a), is this scheme secure or not? Explain.
Hint. Consider what happens if the adversary knows one [ciphertext,plaintext] block-pair.
Solution:
2
Problem 2: DESX and Meet-in-the-middle Attack
Recall DESX from the lecture slides, a variant of DES. DESX: C = k3 E nc(k2 , (k1 P )), where k1 is n-bit inner key, k2 is t-bit encryption key, k3 is n-bit outer key, P is the plaintext and C is the ciphertext with n bits each. Consider two ”reduced” variants of this encryption scheme.
2a DESX1: C = k3 Enc(k2, (0 P )), it is the same as DESX except that it skips inner key by XOR-ing input with zeros before the encryption step. Give an algorithm for a brute-force attack on this block cipher, and discuss its time and space complexity.
2b DESX2: C = 0 Enc(k2, (k1 P )), it is the same as DESX except that it skips outer key by XOR-ing output with zeros after encryption step. Give an algorithm for a brute-force attack on this block cipher, and discuss its time and space complexity.
2c Show how either attack can be extended to brute-force attack on DESX.
Hint: Assume you have two pairs of known [plaintext,ciphertext] blocks, denoted by [P1,C1] and P2,C2]. Try to come up with an algorithm (using meet-in-the-middle attack) for each question. Time complexity of questions 2a and 2b is a function of t and time complexity of question 2c is a function of both t and n.
Solution:
3
4
Problem 3: Probability of Collision
In country of Crapoptamia, a motorized vehicle’s license plate has the form ‘DLLLDDD’ where D is a digit [0,9] and L is an upper-case English letter. In positions 2 and 4, letters I, O, and Q are not allowed.
In a Math course, the instructor tells the class that, assuming that each student has only one car, there is a 99% probability that at least two students have the same first three characters on their license plates.
1. How many students are there in the class? Explain your solution.
2. One student says that his car license plate starts with ‘4TG’ and asks his classmates to raise a hand if anyone has the same first three characters. Weirdly, no one responds. Has the instructor made a mistake? Think about relevant properties of hash functions and contrast the instructor’s logic and the student’s question.
Solution:
5
Problem 4: Fun Math! Group Theory
Recall that FOUR properties must be satisfied for a set G and an operator @ to be a group. For the following sets and operations, show whether each (G,@) is a group. If you think it is a group, clearly illustrate that all four properties are met. Also, determine whether the resulting group is cyclic and whether it’s abelian (explain). If the group is cyclic, show a generator for the group. If you think (G,@) is not a group, provide a counterexample.
a b
1. G=(2x2invertiblematriceswithentriesinR)={ c d ∈M(2,R)|ad−bc̸=0},
@ = matrix multiplication (denoted by “·”)
2. G = Nonnegative integers Z≥ = {0, 1, 2, 3, · · · }, @ = addition (denoted by “+”)
3. G = Integers Z, @ = subtraction (denoted by “-”)
4. G = Z∗18 = {a ∈ Z18|a is coprime to 18}, @ = modular multiplication (denoted by “∗”)
Solution:
6
Problem 5: Cryptographic Hash Functions
Alice wants to monitor changes to all files on her computer. She uses HMAC and appends HMACn = HMAC(k,file namen||file contentn) to each file n. She updates this value for every change she makes to each file. Explain how an attacker (Eve) can make the following changes without being detected by Alice.
1. Content of one of Alice’s files has changed. 2. One of Alice’s file has been deleted.
3. A new file has been added.
In addition to the HMAC value appended to each file, Alice also decides to create a brand new file in every directory containing
HMAC(k,HMAC0||HMAC1||…||HMACN−1) where N is the number of files in that directory, not including the new file containing this hash. Alice updates this file (and the value therein) for every change she makes to any file within the directory. Would Alice now detect whenever the same changes 1, 2, and 3 are made by Eve? Why or why not?
Assume that Eve (e.g., in the form of malware) can save and re-use previous valid versions of Alice’s files and corresponding HMAC values.
NOTE: k denotes a key known ONLY to Alice, || is concatenation, file name is the name of the file and file content is the content of the file.
Solution:
7