CS 4640: Assignment 1
Basic security concepts and applied cryptography
February 19, 2019
Guidelines
Please read and follow the guidelines articulated here.
Groups. As stated in class, on the website, and on Piazza, this assignment will be done in groups of 5 or
- Here are the groups for this assignment.
Group Members - Chris Schulstad, Sriram Srinivasan, John Thiede, Anthony Tran, Elizabeth Valentine
- Derek Choi, Joyanta Debnath, Donny Dong, Yongheng Fan, Owen Kueter, Joshua Magri
- Spencer Gritton, Bryce Kosinski, Evan Raab, Tucker Snider, Daniel Stutz, Bincheng Wang
- Benjamin Alston, James Bongiovanni, Mercury Cagley, James Glowacki, Greg Mich,
Zichen Zheng - Jessi Bierbaum, Connor Eschrich, Jake Espey, Ian Gradert, Ziliang Luo, Xiao Song
- Logan Brown, Ziqing He, Xin Man, Yao Wang, Jiahua Zhang, Gongyu Zhou
If you are unable to get in touch with any of your team-mates, send me an email ASAP and I’ll put you in
touch. I will take complaints of discrimination and harassment extremely seriously and these will be reported
to the appropriate authorities. You are expected to treat your classmates with respect and kindness.
Submission. The following rules will apply for all submissions.
The assignment is due on April 9th at 11:59:00 pm on ICON.
Late submissions will result in a 10% penalty per day.
Each team will only submit one set of solutions to be graded.
You are expected to be able to explain all answers in your submission.
Non-PDF or non-typeset submissions will face a 10% penalty.
Group member feedback. Each team member may also complete the following series of questions about
their team mates and group experience: https://goo.gl/forms/8LbhMqqS... You will receive a
1% bonus for completing this review. Submissions will not be accepted after May 1st.
1 - Basic security concepts (10 points)
- True or False (1 point each).
(a) If Tyrion uses a browser with no code vulnerabilities and uses a unique, long password for every
website he visits, then he will be safe against phishing attacks.
(b) Threat modeling should be done only for the most powerful adversaries. After all, if we’re secure
against them, we’re also secure against every one else.
(c) Your home Wi-Fi network is an attack surface that is exploitable to an attacker seeking control
of your mobile device.
(d) Requiring users to have long passwords and biometric authentication on their mobile phones is
one way to prevent some of the threats posed by a thief that has no drawbacks.
(e) If the system is highly valuable, it is safe to assume that humans will correctly play their roles in
a security mechanism. - Threat modeling (5 points). You need to build a video sharing platform which monetizes videos
by placing ads on them. Revenue generated by a video depends on the number of views received by
the video. These payments are made by the advertisers on your platform. Generated revenue is split
between your platform, the content creator, and any other copyright holders in the video. Perform an
in-depth threat model of this system. - Historical ciphers (10 points)
Write code to decrypt the following alpha-numeric and alphabetic English language strings. Show the
decrypted strings and their keys. Note: You will be required to explain and demo your code in class after
submission. - (3 points) Hint: This string is alpha-numeric.
9QXX P1ZQ TQ4Q’5 G 21UZ65 - (7 points) Hint: This string only has the English alphabet.
XITOVEYRLKKGFIWYYSZVGMOYCXJOCUOVCXSQDVYXKCBWRYPMFIWYYIXSUD
LCBYJOWYXHQYHMSEDEPJMSKWMRWILDWURERSQRRMLUMLQSDISSGSSVHLDK
CDXFSWDBSKKRWYXFOVEECGTYQDAYXRYDIJVCMELMGMKPICVMLQKMDXYWEI
OCMEYLNIPCXYXHLOZCBKMXRYQMTOCMEYNXITOVEYRLKPCDCMEHMGRLOZCB
KMXRYBYLKVMERBKRBNIQOVRISSXITOVEYRLKQYUIWYYABCLOZCBKMXRYCE
WQSMNFWORCFIPQSLXEROPJKPGOELNLSBXWYYUOZCURMGRCKGFYXFOVDYVQ
YPMXKWYYPRIYBXQLICXEARMLQFSDCMEVCDSMCLWDSQKCGDMLCMBOACLSRR
OLYAURERCFCOREYMLQSLGIIXSUDLCQEKOELNACBIEYRLKTJKCGDELNMDIS
SKWIWIFYAGWJCOPGXKBYRRDIJVQCISSBIRYSZVMLNXMCICXITOVEYRLKKG
FIWYYSZRCFIPQSLXEJOXWYYBYALXITOVEYRLKVSXEPYYLNELNHCCIPDCME
RCFIPQSLXEKKOCISSMVWXITOVEYRLKWYIKMYHZIILOZCBKMXRYDIJVEJSI
YXHFEVRISSXITOVEYRLKKGFIWYYSZRCFIPQSLXEJOXWYYBYALXITOVEYRL
KVSXEPYYLNELNHCCIPDCMERCFIPQSLXEKKOCISSMVWXITOVEYRLKWYIKMY
HZIILOZCBKMXRYDIJVEJSIYXHFEVRISSXITOVEYRLKKGFILOZCBKMXRYQM
TOKGFIWYYSZSMRRCFIPQSLXEESZCXITOVEYRLKKGFIESZCISSETUOZCURM
GRCKGFYXFOVDYVQYPMXKWYYPRIYBXQLICXEARMLQFSDCMEVCDSMCLWDSQK
CGDMLCMBOACLSRROLYAURERCFCOREYMLQSLGIIXSUDLCQEKOELNACBIEYR
LKTJKCGDMHEWRGELXEROPJISSRSUSQDOIJSREQSRDEKKOCISSERBOVQDEL
NRCFIPQSLXEESZCISSETLOZCBKMXRYVIRISSNSUXRCFIPQSLXEPERYBSSX
2
HYXHBOWCBXWYYLOZCBKMXRYWEIOCMEGPIRCFIPQSLXEQKCEYSBLCCXITOV
EYRLKXCVPYVMCKRBRYPDCMERCFIPQSLXEESZCISSETLOZCBKMXRYVIRISS
NSUXRCFIPQSLXEPERYBSSXHYXHBOWCBXWYYLOZCBKMXRYWEIOCMEGPIRCF
IPQSLXEQKCEYSBLCCXITOVEYRLKXCVPYVMCKRBRYPDCMERCFIPQSLXEESZ
CISSETLOZCBKMXRYVIRISSNSUXRCFIPQSLXEPERYBSSXHYXHBOWCBXWYYL
OZCBKMXRYWEIOCMEGPI - Perfect secrecy and definitions of security (15 points)
- (5 points) Prove that the WEP protocol is CPA-secure.
- (5 points) Show that when the number of queries permitted by the CPA attacker is ≥ 5K, common
implementations of WEP are practically broken. Assume WEP is being used in 64-bit mode. - (5 points) Assume that we require only that an encryption scheme (Gen, Enc, Dec) over a message
space M satisfies the following: for all m ∈ M, the probability that Deck(Enck(m)) = m is at least t.
Show that perfect secrecy (as defined in class) can be achieved even when |K| < |M| as long as t ≥ 1.
What is the lower bound on the required size of K. - Block ciphers (15 points)
- (5 points) Consider a variant of the CBC-mode encryption where the sender simply increments the IV
by 1 each time a message is encrypted (rather than choosing a random IV). Show that the resulting
scheme is not CPA-secure. - (5 points) Show that the CBC-mode encryption is not CCA-secure.
- (5 points) Let Π1 = (Gen1, Enc1, Dec1) and Π2 = (Gen2, Enc2, Dec2) be two encryption schemes
for which it is known that at least one is CPA-secure. The problem is that you do not know which one
is CPA-secure. Show how to construct an encryption scheme Π which is guaranteed to be CPA-secure
as long as at least one of Π1 or Π2 are CPA-secure. Provide an overview of your proof (similar level of
detail to our in-class proofs).
Hint: Generate two plaintext messages from the original plaintext message so that knowledge of either
one of the parts reveals nothing about the plaintext, but knowledge of both yields the original plaintext. - Integrity (15 points)
- (10 points) Let F be a pesudorandom function. Show that each of the following message authentication
codes is insecure.
(a) (5 points) To authenticate a message m = m1|| . . . ||ml
, where mi ∈ {0, 1}
n, compute tag :=
Fk(m1) ⊕ . . . ⊕ Fk(ml), and send < tag >.
(b) (5 points) To authenticate a message m = m1|| . . . ||ml
, where mi ∈ {0, 1}
n, select r ← {0, 1}
n at
random and compute tag := Fk(r) ⊕ Fk(m1) ⊕ . . . ⊕ Fk(ml), and send < r, tag >. - (5 points) Let H1 and H2 be two hash functions. We define a third hash function H3 such that
H3(x) = H1(x)||H2(x). Prove that as long as at least one of H1 and H2 is collision resistant, then H3
is also collision resistant.
3 - Public-key cryptography (15 points)
- (5 points) Describe in detail a man-in-the-middle attack on the Diffie-Hellman key-exchange protocol
where the adversary ends up sharing a key kA with Aisha and a different key kB with Beth, and Aisha
and Beth cannot detect that anything has gone wrong. How can they try to prevent this scenario from
arising? - (5 points) Consider the following key-exchange protocol:
Maya chooses k, r ← {0, 1}
n at random, and sends s := k ⊕ r to Rashida.
Rashida chooses t ← {0, 1}
n at random and sends u := s ⊕ t to Maya.
Maya computes w := u ⊕ r and sends it to Rashida.
Maya outputs k and Rashida computes w ⊕ t.
Show that Rashida and Maya output the same key. How secure is this scheme? Can an adversary
reconstruct the key by simply observing the public transcript? - (5 points) Generate an OpenSSL RSA public and private key pair. Publish your public key on your
ICON user profile. Submit a file containing your name and sign it using the RSA implementation in
the OpenSSL library. - Credit reel (20 points)
You get 20 points just for submitting this assignment with a well written and formatted credit reel! Use the
following section to tell us what references you used to complete this assignment (e.g., stackoverflow posts,
wikipedia, etc.), who helped you IRL or on Piazza, and which team-mates did which parts of the assignment.
WX：codehelp
