CY 5770 Software Vulnerabilities and Security

Midterm Exam

March 6, 2021

Instructions:

1. This is a take-home exam. You have a full week to work on it, without any limitations. (It should not

take you that much time. The exam was intended to be finished in several hours.)

2. This is also an open book exam. You are allowed to use books, all course material, as well as your

laptops and smart devices.

3. This exam should reflect your own work, so other than Tamara, you are not allowed to ask anyone

else for help/advice/clarification.

4. Please read problems carefully before solving them.

5. Please attempt all problems. For each problem below, explain how you obtain your answer, and include

relevant code.

6. Your submissions are due by 11:59pm on Saturday, March 13, 2021. If this deadline does not

work for you, please let Tamara know as soon as you can.

Deliverables: Please upload your solutions using Canvas. Please consolidate all of your written solutions

into a single .pdf file, and don’t forget to include all relevant code that you have used to solve the assignments.

You are welcome to use any programming language that you prefer to solve the problems.

A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z

13 14 15 16 17 18 19 20 21 22 23 24 25

Table 1. Mapping of alphabets to numerals

Good luck!

Problem 1 (Classical Cryptosystems – 35 points)

Wanda is studying some ancient books of spells. One of these old manuscripts is encrypted using the

following symmetric key cryptosystem.

Given a plaintext of some length n, this text is written downwards and diagonally on successive

positions of an imaginary table, with the number of rows in the table equal to x. The ciphertext

message is then read off by reading rows left-to-right and top-to-bottom.

For example, given a plaintext Scarlet Witch, with lenght n = 12, and the number of rows in our

imaginary table set to x = 3, the table would now look like:

S ? ? R ? ? T ? ? T ? ? ? C ? ? L ? ? W ? ? C ? ? ? A ? ? E ? ? I ? ? H

Table 2. Imaginary table used for encryption in Problem 1.

The corresponding ciphertext would be: SRTTCLWCAEIH

Your tasks:

(a) (5 points) What is the cryptographic key (secret) in the described symmetric key cryptosystem?

(b) (10 points) Is this a well-defined cryptosystem, i.e., given a ciphertext of length n, can an intended

recepient correctly decrypt it, if they know the crypto secret?

(c) (10 points) Is the described cryptosystem secure? If yes, please explain what is the salient feature

that makes it secure. If not, please explain how would an attacker break it.

(d) (5 points) Given a plaintext:

There are six infinity stones

with length n = 25, please encrypt it using the descirbed cryptosystem with x = 5.

(e) (5 points) Implement a function (method) that takes as inputs:

– Plaintext N of length n, – Number of rows in our imaginary table, x

and produces a ciphertext encrypted using the described cryptosystem, for any message where n <

250 characters.

Problem 2 (Public Key Cryptography – 10 points)

Wanda and Vision are big fans of public key cryptography, in particular of the RSA cryptosystem.

They are introducing RSA cryptosystem to Billy and Tommy, and Billy and Tommy are quick learners,

and very creative. They propose that a small size public key e would greatly improve computational

complexity of RSA-based cyrptographic tools.

Vision sends them to examine the following two resources, and gives them a few questions to answer, to

make sure that they understand possible problems:

– Coppersmith’s attack: https://en.wikipedia.org/wiki/Coppersmith%27s attack

– ROCA vulnerability https://en.wikipedia.org/wiki/ROCA vulnerability

Your tasks:

Please help Billy and Tommy answer the following two questions. In both questions, you are not expected

to derive anything, or to use any theorems and proves. Vision is looking for a simple (2-3 sentences)

explanation.

2

(a) (5 points) Examine a part talking about Coppersmith’s short-pad attack, and provide a high-level

explanation why randomized padding of short plaintext messages, when RSA public key is set to

e = 3 may not work.

(b) (5 points) What primality testing format is the root cause of ROCA vulnerability?

Problem 3 (Hash Functions – 15 points)

When it comes to ancient books of magic spells, spell integrity (data integrity) is always a concern for

Wanda. Once upon a time, the following cyptographic hash function was proposed as a way to ensure

spell integrity:

(a) Given some plaintext spell (message), m = m1m2 . . . mn, first encrypt it using a substitution

cipher with the following substitution table:

a b c d e f g h i j k l m n o p q r s t u v w x y z C Z B Y A X G V F U E T J S I R H Q N P M O L K D W

Table 3. Substitution table used in Problem 2.

(b) Next, convert the obtained ciphertext y = y1y2 . . . yn into a number using conversion table 1.

(c) Remove the first five elements from the obtained string of numbers, and add value 2 to each remaining

element in the string.

(d) Then, multiply the remaining numbers, and subtract number 587 from the result.

(e) Steps (c) and (d) can be described with the following formula:

h(y) = Yni=6

(yi + 2)!

587

(f) Finally, release a hash output h(y).

Your tasks:

(a) (10 points) Is the described hash function preimage resistant? Please explain your reasoning.

(b) (5 points) Given some cryptographic hash function, if the set of possible hash outputs is limited

to the set of cardinality 106

, how many times would an attacker have to query that hash function

before they create a collision in hash outputs with probability of at least P = 0.5? Please show your

work.

Problem 4 (Key Management Problem – 40 points)

Wanda, Tommy and Billy need a way to securely communicate across the multiverse. They have decided

to use symmetric key cryptography, but they need to occassionally refresh their shared cryptographic

secrets. They have devised the following scheme:

(a) Wanda chooses large prime numbers pT and pB, and their corresponding generators αT and αB. She

sends (pT , αT ) to Tommy, and (pB, αB) to Billy.

(b) Wanda chooses two secrets, aW1 and aW2, and Billy and Tommy choose their own individual secrets,

aB and aT .

(c) Wanda sends message αaW1 B (mod pB) to Billy, and αaW2 T

(mod pT ) to Tommy.

(d) Tommy sends message αaTT

(mod pT ) to Wanda, and Billy sends αaBB (mod pB) to her.

(e) At this point, Tommy and Wanda can securely communicate using secret key αaT aW2 T

(mod pT ), and

Billy and Wanda can securely communicte using secret key αaBaW1 B (mod pB). However, Billy and

Tommy cannot communicate securely with one another, and Wanda cannot encrypt a message only

once, and send it to both boys.

3

Your tasks:

Please answer the following questions:

(a) (10 points) Propose a secure way to establish one shared cryptographic secret between Wanda, Billy

and Tommy. Your protocol should continue on the already outlined steps, and it should utilize the

already available cryptographic secrets between Wanda and Billy, and Wanda and Tommy.

(b) (10 points) Represent graphically the entire key exchange protocol, including steps (a)–(b).

(c) (10 points) Are steps (a)–(e) resilient to Billy impersonation attacks? Please explain your

reasoning.

(d) (10 points) Are there any attacks that can be mounted against the proposed key exchange mechanism?

If no, please explain what makes the proposed mechanism secure. If yes, please explain how the attack

would work.