Q1 Honor Code

(1 point)

Read the following honor code and sign your name.

Q2 True/False

Each true/false is worth 2 points. (30 point)

Q2.1 True or False: In order for Joey charge his electric car, he gives his assistant a “charging key” that

only allows his assistant to access the GPS, steering wheel, and nothing else. This best illustrates the principle of “Shannon’s Maxim.”

(A) True (B) False

Q2.2 True or False: In little-endian x86, the least-significant byte of multi-byte numbers is placed in the highest memory address.

(A) True (B) False

Q2.3 True or False: x86 registers are stored as part of memory.

(A) True (B) False

Q2.4 True or False: A %c format string modifier moves printf’s argument pointer by a single byte.

(A) True (B) False

Q2.5 True or False: If you don’t know the exact address of shellcode, you can still redirect execution to the shellcode.

(A) True (B) False

Q2.6 True or False: In real-world systems, canary values often contain a null byte to mitigate string- based attacks.

(A) True (B) False

Q2.7 True or False: Block ciphers, such as AES, are IND-CPA secure.

(A) True (B) False

Q2.8 True or False: AES-CTR requires PKCS-7 padding to function correctly.

(A) True (B) False

Q2.9 True or False: Given SHA2(M), an attacker cannot compute SHA2(M||M\ ) for any M\ of the attacker’s choosing, since SHA2 is a secure cryptographic hash function.

(A) True (B) False

Q2.10  xTrue or False: A MITM during the Diffie-Hellman key exchange can force Alice and Bob to

derive a shared key that is different than the one they would have derived without the MITM.

(A) True (B) False

Q2.11 True or False: Encrypting passwords before storing them is the best password storage scheme because the ciphertext does not leak any information about the password.

(A) True (B) False

Q2.12 True or False: A password database stores passwords for 100 users. There are 5000 possible passwords.

If the database stores each password as H(password), an attacker has to compute 5000×100 hashes to learn every password.

(A) True (B) False

Refer to the following certificate tree for the remaining questions.

Barney

Victoria        Punchy

Lily

Robin

Q2.13 True or False: If Victoria’s secret key is compromised by an attacker, then no certificates generated by anyone in the tree can be trusted.

(A) True (B) False

Q2.14 True or False: If Robin is trying to securely get Lily’s public key, the only way to do so would be

to obtain a certificate that was signed by Barney.

(A) True (B) False

Q2.15 True or False: If Robin is trying to securely get Punchy’s public key, the only way to do so would

be to obtain a certificate that was signed by Barney.

(A) True (B) False

Q3.3  (3 points) AES-CTR(K1,M).

PRNG is a secure, rollback-resistant PRNG that has been seeded once with some initial entropy. To generate an IV for each message, generate bytes from PRNG.

Assume that the attacker has compromised the internal state of the PRNG.

(A) IND-CPA secure, because even if an attacker compromises the internal state of the PRNG, they cannot learn anything about future outputs.

(B) IND-CPA secure, because even if the IV is predictable, AES-CTR with predictable IVs does not provide any additional information to the attacker.

(C) Not IND-CPA secure, because compromising the internal state of the PRNG results in

the attacker learning about previous IVs.

(D) Not IND-CPA secure, because a predictable IV in AES-CTR allows the attacker to learn additional information about the plaintexts.

For this question, all future subparts are independent of the previous subparts.

Alice and Bob come up with a new symmetric encryption scheme as follows:

M0 = C0 = IV

Ci = Mi−1 ⊕ EK(Mi) ⊕ Ci−1

E refers to AES-128 block cipher encryption.

Q3.4  (2 points) Write a decryption formula for Mi (for i > 0) using this scheme.

Q3.5  (3 points) Is the scheme IND-CPA secure?

(A) Yes, because Ci is the output of a block cipher that is indistinguishable from random.

(B) Yes, because AES-CBC is IND-CPA secure, and additionally XORing each Ci with Mi−1 does not give the attacker any new information.

(C) No, because encrypting the same plaintext twice gives the same ciphertext twice.

(D) No, because the attacker can manipulate the ciphertext to learn a deterministic value.

Q4 Slap Bet Commissioner (20 point)

Alice and Bob are trying to communicate over an insecure communication channel without their messages getting tampered by Mallory, a MITM.

Assume Mallory knows the 256-bit, one-block message, M, that is being sent across the channel, in addition to the value of the ciphertext, C. For each of the following schemes, first mark whether    Mallory can change the value M to be some value of her choosing, M\ .

If you mark “Yes”, provide a formula for C\ = (C,C) that, when decrypted by Bob, results in the message M\ . Write your answer in terms of M, C1 , C2 , M\ , C, and C . You may also slice any of these values (for example, M[0:127] returns the first 128 bits of M).

If you mark “No”, write “Not Needed” in the textbox.

Assume that:

• K1 and K2 are different, symmetric keys known only to Alice and Bob.

•  PKB is Bob’s public key that is certified by a trusted server.

• AES-CBC and AES-CTR are called with randomly generated IVs.

• H is SHA2-256, a secure, cryptographic, 256-bit hash function.

Q4.1  (4 points) Alice sends C = (C1,C2 )

C1 = AES-CTR(K1,M)

C2 = not used

(A) Yes, Mallory can modify the message. (B) No, Mallory cannot modify the mes-

sage.

C1 = M

C2 = HMAC(K1,M)

(A) Yes, Mallory can modify the message. (B) No, Mallory cannot modify the mes-

sage.

Q4.3  (4 points) Alice sends C = (C1,C2 )

C1 = AES-CBC(K1,M)

C2 = HMAC(PKB,C1 )

(A) Yes, Mallory can modify the message. (B) No, Mallory cannot modify the mes-

sage.

Q4.4  (4 points) Alice sends C = (C1,C2 )

C1 = M

C2 = H(K1  || C1)

(A) Yes, Mallory can modify the message. (B) No, Mallory cannot modify the mes-

sage.

Q4.5  (4 points) Alice sends C = (C1,C2 )

C1 = AES-CTR(K1,M)

C2 = H(K2) || H(C1)

(A) Yes, Mallory can modify the message. (B) No, Mallory cannot modify the mes-

sage.

Q5 Lawyered! (9 point)

Bob goes in front ofJudge Marshal and needs to show proof that a message M was sent by Alice      without any tampering. For each of the following schemes, select whether Judge Marshal should       believe Bob based on his explanations and explain why or why not. Assume that Judge Marshal has the values of all secret keys. You can answer in 10 words or fewer.

Clarification during exam: Assume that Judge Marshal is not malicious.

Q5.1  (3 points)  Bob shows Judge Marshal MAC(K,M). Bob argues that since the message is MACd

using a secret, symmetric key, shared between only Alice and Bob, and MACs provide integrity, the message must have been sent by Alice.

(A) Yes, Judge Marshal can believe Bob. (B) No, Judge Marshal cannot believe Bob.

Q5.2

(3 points) Bob shows Judge Marshal Sign(PKA,M). Bob argues that since the message is signed by Alice’s public key and digital signatures provide integrity and authenticity, the message must have come from Alice.

(A) Yes, Judge Marshal can believe Bob. (B) No, Judge Marshal cannot believe Bob.

Q5.3 (3 points) Bob shows Judge Marshal E(SKA,M), where E is AES-128 block cipher encryption. Bob argues that since the message is encrypted with Alice’s secret key, the message must have been sent by Alice.

(A) Yes, Judge Marshal can believe Bob. (B) No, Judge Marshal cannot believe Bob.

Q6 You sure he’ll crack that code? (13 point)

Consider the following scheme called CBC-MAC. CBC-MAC is very similar to AES-CBC. The IV is always 0 and the algorithm outputs the last block of the ciphertext as the MAC. The image below  illustrates how blocks of a message are encrypted with E (AES-128 block cipher encryption) for a resulting MAC.

Alice and Bob are communicating over an insecure channel. K is a symmetric key known only to Alice and Bob.

For each message, Alice sends:

AES-CBC(K,M), CBC-MAC(K,M)

Clarification during exam: Unless otherwise specified, the IV is randomly generated per encryption.

Q6.1  (2 points) Select all true statements about this scheme.

(A) Bob can always recover M.

(B) A MITM can learn something about M.

(C) A MITM can read some, but not all, of M.

(D) A MITM can read all of M.

(E) None of the above

Q6.2  (2 points) Alice sends a two-block message. Is Mallory able to tamper with the first block M1 to some different value M without being detected by Bob?

(A) Yes, without tampering with the CBC-MAC value

(B) Yes, by also tampering with the CBC-MAC value

(C) No

Q6.3  (2 points) Alice sends a two-block message. Is Mallory able to tamper with the second block M2 to some different value M without being detected by Bob?

(A) Yes, without tampering with the CBC-MAC value

(B) Yes, by also tampering with the CBC-MAC value

(C) No

Q6.4  (4 points) Alice sends an n-block message. Which blocks of the message is Mallory able to tamper

with, without being detected by Bob?

Give your answer in terms of a series of inclusive ranges. For example [1, 5], [n − 3,n] refers to Mallory being able to tamper with the first five blocks and the last three blocks. If none of the blocks can be tampered with, write “None”.

Clarification during exam: [n − 3,n] refers to the last four blocks.

Q6.5  (3 points)  How would you change CBC-MAC to prevent your attack from the previous subparts?

If you said there was no attack, explain why CBC-MAC is secure. Limit your answer to 10 words or fewer.

Q7 La Magle (13 point)

Alice and Bob want to communicate over a public channel using El Gamal encryption. Unfortunately, they have forgotten the details of El Gamal and decide to devise their own encryption scheme they call La Magle. Below are the details for Alice and Bob’s La Magle encryption scheme in the case where    Alice is sending a message to Bob.

• Key Generation: Bob randomly picks b in the range [2,p − 2], and computes B = gb mod p. Bob’s public key is B and his private key is b.

• Encryption: Let Alice’s message be some M between [0,p − 2]. Alice randomly picks r in the range [0,p − 2]. Alice then sends the following (C1,C2 ) as her ciphertext:

C1 = gr mod p

C2 = gM  × Br mod p

Assume the parameters g and p are agreed upon and known by all parties involved.

Q7.1  (3 points)  Bob has received the ciphertext C = (C1,C2 ) from Alice which was encrypted using

La Magle. Bob has access to the following magic functions and all magic functions have efficient runtimes.

• Discrete Log Oracle: A function DL(y), that when given any integer y, returns an integer x such that y ≡ gx mod p.

• Diffie-Hellman Oracle: A function DH(x,y), that when given any two integers of the form ga mod p and gb mod p, returns gab mod p.

• RSA Oracle: A function RSA(x), that when given a large value, N, factors it into prime numbers p and q.

Provide a decryption formula, D(C1,C2 ) for M in terms of C1 , C2 , b, g, p, and at most one of the above magic functions.

Q7.2  (4 points) Alice encrypts the plaintexts M1   and M2   and  sends them to Bob in the form C = (C1,C2 ) and C\ = (C,C). Bob wants to compute the sum of the plaintexts, but Bob is lazy and only willing to use the decryption function found above once.

Provide  a formula that Bob  could use to  get  M1  + M2   in terms  of C1,C2 ,C,C,  and the decryption function D(C1,C2 ). You may use the decryption function D(C1,C2 ) at most once in your formula. You cannot use Bob’s private key b in your formula.