Peyrin & Ryan
Summer 2020
CS 161
Computer Security Midterm
For questions with circular bubbles, you may select exactly one choice on the answer sheet.
Unselected option
Only one selected option
For questions with square checkboxes, you may select one or more choices on the answer sheet.
You can select
multiple squares
For questions with a large box, you need write and label your answer in the blank space below the question
on the answer sheet.
You have 110 minutes. There are 5 questions of varying credit (150 points total).
The exam is open note. You can use an unlimited number of handwritten cheat sheets, but you must work
alone.
Clarications will be posted at https://cs161.org/clarications.
MANDATORY - Honor Code (1 point)
Read the following honor code and sign your name on your answer sheet. Failure to do so will
result in a grade of 0 for this exam.
I understand that I may not collaborate with anyone else on this exam, or cheat in any way. 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.
Page 1 of 19
Q1 True/false (34 points)
Each true/false is worth 2 points. This question has 17 subparts.
Q1.1 True or False: If the discrete-log problem is broken (someone nds a way to eciently calculate푎 given 푔푎 mod 푝), ElGamal encryption is no longer secure.
True False
Solution: True. ElGamal depends on Die-Hellman, which depends on the discrete-log
problem. An attacker could learn 푟 from the ciphertext, then calculate (푚 × 퐵푟 ) × 퐵−푟 mod 푝 to
obtain the original message.
Q1.2 True or False: Buer overows can occur on the stack and heap, but not in the static section of
C memory.
True False
Solution: False. Consider a program where a buer is dened in static memory, and gets is
called on the buer.
Q1.3 True or False: The primary danger of format string vulnerabilities is that they let an attacker
write more bytes into a buer than the buer has space for.
True False
Solution: False. Calls to printf usually don’t write into a buer.
Q1.4 True or False: You create a Reddit bot but leave your secret credentials le in your public
GitHub repo. You believe this is not a problem because attackers won’t look at your Github repo.
This is a failure to consider Shannon’s Maxim.
True False
Solution: True. The security of your bot is reliant upon nobody actually looking through the
repo, which is security through obscurity.
Q1.5 True or False: If ASLR is enabled, leaking the address of a stack variable would give an attacker
the address of heap variables.
True False
Solution: False. Leaking the address of a stack variable would give an attacker the ability to
determine other stack variables due to their deterministic spacing, but the address of the heap
space is still random.
Q1.6 True or False: All cryptographic hash functions are one-to-one functions.
Midterm Page 2 of 19 CS 161 – Summer 2020
True False
Solution: False. By denition, a hash function compresses an input which means you’ll always
have some collisions ⟹ not one-to-one. Cryptographic hash functions try to make nding
those collisions dicult, but they still exist.
Q1.7 True or False: Alice downloads a certicate for TikTok over a channel that is using encryption
based on AES-ECB. She can always verify the validity of the certicate, assuming she has a
validated copy of the parent certicate.
True False
Solution: True. As long as Alice veries the signature on TikTok’s certicate using the public
key from Apple’s certicate, she can trust that TikTok’s certicate is valid.
Q1.8 True or False: Combining two independent detectors in parallel (alert when either detector
alerts) is always more eective than combining them in serial (alert when both detectors alert).
True False
Solution: False. It depends on the cost of getting a false positive vs the cost of a true positive
and how frequently they occur.
Q1.9 Alice and Bob are communicating through RSA encryption, and both parties are attaching digital
signatures to their messages. Alice and Bob each have a public encryption key, a private decryption
key, a public verifying key, and a private signature key.
True or False: If Eve acquires access to both Alice and Bob’s private signature keys, the
communication channel is no longer condential.
True False
Solution: False. Even though Eve can now assume the identity of Alice or Bob, the actual
messages sent between the real Alice and Bob remain encrypted, since Eve doesn’t have access
to either person’s private decryption keys.
Q1.10 True or False: A company requires users to have long, complicated passwords. As a result, some
employees write down their passwords on sticky notes to remember them. This is an example of
not following the “Security is Economics" security principle.
True False
Solution: False. this is an example of not following the ’Consider human factors’ security
principle.
Midterm Page 3 of 19 CS 161 – Summer 2020
Q1.11 True or False: If 푘 is a 128 bit key selected uniformly at random, then it is impossible to distin-
guish AES푘(⋅) from a permutation selected uniformly at random from the set of all permutations
over 128-bit strings.
Clarication made during the exam: AES푘(⋅) refers to the encryption function of AES using key 푘.
True False
Solution: True. AES is believed to be secure, which means that no known algorithm can
distinguish between AES푘(⋅) and a truly random permutation so long as 푘 is selected uniformly
at random.
Q1.12 True or False: Enabling stack canaries, ASLR, and DEP prevents all buer overow attacks.
True False
Solution: False. it makes it harder for buer overow attacks, but doesn’t eliminate the
possibility.
Q1.13 True or False: Coding in a memory-safe language prevents all buer overow attacks.
True False
Solution: True. Memory-safe languages abstract away memory allocation and memory man-
agement or check memory bounds during runtime, avoiding buer overows and many other
memory safety attacks.
Q1.14 True or False: To use ElGamal encryption eciently on very long messages, you should break
up the message into small blocks and encrypt each block individually with ElGamal.
True False
Solution: False. To use asymmetric cryptography with large messages, it is most appropriate
to randomly generate a symmetric key, encrypt the message using symmetric encryption, and
encrypt the key with asymmetric encryption to protect the condentiality of the message.
Using asymmetric cryptography directly on a very long message is very inecient.
Q1.15 True or False: A hash function that is one-way but not collision resistance can be securely used
for password hashing.
True False
Solution: True. Collisions don’t matter in this context as the only property we want is that
an attacker can’t invert a hash.
Q1.16 True or False: A hash function whose output always ends in 0 regardless of the input can’t be
collision resistant.
Midterm Page 4 of 19 CS 161 – Summer 2020
True False
Solution: False. Consider 퐻 (푥) = 푆퐻퐴256(푥)||0. This hash is collision resistant but always
ends in a 0.
Q1.17 True or False: Compared to the trusted directories model, digital certicates are less dependent
on a central point of availability.
True False
Solution: True. Digital certicates can be distributed by anyone, not just the trusted directory.
This is the end of Q1. Proceed to Q2 on your answer sheet.
Midterm Page 5 of 19 CS 161 – Summer 2020
Q2 Asymmetric (29 points)
This question has 7 subparts.
Q2.1 (5 points) In Die-Hellman key exchange, which of the following elements would be known to an
attacker observing network trac between Alice and Bob? Assume the same syntax from notes
and lecture, and Alice has a SK = 푎. Select all that apply.
(A) 푔
(B) 푝 (C) 푎 mod 푝(D) 푔 mod 푝 (E) 푔푎 mod 푎(F) None of the above
Solution: 푔 and 푝 are both public values, which also means the attacker can directly calculate푔 mod 푝.
To calculate 푎 mod 푝 or 푔푎 mod 푎, the attacker needs Alice’s secret 푎. However, in Die-
Hellman, Alice sends 푔푎 mod 푝, and because the discrete-log problem is hard, the attacker
cannot learn the value of 푎 from this.
Q2.2 (5 points) Consider the un-padded ElGamal encryption scheme as shown in lecture. Alice sends
the number 10, but a man-in-the-middle attacker intercepts the message. If Alice sends out the
encrypted message (푅, 푆), write an expression for a modied message that would cause Bob to
receive the number 20.
Please clearly label your nal answer on your answer sheet.
Solution: (푅, 2 × 푆)
The encrypted message is is (푅, 푆) = (푔푟 mod 푝,푚×퐵푟 mod 푝). We can change the message from
10 to 20 by replacing 푚 with 2 ×푚, so the expression becomes (푔푟 mod 푝, 2 ×푚 × 퐵푟 mod 푝) =(푅, 2 × 푆).
Bob is tired of having his email hacked, so he devises a personal encryption method for students to
send him messages. Dene 푔 and 푝 the same way they are dened in ElGamal. Assume that there are 푝
students, each with a unique SID in the range [0, 푝 − 1].
Just like in ElGamal, Bob generates a secret key 푏, and a public key 퐵 = 푔푏 (mod 푝). Students with a
valid student ID (푠푖푑) will encrypt their plaintext message 푚 and send (푅, 푆), where 푅 = 푔푠푖푑 mod 푝 and푆 = (푚 × 퐵)푠푖푑 mod 푝.
Q2.3 (5 points) Assume Bob is expecting a message from a student with SID 푠푖푑 . Write an expression
for 푚 in terms of 푝, 푏, 푅, 푆, and 푠푖푑 .
Please clearly label your nal answer on your answer sheet.
Solution:푆 = (푚 × 퐵)푠푖푑 mod 푝푆 = 푚푠푖푑 × 퐵푠푖푑 mod 푝
Midterm Page 6 of 19 CS 161 – Summer 2020
Using the fact that 퐵 = 푔푏 mod 푝:푆 = 푚푠푖푑 × (푔푏)푠푖푑 mod 푝푆 = 푚푠푖푑 × (푔푠푖푑 )푏 mod 푝
Using the fact that 푅 = 푔푠푖푑 mod 푝:푆 = 푚푠푖푑 × 푅푏 mod 푝푆 × 푅−푏 = 푚푠푖푑 mod 푝푚 = (푆 × 푅−푏)1/푠푖푑 mod 푝
Q2.4 (3 points) Will Bob be able to decrypt a message from someone he is not expecting in polynomial
time?
(G) Yes, because Bob can try every 푠푖푑 in polynomial time
(H) Yes, because the decryption does not require Bob to know 푠푖푑
(I) No, because the discrete-log problem is hard
(J) No, because the factoring problem is hard
(K) None of the above
(L)
Solution: No,푝 is assumed to be large enough that this is not possible. Note, that if bruteforcing
every value of ℤ푝 was possible in polynomial time, than an attacker could break discrete log
in a polynomial amount of time. Furthermore, there would be no guaranteed indication as to
which decryption is the intended message because the message 푚 is not padded. So, in general,
this will be a bad encryption scheme.
Q2.5 (3 points) True or False: The same attack from Q2.2 will succeed under this new schema.
Clarication made during the exam: Subpart 5 is asking if the exact expression you wrote in subpart
2 will have the same eect on the modied scheme.
(A) True (B) False (C) (D) (E) (F)
Solution: False. Multiplying 2 × 푆 = 2 × (푚 × 푅)푠푖푑 ≠ (2 ×푚 × 푅)푠푖푑 , which is what we’d want
to recover.
Q2.6 (5 points) Suppose Alice is sending Bob your grade (푅, 푆), and you know Alice’s 푠푖푑 . You have the
ability to launch a man-in-the-middle attack. Write an expression for a modied message that
would change your grade to be 10 times your original grade.
Midterm Page 7 of 19 CS 161 – Summer 2020
Please clearly label your nal answer on your answer sheet.
Solution: The encrypted message is (푅, 푆) = (푔푠푖푑 mod 푝, (푚 × 퐵)푠푖푑 mod 푝). We can change
the message to be 10 times its original value by replacing 푚 with 10 ×푚, so the expression
becomes:(푔푠푖푑 mod 푝, (10 ×푚 × 퐵)푠푖푑 mod 푝)(푔푠푖푑 mod 푝, 10푠푖푑 × (푚 × 퐵)푠푖푑 mod 푝)(푅, 10푠푖푑 × 푆)
Q2.7 (3 points) Assuming that the recipient knows the 푠푖푑 used, what does this scheme provide? Select
all that apply.
(A) Integrity
(B) Authentication
(C) Condentiality
(D) None of the above
(E)
(F)
Solution: The previous part showed that the message could be manipulated without Bob’s
knowledge, so it lacks authentication and integrity. Without Bob’s private key, the message
maintains condentiality.
This is the end of Q2. Proceed to Q3 on your answer sheet.
Midterm Page 8 of 19 CS 161 – Summer 2020
Q3 IV-e got a question for ya (24 points)
Determine whether each of the following schemes is IND-CPA secure. This question has 6 subparts.
Q3.1 (6 points) AES-CBC where the IV for message 푀 is chosen as HMAC-SHA256(푘2, 푀) truncated to
the rst 128 bits. The MAC key 푘2 is distinct from the encryption key 푘1.
Provide a short justication for your answer on your answer sheet.
(A) Insecure
(B) Secure
(C)
(D)
(E)
(F)
Solution: For any given message, the IV will be the same each time it’s encrypted ⟹
deterministic scheme.
Q3.2 (6 points) AES-CTR where the IV for message 푀 is chosen as HMAC-SHA256(푘2, 푀) truncated to
the rst 128 bits. The MAC key 푘2 is distinct from the encryption key 푘1.
Provide a short justication for your answer on your answer sheet.
Clarication made during the exam: You can assume that IV refers to the nonce for CTR mode.
(G) Insecure
(H) Secure
(I)
(J)
(K)
(L)
Solution: For any given message, the IV will be the same each time it’s encrypted ⟹
deterministic scheme.
Q3.3 (3 points) AES-CBC where the IV for message 푀 is chosen as SHA-256(푥) truncated to the rst
128 bits. 푥 is a predictable counter starting at 0 and incremented per message.
(A) Insecure
(B) Secure
(C)
(D)
(E)
(F)
Solution: CBC mode requires its IVs to be random and thus unpredictable. To break IND-
CPA, the adversary could send its rst challenge as 푀 = SHA-256(0), which would result
in 퐶 = AES-CBC푘(SHA-256(0) ⊕ SHA-256(0)) = AES-CBC푘(0). Next, the adversary would
send the challenge 푀0 = SHA-256(1), 푀1 ≠ 푀0, and the adversary knows that the challenger
encrypted 푀0 if 퐶푏 = 퐶 and 푀1 otherwise.
Q3.4 (3 points) AES-CTR where the IV for message 푀 is chosen as SHA-256(푥) truncated to the rst
128 bits. 푥 is a predictable counter starting at 0 and incremented per message.
Clarication made during the exam: You can assume that IV refers to the nonce for CTR mode.
Midterm Page 9 of 19 CS 161 – Summer 2020
(G) Insecure
(H) Secure
(I)
(J)
(K)
(L)
Solution: CTR mode is secure even with predictable nonces, so long as you never reuse a
counter in any block. Note that if 푥 were used directly as the nonce, this would be insecure.
Consider two 2-block messages 푀0 and 푀1. The rst message would be encrypted with 푥 = 0,
so the two blocks encrypt the counter 0 and 1. THe second message would be encrypted with푥 = 1, so the two blocks encrypt the counter 1 and 2, breaking security.
Q3.5 (3 points) AES-CBC where the IV for message 푀 is chosen as HMAC-SHA256(푘2 + 푥,푀) truncated
to the rst 128 bits. The MAC key 푘2 is distinct from the encryption key 푘1 and 푥 is a predictable
counter starting at 0 and incremented per message.
(A) Insecure
(B) Secure
(C)
(D)
(E)
(F)
Solution: The IV is unpredictable to the attacker, even though the adversary can view previous
IVs due to the properties of the HMAC.
Q3.6 (3 points) AES-CTR where the IV for message 푀 is chosen as HMAC-SHA256(푘2 + 푥,푀) truncated
to the rst 128 bits. The MAC key 푘2 is distinct from the encryption key 푘1 and 푥 is a predictable
counter starting at 0 and incremented per message.
Clarication made during the exam: You can assume that IV refers to the nonce for CTR mode.
(G) Insecure
(H) Secure
(I)
(J)
(K)
(L)
Solution: The IV is unpredictable to the attacker, even though the adversary can view previous
IVs due to the properties of the HMAC.
This is the end of Q3. Proceed to Q4 on your answer sheet.
Midterm Page 10 of 19 CS 161 – Summer 2020
Q4 steg (27 points)
This question has 9 subparts.
Consider a new C function, steg(char *s). It is similar to gets, but instead of writing to higher
memory addresses, steg stores the user input by writing to lower memory addresses, starting at the
memory address pointed to by s.
For example, if I call steg(str) and &str = 0xdeadbeef, and I type in xyz as input, the byte x will
be stored at 0xdeadbeef, the byte y will be stored at 0xdeadbeee, and the byte z will be stored at
0xdeadbeed.
Consider the following vulnerable C code that uses steg:
1 void d i s p l a y ( char ∗ buf ) {
2 s t e g ( buf ) ;
3 p r i n t f ( "%s " , buf ) ;
4 }
5
6 in t main ( ) {
7 char door [ 4 ] ;
8 d i s p l a y (& door ) ;
9 }
(3 points) Fill in the numbered blanks for this incomplete stack diagram. Each box in the diagram
represents 4 bytes. Each blank is worth 3 points.
rip of main
sfp of main
(1)
(2)
(3)
sfp of display
Q4.1 Blank (1)
(A) door
(B) buf = &door
(C) rip of display
(D)
(E)
(F)
Q4.2 Blank (2)
(G) door
(H) buf = &door
(I) rip of display
(J)
(K)
(L)
Midterm Page 11 of 19 CS 161 – Summer 2020
Q4.3 Blank (3)
(A) door
(B) buf = &door
(C) rip of display
(D)
(E)
(F)
Solution: First, in the main stack frame we allocate space for the local variable door. Then,
to call the function display, we push the argument buf = &door on the stack. Finally, we
push the rip of display (which points to the instructions for main) on the stack.
The stack looks like this (the address of each slot is in parentheses):
rip of main (0xbf24)
sfp of main (0xbf20)
door (0xbf1c)
buf = &door (0xbf18)
rip of display (0xbf14)
sfp of display (0xbf10)
Q4.4 (3 points) Which rip is vulnerable to being changed during the call to steg?
Remember that the rip of a function f refers to the EIP of the previous function that is pushed
onto the stack when calling f.
(G) display
(H) main
(I) None of the above
(J)
(K)
(L)
Solution: The call to steg writes to lower addresses, starting at door, so the vulnerable rip
is the rip of display, which is below door.
Suppose we have an 8-byte shellcode. Denote REV_SHELLCODE as a reversed version of this shellcode.
We nd the address of door to be 0xbfffff1c. Complete the exploit in the following three parts to
cause the shellcode to execute.
Hint: x86 is little-endian (ie. the least signicant byte of a word is stored at the lowest address), and we are
writing from higher addresses to lower addresses.
Hint: 0xbfffff1c - 16 = 0xbfffff0c, and 0xbfffff1c - 8 = 0xbfffff14.
Q4.5 (3 points) At the call to steg at line 2, rst input this many bytes of garbage to reach the rip:
(A) 0 (B) 1 (C) 5 (D) 9 (E) 13 (F) 17
Midterm Page 12 of 19 CS 161 – Summer 2020
Solution: The RIP is 4 bytes below door, and steg starts writing at the rst byte of door, so
we have to write 1 byte of garbage to ll the rst byte of door, then another 4 bytes to skip
over the argument buf.
Q4.6 (3 points) Then overwrite the rip with these bytes:
(G) \xbf\xff\xff\x0c
(H) \x0c\xff\xff\xbf
(I) \xbf\xff\xff\x14
(J) \x14\xff\xff\xbf
(K) REV_SHELLCODE
(L)
Solution: The address of the start of shellcode will be 8 bytes below &rip (or 16 bytes below
door), which is 0xbfffff0c.
We want to input the address 0xbfffff0c in little-endian. If we were writing from lower
addresses to higher addresses, like in project 1, this would be \x0c\xff\xff\xbf. Partial
credit was given for this answer.
However, we are writing from higher addresses to lower addresses, so the correct answer is
actually the reverse of this, which is \xbf\xff\xff\x0c.
Q4.7 (3 points) Then input these bytes:
(A) \xbf\xff\xff\x0c
(B) \x0c\xff\xff\xbf
(C) \xbf\xff\xff\x14
(D) \x14\xff\xff\xbf
(E) REV_SHELLCODE
(F)
Solution: Finally, we input the shellcode, remembering to input it backwards because we’re
writing from higher addresses to lower addresses.
Q4.8 (3 points) Would the exploit from the previous parts still work if stack canaries were enabled?
Assume there is no way for the attacker to learn the value of the stack canary.
(G) Yes (H) No (I) (J) (K) (L)
Solution: No. This exploit overwrites 12 bytes below door, which would overwrite the stack
canary just below the sfp of display.
Midterm Page 13 of 19 CS 161 – Summer 2020
A common mistake was to answer yes, because the exploit does not aect the canary just
below the sfp of main, but remember that when we enable stack canaries, a canary is added
below the sfp in every stack frame.
Q4.9 (3 points) What is the length (in bytes) of the longest shellcode that can be executed using the
exploit in the previous parts without triggering a stack canary? Assume there is no way for the
attacker to learn the value of the stack canary.
Please clearly label your nal answer on your answer sheet.
Solution: The intended answer was 4 bytes. After the rip of display, there are 4 bytes of
the sfp you can overwrite with shellcode before the canary is overwritten.
However, you could also put the shellcode at the beginning of your exploit by writing shellcode
all the way until the rip of display. There are 5 bytes you can overwrite here (see subpart 5),
so technically 5 bytes is the correct answer.
This is the end of Q4. Proceed to Q5 on your answer sheet.
Midterm Page 14 of 19 CS 161 – Summer 2020
Q5 A Dangerous Game (35 points)
This question has 9 subparts.
Note: This is the hardest question on the exam. We recommend trying the other questions on the exam
before this one.
A new online game, HackMe, splits 128-512 players into groups of 16 and has all groups compete to
hack each other. HackMe uses a hash table to create groups and store info about each player.
Recall that a hash table is an array of “buckets” (here each bucket is a linked list). To add a player to the
table, a hash function is evaluated to decide which bucket the player goes into, and they are appended
to the linked list of that bucket.
1 typedef s t ruc t P l a y e r {
2 in t i d ;
3 in t h a c k i n g _ a b i l i t y ;
4 } P l a y e r ;
5
6 typedef s t ruc t Bucket {
7 i n t 8 _ t s i z e ; / / 8 b i t s i g n e d i n t e g e r
8 L i n k e d L i s t ∗ b ; / / P o i n t e r t o a l i n k e d l i s t imp l emen t a t i o n
9 } Bucket ;
10
11 typedef s t ruc t HashTable {
12 in t p l a y e r s ;
13 Bucket b u c k e t s [ 1 6 ] ;
14 } HashTable ;
15
16 void a d d _ p l a y e r ( HashTable ∗ t , P l a y e r p ) {
17 s i z e _ t i d x = hash ( p . i d + t −> p l a y e r s ) ; / / hash range i s [ 0 , 1 6 )
18 append ( t −> b u c k e t s [ i d x ] . b , p ) ; / / appends p t o L i n k e d L i s t
19 t −> b u c k e t s [ i d x ] . s i z e += 1 ;
20 t −> p l a y e r s += 1 ;
21 }
Q5.1 (3 points) Assume that hash() outputs an unsigned integer equal to the last 4 bits of a pseudoran-
dom, cryptographic hash function. If the table contains a number of Players with random ids,
what do you expect about the size of the buckets?
(A) They will all roughly be the same size
(B) The 0th bucket will be larger than the 1st bucket
(C) The 1st bucket will be larger than the 0th bucket
(D)
(E)
(F)
Midterm Page 15 of 19 CS 161 – Summer 2020
Solution: Since the hash function is pseudorandom and all the inputs to the hash function
will be dierent with high probability, the Players should be uniformly distributed.
Q5.2 (3 points) Assume that hash() outputs an unsigned integer equal to the last 4 bits of a pseudoran-
dom, cryptographic hash function. If the table contains a number of Players with the same id,
what do you expect about the size of the buckets?
(G) They will all roughly be the same size
(H) The 0th bucket will be larger than the 1st bucket
(I) The 1st bucket will be larger than the 0th bucket
(J)
(K)
(L)
Solution: The inputs to the hash function will still all be dierent since the id is added to the
player count. Thus, the Players should be uniformly distributed.
Q5.3 (3 points) Say a user stores a large number (ie. 10000) of Players in a HashTable.
Which of the following would occur given the code above?
(A) Integer overow
(B) Buer overow
(C) O-by-one
(D)
(E)
(F)
Solution: Each bucket will contain more than 127 elements so the int8_t size variable
will overow.
Q5.4 (3 points) Which line number contains the vulnerability from the previous part?
(G) Line 7
(H) Line 8
(I) Line 13
(J)
(K)
(L)
Solution: The int8_t size variable is dened at line 7.
To register a group for playing HackMe, one inputs a list of Players to the following function which
adds all Players to a HashTable, assigns the group to a server based on size of the 0th bucket, and sets
a group name.
Midterm Page 16 of 19 CS 161 – Summer 2020
1 void r e g i s t e r _ g r o u p ( P l a y e r ∗ p l a y e r s , s i z e _ t num_players ) {
2 char ∗ se rver_names [ 1 2 8 ] = { / ∗ Con t a i n s 128 s e r v e r names ∗ / } ;
3 char ∗ a _ g i f t = 0 x f f f f d 5 2 8 ; / / P o i n t e r t o t h e s t a c k canary
4 char group_name [ 1 6 ] ;
5 HashTable group ;
6 for ( in t i = 0 ; i < num_players ; i ++) {
7 a d d _ p l a y e r (& group , p l a y e r s [ i ] ) ;
8 }
9 p r i n t f ( " Use s e r v e r : %s \ n " , s e rver_names [ group . b u c k e t s [ 0 ] . s i z e ] ) ;
10 p r i n t f ( " P l e a s e p r o v i d e 16 c h a r a c t e r group name : \ n " ) ;
11 g e t s ( group_name ) ;
12 . . .
13 }
Q5.5 (5 points) Consider line 9:
printf("Use server: %s\n", server_names[group.buckets[0].size]);
Which valid values of group.buckets[0].size would cause this statement to print something
outside of server_names?
______ ≤ group.buckets[0].size ≤ ______
Please clearly label your nal answer on your answer sheet.
Solution:
-128 ≤ group.buckets[0].size ≤ -1
server_names is size 128, so 0 ≤ group.buckets[0].size ≤ 127 are all valid memory
accesses. However, group.buckets[0].size is a signed variable (int8_t), so it can also
take on negative values that will cause illegal memory accesses. The negative range of an
int8_t variable is −128 ≤ group.buckets[0].size ≤ −1.
Q5.6 (10 points) Mallory challenges you to hack HackMe. Assume you can invoke register_group
with a list of Player’s of your choosing, but the list must have length between [128, 512] and
num_players must always be correct.
HackMe uses a 32-bit x86 system with stack canaries enabled (assume that canaries don’t contain
null bytes) but no WˆX bit or ASLR. In order to help you out, Mallory has added a pointer to the
stack canary: a_gift.
Describe the list of Players you input. Assume that hash() is a publicly-known function that
you can query before making your list.
Clarication made during the exam: a_gift is a pointer to the stack canary of the register_group
frame.
Clarication made during the exam: Your answer to subpart 6 should give you information to
complete the exploit in subpart 7.
Midterm Page 17 of 19 CS 161 – Summer 2020
(G) (H) (I) (J) (K) (L)
If you need more space on your answer sheet, you can write on a blank sheet of paper and attach it
with your submission.
Solution: The overarching idea is we want to ll up the 0th bucket such that we overow the
size variable, making it negative and causing the print statement at line 8 to print out the
stack canary. To do this, we take advantage of the fact that a hash function is deterministic.
Since hash is public, we query it until we nd an input 푥 that maps to 0. We set this number
to be id of our rst Player. We set id of our second Player to be 푥 − 1, id of third Player
to be 푥 − 2, etc. This causes each Player to be placed in the 0 bucket. We repeat this 255 times
so that the size variable is equal to -1. This will cause the array access to server_names to
print out whatever a_gift points at - which is given to be the stack canary.
Q5.7 (5 points) Write down your exact input to the gets call at line 11. Assume that SHELLCODE holds
64-byte shellcode, GARBAGE is an arbitrary byte, and OUTPUT is the output from the print statement
at line 9.
You can write constants using hex (e.g., 0xFF or 0xA02200FC). For instance,4*GARBAGE + OUTPUT[:1]
+ SHELLCODE would represent four irrelevant bytes, followed by the rst byte of the print result,
followed by the 64-byte shellcode.
(A) (B) (C) (D) (E) (F)
Solution: GARBAGE*(16 + 4 + 128*4) + OUTPUT[12:16] + GARBAGE*4 + 0xffffd534 + SHELLCODE
First, we write 16 bytes of garbage to overwrite local variable char group_name[16]. Then,
we write 4 bytes of garbage to overwrite local variable char *a_gift. Then, we write 128*4
bytes to overwrite local variable char *server_names[128].
Next, we write the canary leaked from the previous part, when the printf call at line 9
accesses server_names[-1].size which is the canary value. This is OUTPUT[12:16] since
we need to skip past the "Use server: ".
Next, we write 4 more bytes of garbage to overwrite the sfp of register_group.
Next, we write a pointer to the start of shellcode, which is 4 bytes after the rip of register_group.
We know that the canary of register_group is located at 0xffffd528, so the sfp is 4 bytes
above the canary at 0xffffd52c. The rip is 4 bytes above the sfp, at 0xffffd530. So 4 bytes
after the rip is 0xffffd534.
Finally, we write the shellcode above the rip.
Q5.8 (3 points) Which of the following could prevent this attack? Assume a_gift always correct points
to the stack canary.
(G) ASLR
Midterm Page 18 of 19 CS 161 – Summer 2020
(H) 푊 ∧ 푋 protection (NX bit)
(I) Increasing the size of server_names to 256
(J) None of the above
(K)
(L)
Solution: Even though a_gift always points correctly, we never have the opportunity to
read its address so ASLR will still stop us.푊 ∧ 푋 protection (making the stack non-executable) will stop us because the exploit involves
running shellcode that we placed on the stack.
Increasing the size of server_names doesn’t have any eect since the exploit is reading lower
memory addresses like server_names[-1], not higher addresses.
This is the end of Q5. You have reached the end of the exam.
Midterm Page 19 of 19 CS 161 – Summer 2020

欢迎咨询51作业君