Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


COMP0025: Introduction to Cryptography

Coursework

Department of Computer Science

 

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

 


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? [2 marks]

(d)  Consider the following RSA public key:

-----BEGIN  PUBLIC  KEY-----

MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA1Zi1M5x6TUmjpf8sV4Op 3RpfjAs0CFvzjzE+C6HxJeMYj8KCZfyuBcVFwz5zaLOYULTPjzz+l98cVIZE5FN/ 2t+2mXFbJN+0vvi5A43JY9YHt81FMsc+MF7XQoLpXwUhkSw3TkrMIhjCmoexCB9V r+lUE3sWamEPh61d2pnwm2L2ZyU3BikNPgUUO6U7hd8h/urBIZLkDUsxOaD2HTYg HqHwLRELS3ewGbQqx9idEkKVtfZgpkIa8GiIpB1m+WqHX2zqlwyGLPAhzgCbBiP9 RpO/0DlI+jnZzuQ+Drd1zXyPSxezMKhoXspXoxuT0IP9CQaUmUnYUxsRFfiYvI1M jQIDAQAB

-----END  PUBLIC  KEY-----

 

Create a plaintext file containing the string Alan  Turing and encrypt it towards the above RSA public key. What is the ciphertext in base64 format?  [4 marks]

(e)  Consider the following Diffie-Hellman parameters and public key:

-----BEGIN  DH  PARAMETERS-----                                                                     MIGHAoGBAL0S3BTNhjlcy2ChLWCxyMzdMEoCY2MOu9VmxlGoiPcLNkUAmCptJD4F 1d95FOswggSgdDCTgaDWizZaefyhH8X1bYNqNrtUyZVjw1KjSzSt/Cq0Cy7h0BvI qtmfviCcAnovb3CgAp9WuLmagruqv+s2/SgpmebHQAIW/qnH2DMLAgEC                -----END  DH  PARAMETERS-----

-----BEGIN  PUBLIC  KEY-----

MIIBIDCBlQYJKoZIhvcNAQMBMIGHAoGBAL0S3BTNhjlcy2ChLWCxyMzdMEoCY2MO u9VmxlGoiPcLNkUAmCptJD4F1d95FOswggSgdDCTgaDWizZaefyhH8X1bYNqNrtU yZVjw1KjSzSt/Cq0Cy7h0BvIqtmfviCcAnovb3CgAp9WuLmagruqv+s2/SgpmebH QAIW/qnH2DMLAgECA4GFAAKBgQCEUQc+0TuYPrnNP7KP/1tR1X0tV4B/GtbKrCFU 863vMPHzozchNvxz+uI2OJGet0evMnz7xCOoZ+w5fE00sldFegAwIaC4QW6BBZcO V2Twtbggz+95r7yKfNRM2ty0SV5CE8fdCeRBoMPver9gJk4uN7KyHFXWbOUzt9YR tiJVTQ==

-----END  PUBLIC  KEY-----

 

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.  [4 marks]


(f)  The following command sequence allows to download TLS certificates:

echo  |  openssl  s_client  -connect  HOST:PORT  |\

sed  -ne  ’/-BEGIN  CERTIFICATE-/,/-END  CERTIFICATE-/p’  >  certificate.pem Consider the following TLS certificate downloaded from a website:

-----BEGIN  CERTIFICATE-----

MIIE7zCCBJSgAwIBAgIQD9WF1Et9s39cPmU79LIm9zAKBggqhkjOPQQDAjBKMQsw CQYDVQQGEwJVUzEZMBcGA1UEChMQQ2xvdWRmbGFyZSwgSW5jLjEgMB4GA1UEAxMX Q2xvdWRmbGFyZSBJbmMgRUNDIENBLTMwHhcNMjAwNzA0MDAwMDAwWhcNMjEwNzA0 MTIwMDAwWjBmMQswCQYDVQQGEwJVUzELMAkGA1UECBMCQ0ExFjAUBgNVBAcTDVNh biBGcmFuY2lzY28xGTAXBgNVBAoTEENsb3VkZmxhcmUsIEluYy4xFzAVBgNVBAMT DmNsb3VkZmxhcmUuY29tMFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEG8yJrKWY lPQG6J3KgKis4XeOY3/cL5qEQ+mP3zgl4ylipgX7/XJLiQ5361b8fJhj/UjIudFJ 0xL9ibOrs6JTDqOCAz4wggM6MB8GA1UdIwQYMBaAFKXON+rrsHUOlGeItEX62SQQ h5YfMB0GA1UdDgQWBBTUxXwi2+exV6YsgMeQajzIlUvqnTBxBgNVHREEajBoghAq LmNsb3VkZmxhcmUuY29tgg5jbG91ZGZsYXJlLmNvbYIUKi5kbnMuY2xvdWRmbGFy ZS5jb22CFCouYW1wLmNsb3VkZmxhcmUuY29tghgqLnN0YWdpbmcuY2xvdWRmbGFy ZS5jb20wDgYDVR0PAQH/BAQDAgeAMB0GA1UdJQQWMBQGCCsGAQUFBwMBBggrBgEF BQcDAjB7BgNVHR8EdDByMDegNaAzhjFodHRwOi8vY3JsMy5kaWdpY2VydC5jb20v Q2xvdWRmbGFyZUluY0VDQ0NBLTMuY3JsMDegNaAzhjFodHRwOi8vY3JsNC5kaWdp Y2VydC5jb20vQ2xvdWRmbGFyZUluY0VDQ0NBLTMuY3JsMEwGA1UdIARFMEMwNwYJ YIZIAYb9bAEBMCowKAYIKwYBBQUHAgEWHGh0dHBzOi8vd3d3LmRpZ2ljZXJ0LmNv bS9DUFMwCAYGZ4EMAQICMHYGCCsGAQUFBwEBBGowaDAkBggrBgEFBQcwAYYYaHR0 cDovL29jc3AuZGlnaWNlcnQuY29tMEAGCCsGAQUFBzAChjRodHRwOi8vY2FjZXJ0 cy5kaWdpY2VydC5jb20vQ2xvdWRmbGFyZUluY0VDQ0NBLTMuY3J0MAwGA1UdEwEB /wQCMAAwggEDBgorBgEEAdZ5AgQCBIH0BIHxAO8AdQD2XJQv0XcwIhRUGAgwlFaO 400TGTO/3wwvIAvMTvFk4wAAAXMbCD9JAAAEAwBGMEQCIGvGTxZeBYgdbs+vnp0c 9y45gwRMOZnKz4eE1d4LdagwAiARwrwO1jORk0C5/VTj+RPxK5HRwK169bwkdVL8 0pB7lAB2AFzcQ5L+5qtFRLFemtRW5hA3+9X6R9yhc5SyXub2xw7KAAABcxsIP38A AAQDAEcwRQIhAMWV1BR5WmEVEfpfyBAJErAa7zbUmn9yqwLzdVDesRcuAiAePxqr LJBQ5ysyisJOIt6GzfUOg1rDmsgmmdj7zz9lgDAKBggqhkjOPQQDAgNJADBGAiEA 42x0wUe7wq/QbXOvyaYX8IXvORQ0L+/cOM4TrVCEG9ECIQDaDyZCKGGpi+MqdDmy dLIonPk4USKu95+gu0CQPQTglQ==

-----END  CERTIFICATE-----

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]


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.



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  Imi I = b for all 1  ≤ i  ≤ n.   Compute chaining values hi   = G(mi  < hi l 1 ) for all 1 ≤ i ≤ n with h0  = 0b .  Finally, set H(m) := hn .

 

 

Is H collision-resistant?  Justify your answer either by constructing a collision or by providing a security proof. [7 marks]


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  8   {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   := 0b  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 e N:

Pr[k 8  Gen(1n ); (m, t) - ATag k ( _) (1n ) : m  o A Verifyk (m, t) = 1] = negl(n) ,

where o 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]


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]