Fall 2018
CS 161 Computer Security
Midterm 1
Print your name: , (last)
(first)
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.
Sign your name:
Print your class account login: cs161-
Name of the person sitting to your left:
and SID:
Name of the person sitting to your right:
You may consult one sheet of paper of notes. You may not consult other notes, textbooks, etc. Calculators, computers, and other electronic devices are not permitted. We use Gradescope for grading so please write your answers in the space provided.
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 11 questions, of varying credit (134 points total). The questions are of varying difficulty, so avoid spending too long on any one question.
Some of the test may include interesting technical asides as footnotes. You are not responsible for reading the footnotes.
Do not turn this page until your instructor tells you to do so.
Page 1 of 14
Problem 1 Cryptography True/False (18 points) Answer the following cryptography questions true or false.
(a) Let Ek be a secure block cipher. True or False: It is impossible to find two messages m and m′ such that m ̸= m′ and Ek(m) = Ek(m′), even if the attacker knows k.
True False
(b) Let Ek be a secure block cipher. True or False: It is computationally difficult to find two pairs
(m,k) and (m′,k′) such that m ̸= m′, k ̸= k′ and Ek(m) = Ek′(m′). True False
(c) Let MACk be a secure MAC. True or False: It is computationally difficult to find messages m and m′ such that m ̸= m′ and MACk(m) = MACk(m′), even if the attacker knows k.
True False
(d) Let H be a cryptographic hash function. True or False: H(M) provides confidentiality for the
message M.
True False
(e) HMAC-DRBG does not have rollback resistance.
True False
(f) Diffie/Hellman is secure in the presence of an active adversary.
True False
(g) Properly constructed RSA Signatures provide both integrity and authenticity.
True False
(h) encryption provides confidentiality but it does not provide integrity or authentication.
True False
(i) In examining a certificate we need to consider how we obtained the certificate as well as the certifi- cate’s contents and signatures.
Midterm 1
Page 2 of 14
CS 161 – Fa 18
True
False
Problem 2 Potpourri (18 points)
(a) Instead of storing user input on the stack, you decide to create a new section of memory (separate from code, static, heap, and stack) for storing user input. You also put a 64-bit canary at the top (largest memory address) of the section. Name one memory-safety vulnerability that this prevents.
(b) Name one memory-safety issue that the scheme from part (a) fails to prevent.
(c) True or False: In a threat detection systems, false negatives can be catastrophic, but false positives are always harmless.
True False
(d) Which of the following are recommended ways to protect a password database? (Select all that apply.)
Salting Passwords Using a Fast Hashing Function
Encrypting Passwords Using a Slow Hashing Function
(e) A heap overflow or use-after-free vulnerability can allow the attacker to overwrite the vtable pointer of an object (that is, the pointer at the start of a C++ object that points to the actual methods for the function, basically a pointer to an array of function pointers). Can this bypass stack canaries without additional information?
Midterm 1
Page 3 of 14
CS 161 – Fa 18
Yes
(f) At what rank did retire?
Rear Admiral
No
Captain
Brigadier General
(g) Alice generates a MAC on her homework answers that she stores with her homework answers in a secret remote server. When she needs to submit her homework, she uses the MAC to check that her answers have not been tampered with. Only she has the key needed to generate the MAC. Which of the following apply in this scenario?
Integrity and Confidentiality Integrity and Authentication
Authentication and Confidentiality Only Integrity
Midterm 1
Page 4 of 14
CS 161 – Fa 18
(h) Which of the following attacks can be used against a crypto system? (Select all that apply.)
Side-Channel Rolling-regression Chosen-plaintext
(i) ”Crypto” means: Cryptography
Cryptocurrency
(j) The Magic Word is:
Chosen-ciphertext Rubber-Hose Cryptanalysis
Kitties
Stupify Crucio
Problem 3 Security Principles (12 points) Write the best match for which security principle each situation.
Four CS 161 students, Chiyo, Habiba, Mr. Anderson, and Not Outis, decided that after learning about security principles and buffer overflows, they could implement their own distributed database (a database across multiple machines) with a focus on security!
(a) Mr. Anderson suggests code their database in a higher-level programming language since they could avoid common security problems later on. Which security principle did he to use here?
(b) Let’s say they start coding their database and realized that a malicious user on one machine could corrupt their database. As a result, Habiba wants permission from at least 50% database users before a machine can be taken down. Which security principle is she using here?
(c) The database the students built was password-protected for modification and they use a snippet (like the following) everywhere to check passwords:
String password = getPassword(“user”);
if (!password.equals(enteredPassword)) error();
Not Outis eventually forgets to put this snippet to check the passwords. What security principle does this violate?
(d) To encrypt the data, Not Outis decides to take each piece of data and rotate the bytes in it by a fixed amount. It figured that since their database was closed source, no one would figure out how they were encrypting things. What security principle does this violate?
(e) Mr. Anderson decides that new users should automatically get privileged access in order to set up their account to access whatever items they needed. After 1 hour, they would be dropped back to regular permissions, an administrator would be notified of changes, and they could revert changes if necessary. What security principle says this is not a good idea?
(f) After fixing all previous problems, Chiyo decides to refactor their encryption code into its own module since a lot of it was spread across multiple modules. She also put all non-encryption code in a sandbox so that no vulnerabilities in those modules could effect the overall security of the database. What security principle is she trying to follow? What is she trying to minimize the size of?
Midterm 1 Page 5 of 14 CS 161 – Fa 18
Problem 4 Go With The Control Flow (14 points) The code below runs on a 32-bit Intel architecture. No defenses against buffer overflows are enabled. The code was not compiled to produce a position independent executable. No optimizations are enabled, and the compiler does not insert padding or reorder stack variables, which means buffer is at a lower address than fp.
1 2 3 4 5 6 7 8 9
10 11 12 13
int run command(char ∗cmd) { return system (cmd) ;
}
int print hello (char ∗msg) {
printf(”Hello %s!\n”, msg); return 0 ;
}
int main() {
int (∗fp)(char ∗) =&print hello; char buffer [8];
gets ( buffer ) ;
fp ( buffer ) ;
}
Note that the syntax int (*fp)(char *) indicates that fp is a pointer to a function which takes in a char * and returns an int.
(a) What line contains a memory vulnerability? What is this vulnerability called?
(b) At line 12, we have that %ebp = 0xbfdead20 and &print hello = 0x08cafe13. Fill in the Python egg below to give an input which will overwrite the return address of main, causing the exe- cution of the shellcode after the program returns from main.
print ’A’ * + ’ ’ + ’AAAA’ + ’ ’ + SHELLCODE
(c) Which of the following would sometimes or always prevent the code that you gave in part (b) from working? (Select all that apply.)
ASLR (same as part 5 on the project) Selfrando
WˆX Using a memory-safe language instead of C
(d) “I know,” says , “let’s add stack canaries to make this impossible to exploit!” Obvi- ously this doesn’t work. Fill in the Python egg below to give an input which will cause the execution of run command(“/bin/sh”). At line 12, we have that %ebp = 0xbfdead20 and &run command = 0x08c0de42. Hint: Note that gets can read in a NUL byte (\x00), even in the middle of its input.
print ’ ’
(e) Which of the following would sometimes or always prevent the code that you gave in part (d) from working? (Select all that apply.)
Midterm 1
Page 6 of 14
CS 161 – Fa 18
ASLR (same as part 5 on the project) WˆX
Selfrando
Using a memory-safe language instead of C
Problem 5 ’s Preconditions (8 points) did not do a good job at coming up with a set of preconditions for some functions. For each code block, explain why with a short example the given preconditions are not sufficient to ensure memory safety by giving a small example.
(a) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/∗ array of strings != NULL
n <= size(array of strings) max size > 0
for all i . 0 <= i < n ==>
array of strings [ i ] != NULL and is a NUL−terminated string ∗/
char ∗
concat all(char ∗array of strings [] , size t n, size t max size) {
char ∗concat = calloc(max size , sizeof(char)); if (!concat) return NULL;
size t space used = 0;
for (size t i = 0; i < n; i++) {
char ∗s = array of strings [ i ];
size t len = strlen(s);
strncpy(concat + space used, s, max size − space used − 1); space used += len ;
}
return concat ; }
(b) 1 2 3 4 5 6 7 8 9 10 11
Explanation:
/∗ arr != NULL
n <= size(arr)
for all i . 0 <= i < n ==> 0 <= arr[i] < n ∗/ int solve interview question(int ∗arr, size t n) {
for (size t i = 0; i < n; i++)
arr[arr[i]] ∗= −1;
for (size t i = 0; i < n; i++)
if (arr[i] < 0) return i ;
return 0 ; }
Midterm 1
Page 7 of 14
CS 161 – Fa 18
Explanation:
Problem 6 Greetings Professor Falken! (9 points) Consider the code below.
1
2
3
4 exit (1) ; 5}
6
7 #define MAX INPUT 8
8 int main() {
9 char ∗correct password = malloc(MAXINPUT ∗ sizeof(char));
10
11
12
13
14
15
16
17
18
19
20
void launch nuclear missiles () { puts(”Launching the nukes...”);
/∗ code to launch nuclear missiles here ∗/
strcpy ( correct password , ”S3creT\n”) ; while (!feof(stdin)) {
char ∗user password = malloc(MAXINPUT ∗ sizeof(char)); fgets(user password , MAXINPUT, stdin);
if (strcmp(user password , correct password) == 0)
launch nuclear missiles () ;
} }
free(user password);
free(correct password);
puts(”Wrong password, try again!”);
All compiler optimizations are disabled, and both the source and binary are not available to , who’s trying to log in to play a game. Consider the following (buggy) interaction:
1. David inputs “Hello” followed by a newline.
2. The program outputs “Wrong password, try again!”.
3. David inputs “Joshua” followed by a newline.
4. The program outputs “Launching the nukes...”, and then the nukes are launched.1
(a) Which memory safety vulnerability is present in this code?
(b) Explain why this issue leads to the behavior David observes.
(c) How could you fix this issue in the code?
1This immediately vaporizing millions of humans and wildlife on impact, beginning World War III and eventually wip- ing out most of the world due to an extended nuclear winter. This is why you don’t hack into systems without per- mission. If you want to understand more how nuclear command, control, and decision making works, the two books to read are Command and Control: Nuclear Weapons, the Damascus Accident, and the Illusion of Safety by , and The 2020 Commission Report on the North Korean Nuclear Attacks Against the United States (A Speculative Novel) by Jef- frey Lewis.
Midterm 1 Page 8 of 14 CS 161 – Fa 18
Problem 7 Fail Caesar (12 points) A student at a well known decided to write their own after learning about them in their computer security class. Unfortunately for the student, they fell asleep during the lecture on memory safety. (Note: The atoi() function converts the initial portion of the string to an integer, returning 0 in case of an error.)
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include
void encrypt(int offset , char plaintext []) { char ciphertext [64];
memset( ciphertext , int i=0;
0 ,
64) ;
fgets(plaintext , 64, stdin); while (plaintext[i]){
ciphertext [ i ] = plaintext [ i ] + offset ;
i ++;
}
printf(ciphertext);
}
int main(int argc, char ∗argv[]){ char buffer [64];
int offset = 0;
if (argc > 1) offset = atoi(argv[1]) % 26;
while (!feof(stdin)){ memset(buffer , 0, 64); encrypt(offset , buffer);
}
return 0 ; }
(a)
(b)
(c)
(d)
What line contains a memory vulnerability? What is this vulnerability called?
Give a file that, when input to the command failcaesar with no arguments, will cause the program to crash.
How would you change the line to fix the vulnerability?
The student’s friend who was awake for the memory safety lecture tells them to enable stack canaries to make their code more secure. If an attacker does not have time to perform a bruteforce attack, does enabling stack canaries prevent this code from being exploited? Explain why or why not.
Midterm 1 Page 9 of 14 CS 161 – Fa 18
Problem 8 A Lack of Integrity… (9 points) Alice and Bob want to communicate. They have preshared a symmetric key k. In order to send a message M to Bob, Alice encrypts it using AES-CBC, and sends the encryption to Bob. (You may assume that M’s length is divisible by the AES-CBC block length and that characters are 8 bits, so no padding is necessary.) Recall that the actual message sent is IV ||E(M), that is, the IV is prepended to the message and sent all as a single stream of bytes. Alice uses a random IV for each message.
In order to make sure that Bob is listening, they agree to using pingback messages. If Alice sends a message whose plaintext begins with the two bytes “PB”, then Bob sends back the rest of the message in plaintext. For example, if Alice sends AES-CBCk(“PBI Love CS 161!”), then Bob responds “I Love CS 161!” without any encryption.
Alice uses the protocol to communicate some message M to Bob. Assume M is not a pingback message. Mallory, a man-in-the-middle attacker, decides to attempt to trick Bob into generating a pingback message. She thus sends the message IV ′||IV ||E(M), where IV ′ is a random 128b string.
(a) With what probability will Mallory’s message trigger a pingback message?
(b) If Mallory’s message triggers a pingback message, what does Mallory receive?
(c) How can Alice and Bob change their protocol to prevent this attack?
Midterm 1 Page 10 of 14 CS 161 – Fa 18
Problem 9 Screwups in Inserting an IV (15 points) Alice encrypts two messages, M1 and M2 using the same IV/nonce and a deterministic padding scheme (when appropriate for the particular mode) using AES (a 128b block cipher). Eve, the Eavesdropper, knows the plaintext of M1, that each block of M1 is different, that M1 is 120 bytes, and that Alice never sends any bytes she doesn’t have to. Unbeknownst to Eve, it turns out that the messages differ only in the 21st byte of the two messages but are otherwise identical.
Yes, Alice screwed up. But how badly? For each possibility, select all which apply.
(a) If Alice used AES-ECB (Electronic Code Book), Eve is able to determine which of the following
Midterm 1
Page 11 of 14
CS 161 – Fa 18
about M2:
That M2 is exactly 120B long
The entire plaintext for M2
The entire plaintext for M2 except for the
2nd block
(b) If Alice used AES-CTR (Counter), Eve is able to determine which of the following about M2:
That M2 is exactly 120B long The entire plaintext for M2
The entire plaintext for M2 except for the 2nd block
That M2 is less than 129B long but not the exact length
The plaintext for only the first two blocks of
M2
The plaintext for only the first block of M2 (c) If Alice used AES-CBC (Cipher Block Chaining), Eve is able to determine which of the following
about M2:
That M2 is exactly 120B long
The entire plaintext for M2
The entire plaintext for M2 except for the
2nd block
(d) If Alice used AES-CFB (Ciphertext Feedback), Eve is able to determine which of the following
about M2:
That M2 is exactly 120B long
The entire plaintext for M2
The entire plaintext for M2 except for the
The plaintext for only the first block of M2 (e) If Alice did not screw up, which modes allow Eve to determine the exact length of a third message
2nd block
M3 that is completely different from M1 and M2. AES-ECB
AES-CTR
AES-CBC AES-CFB
That M2 is less than 129B long but not the exact length
The plaintext for only the first two blocks of
M2
The plaintext for only the first block of M2
That M2 is less than 129B long but not the exact length
The plaintext for only the first two blocks of
M2
The plaintext for only the first block of M2
That M2 is less than 129B long but not the exact length
The plaintext for only the first two blocks of
M2
Problem 10 No More Keys (7 points) Frustrated by your newfound love of encryption schemes, your partner decides to throw away all of your secret keys. As a student in CS 161, you decide to make the best of a bad situation. You decide to design your own encryption scheme!
Midterm 1
Page 12 of 14
CS 161 – Fa 18
(a) Design the Decryption scheme.
(b) This is IND-CPA:
True
(c) The encryption is parallelizeable:
True
(d) The decryption is parallelizeable:
True
False
False
False
Problem 11 Like Water off a DUHK’s Back (12 points) The ANSI X9.17/X9.31 is a fairly simple pRNG that was widely used based on a block cipher (commonly AES). The internal state V and key K are combined with the current time T to update the state and produce a ”random” value.
The current time is measured in microseconds as that is what the common operating system routines return. This is a strong pRNG as long as the initial state V0 and the key K are both high entropy and secret, and the block cipher is secure.
Unfortunately this scheme can fail badly when common mistakes are made. The standard never specified how to select K. So some implementations, rather than using a high-entropy source to seed a secret K, used a hardcoded key. The result is a catastrophic failure2.
(a) If the attacker exactly knows K, T1, and R1, the attacker can then recover V0. How?
(b) Since one can then use this to calculate R0 given T0, what design principle for a good pRNG does this fail to implement?
(c) If the attacker knows T0 and T1 with just millisecond resolution, the attacker can check to see if a possible candidate for T0 and T1 is consistent with guesses for R0 and thereby know they found V0. How many possible combinations of T0 and T1 may potentially need to be checked to determine V0?
2This was analyzed as the DUHK (“Don’t Use Hardcoded Keys”) attack, and it worked against FortiGate VPNs. For more details see https://duhkattack.com. This catastrophic failure mode is why it is no longer part of the standard suite of pRNGs.
Midterm 1 Page 13 of 14 CS 161 – Fa 18
Midterm 1 Page 14 of 14 CS 161 – Fa 18