CS166 Computer Systems Security Spring 2021

CS166 Computer Systems Security Spring 2021
Homework 1: Crypto Party
Due: Thursday, February 11 @ 11:59 pm ET
Do not include any identifying information (name, login, Banner ID, etc.) on your handin. When you’re
done, please submit a PDF le to Gradescope where your answer to each problem (not each individual
question) is on a separate page. Make sure to assign each problem on Gradescope to the correct pages
in your writeup (or you may receive a deduction).
Unless otherwise stated, you should justify and explain all of your proposed attacks, schemes, protocols,
defenses, etc., referencing speci c properties when necessary. Precise, e ective communication and
presentation of your ideas and solutions in your writeups is something we highly value when grading.
Similarly, be concise, but make sure that you don’t elide intermediate details, take subtleties for granted,
or make any assumptions without justi cation.
While we encourage everyone to discuss and work through the problems on the homeworks, please
remember that your homework solutions must be written up entirely independently, in your own words.
You may not share your solutions with anyone (or read solutions written by others). You should not
write your solutions while working with other students, and when you’re writing your solutions, you
should ensure that you independently understand and can reproduce your answers without referring to
notes from collaboration sessions and consulting with other students.
Reminder: At the top of every problem (not question), you should write a collaboration statement
that states who you discussed the problem with, who contributed major intellectual insights to your
understanding of the problem, and any external resources you referenced while solving the problem.
See the Collaboration Policy for examples. If you did not collaborate with anyone and did not refer to
any sources, your collaboration statement should state as much.
Homework 1 Instructions
Answer Problems 1{5. If you’re a CS162 student, you must also answer Problems 6 and 7.
When you’re ready to submit, you should hand in your answers to Problems 1{5 to the \CS166: Problems
1{5″ drop on Gradescope. CS162 students should also hand in their answers to Problems 6{7 to the \CS162:
Problems 6{7″ drop on Gradescope in a separate PDF. (Answers submitted by CS166-only students to the
CS162 questions will not be graded.)
Questions start on Page 2.
1
CS166 Computer Systems Security Spring 2021
Problem 1: Dating with Public Keys
Alice and Bob, both Brown CS students, are secretly dating. In order to set up a meeting, they exchange
encrypted messages using a deterministic public key encryption scheme (deterministic meaning that multiple
encryptions of a given plaintext always produce the same ciphertext).
Alice and Bob both have their own public-private key pair, (PKA; SKA) and (PKB; SKB) respectively.
When Alice wants to send a message, m, to Bob, she encrypts it using his public key and sends the resulting
ciphertext, c = Enc(m; PKB), to him. Similarly, Bob’s messages to Alice are computed from Enc(m; PKA).
In plaintext, the messages Alice and Bob exchange are always of the following form:
Alice
CIT, 7:00pm
NO
GCB, 8:30pm
YES
Bob
Assume that they always plan to meet at a Brown building, and when referring to a speci c Brown building,
the name they use is consistent (i.e. they won’t alternate between \SciLi” and \Sciences Library”).
For all parts of this problem, limit each of your answers to 150 words maximum|longer responses
will receive no credit.
Question a) Sierra is Alice’s curious roommate who wants to nd out about the secret dates between Alice
and Bob. She knows both of their public keys, the form of their messages (including the name
they use to refer to all of Brown’s buildings), and she can eavesdrop on the ciphertexts being
exchanged. Describe how Sierra can nd out when and where the next meeting is going to
be, even though she is unable to learn the secret keys.
Question b) Alice and Bob found out that Sierra can learn about their meetings. Propose a simple modi-
cation to the protocol that prevents the attack from part (a) and explain why the protocol
will prevent the attack, and explain why it works. By \simple”, your new protocol cannot
rely on sending additional messages or require changing any of the cryptographic functions
involved or adding new cryptographic functions.
Question c) True or False: Sierra is an IND-CPA adversary. Explain.
2
CS166 Computer Systems Security Spring 2021
Problem 2: Commitments (in the Midst of a Breakup)
After Bob didn’t show up at the Graduate Center Bar at 8:30pm (even though he previously agreed to go
there in Problem 1), Alice decided that it was time for them to break up. They no longer trust each other,
so much in fact that they refuse to be together in the same room. As part of the breakup, Bob wants to
take one of the n houseplants he and Alice previously shared. Alice agrees, but she likes some houseplants
more than others, and so she doesn’t want Bob to just be able to pick any particular one.
To settle this, they send texts to each other over a communication channel (which guarantees message
delivery, but the time to deliver a given message is unpredictable) and assign unique numbers f0; 1; :::; n􀀀1g
to each plant. Then, they agree that Bob should roll an n-sided die, and Bob will receive the plant that
corresponds to the number Bob rolled. However, suppose Bob really wants a particular houseplant with
associated number b. All Bob needs to do is simply notify Alice that he rolled b, regardless of what his
n-sided die actually rolled.
For parts (b) and (c), limit each of your answers to 50 words maximum|longer responses will receive
no credit. Part (a) has no word limit, but your entire answer to this speci c problem has to t on a single
page in your writeup, or part (a) receives no credit.
Question a) Using cryptography, design a protocol between Alice and Bob that emulates the rolling of an
unbiased n-sided die (that is, the outcome is uniformly distributed in f0; 1; :::; n 􀀀 1g), and
does it in such a way that neither Alice nor Bob can \cheat” during the protocol; that is,
neither Alice nor Bob can a ect the outcome of the die roll without the other person knowing.
(Recall that Alice and Bob don’t want to meet in person and communicate only via text
messages. Your solution should not involve the use of a third-party.)
If a player detects cheating during the course of the protocol, your protocol should specify that
the player should abort from the protocol; that is, they stop participating and no outcome is
reached.
Then, explain why your protocol prevents Alice and Bob from cheating. Speci cally, explain
why the outcome is uniformly distributed in f0; 1; :::; n 􀀀 1g as long as at least one player
follows the protocol honestly and no player aborts during the protocol. Your justi cation
should reference all of the relevant properties of the cryptographic methods you have employed
in the protocol.
Question b) In your protocol from part (a), is it possible for Alice or Bob to discover the outcome of the die
roll before their ex? If so, what could they do to prevent their ex from knowing the outcome?
Question c) JC is a trustworthy friend of Alice and Bob. JC is known for keeping their friends’ secrets
safe and would never be bribed. JC can communicate via text messages with Alice and Bob
and keep track of messages previously exchanged. However, JC cannot perform any compu-
tations. In particular, JC cannot execute arithmetic operations, generate random numbers,
run programs, or apply cryptographic methods to the content of the messages transmitted by
Alice and Bob.
Can JC help Alice and Bob with their protocol such that they learn the outcome of the die
roll at the same time (if at all)? If yes, explain how and why your proposed protocol ensures
both Alice and Bob receive the outcome at the same time; if no, explain what parts of the
protocol prevent such a system from existing.
3
CS166 Computer Systems Security Spring 2021
Problem 3: Hybrid Cryptosystems
Zachary says: \This was a midterm problem from a previous o ering of the course! You might want to
work on it independently before discussing with others to get a sense of how the midterm works.”
Consider Alice and Bob, two former lovers who exchange con dential messages over an insecure channel. Alice
and Bob both have their own public key (PKA, PKB) and private key (SKA, SKB), and Alice and Bob each
know each other’s public keys. When Alice and Bob want to communicate, they keep their communication
con dential by rst exchanging symmetric keys kA and kB in the following \setup phase”:
1. Alice randomly generates a symmetric key, kA, encrypts it with Bob’s public key using an IND-CPA-
secure public key cryptosystem, and sends the resulting ciphertext as a payload to Bob.
2. Bob decrypts the ciphertext using his private key, and learns kA.
3. Bob randomly generates a symmetric key, kB, encrypts it with Alice’s public key using an IND-CPA-
secure public key cryptosystem, and sends the resulting ciphertext as a payload to Alice.
4. Alice decrypts the ciphertext using her private key, and learns kB.
After doing this, Alice and Bob can send symmetrically encrypted messages to each other in the \chat
phase”: whenever Alice wants to send a chat message to Bob, she encrypts it with kB using some arbitrary
symmetric cryptosystem and sends the resulting ciphertext; when Bob wants to send a message to Alice, he
does the same except using kA. (It’s also worth noting that Alice and Bob’s chat messages are arbitrary,
sometimes seemingly random and unpredictable plaintexts.)
For all parts of this problem, limit each of your answers to 200 words maximum|longer responses
will receive no credit.
Question a) Consider an adversary, Erica, who knows PKA and PKB, is able to intercept payloads sent
between Alice and Bob, and is able to modify or replace them entirely with payloads of her
own.
Show how Erica can perform an attack that allows her to read the contents of messages Alice
sends to Bob (and vice versa). (Hint: There’s no requirement that Alice and Bob have to be
able to read each other’s messages after Erica’s attack.)
Question b) What is something simple that Alice and Bob can do to ensure they can detect if the attack
described in part (a) is happening (but not necessarily prevent it)? Explain. By \simple”,
your answer should not involve any applications of cryptography outside of what’s already
de ned in the protocol, and should not require Alice and Bob to agree beforehand on some
predetermined shared secret or phrase (since then they might just agree on a symmetric key).
Question c) We’d like to modify the \setup phase” of the chat protocol to x the problems described in part
(a). Alice and Bob would like to avoid simply defaulting to public/private key encryption for all
messages|as we’ve previously discussed, this is much slower than symmetric key encryption,
and if they are chatting frequently then the performance overhead might be too great.
Explain how to modify the \setup phase” of the protocol such that the attack from part (a)
is impossible, but still preserves usage of symmetric-key-only encryption in the chat phase.
Question d) For this question, ignore the changes you proposed in part (b) and (c). Consider a slight
modi cation to the scenario where Alice and Bob do not know each other’s public keys prior
to the \setup phase”. They quickly resolve this issue by sending their public keys to each
other as payloads. At this point, they now know each other’s public keys, and therefore can
proceed to the \setup phase” as normal.
Does Erica have less, the same, or more capabilities in this scenario than she did in the attack
in part (a)? Explain your answer. (To be speci c, her \capabilities” refer to her ability to
read the contents of Alice and Bob’s chat messages.)
4
CS166 Computer Systems Security Spring 2021
Problem 4: Exceptional Access
Law enforcement agencies have been lobbying for exceptional access to encrypted communications. However,
many cybersecurity experts have argued that enabling exceptional access would have untenable security con-
sequences. Two cryptographers from GCHQ (the UK’s equivalent of the NSA) have proposed a method of
exceptional access that they believe does not compromise the integrity of encryption in the following arti-
cle: https://www.lawfareblog.com/principles-more-informed-exceptional-access-debate. Please
reference the article in your answers.
The second article describes a Cisco Webex vulnerability which unintentionally allows \ghost access” to
meetings. Feel free to refer to this article in your answers (though this article is optional): https://www.
securityweek.com/cisco-webex-vulnerability-allows-ghost-access-meetings
Question a) The rst article discusses several principles that can be used to evaluate exceptional access
methods. What standards would need to be followed for you to nd an exceptional access
reasonable (3 standards max)? If you believe that exceptional access is never acceptable,
please justify why. How does your answer di er from the GCHQ principles, if at all?
Question b) Do you believe that the GCHQ authors’ fth principle|that \any exceptional access solution
should not fundamentally change the trust relationship between a service provider and its
users”|is met by their proposed exceptional access mechanism? Why or why not? (4{6
sentences)
Question c) One argument when it comes to exceptional access is that if companies don’t provide a mecha-
nism for the government to access communications between users, then the only option left for
government agencies is hacking. Resorting to hacking negatively impacts government agen-
cies’ incentives to disclose vulnerabilities. Do you nd this argument in favor of exceptional
access convincing? Why or why not? (4{6 sentences)
These are open questions and will be graded for thought and justi cation. Please reference and/or quote
speci c arguments from the readings in your answers.
5
CS166 Computer Systems Security Spring 2021
Problem 5: CIT-Branded Block Ciphers
Charles has ignored all of the warnings about hand-rolling your own cryptography (see the Lecture 3 readings)
and has created a new block cipher mode called CIT mode. Figure 1 provides an overview of how CIT mode
works|you can assume that the block cipher used is a secure, deterministic block cipher with a block size
and key size of 256 bits.
Figure 1: The encryption scheme for CIT mode.
(And yes, you’re seeing that correctly|the CIT block cipher mode involves encrypting the encryption key
with itself…)
For parts (a) through (e), limit each of your answers to 100 words maximum|longer responses will
receive no credit. Part (f) has no word limit.
Question a) Draw a diagram of the decryption scheme for CIT mode.
Question b) Suppose Charles encrypts two equal-length plaintext messages, m1 and m2, using the same
key and the same initialization vector under CIT mode, to produce two ciphertexts, c1 and
c2. m1 and m2 di er in at least one bit at some index i.
Consider an adversary, Marcus, who can eavesdrop on the ciphertexts produced by Charles;
that is, Marcus can see c1 and c2. What, if anything, can Marcus learn about the underlying
plaintexts m1 and m2?
Question c) Suppose that exactly one bit at index j of a given ciphertext, c, which was encrypted in CIT
mode, is corrupted in transmission (that is, after the encryption is complete). When c is
decrypted using CIT decryption, which bits of the plaintext will be corrupted? Explain.
Question d) True or False: Encryption in CIT mode is parallelizable.1 Explain.
Question e) True or False: Decryption in CIT mode is parallelizable. Explain.
Question f) True or False: CIT mode is IND-CPA-secure. Explain.
(Hint: In a IND-CPA game, the key remains xed throughout the duration of the game, but
the IV used will be di erent for every encryption.)
1\Parallelizable” in the context of block ciphers comes from our discussion of ECB mode in Lecture 3: that is, for a given
input plaintext (split into xed-length blocks), we should be able to compute ciphertext blocks without having to wait for
previous ciphertext blocks (and thus we can parallelize the computation of the ciphertext blocks), and vice versa for decryption
of ciphertext blocks to plaintext blocks. Thus, we say encryption and decryption in ECB mode is parallelizable.
6
CS166 Computer Systems Security Spring 2021
Problem 6: Hash Functions, RSA Edition?
Only CS162 students are required to complete this problem.
In the Cryptography II lecture, we discussed how public-key digital signature cryptosystems generally form
signatures over a cryptographic hash of the intended message. Consider the standard RSA public-key cryp-
tosystem described below, which we’ll denote as RSAstd (pronounced as \RSA standard”):
• A standard RSA key-pair is formed via public key PK = hn; ei, where n is the \RSA modulus” (which
is a large prime number that de nes the key length) and e is some xed, small, prime number, and
private key SK = d, where d has the property (xe)d = x mod n for all x. (For the purpose of this
problem, exactly how these numbers are generated doesn’t matter.) In this problem, let’s assume
e = 3.
• In RSAstd, the signing operation SignSK(M) works by computing S = hash(M)d mod n, where S is
the signature on M. To verify the signature S, a third-party can execute Verify(M; S; PK), which
results in a correct veri cation if S3 = hash(M) mod n holds true. (Observe that the veri cation
algorithm does not require knowledge of d, only PK = hn; 3i.)
You can assume that the hash function satis es all of the properties of cryptographic hash functions.
Observe that RSAstd’s Sign operation is over the hash of the message M. We discussed in lecture how signing
a cryptographic hash has performance bene ts over signing the full message; speci cally, by signing a smaller
message (the hash), the signing operation is faster overall. However, it’s worth asking whether or not the
cryptographic hash has anything more to do with the security of the cryptosystem as well. For instance, if
we’re in a situation where all of our messages are smaller than the output length of hash, perhaps removing
the hash function will result in a more performant cryptosystem!
Thus, consider the following simpli ed scheme RSAsimple. In RSAsimple, SignSK(M) is exactly the same as
the corresponding operation from RSAstd, except without the application of the hash function. That is,
in RSAsimple, SignSK(M) produces the signature S = Md mod n and Verify(M; S; PK) checks if S3 = M
mod n holds true.
Question a) Zachary and Lilika are using RSAsimple to send messages with integrity guarantees to each
other. William is a network attacker who can inject, modify, and drop messages sent between
Zachary and Lilika, and William wants to trick Lilika into believing that Zachary sent a
message that Zachary did not.
Explain how William, who knows Zachary’s public key PK, can nd a (M; S) pair (and
give a speci c example of such a pair) such that S is a valid signature on M, even without
knowledge of Zachary’s secret key SK. (For part (a), the message M does not have to be
chosen in advance and can be gibberish.)
Question b) Bernardo is holding an auction for his personal collection of balloon animals. In this auction,
Zachary and Lilika submit bids to Bernardo, where their bids are signed using RSAsimple.
Each bid M is an integer (in dollars), and they will send their RSAsimple signature on M; that
is, they send S = Md mod n. Bernardo will accept whichever bid is highest (and will expect
that person to pay up however much they bid!).
Suppose Zachary sends a bid M (and its corresponding signature S) to Bernardo. Is it
possible for William to tamper with S in such a way that he can nd a new signature, S0,
that corresponds to a bid that is some x times as much as Zachary’s original bid? Explain.
(You can choose any value of x > 0, and you can assume that xM < n for your chosen x.)
Question c) Explain why the use of a cryptographic hash function in RSAstd prevents the forgery attacks
described in parts (a) and (b). (Hint: How do the properties|and which properties|of a
cryptographic hash function prevent these kind of attacks?)
7
CS166 Computer Systems Security Spring 2021
Problem 7: Counting for Cryptographers is Hard
Only CS162 students are required to complete this problem.
In the Cryptography II lecture, we described how one can convert a block cipher into a stream cipher using a
\counter” technique. This technique is actually more formally known as CTR block cipher mode encryption.
Speci cally, CTRlecture (to denote the scheme speci cally shown on Slide 17 in Lecture 3) works in the
following way:
• The encrypting user knows the secret key hk; ti, where k is a random bitstring and t is a \counter”
with a number of bits equal to the block size.
• Given a plaintext M = m0jjm1jj    jjmn􀀀1, the ciphertext generated by CTRlecture mode is
C = c0jjc1jj    jjcn􀀀1
where each ci = Ek(t + i)  mi.
• After encrypting a message M (not after each individual mi), the user updates their secret key hk; ti
to hk; t + 1i.
For this question, assume that the block size of the block cipher used is 32 bits.
Question a) True or False: CTRlecture mode is IND-CPA-secure against an attacker with polynomially
bounded resources. Explain. (Hint: The answer is False.)
Question b) Is there a way to easily x the security issues described in part (a)? Under your proposed
mitigation, are there any limitations on the number of times the encrypting user can use a
given secret key k under your new version of CTR mode? Explain. (Hint: How many times
can you use the secret key k?)
8
<a class=”btn btn-outline-primary w-100 btn-lg” href=”https://eliteacademicbrokers.com/main.php?get=order”>Order Now</a>

Calculate a fair price for your paper

Such a cheap price for your free time and healthy sleep

1650 words
-
-
Place an order within a couple of minutes.
Get guaranteed assistance and 100% confidentiality.
Total price: $78
WeCreativez WhatsApp Support
Our customer support team is here to answer your questions. Ask us anything!
👋 Hi, how can I help?