Introduction to IT Security  Homework #1

CS306: Introduction to IT Security 
Homework #1

Instructions
Please carefully read the following guidelines on how to complete and submit your solutions.
1. The homework is due on Friday, September 28, 2018, at 11:59pm. Late submissions are
accepted subject to the policy specified in the course syllabus. Starting early always helps!
2. Solutions are accepted only via Canvas, where all relevant files should be submitted as a
single .zip archive. This should include your typed answers as a .pdf file and the source code
of any programming possibly used in your solutions.
3. Unless otherwise specified, for any assignment involving programming you may use any programming language of your choice. If asked, you should be able to explain details in your
source code (e.g., related to the design of your program and its implementation).
4. You are bound by the Stevens Honor System. Collaboration is not allowed for this homework.
You may use any sources related to course materials, but information from external sources
must be properly cited. Your submission acknowledges that you have abided by this policy.
5. This assignment provides a 10% extra credit opportunity.
Problem 1: Remind me, what is your name? (10%)
If I have a chance to get to learn your name, I need to remind myself outside class. Take a fresh
picture of your smiling face and handin it in .jpeg format.
Problem 2: Shared or forgotten keys? (20%)
Long ago, Alice and Bob shared an n-bit secret key but now they are no longer sure they still
possess the same key. To verify that the key ka currently held by Alice is the same as the key kb
currently held by Bob, they need to communicate over an insecure channel.
(1) Which two basic security properties should be considered in the design of a secure protocol
for solving the above problem and why these properties become relevant in this setting?
Hint: Consider two cases: Attacker Eve who only eavesdrops on the channel and attacker
Mallory who can do more than eavesdropping.
1
Homework #1 CS306 - Introduction to IT security
(2) Suppose that Alice and Bob use the following protocol to check if they store the same secret.
1. Alice generates a random n-bit value r.
2. Alice computes x = ka ⊕ r, and sends x to Bob.
3. Bob computes y = kb ⊕ x and sends y to Alice.
4. Alice compares r and y. If r = y , she concludes that ka = kb—that is, Alice and Bob share
a secret key.
Does the above protocol satisfy the two security properties identified in question (1)?
Problem 3: Perfect or imperfect ciphers? (30%)
(1) Assume that an attacker knows that a user’s password is either p1 = abcd or p2 = bedg.
Say the user encrypts his password using the Vigen´ere cipher, and the attacker sees the resulting
ciphertext c. Show how the attacker can determine the user’s password, or explain why this is not
possible, when the period t used by cipher is 1, 2, 3, or 4 respectively.
(2) Show that the mono-alphabetic substitution cipher is trivial to break when the attacker
launches a chosen-plaintext attack. How much chosen plaintext is needed to recover the entire
secret key? What is the shortest chosen single-message plaintext that you can find, which is a valid
English message and would successfully recover the key? Finally, under which conditions, and why,
is the mono-alphabetic substitution cipher perfectly secure (against a ciphertext-only attacker)?
Problem 4: Crypt-analyze this! (50%)
I just discovered that two of my TAs, Alice and Bob, have been secretly communicating with each
other in our common group chat that we use for course matters. I often see unintelligible short
texts on my screen to which I didn’t pay attention, but now I suspect they plan behind my back.
I am pretty sure they make use of one-time pad encryption with the following parameters: The
message space consists of English messages which are 33 characters long, where only letters (of
either case) and spaces are used. To ease key management, they change their shared key only every
midnight. Please help me break their code!
Below are eleven ciphertexts (in hex format) that they exchanged just minutes before our class
this week, i.e, on September 11, 2018 (in this order).
2d0a0612061b0944000d161f0c1746430c0f0952181b004c1311080b4e07494852
200a054626550d051a48170e041d011a001b470204061309020005164e15484f44
3818101500180b441b06004b11104c064f1e0616411d064c161b1b04071d460101
200e0c4618104e071506450604124443091b09520e125522081f061c4e1d4e5601
304f1d091f104e0a1b48161f101d440d1b4e04130f5407090010491b061a520101
2d0714124f020111180c450900595016061a02520419170d1306081c1d1a4f4601
351a160d061917443b3c354b0c0a01130a1c01170200191541070c0c1b01440101
3d0611081b55200d1f07164b161858431b0602000454020d1254084f0d12554249
340e0c040a550c1100482c4b0110450d1b4e1713185414181511071b071c4f0101
2e0a5515071a1b081048170e04154d1a4f020e0115111b4c151b492107184e5201
370e1d4618104e05060d450f0a104f044f080e1c04540205151c061a1a5349484c
2
Homework #1 CS306 - Introduction to IT security
(1) Write down the 11 plaintext messages that were exchanged. You may write a program that
will help you with your cryptanalysis. In designing your program, remember that most likely spaces
will be among the most frequent characters in the plaintexts, and carefully observe what their role
may be in the mapping from plaintexts to ciphertexts. Explain what your cryptanalysis strategy
is and what algorithm your program implements.
(2) Rather than randomly generating (and securely exchanging) a new key every midnight, the
TAs created an algorithm to automatically generate the new key pseudorandomly using the current
(i.e., previous day’s) key as input. That is, they replace the current key ki with the new key
ki+1 = SHA256(ki)k00100001, where k denotes concatenation. What is the key the TAs will be
using in two weeks’ time from the time I intercepted the above ciphertexts, i.e., during our class
on September 25, 2018?
3