Assignment 2 cryptography

Total points: 80 (+6 bonus)
Assignment 2

Written assignment
1. Bob runs a social network web server that requires users, such as Alice, to log in. He
wants to use cryptography to protect Alice’s account. However, he doesn’t understand
cryptography very well. For each of the below uses of cryptography, identify his mistake,
and explain what he should do instead.
(a) [4 points] Bob obtains a public/private encryption key pair using RSA. When Alice
visits his site, Alice generates a 128-bit secret key intended for AES in CBC mode,
encrypts it using Bob’s RSA public key, and sends it to Bob. Bob asks Alice to
use a SHA-256 HMAC based on the same 128-bit secret key to authenticate this
message so as to prove that it is indeed Alice who sent the key.
(b) [4 points] To establish trust, Bob asks a CA to sign his public 256-bit RSA key
using the CA’s private 256-bit ECC key. The CA’s public 256-bit ECC key is in
Alice’s browser, so Alice can verify Bob’s key automatically when she visits his site,
even though she does not explicitly know who the CA is.
(c) [4 points] For Alice’s login, Bob requires Alice to hash and salt her password on the
client side using SHA-512, and then send it to Bob using 128-bit AES. Then, Bob
will store Alice’s hashed password and the salt in his database. In future attempts,
Alice can use the same hashed password and salt to login.
(d) [4 points] To store Alice’s password securely, Bob uses AES encryption with a secret
key and a 128-bit IV to encrypt her password. A CRC32 checksum is used to ensure
correctness against random bit flip errors.
1 CMPT479 A2
2. [9 points] In February 2015, it was found that Lenovo computers came pre-installed
with Superfish. Superfish adds itself as a root certificate authority to the computer. It
also comes with the same signing key and verification key for every computer. Every
time a user visits an HTTPS site with a valid certificate, Superfish instead generates a
fake certificate for the website to the user, and the browser would automatically trust
such certificates. (The website’s real certificate is intercepted and never presented to
the user.) Using the fake certificate, Superfish identified users’ browsing patterns and
added or changed advertisements on web pages, creating a scandal for Lenovo. In the
same month, Windows Defender started removing Superfish, and Lenovo ended their
partnership with Superfish.
(a) [3 points] Explain why Superfish is able to change the contents of an encrypted web
page. (Hint: If the user is talking to the website using the website’s encryption key,
then Superfish certainly cannot change the contents because Superfish doesn’t have
the website’s decryption key. So...)
(b) [3 points] Superfish used the same signing key in every laptop computer. If an
attacker (not Superfish) wants to impersonate a website, explain how the attacker
can generate a valid certificate for that website to present to any computer with
Superfish installed.
(c) [3 points] How can a careful user notice that their computer is infected by Superfish
using the browser?
2 CMPT479 A2
Programming assignment
Breaking Cryptography
In this assignment, we will write programs to automatically break some weak ciphers.
Please make sure to read the submission instructions carefully.
Two-Time Pad [25 points]
Two files, ctext0 and ctext1, have been sent to you by e-mail. Those two files were
encrypted using the same one-time pad. They are exactly 400 bytes each, and they both
come from popular English Wikipedia articles. Find the contents of both files using
crib-dragging, and submit them as ptext0 and ptext1. You can flip around ptext0 and
ptext1.
You may assume the plaintext to consist only of ASCII characters with the following
byte values, all ranges being inclusive of both ends:
• Symbols: 32 to 41, 44 to 59, 63, 91, 93.
• Capital letters: 65 to 90.
• Small letters: 97 to 122.
The ctext file was derived by XOR’ing the plaintext (as ASCII bytes) with the 400-byte
key. Each byte of the ctext file would be the XOR of the corresponding byte of plaintext
with the corresponding byte of the key (written as bit strings). If you cannot find the
full texts, submit as much of the text as you can find.
Padding Oracle Attack [30 points]
AES — the standard block cipher in use today — had a padding algorithm that introduced vulnerabilities when combined with CBC (Ciphertext Block Chaining). In this
assignment, we will investigate why it was insecure. In fact, the attacker can arbitrarily decrypt and encrypt in AES without knowledge of the key, and even without any
understanding of the operations of AES.
The following is a partial adaptation of Vaudenay’s “Security Flaws Induced by CBC
Padding — Applications to SSL, IPSEC, WTLS ...” paper. You may skip the explanation here and read the first four pages of that paper to answer the questions directly.
Note that AES operates on blocks of 16 bytes instead of 8 in that paper.
AES encrypts plaintexts in blocks of 16 bytes at a time. If there are fewer than 16 bytes
of plaintext data, AES adds padding bytes to the end of the plaintext until there are
16 bytes exactly. (During decryption, those padding bytes will be discarded.) If there
are more than 16 bytes of data, AES operates on each block one by one in order, and
pads the final block to 16 bytes. If we need to add n bytes of padding, then the bytes to
add is exactly n copies of n. For example, suppose the plaintext we want to encrypt is:
x
0 = (CA013AB4C561)16
3 CMPT479 A2
In the above, x
0
is written in hexadecimal notation, and it has 6 bytes. We want to add
10 bytes to make 16 bytes, so we will add the byte (0A)16 = 10 ten times to make x, the
padded version of x
0
:
x = (CA013AB4C5610A0A0A0A0A0A0A0A0A0A)16
Note that the minimum amount of padding is 1 byte: that is to say, if the original
plaintext has a multiple of 16 bytes, then we will need to add 16 bytes of padding of
(10)16 = 16. There will be a whole block of padding at the end.
After padding x
0
to x, we can perform AES encryption (denote the operation as C) on
x to get the ciphertext C(x). C is dependent on the secret key K and the initialization
vector IV ; the attacker knows IV because it is sent in the clear.
Suppose x contains N blocks of data (in other words, the size of x is 16N bytes), denoted
as (x1|x2| . . . |xN ). | is the concatenation operation, meaning that the bytes of x1 are
followed by that of x2, and then by x3, and so on. After encryption, the resulting
ciphertext is (IV |y1|y2| . . . |yN ). In CBC mode, we have:
y1 = C(IV ⊕ x1)
yi = C(yi−1 ⊕ xi) for i = 2, 3, . . . , N
The inverse of C, the AES block encryption function, is denoted as D, the block decryption function. Note that both C and D do not perform any padding on their own; they
both input and output 16 bytes of data. For any 16-byte block z, D(C(z)) = z.
We will now break AES in CBC mode using a padding oracle. A padding oracle is
some entity that tells the attacker if the padding of some ciphertext (IV |y1| . . . |yN ) is
correct after decryption. In other words, it decrypts (IV |y) using the correct key, gets
the plaintext x, and checks if x uses the correct padding scheme described above. The
padding oracle has been shared with you. (See “Notes on the Padding Oracle” later for
more details on how to run the padding oracle.)
Suppose we are deciphering some ciphertext (IV |y1| . . . |yN ). There will be three steps.
First, we will learn how to find the last byte of xN (“Decrypt byte”). Then, we will find
the whole xN (“Decrypt block”). Finally, we will find all of (x1|x2| . . . |xN ) (“Decrypt”).
— Decrypt byte —
Extract yN from the ciphertext by taking the last 16 bytes, and yN−1 as the last 32 to
16 bytes. Denote the ith byte of yN as yN,i. Here, we want to find xN,16.
1. First, generate a random block r = (r1|r2| . . . |r15|i) with 15 random bytes, followed
by a byte i. Initially i = 0.
2. Ask the padding oracle if (r|yN ) is valid. (r|yN ) contains the 16 bytes of r, followed
by the 16 bytes of y.
3. If the padding oracle returns “no”, increment i by 1, and then ask the padding
oracle again. Keep incrementing i until the padding oracle returns “yes”.
4 CMPT479 A2
4. Replace r1 with any other byte and ask the oracle if the new (r|yN ) has valid
padding. If the padding oracle returns “yes”, similarly replace r2. Repeat until
either we have finished replacing r15 and the oracle always returned “yes”, or the
oracle has returns “no” while we were replacing some rk.
5. If the oracle always returned “yes” in Step 4, set D(yN )16 = i ⊕ 1.
6. If the oracle returned “no” when we replaced rk in Step 4, set D(yN )16 = i⊕(17−k).
7. The final byte of xN is xN,16 = D(yN )16 ⊕ yN−1,16.
— Decrypt block —
After finding xN,16, the attacker can proceed to find all other bytes of xN , starting
from the 15th byte xN,15, then xN,14, and proceeding backwards to xN,1. In this process, the attacker will also find D(yN )16, D(yN )15, . . . , D(yN )1 as above. The following
describes how the attacker can find xN,k for any k; the attacker has already found
D(yN )k+1, D(yN )k+2, . . . , D(yN )16.
1. Set r as (r1|r2| . . . |rk−1|i|D(y)k+1⊕(17−k)|D(y)k+2⊕(17−k)| . . . |D(y)16⊕(17−k)).
Initially i = 0.
2. Ask the oracle if r|yN is valid.
3. If the padding oracle returns “no”, increment i and ask the padding oracle again.
Keep incrementing i until the padding oracle returns “yes”.
4. When the padding oracle returns “yes”, set D(yN )k = i ⊕ (17 − k)
5. The k-th byte of xN is xN,k = D(yN )k ⊕ yN−1,k.
— Decrypt —
The above shows how the attacker can decrypt the last block yN to obtain XN . To
decrypt the k-th block yk, the attacker simply replaces all of the above yN with yk and
yN−1 with yk−1.
Your task is to write a program, decrypt, which finds the plaintext x for any ciphertext
y and outputs it to standard output. It is run with:
./decrypt ciphertext
ciphertext is a file that contains an amount of data that is a multiple of 16 bytes, and
at least 32 bytes. It is formatted as IV |y1| . . . |yN , where the IV is the first 16 bytes, y1
are bytes 17 to 32, and so on.
After you get the plaintext, output it to standard output. Do not add a newline.
This is a difficult task. You should tackle the assignment step by step: do the “Decrypt
byte” step, then the “Decrypt block” step, then the “Decrypt” step. In case you cannot
finish the assignment, marks will be given for partially completing each step.
Hint: Suppose you are given the ciphertext (IV |y1|y2). Write down the plaintext (x1|x2)
using D, IV , y1, and y2. (It is not simply D(y1) and D(y2).)
5 CMPT479 A2
Bonus (6 points) Write a program, encrypt, which takes in some plaintext x and
encrypts x using the same encryption algorithm and key that is behind the padding
oracle provided. It is run with:
./encrypt plaintext
plaintext contains an amount of data that is a multiple of 16 bytes, and at least 16
bytes. It is formatted as x1|x2| . . . |xN . Output the ciphertext and the IV to standard
output as IV |y1| . . . |yN .
(Hint: encrypt should call decrypt as a subroutine in order to guess the right ciphertext.
You only need to call decrypt once for each block. Note that you can choose your own
IV.)
6 CMPT479 A2
Notes on the padding oracle
The padding oracle should be run with:
python3 oracle.py ciphertext
It will decrypt the ciphertext with the secret AES key, check the padding of the plaintext,
and output “1” if the padding is correct and “0” if the padding is incorrect.
The padding oracle was written in Python. It is not compiled, and it can be directly run
on Unix-like systems such as Ubuntu and macOS. If you want to run it on Windows, you
will have to install Python and then type:
python3 oracle.py ciphertext
You will also have to capture the output and feed it into your own code. The command
to do so is system(<your command>) in C and C++, subprocess.check output(<your
command>) in Python, and Runtime.getRuntime().exec(<your command>) in Java. You
may have to read about your preferred function specifically to learn how to use it.
Since the oracle is not compiled, the key is hardcoded into the oracle code. Do not use
the key in any way. When we test your code, we will use a different oracle with a different
key. Your code should work independent of what the actual key value is.
You are also provided with a ciphertext called ciphertext for reference, with its generator ciphertext gen.py. It was encrypted with the same key as the oracle, with an IV =
CMPT 479 test iv, and the plaintext message is Alice and Bob in Wonderland. Since
the plaintext is 27 bytes long, it will be padded with 5 bytes, each with a byte value of 5. If
you find that the byte value of the last byte of the plaintext is 5, you are on the right track!
7 CMPT479 A2
Submission instructions
All submissions should be done through CourSys. Submit the following files:
• a2.pdf, containing all your written answers. Make sure it is not the question file.
• ptext0 and ptext1, for part (a) of the programming assignment.
• decrypt.{cpp, py, java}, for part (b) of the programming assignment, as well as
any other code necessary to run it. This may include a Makefile. Submit your code;
do not submit any compiled files. You may also submit encrypt.{cpp, py, java}
for the bonus marks. The bonus marks can only be applied to this assignment.
To run decrypt, for example, I will do the following:
C++: I will compile ./gcc decrypt.cpp -o decrypt and then run ./decrypt.
Python3: I will call python decrypt.py.
Java: I will compile javac decrypt.java and then call java decrypt.
If you are using Python, pleaase make sure it is Python3 instead of Python2.
If there is a Makefile in your folder, the Makefile will override all of the above. I will call
make to compile the code, and then I will call make run.
Keep in mind that plagiarism is a serious academic offense; you may discuss the assignment, but write your assignment alone and do not show anyone your answers and code.
The submission system will be closed exactly 48 hours after the due date of the assignment. You will receive no marks if there is no submission within 48 hours after the due
date.
8 CMPT479 A2