Week 2 – Problem Set >> Cryptography I
1. Question 1 Consider the following five events: Correctly guessing a random 128-bit AES key on the first try. Winning a lottery with 1 million contestants (the probability is 1/10^6\ 1/10 6 ). Winning a lottery with 1 million contestants 5 times in a row (the probability is (1/10^6)^5\ (1/10 6 ) 5 ). Winning a lottery with 1 million contestants 6 times in a row. Winning a lottery with 1 million contestants 7 times in a row. What is the order of these events from most likely to least likely? 1 point 2, 3, 4, 5, 1 2, 3, 4, 1, 5 2, 3, 5, 4, 1 3, 2, 5, 4, 1 2. Question 2 Suppose that using commodity hardware it is possible to build a computer for about $200 that can brute force about 1 billion AES keys per second. Suppose an organization wants to run an exhaustive search for a single 128-bit AES key and was willing to spend 4 trillion dollars to buy these machines (this is more than the annual US federal budget). How long would it take the organization to brute force this single 128-bit AES key with these machines? Ignore additional costs such as power and maintenance. 1 point More than a year but less than 100 years More than a week but less than a month More than a billion (10^910 9 ) years More than a month but less than a year More than a 100 years but less than a million years 3. Question 3 Let F:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^nF:{0,1} n ×{0,1} n →{0,1} n be a secure PRF (i.e. a PRF where the key space, input space, and output space are all \{0,1\}^n{0,1} n ) and say n=128n=128. Which of the following is a secure PRF (there is more than one correct answer): 1 point F'(k, x) = F(k,\ x \bigoplus 1^n)F ′ (k,x)=F(k, x⨁1 n ) F'( (k_1,k_2),\ x) = F(k_1,x) \bigoplus F(k_2,x)F ′ ((k 1 ,k 2 ), x)=F(k 1 ,x)⨁F(k 2 ,x) F'( (k_1,k_2),\ x) = F(k_1,x) \ \ \big\| \ \ F(k_2, x)F ′ ((k 1 ,k 2 ), x)=F(k 1 ,x) ∥ ∥ ∥ F(k 2 ,x) (here \big\| ∥ ∥ ∥ denotes concatenation) F'( k,\ x) = k \bigoplus xF ′ (k, x)=k⨁x F'( k,\ x) = {F(k,x)kwhen x≠0notherwise F ′ (k, x)={ F(k,x) k when x =0 n otherwise F'( k,\ x) = {F(k,x)0nwhen x≠0notherwise F ′ (k, x)={ F(k,x) 0 n when x =0 n otherwise 4. Question 4 Recall that the Luby-Rackoff theorem discussed in The Data Encryption Standard lecture states that applying a three round Feistel network to a secure PRF gives a secure block cipher. Let’s see what goes wrong if we only use a two round Feistel. Let F: K \times \{0,1\}^{32} \to \{0,1\}^{32}F:K×{0,1} 32 →{0,1} 32 be a secure PRF. Recall that a 2-round Feistel defines the following PRP F_2: K^2 \times \{0,1\}^{64} \to \{0,1\}^{64}F 2 :K 2 ×{0,1} 64 →{0,1} 64 : Here R_0R 0 is the right 32 bits of the 64-bit input and L_0L 0 is the left 32 bits. One of the following lines is the output of this PRP F_2F 2 using a random key, while the other three are the output of a truly random permutation f:\{0,1\}^{64} \to \{0,1\}^{64}f:{0,1} 64 →{0,1} 64 . All 64-bit outputs are encoded as 16 hex characters. Can you say which is the output of the PRP? Note that since you are able to distinguish the output of F_2F 2 from random, F_2F 2 is not a secure block cipher, which is what we wanted to show. Hint: First argue that there is a detectable pattern in the xor of F_2(\cdot,\ 0^{64})F 2 (⋅, 0 64 ) and F_2(\cdot,\ 1^{32} 0^{32})F 2 (⋅, 1 32 0 32 ). Then try to detect this pattern in the given outputs. 1 point On input 0^{64}0 64 the output is “9f970f4e 932330e4”. On input 1^{32} 0^{32}1 32 0 32 the output is “6068f0b1 b645c008”. On input 0^{64}0 64 the output is “7c2822eb fdc48bfb”. On input 1^{32} 0^{32}1 32 0 32 the output is “325032a9 c5e2364b”. On input 0^{64}0 64 the output is “4af53267 1351e2e1”. On input 1^{32} 0^{32}1 32 0 32 the output is “87a40cfa 8dd39154”. On input 0^{64}0 64 the output is “2d1cfa42 c0b1d266”. On input 1^{32} 0^{32}1 32 0 32 the output is “eea6e3dd b2146dd0”. 5. Question 5 Nonce-based CBC. Recall that in Lecture 4.4 we said that if one wants to use CBC encryption with a non-random unique nonce then the nonce must first be encrypted with an independent PRP key and the result then used as the CBC IV. Let’s see what goes wrong if one encrypts the nonce with the same PRP key as the key used for CBC encryption. Let F: K \times \{0,1\}^{\ell} \to \{0,1\}^{\ell}F:K×{0,1} ℓ →{0,1} ℓ be a secure PRP with, say, \ell=128ℓ=128. Let nn be a nonce and suppose one encrypts a message mm by first computing IV = F(k,n)IV=F(k,n) and then using this IV in CBC encryption using F(k,\cdot)F(k,⋅). Note that the same key kk is used for computing the IV and for CBC encryption. We show that the resulting system is not nonce-based CPA secure. The attacker begins by asking for the encryption of the two block message m = (0^{\ell}, 0^{\ell})m=(0 ℓ ,0 ℓ ) with nonce n=0^{\ell}n=0 ℓ . It receives back a two block ciphertext (c_0, c_1)(c 0 ,c 1 ). Observe that by definition of CBC we know that c_1 = F(k, c_0)c 1 =F(k,c 0 ). Next, the attacker asks for the encryption of the one block message m_1 = c_0 \bigoplus c_1m 1 =c 0 ⨁c 1 with nonce n=c_0n=c 0 . It receives back a one block ciphertext c_0’c 0 ′ . What relation holds between c_0, c_1, c_0’c 0 ,c 1 ,c 0 ′ ? Note that this relation lets the adversary win the nonce-based CPA game with advantage 1. 1 point c_1 = c_0c 1 =c 0 c_0 = c_1 \bigoplus c_0’c 0 =c 1 ⨁c 0 ′ c_1 = c_0’c 1 =c 0 ′ c_0′ = c_0 \bigoplus 1^{\ell}c 0 ′ =c 0 ⨁1 ℓ 6. Question 6 Let mm be a message consisting of \ellℓ AES blocks (say \ell = 100ℓ=100). Alice encrypts mm using CBC mode and transmits the resulting ciphertext to Bob. Due to a network error, ciphertext block number \ell/2ℓ/2 is corrupted during transmission. All other ciphertext blocks are transmitted and received correctly. Once Bob decrypts the received ciphertext, how many plaintext blocks will be corrupted? 1 point \ell/2ℓ/2 \ellℓ 3 0 2 7. Question 7 Let mm be a message consisting of \ellℓ AES blocks (say \ell = 100ℓ=100). Alice encrypts mm using randomized counter mode and transmits the resulting ciphertext to Bob. Due to a network error, ciphertext block number \ell/2ℓ/2 is corrupted during transmission. All other ciphertext blocks are transmitted and received correctly. Once Bob decrypts the received ciphertext, how many plaintext blocks will be corrupted? 1 point 1 0 2 \ellℓ \ell/2ℓ/2 8. Question 8 Recall that encryption systems do not fully hide the length of transmitted messages. Leaking the length of web requests hasbeen used to eavesdrop on encrypted HTTPS traffic to a number of web sites, such as tax preparation sites, Google searches, and healthcare sites. Suppose an attacker intercepts a packet where he knows that the packet payload is encrypted using AES in CBC mode with a random IV. The encrypted packet payload is 128 bytes. Which of the following messages is plausibly the decryption of the payload: 1 point ‘The most direct computation would be for the enemy to try all 2^r possible keys, one by one.’ ‘We see immediately that one needs little information to begin to break down the process.’ ‘In this letter I make some remarks on a general principle relevant to enciphering in general and my machine.’ ‘To consider the resistance of an enciphering process to being broken we should assume that at same times the enemy knows everything but the key being used and to break it needs only discover the key from this information.’ 9. Question 9 Let R := \{0,1\}^4R:={0,1} 4 and consider the following PRF F: R^{5} \times R \to RF:R 5 ×R→R defined as follows: \hspace{1cm} F( k, x) := \left\{ t=k[0] for i=1 to 4 doif (x[i−1]==1)t=t⊕k[i] output t \right.F(k,x):= ⎩ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎧ t=k[0] for i=1 to 4 do if (x[i−1]==1)t=t⊕k[i] output t That is, the key is k = (k[0],k[1],k[2],k[3],k[4])k=(k[0],k[1],k[2],k[3],k[4]) in R^5R 5 and the function at, for example, 01010101 is defined as F(k, 0101) = k[0] \oplus k[2] \oplus k[4]F(k,0101)=k[0]⊕k[2]⊕k[4]. For a random key kk unknown to you, you learn that \hspace{1cm} F(k, 0110) = 0011\ F(k,0110)=0011 and \ F(k, 0101) = 1010\ F(k,0101)=1010 and \ F(k, 1110) = 0110\ F(k,1110)=0110 . What is the value of F(k, 1101)F(k,1101)? Note that since you are able to predict the function at a new point, this PRF is insecure. 1 point Enter answer here
*Please Wait 15 Seconds To Get The Pdf Loaded