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 13
Problem 1 Potpourri Question (16 points)
Midterm 1
Page 2 of 13
CS 161 – Spring 2019
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
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?
Confidentiality Integrity
Authenticity Availability
Polytime Hardness None of the above
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 3 of 13
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 4 of 13
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.
Midterm 1
Page 5 of 13 CS 161 – Spring 2019
(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 = 𝖨𝖵 (generated randomly), 𝐶𝑖 =𝐸𝑘(𝐶𝑖−1⊕𝑀𝑖)⊕𝐶𝑖−1.
where ⊕ is bit-wise XOR.
⋄ Write the equation to decrypt 𝑀𝑖 in terms of the ciphertext blocks and the key 𝑘.
Mark each of the properties below that AES-CBC-STAR satisfies. Assume that the plaintexts are 100 blocks long, and that 10 ≤ 𝑖 ≤ 20.
(b)
(c)
Now we consider a modified version of AES-CBC-STAR, which we will call AES-CBC-STAR-STAR. Instead of generating the 𝖨𝖵 randomly, the challenger uses a list of random numbers which are public and known to the adversary. Let 𝖨𝖵𝑖 be the 𝖨𝖵 which will be used to encrypt the 𝑖th message from the adversary.
⋄ Argue that the adversary can win the IND-CPA game.
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.
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 ;
}
Midterm 1
Page 6 of 13 CS 161 – Spring 2019
(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.
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.)
Midterm 1
Page 7 of 13
CS 161 – Spring 2019
𝑀 || SHA3(𝑀) SHA3(𝑀 || 𝑘′)
𝑀 || SHA3(𝑀 || 𝑃𝐵)
Enc𝑘(𝑀)
𝑀 || SHA3(𝑀 || 𝑆𝐴) Enc𝑘(𝑀) || SHA3(𝑀 || 𝑘′)
(b) Mark which of her following proposals provide integrity. (Select all that apply.)
𝑀 || SHA3(𝑀) SHA3(𝑀 || 𝑘′)
𝑀 || SHA3(𝑀 || 𝑃𝐵)
Enc𝑘(𝑀)
𝑀 || SHA3(𝑀 || 𝑆𝐴) Enc𝑘(𝑀) || SHA3(𝑀 || 𝑘′)
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𝑥andhispublickeyis𝖯𝖪=(𝑝,𝑔,h),whereh=𝑔𝑥 mod𝑝.However,tosend amessage𝑀toBob,Aliceencrypts𝑀asEnc𝖯𝖪(𝑀)=(𝑠,𝑡),where𝑠=𝑔𝑟 mod𝑝and𝑡=𝑔𝑀×h𝑟 mod𝑝, for a randomly chosen 𝑟.
(a) Consider two distinct messages 𝑚1 and 𝑚2. Let Enc𝖯𝖪(𝑚1) = (𝑠1, 𝑡1) and Enc𝖯𝖪(𝑚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 Enc𝖯𝖪(𝑚1 + 𝑚2). 𝑡1 × 𝑡2 mod 𝑝) is a possible value for Enc𝖯𝖪(𝑚1 + 𝑚2). 𝑡1 × 𝑡2 mod 𝑝) is a possible value for Enc𝖯𝖪(𝑚1 × 𝑚2). 𝑡1 + 𝑡2 mod 𝑝) is a possible value for Enc𝖯𝖪(𝑚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 ≤ 𝑀 < 𝑝.
Midterm 1 Page 8 of 13 CS 161 – Spring 2019
Midterm 1
Page 9 of 13 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 𝖯𝖪 = (𝑝, 𝑔, h).
⋄ Question: How should Mallory create 𝐶1?
2. MalloryknowsAlice’sciphertext𝐶0,butonlyknows𝑝and𝑔inBob’spublickey𝖯𝖪=(𝑝,𝑔,h). (That is to say, Mallory does not know h.)
⋄ Question: How should Mallory create 𝐶1?
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 ________ [64]
char ________ [64]
________________________
________________________
________________________
________________________
________________________
char buffer[16]
Midterm 1
Page 10 of 13
CS 161 – Spring 2019
Midterm 1
Page 11 of 13 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
(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
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 12 of 13 CS 161 – Spring 2019
Midterm 1 Page 13 of 13 CS 161 – Spring 2019