Popa & 2019
Print your name:
CS 161 Computer Security
,
(last)
I am aware of the Berkeley Campus Code of Student Conduct and acknowledge that academic misconduct will be reported to the Center for Student Conduct and may further result in partial or complete loss of credit. I am also aware that in particular takes cheating personally and, like the Hulk®, you don’t want to see him angry.
Sign your name:
Print your SID:
Name of the person Name of the person sitting to your left: sitting to your right:
You may consult one double-sided, handwritten sheet of paper of notes. You may not consult other notes, textbooks, etc. Calculators, computers, and other electronic devices are not permitted.
Bubble every item completely! Avoid using checkmarks, Xs, writing answers on the side, etc.. If you want to unselect an option, erase it completely and clearly.
For questions with circular bubbles, you may select only one choice. Unselected option (completely unfilled)
Only one selected option (completely filled)
For questions with square checkboxes, you may select any number of choices (including none or all). You can select
multiple squares (completely filled).
If you think a question is ambiguous, please come up to the front of the exam room to the staff. If we agree that the question is ambiguous we will add clarifying assumptions to the central document projected in the exam rooms.
You have 110 minutes. There are 8 questions, of varying credit (96 points total). The questions are of varying difficulty, so avoid spending too long on any one question.
Do not turn this page until your instructor tells you to do so.
Midterm 1
(first)
Page 1 of 18
Grade distribution (out of 96 points):
Midterm 1 Page 2 of 18 CS 161 – Spring 2019
Problem 1 Potpourri Question (16 points)
(a)
(b)
(c)
(d)
(e)
(f)
(g)
True or False: Unlike CTR mode, CBC offers integrity against flipping bits of the ciphertext. True False
True or False: ASLR helps prevent buffer overflow attacks by randomizing the relative position of a buffer with respect to the overwritable return instruction pointer on the stack.
True False
True or False: ASLR helps prevent buffer overflow attacks by randomizing the relative order in which function stack frames are placed on the stack.
True False
True or False: It is possible to use the ret2esp attack from Project 1 when W^X is enabled. True False
TrueorFalse:SandboxingdifferentpartsofanapplicationcanhelpreducethesizeoftheTCB. True False
True or False: Symmetric key encryption is faster than asymmetric key encryption. True False
Let 𝑚 be a message, let 𝐸𝑘 be any IND-CPA encryption scheme and MAC𝑘 be any secure MAC function. Let 𝑘 be a randomly generated key. Write 𝐶 = 𝐸𝑘 (𝑚).
True or False: If an eavesdropper sees 𝐶 || MAC𝑘(𝐶), the message 𝑚 is still confidential. True False
Mallory is a man-in-the-middle attacker, but Alice and Bob want to send messages to each other without her interference. Which of the following properties alone is enough to ensure that Mallory can neither read nor tamper with any of their messages?
Solution: Bit flipping in CBC can cause different decryption result.
Solution: ASLR randomizes the start of different memory sections, but does not affect the order of each function’s stack frame.
Solution: As described, the ret2esp attack is not possible because the shellcode can only be placed on the stack. W^X/NX/DEP will prevent the shellcode from executing, so the attack will fail.
Midterm 1
Page 3 of 18 CS 161 – Spring 2019
(h)
Solution: Nope, reuses key 𝑘! It is incorrect in general to reuse a key for two different purposes, as discussed in the 2/19 and 2/21 lectures.
Midterm 1
Page 4 of 18
CS 161 – Spring 2019
Confidentiality Integrity
Authenticity Availability
Polytime Hardness None of the above
Solution: None of the properties alone are enough.
Problem 2 Greetings from Mallory (9 points) The following program has two security-critical vulnerabilities. Appendix: See the Appendix for a list of C functions.
1 2 3 4 5 6 7 8 9
10 11 12 13 14
void get_name(char ∗prompt, char ∗greeting) { printf (prompt) ;
intfd=0; //stdin
char ∗buf = greeting + strlen ( greeting ) ; // remaining buffer size_t count = sizeof(greeting) − strlen(greeting); // size left
read(fd, buf, count); }
int main() {
char prompt[] = “Please enter your name:\n”; char greeting [64] = “Welcome back , ” ;
get_name ( prompt , greeting ) ; printf ( greeting ) ;
}
Identify the two security-critical vulnerabilities in the code. For each vulnerability, provide the line num- ber and a short explanation. (Grading Note: You will receive six points if you find one vulnerability, and nine points if you find both vulnerabilities.)
(a) Vulnerability 1:
⋄ Line number: _______
⋄ Explanation: (20 words max)
(b) Vulnerability 2:
⋄ Line number: _______
⋄ Explanation: (20 words max)
Midterm 1
Page 5 of 18
CS 161 – Spring 2019
Solution:
• Vulnerability 1: Line 5
sizeof(greeting) evaluates to sizeof(char *), which is 4 and not 64, so count underflows and becomes a large unsigned number. The read operation can then overflow past the end of the greeting buffer.
This can be exploited by overwriting the saved return address of function main and hijacking the control-flow of the program.
• Vulnerability 2: Line 13
String format vulnerability, since contents of the greeting argument are controlled by the attacker, who can insert format modifiers %s, %n, etc.
A string format vulnerability is very dangerous and can actually allow arbitrary code execution through special use of %n and other formats.
• Another issue (partial credit):
Another issue with this program is that the greeting string is not guaranteed to be null terminated after the read operation. This allows the printf function on line 13 to read past the end of the greeting buffer. On this particular program, this is not security-critical, because after the greeting buffer it will find the prompt buffer, which is null terminated and doesn’t give any new information to the attacker.
Midterm 1 Page 6 of 18 CS 161 – Spring 2019
Problem 3 Prince of Security (8 points)
(a) Rather than using a password manager, you decide to hide your passwords under the directory old-tax-returns/old-things/not-secret/passwords, reasoning that it is secure because hackers won’t be able to find them. Which security principle does this violate?
Least privilege Consider human factors
Shannon’s maxim Know your threat model
(b) Atnight,youcannotenterEtcheverrywithoutspecialcardkeyaccess.Howeveryoucangetaround this by going to the second floor of Soda, and then using your cardkey to open the Etcheverry-Soda door on the second floor. Which security principle does this violate?
Ensure complete mediation Consider human factors
Shannon’s maxim Least privilege
(c) You enjoy CS 161 and decide to become the head TA! The front desk hands you physical keys: some access the printing room and some access a closet full of exam questions. You give away only the keys which access the printing room to the TAs in charge of printing discussion worksheets. Which security principle did you consider?
Ensure complete mediation Division of trust
Design in security from the start Least privilege
(d) In certain government agencies, employees are required to use government-approved phones for work. Some employees find these phones too difficult to use, so they do work on their personal phones instead. Which security principles does this violate?
Midterm 1
Page 7 of 18
CS 161 – Spring 2019
Ensure complete mediation Least privilege
Division of trust Consider human factors
Problem 4 AES-CBC-STAR (13 points) Let 𝐸𝑘 and 𝐷𝑘 be the AES block cipher in encryption and decryption mode, respectively.
(a) We invent a new encryption scheme called AES-CBC-STAR. A message 𝑀 is broken up into plaintext blocks 𝑀1, … , 𝑀𝑛 each of which is 128 bits. Our encryption procedure is:
𝐶0 = IV (generated randomly), 𝐶𝑖 =𝐸𝑘(𝐶𝑖−1⊕𝑀𝑖)⊕𝐶𝑖−1.
where ⊕ is bit-wise XOR.
⋄ Write the equation to decrypt 𝑀𝑖 in terms of the ciphertext blocks and the key 𝑘.
(b) Mark each of the properties below that AES-CBC-STAR satisfies. Assume that the plaintexts are 100 blocks long, and that 10 ≤ 𝑖 ≤ 20.
Solution: 𝑀𝑖 = 𝐷𝑘(𝐶𝑖 ⊕ 𝐶𝑖−1) ⊕ 𝐶𝑖−1.
Encryption is parallelizable.
Decryption is parallelizable.
If 𝐶𝑖 is lost, then 𝐶𝑖+1 can still be decrypted.
If we flip the least significant bit of 𝐶𝑖 , this always flips the least significant bit in 𝑃𝑖 of the decrypted plaintext.
If we flip a bit of 𝑀𝑖 and re-encrypt using the same IV, the encryption is the same except the corresponding bit of 𝐶𝑖 is flipped.
If 𝐶𝑖 is lost, then 𝐶𝑖−1 can still be decrypted. If 𝐶𝑖 is lost, then 𝐶𝑖+2 can still be decrypted. If 𝐶𝑖 is lost, then 𝐶𝑖−2 can still be decrypted.
If we flip the least significant bit of 𝐶𝑖 , this always flips the least significant bit in 𝑃𝑖+1 of the decrypted plaintext.
It is not necessary to pad plaintext to the blocksize of AES when encrypting with AES-CBC-STAR.
(c) Now we consider a modified version of AES-CBC-STAR, which we will call AES-CBC-STAR-STAR. Instead of generating the IV randomly, the challenger uses a list of random numbers which are public and known to the adversary. Let IV𝑖 be the IV which will be used to encrypt the 𝑖th message from the adversary.
⋄ Argue that the adversary can win the IND-CPA game.
Solution: Adversary sends two arbitrary (unequal but equal length), one-block messages (𝑀,𝑀′) as the challenge. The resulting ciphertext is either 𝐶0 = IV0||𝐸𝑘(IV0 ⊕ 𝑀) ⊕ IV0 or 𝐶0 =IV0||𝐸𝑘(IV0 ⊕𝑀′)⊕𝐼𝑉0.
Next the adversary sends IV1 ⊕ IV0 ⊕ 𝑀. The resulting ciphertext is 𝐶1 = IV1||𝐸𝑘(IV1 ⊕ (IV0 ⊕ IV1 ⊕ 𝑀)) ⊕ IV1, which simplifies to IV1||𝐸𝑘(IV0 ⊕ 𝑀) ⊕ IV1. If the second block of 𝐶1 ⊕ IV1 equals the second block of 𝐶0 ⊕IV0, then the challenger encrypted 𝑀. Otherwise the challenger encrypted 𝑀′. Hence we break IND-CPA with advantage significantly above 12 (in fact such an adversary wins all the time).
Midterm 1 Page 8 of 18 CS 161 – Spring 2019
An alternative solution is to send the challenger ciphertexts 𝑀 = IV1 and 𝑀′ = anything else. If the challenger encrypts 𝑀, the message received is 𝐸𝑘(0)⊕IV1. Then for the second message, send IV2. If the output ciphertext ⊕IV1 ⊕IV2 equals the challenge ciphertext, then the challenger encrypted 𝑀. Otherwise they encrypted 𝑀′.
Midterm 1 Page 9 of 18 CS 161 – Spring 2019
Problem 5 Extreme conditioning (9 points) Consider the following code:
1 2 3 4 5 6 7 8 9
10 11 12 13
int my_strcmp(char ∗s1 , char ∗s2) {
size_t i = 0; while (s1[i]) {
/∗∗ part b ∗∗/
if (s1[i] != s2[i]) { break ;
}
i ++; }
char uc1 = ∗s1, uc2 = ∗s2; if ( uc1 < uc2 ) return −1; return uc1 > uc2 ;
}
(a) Consider the preconditions necessary to ensure memory safety. What is required about null termination and length of the strings?
⋄ Write at most two preconditions, of at most ten words each.
(b) State one invariant at line 4 about s1 that is about memory safety. Do not include an invariant which is already a precondition.
⋄ Write this invariant.
Solution: (1) s1 must be null terminated
(2) The length of s1 also cannot be greater than the length of s2 or s2 must be null terminated, otherwise we would read past the end of s2.
Midterm 1
Page 10 of 18 CS 161 – Spring 2019
Solution: for all x in [0, i], s1[x] ! = ’\0’ OR 0 <= i < strlen(s1) [these two are equivalent]
Problem 6 Please, Just Use HMAC (8 points) Alice and Bob are partners struggling through their CS 161 project, and need to share code with one another, but their only option is to pass messages through an insecure server in Soda. They are afraid another student, Mallory, might read or tamper with the messages.
They have already established public-keys (𝑃𝐴 and 𝑃𝐵 ), secret keys (𝑆𝐴 and 𝑆𝐵 ) and two shared symmetric keys (𝑘 and 𝑘′). Using these, the SHA3 cryptographic hash function (SHA3), and an IND-CPA secure symmetric-key encryption (Enc𝑘), Alice proposes a set of ways to send her messages (𝑀) to Bob. Note that || denotes the concatenation operation.
(a) Mark which of her following proposals provide confidentiality and allow Bob to retrieve the message 𝑀 in the presence of only passive adversaries. (Select all that apply.)
𝑀 || SHA3(𝑀) SHA3(𝑀 || 𝑘′)
𝑀 || SHA3(𝑀 || 𝑃𝐵)
Enc𝑘(𝑀)
𝑀 || SHA3(𝑀 || 𝑆𝐴) Enc𝑘(𝑀) || SHA3(𝑀 || 𝑘′)
Solution:
Any protocol that provides the plaintext (M) in the clear does not provide confidentiality. Enc is an IND-CPA encryption function, as is by definition confidential.
Since cryptographic hash functions are deterministic, they do not provide confidentiality. In particular, an attacker can tell if the same message is sent twice.
(b) Mark which of her following proposals provide integrity. (Select all that apply.)
𝑀 || SHA3(𝑀) SHA3(𝑀 || 𝑘′)
𝑀 || SHA3(𝑀 || 𝑃𝐵)
Enc𝑘(𝑀)
𝑀 || SHA3(𝑀 || 𝑆𝐴) Enc𝑘(𝑀) || SHA3(𝑀 || 𝑘′)
Solution: Anyproposalthatdoesnotincludeanysecretinformationcannotprovideintegrity, since the entire ciphertext can be recomputed by the adversary Mallory. This includes proposals that use 𝑃𝐵, since this is a publicly-known key.
H(M || K) fails to provide integrity, since the original message is not recoverable (Bob cannot invert the cryptographic hash function). Bob does not have access to Alice’s secret key, and can never compute H(M || 𝑆𝐴) to verify that M was not tampered with.
Lastly, Enc𝐾 (M) fails to provide integrity even though Mallory doesn’t know K: she doesn’t have to create a valid encryption to tamper with the original. While tampered messages will likely decrypt to random bits, this is still often useful (i.e., Alice is sending a new random key).
Midterm 1
Page 11 of 18
CS 161 – Spring 2019
Problem 7 ElGamal and friends (15 points) Bob wants his pipes fixed and invites independent plumbers to send him bids for their services (i.e., the fees they charge). Alice is a plumber and wants to submit a bid to Bob. Alice and Bob want to preserve the confidentiality of Alice’s bid, but the communication channel between them is insecure. Therefore, they decide to use the ElGamal public key encryption scheme in order to communicate privately.
Instead of using the traditional version of the ElGamal scheme, Alice and Bob use the following variant. Asusual,Bob’sprivatekeyis𝑥andhispublickeyisPK=(𝑝,𝑔,h),whereh=𝑔𝑥 mod𝑝.However,tosend amessage𝑀toBob,Aliceencrypts𝑀asEncPK(𝑀)=(𝑠,𝑡),where𝑠=𝑔𝑟 mod𝑝and𝑡=𝑔𝑀×h𝑟 mod𝑝, for a randomly chosen 𝑟.
(a) Consider two distinct messages 𝑚1 and 𝑚2. Let EncPK(𝑚1) = (𝑠1, 𝑡1) and EncPK(𝑚2) = (𝑠2, 𝑡2). For the given variant of the ElGamal scheme, which of the following is true?
(𝑠1 + 𝑠2 mod 𝑝,
(𝑠1 × 𝑠2 mod 𝑝,
(𝑠1 × 𝑠2 mod 𝑝,
(𝑠1 + 𝑠2 mod 𝑝,
𝑡1 + 𝑡2 mod 𝑝) is a possible value for EncPK(𝑚1 + 𝑚2). 𝑡1 × 𝑡2 mod 𝑝) is a possible value for EncPK(𝑚1 + 𝑚2). 𝑡1 × 𝑡2 mod 𝑝) is a possible value for EncPK(𝑚1 × 𝑚2). 𝑡1 + 𝑡2 mod 𝑝) is a possible value for EncPK(𝑚1 × 𝑚2).
None of these
(b) In order to decrypt a ciphertext (𝑠, 𝑡), Bob starts by calculating 𝑞 = 𝑡𝑠−𝑥 mod 𝑝. Assume that the
message 𝑀 is between 0 and 1000. How can Bob recover 𝑀 from 𝑞?
(c) Explain why Bob cannot efficiently recover 𝑀 from 𝑞 if 𝑀 is randomly chosen such that 0 ≤ 𝑀 < 𝑝.
Solution: If Bob knows the possible set of messages, then he can pre-compute a lookup table forvaluesof𝑞=𝑔𝑀 mod𝑝.
Solution: Requires solving the discrete log mod𝑝, which is thought to be computationally hard.
Midterm 1 Page 12 of 18 CS 161 – Spring 2019
Midterm 1
Page 13 of 18 CS 161 – Spring 2019
(d) Suppose Alice sends Bob a bid 𝑀0 = 500, encrypted under Bob’s public key. We let 𝐶0 = (𝑠, 𝑡) be the ciphertext here.
Mallory is an active man-in-the-middle attacker who knows Alice’s bid is 𝑀0 = 500. Mallory wants to replace Alice’s bid with 𝑀1 = 999. To do that, Mallory intercepts 𝐶0 and replaces it with another ciphertext 𝐶1. Mallory wishes that when Bob decrypts 𝐶1, Bob sees 𝑀1 = 999.
Describe how Mallory creates 𝐶1 in each of the following situations:
1. Mallory didn’t obtain 𝐶0, but knows Bob’s public key PK = (𝑝, 𝑔, h).
⋄ Question: How should Mallory create 𝐶1?
2. MalloryknowsAlice’sciphertext𝐶0,butonlyknows𝑝and𝑔inBob’spublickeyPK=(𝑝,𝑔,h). (That is to say, Mallory does not know h.)
⋄ Question: How should Mallory create 𝐶1?
Solution: Mallorycansimplyencrypt𝑀ofherchoiceusingBob’spublickeyandreplace the ciphertext.
Solution: Mallory can create (𝑠′, 𝑡′) = (𝑠, 𝑡𝑔499) (mod 𝑝).
Problem 8 Canaries Schmanaries (18 points) The following code runs on a 32-bit x86 system. Stack canaries are enabled, but other memory safety defenses are disabled. As in Project 1, all four bytes of the canary are completely random.
The compiler does not rearrange stack variables. Note the volatile keyword on line 1: this means the arguments s1 and s2 are loaded from memory whenever referenced by doit, instead of being stored in registers. Appendix: See the Appendix for a list of C functions.
1 2 3 4 5 6 7 8 9
10 11 12 13
void doit(char∗ volatile s1, char∗ volatile s2) { char buffer [16];
strcpy ( buffer , s1 ) ; strcpy(s1, s2);
printf("%s\n%s\n%s\n", buffer , s1, s2); }
int main() {
char s1 [64]; char s2 [64];
fgets(s1, sizeof s1, stdin);
fgets(s2, sizeof s2, stdin);
doit(s1, s2); }
(a) Which line contains a memory safety vulnerability? What is the name of the vulnerability present on that line?
(b) Complete the diagram of the stack, right before line 3. Assume normal (non-malicious) program execution. You do not need to write the values on the stack, only the names. There are no extraneous boxes. As in discussion, the bottom of the page represents the lower addresses.
compiler padding = 0x00000000
main’s canary
char s1 [64]
char s2 [64]
s2
s1
saved eip / rip
saved ebp / sfp
doit’s canary
char buffer[16]
Midterm 1
Page 14 of 18
CS 161 – Spring 2019
Solution: Line 3: buffer overflow.
Midterm 1
Page 15 of 18 CS 161 – Spring 2019
(c) Now we will exploit the program. There is already shellcode at the address 0xbfffdead. Using gdb, you discovered that the address of main’s canary is 0xbfffdab4. Due to a bug in the compiler, you discover that although stack canaries are present, they are not checked! Complete the Python script below in order to successfully exploit the program.
Note: The Python syntax ’A’ * n indicates that the character ’A’ will be repeated n times. The syntax \xRS indicates a byte with hex value 0xRS.
s1 = ’A’ * ____ + ’_____________________________________________________’ + \
’_____________________________________________________’
s2 = ’B’ * ____ + ’_____________________________________________________’ + \
’_____________________________________________________’
print s1
print s2
Solution:
s1 = ’A’ * 24 + ’\xad\xde\xff\xbf’
s2 = ’anything’
Note that there is a slight technical nit, since fgets adds a newline and a terminating NUL character. This means that such a solution clobbers the address of s1. In practice this is unlikely to be an issue, although one can get around it by writing the original values into s1 and s2. We didn’t deduct points from solutions which failed to notice this issue.
(d) Unfortunately, the bug in the previous part was fixed, and now your exploit must successfully bypass the stack canary. As in part (c), there is already shellcode at the address 0xbfffdead and the address of main’s canary is 0xbfffdab4. Complete the Python script below in order to successfully exploit the program.
Hint: You should do the following. Start by using your exploit from the part above. Overwrite the arguments s1 and s2 of doit to ensure that the second strcpy will “fix” the canary. Note that the main’s function frame has the same canary as the canary that should appear in doit’s function frame. The use of the volatile keyword ensures that s1 and s2 are passed using their values from the stack. Since your solution should overwrite the pointer s2, it does not matter what it originally points to.
s1 = ’A’ * ____ + ’_____________________________________________________’ + \
’_____________________________________________________’ + \
’_____________________________________________________’
s2 = ’not needed, see the hint’
print s1
print s2
Solution:
s1 = ’A’ * 24 + ’\xad\xde\xff\xbf’+’\x20\xda\xff\xbf’+’\xb4\xda\xff\xbf’
s2 = ’not needed, see the hint’
print s1
print s2
Explanation: after the execution of the first strcpy on line 3, our stack looks as follows:
main’s canary
char s1[64]
char s2[64]
s2 = 0xbfffdab4
s1 = 0xbfffda20
saved eip = 0xbfffdead
saved ebp = AAAA
doit’s canary = AAAA
char buffer[16] = A...A
Even though the canary is messed up after the first strcpy, this does not cause the program to exit. Stack canaries are only checked before we exit the function.
Note that we have now overwritten the arguments to doit. We have engineered the stack such that s2 = &main’s canary and s1 = &doit’s canary. The next strcpy on line 4 therefore fixes doit’s canary. The compiler padding of all 0s is useful, because it acts as a NUL-terminator for the strcpy. It does clobber the last byte of the saved ebp, but that doesn’t matter since the shellcode will execute before this becomes a problem.
The exploit works with probability ≈ 63/64, since the canary might have a NUL byte, making it impossible to copy via strcpy.
Note that an optimizing compiler might save the value of s1 in a register in between the two strcpy calls, which would prevent this exploit, but the use of the volatile keyword prevents this.
Midterm 1
Page 16 of 18 CS 161 – Spring 2019
Selected C Manual Pages
char *fgets(char *s, int size, FILE *stream);
fgets() reads in at most one less than _size_ characters from
_stream_ and stores them into the buffer pointed to by _s_. Reading
stops after an EOF or a newline. If a newline is read, it is stored
into the buffer. A terminating null byte (’\0’) is stored after the
last character in the buffer.
int printf(const char *format, ...);
printf() produces output according to the format string _format_.
ssize_t read(int fd, void *buf, size_t count);
read() attempts to read up to _count_ bytes from file descriptor _fd_
into the buffer starting at _buf_.
char *strcpy(char *dest, const char *src);
The strcpy() function copies the string pointed to by _src_,
including the terminating null byte (’\0’), to the buffer pointed to
by _dest_.
size_t strlen(const char *s);
The strlen() function calculates the length of the string _s_,
excluding the terminating null byte (’\0’).
Midterm 1 Page 17 of 18 CS 161 – Spring 2019
Midterm 1 Page 18 of 18 CS 161 – Spring 2019