Popa CS 161 Spring 2018 Computer Security
Solutions updated May 2021 by CS161 SP21 course staff.
Print your name: , (last)
Final Exam
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.
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 three double-sided, handwritten sheet of paper of notes. You may not consult other notes or textbooks. Calculators, computers, and other electronic devices are not permitted.
Bubble every item completely. Avoid using checkmarks or Xs. 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 one or more choices. 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 TAs. If we agree that the question is ambiguous we will announce the clarification to everyone.
You have 170 minutes. There are 12 questions of varying credit (221 points total).
Do not turn this page until your instructor tells you to do so.
(first)
Page 1 of 30
SID:
Problem 1 True or False (40 points) Answer the following true or false questions.
(a) The Harvard Architecture separates the code and data of a program into two separate address spaces. This makes it impossible to treat data as code, or code as data. True or False: Buffer overflows are not exploitable on a Harvard Architecture.
True False
(b) True or False: Postconditions for a function are independent of implementation details of the function.
True False
(c) Consider the splitting problem: given a natural number n, find integers a and b such that ab = n and a,b > 1. (Note that a and b need not be prime.) True or False: If we had a polynomial time solution to the splitting problem, we could create a polynomial time solution for factoring into prime numbers.
True False
(d) Consider the function H : {0, 1}2b → {0, 1}b . H takes a 2b-bit string s, and splits it into two b-bit blocks k and x. It then computes Ek(x), where Ek is a secure block cipher encryption using b-bit blocks and keys. True or False: H is a one-way function.
True False
(e) True or False: If an arbitrary function is collision-resistant, then it is preimage resistant.
Solution:
False, as a buffer overflow could still overwrite local variables.
Solution:
True, the postcondition deals with the final result of the function, not about how the function gets there.
Solution:
True, since we can factor a number by splitting it once, and then splitting a and b. (There is some work associated to show that this is still polynomial time.)
Solution:
Let y be any arbitrary output. Then H(k′||Dk′ (y)) = y for any k′.
Final Exam
Page 2 of 30
CS 161 – Spring 2018
True
False
SID:
Solution:
Consider the identity function. Then the function is collision-resistant (there are no two inputs such that Id(x) = Id(y) with x ̸= y), but it is clearly not preimage resistant (given y, its inverse is simply y).
(f) True or False: If an arbitrary function is collision-resistant, then it is second preimage resistant. True False
(g) True or False: If it is possible, one way to prevent CSRF attacks is to use HTTP POST requests instead of HTTP GET requests, since this prevents an attacker from creating a request using an img tag.
True False
(h) True or False: If we do not use frames on our site, this prevents attackers from performing a clickjacking attack.
True False
(i) True or False: If you know the IP addresses, ports, TCP sequence numbers and TCP acknowl- edgement numbers in a TCP connection, you can inject TCP traffic.
Solution:
Say that we had a function f was not second preimage resistant. Then for any x we can find another preimage x ̸= x′ with f(x) = f(x′). Therefore f is not collision-resistant.
Final Exam
Page 3 of 30
CS 161 – Spring 2018
Solution: An attacker can still write Javascript to submit a POST request.
Solution: A clickjacking attack often involves when another site frames you.
True
False
Solution: TCP provides no authentication – this is all the information you need to spoof messages from either side.
SID:
(j) True or False: If we have two independent detectors, there is always a way to combine them such that the combined detector is more cost-effective than either detector alone. (Ignore the cost of the detectors.)
True False
Solution:
Intuitively: you don’t know which detector is right so you might not be able to combine them to be more effective.
As a pathological counterexample: say we have a detector that always triggers and another detector that never triggers. Say the cost of a false-positive is $100, and the cost of a false- negative is $100. Furthermore say that the base-rate of attacks is 0. The detector that never triggers is more cost-effective, since it costs $0. Any combination of it with the detector that always triggers must be less cost-effective.
(k) True or False: HTTPS provides security even against attackers on the local network. True False
(l) True or False: Even if you carefully inspect all URLs in the address bar to make sure they do not contain Javascript, you can still fall victim to a reflected XSS attack.
True False
(m) True or False: Disabling Javascript in your browser prevents clickjacking attacks completely. True False
(n) True or False: Disabling Javascript in your browser prevents CSRF attacks completely. True False
(o) True or False: If we hash the MAC of a message, this provides confidentiality.
Solution:
HTTPS provides end-to-end security.
Solution:
Example: you click an innocent URL, which contains a iframe with the reflected XSS as the source.
Solution: There are CSS-based clickjacking attacks. Also, browser-in-browser still works.
Solution:
False, a CSRF attack can be performed by simply including the URL in the src tag of an image, as shown in HW4.
Final Exam Page 4 of 30 CS 161 – Spring 2018
SID:
True False
(p) True or False: If we have a secure MAC, it is computationally difficult to find two keys k and k′, and a message m such that MACk (m) = MACk′ (m).
True False
(q) True or False: Prepared statements are a possible defense for SQL injection attacks. True False
(r) True or False: DNSSEC and TLS combined prevents eavesdroppers from seeing what sites we are visiting.
True False
(s) True or False: ARP spoofing requires that the attacker has two devices on the network: one to send requests and the other to give fake answers.
True False
(t) True or False: Whitelist approaches are often more effective than blacklists in preventing injection attacks.
Solution:
False, as neither MACs nor hashes are designed for confidentiality. (As a simple example: both are deterministic and so sending the same message twice leaks.)
Solution:
False, this is not a property that MACs aim to provide. In fact we can define a patholog- ical MAC which does not have this property. For example, consider NEW-MAC0||k(m) = NEW-MAC1||k = HMACk(m). Then this MAC is secure (in the unforgeability sense), but the given statement is false.
Final Exam
Page 5 of 30
CS 161 – Spring 2018
Solution: This is the main purpose of prepared statements (in addition to improved efficiency).
Solution: False, DNSSEC does not provide confidentiality.
Solution: False, they only need one to give fake answers.
True
False
Solution: Whitelisting is less error-prone.
SID:
Problem 2 Party, No Theme (35 points) Answer the following questions about various course topics.
(a) (6 points) You have discovered a vulnerability in Snapitterbook which lets you create malicious posts. Whenever someone visits your Snapitterbook page, the evil post sends a request to the Snapitterbook webserver which causes the visitor to post a copy of the evil post to their own wall. Now their wall is also infected!
i. Which of the following concepts are relevant to this situation? CSRF Reflected XSS
Virus Clickjacking Worm SQL Injection XSS
ii. Which of the following technologies could help fix or detect the situation above?
Solution:
This is a worm (similar to the MySpace Sammy Worm) since it propogates by copying itself to another target. It is also a stored XSS, as that is the exploit it uses to make evil requests.
Note that this is not a CSRF: the origin is the same as the referring site.
A strict X-Frame-Options
Input escaping
A strict Content-Security-Policy Prepared Statements
Anomaly-based detection Referer checking
CSRF Tokens
HTTPS
Solution:
Input escaping is an easy fix: if inputs were escaped then XSS could not occur.
A strong CSP would prevent inline and foreign scripts, preventing XSS from executing.
Anomaly-based detection could help detect this problem through the large volume of posts, or through the anomalous referers of HTTP requests to the post endpoint.
(b) (3 points) You are considering buying three detector solutions, with the following statistics: 1. Detector X: False positive rate 5%; False negative rate 2%
2. Detector Y: False positive rate 1%; False negative rate 5%
3. Detector Z: False positive rate 2%; False negative rate 1%
A false positive costs $50, while a false negative costs $100.
Answer the following questions which attempt to compare the cost effectiveness of each detector.
If the detectors are equally effective, either choice will be accepted. i. Compare X and Y .
Final Exam
Page 6 of 30 CS 161 – Spring 2018
SID:
X is better (or equal)
ii. Compare Y and Z.
Y is better (or equal)
iii. Compare X and Z.
X is better (or equal)
Y is better (or equal)
Z is better (or equal)
Z is better (or equal)
Cannot say
Cannot say
Cannot say
Solution:
This is the base rate fallacy: without knowing how often attacks occur, you cannot deter- mine which detector is better. The exception is X vs. Z, since Z has a lower false positive and false negative rate, it must be more effective.
(c) (3 points) What security principle explains why using proof of work to prevent email spam might work?
(d) (3 points) A company decides to implement a complicated password policy for its employees. What security principle explains why the overall security of the system might go down?
(e) (3 points) For RSA signatures as discussed in lecture, why is verification faster than signing?
(f) (5 points) Bob allegedly posted a rude statement about Alice on https://bob.com/alice-sux. Alice decides to take Bob to court! As proof that the Bob’s site had the statement at some point in time, Alice presents the entire HTTPS dialogue between her and the site. She also provides all the keys derived through the process. Should the judge be convinced? Explain your answer in 2–3 sentences.
Ignore the possibility that an attacker has compromised bob.com or Bob’s private keys. Assume bob.com uses RSA TLS and has a certificate signed by a trusted certificate authority.
Judge should be convinced Judge should not be convinced Explain:
(g) (3 points) Which of the following attacks require an attacker to be on the same local network as their target?
Solution: Security is economics: a spammer who has to spend money (as proof of work) in order to send spam is less incentivized to send spam.
Solution: Consider human factors: people will often write their passwords on post-it notes if they are too complicated.
Solution: Verification requires raising to the 3rd power, can be done fast (O(1) multiplica- tions). Signing requires raise to the d, which is bigger than 3 and therefore slower (O(log d) = O(logN) multiplications).
Solution:
After Alice and Bob agree on a PS, both sides derive the TLS symmetric keys Ib,Is,Cb,Cs. This means that Alice can easily forge messages which appear to come from Bob.
Final Exam Page 7 of 30 CS 161 – Spring 2018
SID:
TCP Injection ARP Spoofing DNS Spoofing
DHCP Spoofing Reflected XSS Stored XSS
Solution:
Both ARP and DHCP spoofing require that the attacker is on the same local network, since neither protocol actually leaves the local network.
(h) (3 points) Which property of the hash function does the hash chain in Bitcoin rely on? List one property alone.
(i) (3 points) Which of the following defenses are typically implemented using the compiler?
Solution: Collision resistance: must prevent attackers from creating two blocks with the same hash.
Position-Independent Executables NX bit
ASLR
Stack Canaries
Solution:
PIE requires the compiler to output position-independent code which can execute in any loca- tion in memory.
Stack canaries are added by the compiler: it emits code to check that the canary does not change before leaving the function.
ASLR is implemented at the OS level, the NX bit is either implemented at the OS level or the hardware level.
(j) (3 points) Alice receives the following email:
From: Mallory < >
To: Alice < >
Hey Alice,
Your boss, Steven, wanted me to send you this link to those expense
reports for the Fall 2016 Quarter. He said that you would look at
them and give Evelyn the tax estimate she asked for earlier.
What attack does this represent? (Be as specific as possible!)
Solution: Spearphishing: the attack contains specific information about Alice, but the site rsa.com.evil.org is trying to steal her login information. (Significant partial credit for phish- ing or social engineering.)
Final Exam Page 8 of 30 CS 161 – Spring 2018
SID:
Problem 3 D ́ej`a Vu (16 points) The code below runs on a 32-bit Intel architecture. ASLR is enabled. There are no stack canaries, no position-independent executables and no NX bit. No padding is added by the compiler.
1 2 3 4 5 6 7 8 9
10 11
1 2 3 4 5 6
char *gets(char *s) { /* simple implementation of gets */ char *s_ = s;
while ((*s_++ = getchar()) != ’\n’); s_[-1] = ’\0’;
return s;
deja_vu () { char door [16]; gets(door);
}
} void
(a) What sort of exploit technique works by chaining execution of small blocks of code (“gadgets”)?
(b) After disassembling the code, you find the following gadgets.
Solution: Return-oriented programming
Gadget 1:
0x080484a2 <+30>: sub 0x080484a5 <+33>: ret
Gadget 2:
0x080484fc <+30>: add 0x080484ff <+33>: ret
$0x14 ,%esp $0x14 ,%esp
Which of the above gadgets was most likely generated intentionally by the compiler? Gadget 1 Gadget 2
Solution: Recall that the stack grows towards down towards lower memory addresses, so decrementing the esp register is “extending” the stack while adding to the esp register is “popping” from the stack.
Gadget 1 shows a 20 byte allocation on the stack (extending the stack down) directly before returning from a function.
Gadget 2 shows a 20 byte deallocation from the stack (popping from the stack) directly before returning from a function.
When we return from a function, we want to deallocate the memory of that frame, not add more memory to the stack. Thus Gadget 2 seems more likely to have been generated intentionally by the compiler.
(c) On some older Intel processors, a single instruction could halt the entire system. The machine code for one such instruction is \xf0\x0f\xc7\xc8. Give an input which will cause the execution of this shellcode. Hint: We pushed &door onto the stack in order to call gets. This forms a “perfect pointer” for shellcode. Knowing that, how can you make the program start executing door?
Final Exam Page 9 of 30 CS 161 – Spring 2018
SID:
Solution: Short solution:
Earlier, we pushed &door onto the stack for the call to gets. We juggle %esp so that it points to &door right before a ret.
More detailed solution:
[4] rip of deja_vu
[4] sfp of deja_vu
[16] door
[4] char *s = &door
[4] rip of gets
[4] sfp of gets
[4] char * s_
The idea is to overwrite the 24 bytes comprising door, sfp, and rip. Since we have &door on the stack, we need to get esp to point to that address and have call ret after that. This means that the first 4 bytes of door must be the F00F instruction address.
Now note that we have the gadget that subtracts 20 bytes from esp and calls ret. However, &door and rip of main are 24 bytes apart, so we will need to call this gadget twice. If we put the address of the gadget in the top rip, that will get us to door + 4, which isn’t enough. However, if we put another gadget here, that will get us to s , which is too far. Thus, we ret twice to get to door + 12, and then we put the address of the gadget there again. Now, when the esp – 20 is performed, it points to &door, and the ret will execute the instruction at door.
Extremely detailed solution:
Start by drawing a stack diagram:
[4] rip of deja_vu
[4] sfp of deja_vu
[4] door4
[4] door3
[4] door2
[4] door1
[4] char *s = &door
[4] rip of gets
[4] sfp of gets
[4] char * s_
Note that we wrote the 16-byte buffer door as 4 labeled rows of 4 bytes each. This is just for clarity in later parts of the exploit.
Note that the value below the door buffer, char *s = &door, is the argument to gets. (Recall that arguments of a function are pushed onto the stack before that function’s rip and sfp.)
If ASLR wasn’t in use, we could simply start writing at door and overwrite the rip with the address of our shellcode. However, because ASLR randomizes absolute addresses each time the program is run, we won’t know what address to overwrite the rip with.
As the hint notes, &door on the stack is a perfect pointer. This means that no matter how ASLR shuffles the addresses each time the program is run, this value on the stack will always contain the correct address of the door buffer. Thus we want to force the program to treat &door as the rip, because this would cause instructions to be executed starting at door every time. Also note that the gets function writes our input to door every time, so if we can force the program to reliably execute instructions at door, we have defeated ASLR.
Final Exam Page 10 of 30 CS 161 – Spring 2018
SID:
Now our goal is to make the program believe that &door is an rip. To do this, we have to make use of the gadgets from the previous question. Note that the gadgets can be used in two ways: if we start executing instructions at 0x080484a2, the program will subtract 14 from the esp register and then execute ret. If we start executing instructions at 0x080484a5, the program will just execute ret. A similar idea works for Gadget 2. In both cases, note that position-independent executables are not enabled, so the address of the gadget instructions (in the code section) will not change.
A quick refresher on the ret instruction: it is effectively equivalent to pop %eip. In other words, it takes the next value on the stack, places it in the eip register, and then increments esp by 4 to delete the value off the stack. The eip register is the program counter, so this can also be thought of taking the next value on the stack, treating it as an address, and jumping program execution to that address. In other words, we are treating the next value on the stack as an rip and executing the instructions at the rip.
If we want the program to treat &door as an rip, we should force the esp to point at &door, and then execute a ret instruction. This will cause &door to be treated as an rip, and instructions at door to be executed.
After the rip of deja vu is popped off the stack, the esp is pointing 4 bytes above the rip of deja vu. This is above &door, which is where we want esp to point. Thus we want to decrement esp and move it further down the stack. We can achieve this by overwriting the rip with the address of the sub $0x14, %esp instruction:
[4] rip of deja_vu
[4] sfp of deja_vu
[4] door4
[4] door3
[4] door2
[4] door1
[4] char *s = &door
[4] rip of gets
[4] sfp of gets
[4] char * s_
0x080484a2 (sub, ret)
Now, when the deja vu function exits, it will start executing instructions at 0x080484a2. This means the program will decrement esp by 0x14 = 20 bytes to door2, then execute a ret instruction. The ret instruction treats door2 as an rip and executes instructions there.
After this ret instruction, esp is at door3. We could try decrementing esp again, but since we can only decrement esp in multiples of 20 bytes, that would cause the esp to move too far below &door. Alternatively, we could try to increment esp in multiples of 4 bytes, using the ret instruction. (Recall that the ret instruction causes esp to move up by 4 bytes.)
Since decrementing esp now would take us too far below &door, our strategy is to increment esp a little bit, and then once it’s in the right location, decrement esp to force it to point exactly at &door. This technique is known as stack juggling.
Let’s try to stack juggle esp into the right place. The last ret instruction caused instructions at door2 to execute, so we should put a ret instruction here to increment esp.
Final Exam Page 11 of 30 CS 161 – Spring 2018
SID:
[4] rip of deja_vu
[4] sfp of deja_vu
[4] door4
[4] door3
[4] door2
[4] door1
[4] char *s = &door
[4] rip of gets
[4] sfp of gets
[4] char * s_
0x080484a2 (sub, ret)
0x080484a5 (ret)
When this ret instruction gets executed, it will increment esp by 4 bytes to door4 (esp was at door3 after the previous ret). This ret will treat the value at door3 as an rip, and start executing instructions at the address stored in door3.
Decrementing esp by 20 bytes from door4 would still take us below &door, so we need to insert another ret instruction at door3 to increment esp one more time.
[4] rip of deja_vu
[4] sfp of deja_vu
[4] door4
[4] door3
[4] door2
[4] door1
[4] char *s = &door
[4] rip of gets
[4] sfp of gets
[4] char * s_
0x080484a2 (sub, ret)
0x080484a5 (ret)
0x080484a5 (ret)
As a result of this ret instruction, esp will be at the sfp of deja vu, and the program will treat door4 as an rip.
Decrementing esp by 20 bytes from the sfp of deja vu will make it point exactly at &door, so we are done with stack juggling! We insert the instruction to subtract 20 from esp at door4. The subtraction will cause esp to point at &door, and the ret will cause &door to be treated as an rip.
[4] rip of deja_vu
[4] sfp of deja_vu
[4] door4
[4] door3
[4] door2
[4] door1
[4] char *s = &door
[4] rip of gets
[4] sfp of gets
[4] char * s_
0x080484a2 (sub, ret)
0x080484a2 (sub, ret)
0x080484a5 (ret)
0x080484a5 (ret)
Since &door is treated as an rip, this exploit will cause instructions at door to execute. So we put our 4-byte shellcode at the start of door.
Finally, we fill in the sfp of deja vu with garbage, since it wasn’t needed in the exploit. Our final exploit looks like this:
Final Exam Page 12 of 30 CS 161 – Spring 2018
SID:
[4] rip of deja_vu
[4] sfp of deja_vu
[4] door4
[4] door3
[4] door2
[4] door1
[4] char *s = &door
[4] rip of gets
[4] sfp of gets
[4] char * s_
0x080484a2 (sub, ret)
garbage
0x080484a2 (sub, ret)
0x080484a5 (ret)
0x080484a5 (ret)
shellcode
Our final input looks like this:
• Shellcode: \xf0\x0f\xc7\xc8
• ret: \xa5\x84\x04\x08
• ret: \xa5\x84\x04\x08
• subtract 20 from esp, ret: \xa2\x84\x04\x08 • padding to overwrite sfp: AAAA
• subtract 20 from esp, ret: \xa2\x84\x04\x08
Other solutions exist.
Final Exam Page 13 of 30 CS 161 – Spring 2018
SID:
Problem 4 Mystery Matrix Math (15 points) Consider the following code which performs a mystery operation on the input matrix.
1 2 3 4 5 6 7
void mystery(int **A, size_t m, size_t n) { for (size_t i = 0; i < m; i++) {
for (size_t j = 0; j < n; j++) { A[i][j] = A[j][i];
} }
}
Assume that m and n are both non-zero. Ignore the possibility of negative indices.
(a) For each of the subparts below, mark necessary preconditions for mystery to be memory-safe.
i. A ̸= NULL size(A) > m
size(A) ≥ m
ii. m̸=i,n̸=j i
i, j < max(m, n) 0 ≤ i, j
∀i∀j:i
Here is a GIF of puppies
