COMP0025: Introduction to Cryptography
Coursework
Department of Computer Science
University College London
Released: December 14, 2021
Due: January 11, 2022 at 16:00 UK time
Instructions
This assignment is part of the mandatory assessment of the COMP0025: Introduction to Cryptography
module and will count 25% towards your final overall mark.
Assignment submission is due via Moodle through the TurnItIn interface on January 11, 2022 at 16:00
UK time. Late submissions will be accepted with deductions according to UCL’s late submission policy.
Only PDF submissions that are typeset with LaTeX, e.g., via https://www.overleaf.com/edu/ucl,
will be accepted. Submissions must not include screenshots, e.g., of handwritten or drawn solutions,
unless explicitly permitted. Students with disability accommodations are excluded from this requirement.
This assignment is open note, open book, and open course resources. You must identify sources as
accurately and fully as possible. UCL plagiarism policies will be strictly enforced. For more details, see
http://www.ucl.ac.uk/current-students/guidelines/plagiarism.
You are not allowed to consult other people (outside of course staff) on this work. Each student has to
work on the assignment individually.
Your answers will be judged in terms of their quality, the depth of understanding, and also their brevity.
Explain your answers clearly, but succinctly. Partial credit may be awarded.
The assignment has a maximum of 100 marks allocated as follows:
Q1 Q2 Q3 Q4 Q5 Total
Marks 20 20 20 20 20 100 marks
1
Question 1: Cryptographic Software [20 marks]
OpenSSL is a widely used open source cryptography library that allows you to generate keys, encrypt
messages, sign messages, etc. In many cases the OpenSSL tool comes already pre-installed with your
operating system. If that’s not the case, you can usually install it through your favorite package manager
or download it, e.g., at https://www.openssl.org/. Make sure you have the latest stable version
OpenSSL 3.0.0 from September 07, 2021. Use OpenSSL to answer the following questions:
(a) Save the two passphrases enc-cryptorulez2600 and mac-cryptorulez2600 in the text files
enc.pw and mac.pw, respectively. What are the SHA256 fingerprints of these passphrases?
[2 marks]
(b) You received the following encrypted message:
pCSUbwVFZxGM1SsJCtQRZmDcd5zyC2ygMVG64oJjtoNYGGzQnhI=
This ciphertext was produced with the ChaCha20 stream cipher using the SHA256 fingerprint
of enc-cryptorulez2600 as a key and c0dec0dec0dec0dec0dec0dec0dec0de as an IV. What
was the message? [2 marks]
(c) Next to the above ciphertext you also received the following authentication tag for it:
b1086574bd1100947e32ed9e8f56be85cd49274b7e5b9669e126fda1b7a9c72a
It was created with the HMAC-SHA256 message authentication code using the SHA256 fingerprint
of mac-cryptorulez2600 as a key. Is it correct? What OpenSSL command did you use to verify
it?
Assume the DH parameters and public key are stored in files dhp.pem and dhpub1.pem, respec-
tively. Describe the steps to setup your own DH key pair and do a DH key exchange using the
given DH parameters and public key.
Answer the following questions:
(i) Which HOST and PORT parameters were used to download the above certificate? [2 marks]
(ii) What is the certificate’s serial number? [1 mark]
(iii) Until when is the certificate valid? [1 mark]
(iv) What signature algorithm was used to sign the certificate? [1 mark]
(v) What is the certificate’s fingerprint? [1 mark]
3
Question 2: Semantic Security [20 marks]
Let λ denote a security parameter. Let Π1 and Π2 be two encryption schemes for which it is known
that at least one of them is IND-CPA secure with respect to λ. However, you do not know which one
is definitely IND-CPA secure and which one may be not.
(a) Build a correct and IND-CPA secure encryption scheme Π using Π1 and Π2. [8 marks]
(b) Prove that Π is IND-CPA secure with respect to λ. [12 marks]
Remark: Both encryption schemes can be assumed to leak the exact length of the input message.
4
Question 3: Hash Functions [20 marks]
(a) Let E : {0, 1}λ × {0, 1}b → {0, 1}b be a block cipher. Assume λ = b. Consider the following
compression function:
f(x, y) = E(x, x⊕ y)⊕ x .
Is f second-preimage resistant? Justify your answer either by constructing a collision or by
providing a security proof. [6 marks]
(b) Let F and G be hash functions one of which one is collision-resistant and let
H(x) = F (G(x) ‖ x) ‖ G(F (x) ‖ x) .
Is H collision-resistant? Justify your answer either by constructing a collision or by providing a
security proof. [7 marks]
(c) Let G be a collision-resistant hash function with output length b and let H denote a function which
iterates G in a CBC-like manner as follows: Parse input message m as pad(m) = m1, . . . ,mn
such that |mi| = b for all 1 ≤ i ≤ n. Compute chaining values hi = G(mi ⊕ hi?1) for all
1 ≤ i ≤ n with h0 = 0b. Finally, set H(m) := hn.
G G G
0b
m1 m2 mn
hn
Is H collision-resistant? Justify your answer either by constructing a collision or by providing a
security proof. [7 marks]
5
Question 4: Message Authentication Codes [20 marks]
(a) Let MAC = (Gen,Tag,Verify) be a fixed-length CBC-MAC for messages of length s blocks each
of size b bits. Prove or disprove that the following CBC-MAC variants are EUF-CMA secure.
(i) MAC.Tagk(m) uses a random IV t0
$←? {0, 1}b and returns t := (t0, ts) as the CBC-MAC
tag where ts is output of the last block cipher call. [5 marks]
(ii) MAC.Tagk(m) uses the IV t0 := 0
b and returns t := (t1, . . . , ts) as the CBC-MAC tag,
where ti is the output of the i-th block cipher call. [5 marks]
(b) Weak existential unforgeability under adaptive chosen-message attacks (wEUF-CMA) is a variant
of the EUF-CMA security notion of a message authentication code MAC = (Gen,Tag,Verify)
which requires that for all PPT adversaries A there is a negligible function negl such that for all
n ∈ N:
Pr[k
$←? Gen(1n); (m, t)← ATagk(·)(1n) : m /∈ Q ∧ Verifyk(m, t) = 1] = negl(n) ,
where Q is the set of messages the adversary has queried to its message authentication oracle
Tagk(·). Note that A does not have access to the verification oracle here unlike in EUF-CMA.
Suppose that MAC is wEUF-CMA secure. Separate the two security notions by constructing a
message authentication code MAC′ = (Gen′,Tag′,Verify′) using MAC that is also wEUF-CMA
secure, but is not EUF-CMA secure. Argue why it is wEUF-CMA secure. Describe an attack that
shows it is not EUF-CMA secure. [10 marks]
6
Question 5: Digital Signatures [20 marks]
(a) Let DSRSA = (Gen,Sign,Verify) denote the textbook RSA signature scheme with n = 77 and
e = 11.
(i) What are φ(n) and d? [2 marks]
(ii) What is the message for signature σ = 3? [2 marks]
(iii) Given e = 59, what is the signature for message m = 3? [2 marks]
(b) Let DSRSA = (Gen,Sign,Verify) denote the textbook RSA signature scheme. Assume we have
two public keys pk1 = (e1, n) and pk2 = (e2, n) for DSRSA where e1 and e2 are coprime. Let
m1,m2 be two messages in Zn. Suppose there exists a signature σ that is valid on m1 and m2
under pk1 and pk2, respectively. Describe how you can find σ. [7 marks]
(c) Consider the FDH-RSA digital signature algorithm. Show that an adversary can break EUF-CMA
security of FDH-RSA if it can find collisions in the used hash function H. [7 marks]