COMP2700 ASSIGNMENT 2 (Version 13/10/2019)
1
COMP2700 ASSIGNMENT 2:
APPLICATIONS OF CRYPTOGRAPHY
SUBMISSION DEADLINE: Sunday, October 27th, 2019 – 11:55pm (AET).
SUBMISSION PROCEDURE: See the Wattle page for the course
OBJECTIVES:
The main objective of this assignment is for the students to understand the applications of basic cryptographic
operations and to analyse potential weakness in the design and implementation of these operations in
applications. In particular, the students will learn how improper use of cryptographic operations can give rise
to vulnerabilities even if the cryptographic operations are individually secure.
PROBLEM DESCRIPTION:
There are four problems in this assignment, described below, with the total possible marks of 100.
In this assignment, each student is assigned a unique set of files. These files are contained in the provided
‘assignment2-files.zip’on the Wattle page for this assignment. Unzip this file. You will see that it contains 106
folders, each of which is named based on a Uni ID. The name of the folder containing your assigned files is the
same as your Uni ID. These files form a critical part this assignment and your answers will be assessed based
on your individually assigned files.
For example, if your Uni ID is ‘u1234567’ then your individually assigned files are contained in the folder
named‘u1234567’. In this folder, you will find four sub-folders, named‘problem1’,‘problem2’,‘problem3’,
and‘problem4’; each contains files related to, respectively, Problem 1, Problem 2, Problem 3 and Problem 4
described below. Here is an example of the directory structure for a student with Uni ID‘u1234567’.
u1234567
├── problem1
│ └── cipher.txt
├── problem2
│ └── cipher.bin
├── problem3
│ ├── file1.bin
│ ├── file2.bin
│ ├── mac1.bin
│ └── mac2.bin
└── problem4
├── file1.bin
└── file2.bin
We shall refer to these directories/files in the problem description below.
In addition to the assignment files above, you are also given some sample files, contained in sample-files.zip,
also available on the Wattle page. The sample files there are to give you examples of plaintexts and
ciphertexts, with the necessary key materials and Python scripts used to generate the ciphertexts from the
COMP2700 ASSIGNMENT 2 (Version 13/10/2019)
2
plaintexts. You may find these useful in testing your attack methods. More details can be found in the README
file in contained in sample-files.zip.
In each problem below, you are required to submit one or two artefacts (binary files or text files) and a report
component, containing a description of your attack methods (except for Problem 1, where no report
components are required). The report components should be combined into a single PDF file.
PROBLEM 1. SUBSTITUTION CIPHER (25 MARKS)
In this problem you are asked to decrypt an encrypted text file in problem1/cipher.txt. The plaintext that
corresponds to this encrypted file is extracted from an English text, and is encrypted using a substitution
cipher. You can assume that the plaintext contains only lower-case Latin alphabets, ranging from‘a’to‘z’, and
whitespace characters (new lines and space). The whitespace characters (spaces, new lines) are not encrypted.
Punctuation marks have been removed and replaced with spaces. You can assume that most words are
correctly spelled (but they may be following British English spelling or American English spelling), but there
may be a small number of misspelled words or abbreviated words.
You must provide answers to the following subproblems:
PROBLEM 1.A (12.5 MARKS). Provide the plaintext for the encrypted text in your assigned file
problem1/crypt.txt.
Artefact submission required: Submit your answer to Problem 1.A in a text file called P1A.txt.
PROBLEM 1.B (12.5 MARKS). Provide the substitution key that is used to encrypt the plaintext you
uncovered in Problem 1.A. The substitution key must be represented as a permutation of the alphabet string
‘abcdefghijklmnopqrstuvwxyz’. For example, if the substitution you found is the following mapping:
[a à h, b à m, c à o, d à x, e à a, f à c, g à e, h à d, i à f, j à i, k à j, l à k, m à b, n à n, o à p, p à
r, q à t, r à u, s à v, t à w, u à y, v à z, w à g, x à q, y à s, z à l]
then your answer should be the following text:
hmoxacedfijkbnprtuvwyzgqsl
Artefact submission required: Submit your answer to Problem 1.B in a text file called P1B.txt.
PROBLEM 2. STREAM CIPHER (25 MARKS)
In this problem, we consider a stream cipher constructed using the linear congruential generator (LCG) as
follows. The LCG uses four parameters: the modulus , the initial seed #, and the coefficients and . It is
generated using the following equation, where ‘ denotes the random number generated at iteration , for ≥1: ‘ = ‘,- × +
In this problem, the modulus is fixed to the following 64-bit prime number = 14202276565537260427
COMP2700 ASSIGNMENT 2 (Version 13/10/2019)
3
The values of #, and constitute the secret key in this scheme. We assume they are all 64-bit integers.
This means at each iteration, LCG generates a random number of size 64 bit (8 bytes), which we use as a
keystream. To encrypt an input of bytes, we need (<= + 1) iterations of the LCG to ensure we generate a
keystream long enough to match the length of the input. Note that the keystream starts with the random
number -, so the seed # is not part of the keystream. The encryption is then done by byte-wise XOR of the
input and the keystream.
You are provided with the file problem2/cipher.bin containing the ciphertext. The plaintext from which the
ciphertext is derived is always of a string of the form:
uNNNNNNN: Your flag is f{xxxxxxxxxxxxxxxx}
where‘NNNNNNN’is your Uni ID and‘xxxxxxxxxxxxxxxx’is a randomly generated‘flag’which is a 16 character
string representing an 8-byte integer in HEX notation. Here is an example of a plaintext, assuming your Uni ID
is 1234567 and the flag is bf67cfa82d2f9572:
u12345678: Your flag is f{bf67cfa82d2f9572}
Your task is to solve the following problems, given your assigned file problem2/cipher.bin:
PROBLEM 2.A. (10 MARKS) Find out the flag in your problem2/cipher.bin file.
Artefact submission: Submit your answer to Problem 2.A in a text file called P2A.txt. The file P2A.txt must
contain only one line of text of the form f{xxxxxxxxxxxxxxxx} where xxxxxxxxxxxxxxxx is the flag in HEX
notation.
PROBLEM 2.B. (15 MARKS) What are the secret values S0, A and B used to encrypt your
problem2/cipher.bin file? Explain how you obtain these secret values. Your solution must rely on an analytical
attacks, without brute force exhaustive search on the key space.
Report submission: Submit your answer to Problem 2.B as part of your report file, under the heading Problem
2.B.
PROBLEM 3. MESSAGE AUTHENTICATION CODE (25 MARKS)
For this problem, we consider an implementation of CBC-MAC. Recall that in CBC-MAC, the MAC of an input is
constructed by first encrypting the input data using a block cipher in CBC mode, and then take the last cipher
block as the MAC. In this case, we use AES, with 128-bit key, as the block cipher, so the MAC will be 128 bit
long (i.e., the block size of AES). You are given two binary files, problem3/file1.bin and problem3/file2.bin, and
their respective MACs, problem3/mac1.bin and problem3/mac2.bin.
PROBLEM 3.A. (10 MARKS). Provide a file and its valid MAC. The file must be distinct from
problem3/file1.bin and problem3/file2.bin.
Artefact submission: Submit your answer to Problem 3.A. as two files: P3A.bin and its valid MAC as file
P3A.mac.
PROBLEM 3.B. (15 MARKS). Explain how you construct the P3A.bin and P3A.mac you provided in Problem
3.a. and why the constructed MAC is valid, regardless of the actual key or IV used in the MAC computation.
COMP2700 ASSIGNMENT 2 (Version 13/10/2019)
4
Report submission: Submit your answer to Problem 3.B as part of your report file, under the heading Problem
3.B.
PROBLEM 4. ENCRYPTION MODE (25 MARKS)
In this problem, we consider the use of AES in counter mode (CTR) to encrypt certain plaintexts. Recall that in
CTR mode, the length of the IV and the counter combined must be exactly 128 bits. We will use openssl to
encrypt the plaintext. In this case, instead of specifying the IV and the counter separately, openssl requires the
IV to be 128 bit long, and uses the last 32 bit as the counter. So for example, if the IV provided to the openssl
in CTR mode is (in HEX notation) 112233445566778899AABBCC0000000A then the last four bytes (0000000A)
is the starting value of the counter.
We assume a fictional scenario where the attacker managed to intercept two messages sent in an internal
network of ANU. These messages are given here as two encrypted files: problem4/file1.bin and
problem4/file2.bin. Suppose that the person sending the files used AES in CTR mode to encrypt their data, and
the IV is incremented by one every time a new file is sent over the network. The attacker managed to find out
that problem4/file2.bin was the sixth files sent after problem4/file1.bin (so its IV has been incremented by 6
from the IV for problem4/file1.bin). Furthermore, the attacker also found out the two files sent are encrypted
from two comma-separated values (CSV) text file, containing results for an assessment for COMP2700 for
Semester 2 2019. In particular, every line in the plaintext CSV files has the following format:
COMP2700S2-2019,XXXXXXX,YY,ZZZZZZZZZZZZ
where XXXXXXX is a student Uni ID, YY is a number between 10 and 99, and ZZZZZZZZZZZZ is a random
number, presented in HEX notation. Each line ends with a new line character. Here is an example row:
COMP2700S2-2019,3032043,67,ea3b1dd44d6e
So each line is exactly 40 byte long (taking into account the newline character at the end of the line). For this
assignment, we assume that problem4/file2.bin contains an encryption of a row of the form:
COMP2700S2-2019,*,f{ZZZZZZZZZZZZ}
where ZZZZZZZZZZZZ is a 6-byte random integer (in HEX notation). We assume this is the secret information
the attacker wanted, so this value is our‘flag’. Here is an example of a row containing a flag:
COMP2700S2-2019,*,f{af32ca81a153}
The provided sample-files.zip contains examples of plaintexts and their corresponding ciphertexts. Note that
the position of the flag in the actual assignment file may differ from the position of the flag in the
corresponding sample file provided in sample-files.zip.
Your task is to solve the following:
PROBLEM 4.A. (10 MARKS). Using the given files problem4/file1.bin and problem4/file2.bin, discover the
flag that was encrypted in problem4/file2.bin.
Artefact submission: You must submit your answer to Problem 4.A. in a text file P4A.txt with the flag, i.e., its
content is exactly one line of texts of the form f{XXXXXXXXXXXX} where XXXXXXXXXXXX is the flag value.
COMP2700 ASSIGNMENT 2 (Version 13/10/2019)
5
PROBLEM 4.B. (15 MARKS). Explain how you decrypt the flag you find in Problem 4.a. Your attack must
rely on an analytical method, without brute force exhaustive search on the key space.
Report submission: Submit your answer to Problem 4.B as part of your report file, under the heading Problem
4.B.
SUBMISSION REQUIREMENTS
Your submission will contain two components:
• Artefacts: These are the files P1A.txt, P1B.txt, P2A.txt, P3A.bin, P3A.mac and P4A.txt specified in each
problem description above. You must comply with this naming requirement of the files; failure to
comply with this may cause your solutions to be wrongly marked.
• Report: This must be a PDF file, named‘report.pdf’, containing answers to Problem 2.B., Problem
3.B., and Problem 4.B. The report should not be longer than 2000 words.
To help us organise your submissions, please put all those files in one zip file, name it according to your last
name and Uni ID. For example, if your last name is Bond and your Uni ID is u1234567 then put all the files
above in a zip file called‘Bond_u1234567.zip’.
Failure to comply with the above requirements may result in mark deduction up to 5% of possible marks of
this assignment.
DEADLINE AND PENALTY
- The submission deadline is Sunday, October 27th, 2019 – 11:55pm (AET).
- The penalty for late submissions is 100% of the possible marks; in other words, you will get 0 marks
for late submissions. The only exception to this is if you obtain an explicit written approval from the
course convener to submit late.
- All submissions must be done through the Wattle submission site set up for this assignment.
HELP AND HINTS
A separate FAQ document will be provided that will contain useful hints and further details on how each
problem is assessed. Please check the Wattle page for this assignment for details. Further clarification and
hints may be provided in the discussion forum on Piazza when the needs arise.
更多可加 V
V：woshibb55