CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Milestone due date: Friday, November 26th, 2021. 3:00 pm EST (48 hours automatic extension)
Assignment due date: Friday, December 3rd, 2021. 3:00 pm EST (48 hours automatic extension)
Total marks: 29 + 24 = 53
Written Response TA: Setareh Ghorshi
Programming Response TA: Jiayi Chen
TA Office Hours: Thursdays 9:00 am – 10:00 am EST
Please use Piazza for all communication. Ask a private question if necessary. The TAs’ office
hours will be hosted in the A3 Programming and Written Office Hour channels of the CS 458/CS
658 – Fall 21 Microsoft Team (see TA and Professor Office Hours in Learn).
What to hand-in
All assignment submission takes place on the linux.student.cs machines (not ugster or the
virtual environments), using the submit utility. Log in to the linux student environment, go to the
directory that contains your solution, and submit using the following command:
submit cs458 3 . (dot at the end)
CS 658 students should also use this command and ignore the warning message. Please consult
the course homepage for help with the submit utility and accessing the liux student
environment.
By the milestone deadline, you are required to hand in:
a3 milestone.tar: Your source files for the Questions 1 and 2 of the programming
assignment, in your supported language of choice, inside a tarball. Note that you will not
be able to submit the tarball for the first two questions after this deadline. It should be
clear to see how your code can issue web requests to the API to solve each question. If it is
not obvious to see how you solved a question, then you will not receive the marks for that
question, even if marks were awarded on the assignment website. To create the tarball, for
example, which is developed in the directory a3 milestone/, run the command
tar cvf a3 milestone.tar -C a3 milestone/ .
(including the .). You can check that your tarball is formatted correctly by running “tar
-tf file.tar”. For example (note that there are no folder names in the output), if you
use Python to finish the assignment, you may get:
$ tar -tf a3 milestone.tar
./
./q1.py
./q2.py
By the assignment deadline, you are required to hand in:
• a3 written.pdf: A PDF file containing your answers for the written-response questions.
https://student.cs.uwaterloo.ca/~cs_build/coursework/submit/submit
https://crysp.uwaterloo.ca/courses/cs458/S21-material/S21-syllabus.html
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
• a3 code.tar: Your source files for the Questions 3, 4 and 5 of the programming
assignment, in your supported language of choice, inside a tarball. It should be clear to see
how your code can issue web requests to the API to solve each question. If it is not obvious
to see how you solved a question, then you will not receive the marks for that question,
even if marks were awarded on the assignment website.
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Written Response Questions [29 marks]
For written questions, be sure to use complete, grammatically correct sentences. You will be
marked on the presentation and clarity of your answers as well as the content.
Question 1: ElGamal Encryption [Total: 6 marks]
ElGamal encryption is a popular public-key encryption algorithm based on the Diffie-Hellman
key exchange.
Description of the algorithms in this cryptosystem can be found at: https://en.wikipedia.
org/wiki/ElGamal_encryption.
(a) [2 marks] Describe the ElGamal encryption algorithm. What is the ”hard-to-solve”
problem that it is based on?
(b) [3 marks] Assume that the attacker, Eve, has access to an ElGamal public-key (not
the corresponding secret key), a specific ciphertext C, and an oracle that decrypts any
ciphertext except C. Eve is interested in finding out the plain text corresponding to C,
which could be some confidential value. Briefly describe how Eve can use the oracle
and ciphertext C to calculate the corresponding plaintext to C. (Hint: Think about how
you can take advantage of the homomorphic property of ElGamal encryption.)
(c) [1 mark] Under which condition will ElGamal encryption be semantically secure?
(Briefly explain the condition. A description of semantic security can be found here:
https://en.wikipedia.org/wiki/Semantic_security.)
Question 2: TLS and HTTPS [Total: 9 marks]
HTTPS uses the Transport Layer Security (TLS) protocol to establish a secure channel be-
tween the client and the server. TLS encrypts communication between the two parties.
(a) [2 marks] The client and the server first conduct a handshake in the TLS protocol. What
cryptographic information do the server and the client agree on during the handshake?
(b) [2 marks] The TLS protocol uses both symmetric and asymmetric encryption. Briefly
describe what each type of encryption is used for in the TLS protocol and why it is
preferred for that purpose, over the other type.
(c) [1 mark] Briefly describe how Certification Authorities (CAs) support clients in au-
thenticating servers.
(d) [4 marks] Suppose that Bob is a terrible webmaster and chooses an invalid TLS cer-
tificate for his online store website. Alice trusts her friend Bob and chooses to ignore
her browser’s warning and proceeds to Bob’s website to buy some stuff. An attacker,
Mallory, can perform a man-in-the-middle attack in this scenario to steal Alice’s cre-
dentials and banking information. You know that man-in-the-middle attacks involve the
https://en.wikipedia.org/wiki/ElGamal_encryption
https://en.wikipedia.org/wiki/ElGamal_encryption
https://en.wikipedia.org/wiki/Semantic_security
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
attacker establishing a channel with both ends — the server (Bob) and the client (Al-
ice). Note that Mallory might need to perform some preparation even before Alice’s
attempt to connect to Bob’s website.
i. [2 marks] Specify what cryptographic information Mallory needs to generate or
modify so that Alice’s vulnerable browser (the client) will establish a secure chan-
nel with Mallory.
ii. [2 marks] Mallory needs to convince Alice that she is communicating with Bob’s
server, to reassure her that her purchase was successful. Present a clear and con-
cise protocol that Mallory executes in order to convince Alice of a successful pur-
chase and to steal her banking credentials. Mallory will need to communicate with
the server and relay (repeat) information back to Alice and vice versa. So, in steps
of your protocol, include what Mallory encrypts or decrypts, under a key shared
with one of Alice or Bob, and sends to/receives from them.
Question 3: Inference Attacks [Total: 10 marks]
Suppose a research group working on diversity and inclusion gathers the data about race,
position, and salary of employees in a big software company. The data is stored in a table
of size N , Employee, in their database. Their initial analysis shows that 31% of the em-
ployees are identified as Asian, 43% as European American, 15% as African American, and
11% as Others. Below is an excerpt (not the entire table): To deter people from learning
Name Race Position Salary
Sarah Asian Manager 102,000
Cindy African American Chief Security Officer(CSO) 84,129
Zahra Asian Software Developer 80,325
John European American Software Developer 82,721
Abigail Others Human Resources Officer 73,426
Cori European American Manager 100,908
Thomas European American Software Developer 78,923
Table 1: Part of Employee Table
other people’s salaries, the database is set up to suppress the Salary field in the output of
queries. However, users can execute queries of the form SELECT SUM(Salary) FROM
Employee WHERE … where queries that match fewer than k or more than N − k (but
not all N ) records are rejected. We will use k = N
8
.
(a) [4 marks] Suppose that you are going to infer the salary of an employee named Nicky
(not shown on the excerpt) by doing several queries, but you do not know any other
details about them. Use a tracker attack, as defined in Module 6, to design a tracker
and a set of three queries based on this tracker that will let you infer the salary. In your
solution, you should give 1) your tracker, 2) the set of three queries, and 3) how to
obtain the salary.
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
(b) [3 marks] The research group becomes aware of the tracker attack and forbids SUM(Salary)
queries. Instead, they allow only queries of the form SELECT COUNT(*) FROM
Employee WHERE Q. Note that Q may include testing the value of the Salary field.
(Again, queries that match fewer than k or more than N − k, with the exception of
N , records are ruled out.) How would you modify your attack from part (a) to learn
Lily’s salary (not shown on the excerpt)? Explain the new attack. You may assume
that no one in the database has a salary of more than $200,000 and that all salaries are
non-negative if that simplifies your attack.
(c) [3 marks] Suppose a similar research is being done on the university students and the
generated dataset is going to be published along with the research results. This dataset
includes names, ages, genders, and races of the university students. The initial dataset
is shown below.
Name Age Gender Race
Sarah 18 F Asian
Maria 20 F Asian
Jake 21 M African American
Robin 29 F European American
Bob 24 M Others
Jack 22 M Others
Lily 25 F Asian
Alex 18 F European American
Ted 23 M European American
Cindy 27 F African American
The research group declares that the Race field is vital to research studies and should
therefore not be masked. ((Name, Age, Gender) forms the quasi-identifier.) Thus, the
group adopts the following way to anonymize the data:
i. Name fields are fully masked by stars;
ii. Age fields are generalized to (at least) 3 age groups: [18-21], [22-25],[26-29].
The processed table is shown below.
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Name Age Gender Race
* [18-21] F Asian
* [18-21] F Asian
* [18-21] M African American
* [26-29] F European American
* [22-25] M Others
* [22,25] M Others
* [22,25] F Asian
* [18-21] F European American
* [22-25] M European American
* [26-29] F African American
Is the anonymized table 3-anonymous? If yes, please explain and give the value of `
for which the table is `-diverse. Otherwise, please present a correct solution and give
the value of ` for which your table is `-diverse.
Question 4: Administering Security [Total: 4 marks]
Suppose you are the head of the security planning team in a computer company produc-
ing money transfer platforms. Briefly explain four things that you consider in the incident
response plan for a data breach.
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Programming Question [24 marks]
Note: This assignment is long because it in-
cludes a lot of text to help you through it.
”
The use of strong encryption in personal communications may itself be a red
flag. Still, the U.S. must recognize that encryption is bringing the golden age of
technology-driven surveillance to a close.
MIKE POMPEO
CIA director
“
Encryption works. Properly implemented strong crypto systems are one of the
few things that you can rely on.
EDWARD SNOWDEN
In this assignment, you will use “strong encryption” to send secure messages. Each question
specifies a protocol for sending secure messages over the network. For each question, you will use
the libsodium1 cryptography library in a language of your choice to send a message through a
web API.
For the assignment questions, you will send messages to and receive messages from a fake user
named Scholar in order to confirm that your code is correct.
Assignment website: https://hash-browns.cs.uwaterloo.ca
The assignment website shows you your unofficial grade for the programming part; the grade
1https://libsodium.org/
https://libsodium.org/
https://hash-browns.cs.uwaterloo.ca
https://libsodium.org/
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
becomes official once your final code submission has been examined. Your unofficial grade will
update as you complete each question, so you will effectively know your grade by converting it
to your final grade with our formula (see the top note frame of Programming Question) before the
deadline. The assignment website also allows you to debug interactions between your code and
the web API.
libsodium documentation
The official documentation for the libsodium C library is available at this website:
https://libsodium.org/doc/
You should primarily use the documentation available for the libsodium binding in your lan-
guage of choice. However, even if you are not using C, it is occasionally useful to refer to the C
documentation to get a better understanding of the high-level concepts, or when the documentation
for your specific language is incomplete.
In the past, the website has been unavailable for extended periods of time. If the documentation
site is down, you can access an offline mirror of the PDF documentation on LEARN.
Choosing a programming language
Since we will not be executing your code (although we will read it to verify your solution), you
may theoretically choose any language that works on your computer.
You will need to use libsodium to complete the assignment. While libsodium is available
for dozens of programming languages (check the list of language bindings2 to find an interface
for your language), you will need to limit your language choice as not all libsodium language
bindings support all of the features needed for this assignment. Specifically, you should quickly
check the libsodium documentation for your language to ensure that it gives you access to the
following features:
• “Secret box”: secret-key authenticated encryption using XSalsa20 and Poly1305 MAC
• “Box”: public-key authenticated encryption using X25519, XSalsa20, and Poly1305 MAC
• “Signing”: public-key digital signatures using Ed25519
• “Password hashing”: key derivation function (KDF) using Scrypt with Salsa20/8 and SHA-256
2https://download.libsodium.org/doc/bindings_for_other_languages/
https://libsodium.org/doc/
https://download.libsodium.org/doc/bindings_for_other_languages/
https://download.libsodium.org/doc/bindings_for_other_languages/
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
• “Generic hashing”: using BLAKE2b
You should also choose a language that makes the following tasks easy:
• Encoding and decoding base64 strings
• Encoding and decoding hexadecimal strings
• Encoding and decoding JSON data
• Sending POST requests to websites using HTTPS
While you are not required to use a single language for all solutions, it is best to avoid the need to
switch languages in the middle of the assignment.
You may use any third-party libraries and code. However, if you copy code from somewhere else,
be sure to include prominent attribution with clear demarcations to avoid plagiarism.
We have specific advice for the following languages, which we have used for sample solutions:
• Python: This language works very well. Use the nacl module (https://github.com/
pyca/pynacl) to wrap libsodium. The box and secret box implementations include
nonces in the ciphertexts, so you do not need to manually concatenate them. The base64,
json, and requests modules from the standard library work well for interacting with the
web API.
• PHP: This language works well if you are already familiar with it. Use the libsodium
extension (https://github.com/jedisct1/libsodium-php) for cryptography. The
libsodium-php extension is included in PHP 7.2. Otherwise, you may need to install
the php-dev package and install the libsodium-php extension through PECL. In that
case, you must manually include the compiled sodium.so extension in your CLI php.ini.
Interacting with the web API is easy using global functions included in the standard library:
pack and unpack for hexadecimal conversions, base64 encode and base64 decode,
json encode and json decode, and either the curl module or HTTP context options
for submitting HTTPS requests.
• Java: This language is a reasonable choice if you are comfortable using it. The
libsodium-jna binding (https://github.com/muquit/libsodium-jna) con-
tains all of the functions that you will need. Please follow the installation instructions listed
in the website. The java.net.HttpURLConnection class works for submitting web re-
quests. Base64 and hexadecimal encoding functions are available in java.util, and JSON
encoding functions are available in org.json. Note that the ugsters may not contain updated
packages for Java.
• JavaScript: The simplest way to solve the assignment in JavaScript is to use Node.JS with
the libsodium.js binding (https://github.com/jedisct1/libsodium.js).
Unfortunately, the method signatures in libsodium.js are slightly different than the
https://github.com/pyca/pynacl
https://github.com/pyca/pynacl
https://github.com/jedisct1/libsodium-php
https://github.com/muquit/libsodium-jna
https://github.com/jedisct1/libsodium.js
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
C library, and the wrapper is poorly documented; you may need to look at the proto-
types in wrapper/symbols/ to identify the inputs and outputs. You should use the
dist/modules-sumo package (not the default), since it includes the required hashing func-
tions. libsodium.js includes helper functions for converting between hexadecimal and
binary. The standard library includes the other encoding functions you will need: atob and
btoa for base64, and the JSON object for JSON processing. Be wary of string encoding:
you may need to use the from string and to string functions in certain situations.
• C: While C has the best libsodium documentation, all of the other tasks are more difficult
than other languages. The assignment is also much more challenging if you use good C pro-
gramming practices like error handling and cleaning up memory. If you choose C, you will
spend a significant amount of time solving Question 1 before receiving any marks. We rec-
ommend libcurl (https://curl.haxx.se/libcurl/) for submitting API requests,
Jansson (http://www.digip.org/jansson/) for processing JSON, and libb64
(http://libb64.sourceforge.net/) for base64 handling. Note that you will need
to search for the proper usage of the cencode.h and cdecode.h headers for base64 pro-
cessing. You will need to provide your own code for hexadecimal conversions; it is acceptable
to copy code from the web for this purpose, but be sure to attribute its author using a code
comment.
You may use any other language, but then we cannot provide informed advice for language-specific
problems. We also cannot guarantee that bindings for other languages contain all required features.
Ugster availability
Some of the aforementioned programming languages (C, Python, PHP) and libraries for libsodium
will be made available on the Ugsters in case you do not have access to a personal development
computer. Note that we do not have updated packages for Java or Javascript on the ugsters. We do
support Ruby on the ugsters though we will not be able to provide informed advice for language-
specific problems for Ruby.
Question 1: Using the API [5 marks]
In this first question, we will completely ignore cryptography and instead focus on getting your
code to communicate with the server.
Begin by visiting the assignment website and logging in with your WatIAM credentials. You will
be presented with an overview of your progress for the assignment. While you can simply use a
web browser to view the assignment website, your code will need to communicate with the web
https://curl.haxx.se/libcurl/
http://www.digip.org/jansson/
http://libb64.sourceforge.net/
https://hash-browns.cs.uwaterloo.ca
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
API. The web API does not use WatIAM for authentication. Instead, you will need an “API token”
so that your code is associated with you.
Click on the “Show API Token” button on the assignment website to retrieve your API token. Do
not share your API token with anyone else; if you suspect that someone else has access to your
token, use the “Change API Token” button to generate a new one, and then inform the TA. Your
code will need to use this API token to send and receive messages.
Question 1 part 1: send a message [3 marks]
Your first task is to send an unencrypted message to Scholar using the web API. To do this, submit
a web request with the following information:
• URL: https://hash-browns.cs.uwaterloo.ca/api/plain/send
• HTTP request type: POST
• Accept header: application/json
• Content-Type header: application/json
For every question in this assignment, the request body should be a JSON object. The JSON object
must always contain an api token key with your API token in hexadecimal format.
To send a message to Scholar, your JSON object should also contain to and message keys. The
to key specifies the username for the recipient of your message; this should be set to Scholar.
The message key specifies the message to send, encoded using base64.
You will receive marks for sending any non-empty message to Scholar (sadly, Scholar is a script
that lacks the ability to understand the messages that you send). For example, to send a message
containing “Hello, World!” to Scholar, your request would contain a request body similar to this:
{“api token”: “3158a1a33bbc…9bc9f76f”,
“to”: “Scholar”, “message”: “SGVsb…kIQ==”}
Consult the documentation for your programming language of choice to determine how to con-
struct these requests.
The web API always returns JSON data in its response. If your request completed successfully, the
response will have an HTTP status code of 200 and you will receive an empty object; check the
assignment website to verify that you have been granted marks for completing the question. If an
error occurs, the response will have an HTTP status code that is not 200, and the JSON response
will contain an error key in the object that describes the error.
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
If you are having difficulty determining why a request is failing, you can enable debugging on
the assignment website. When debugging is enabled, all requests that you submit to the web API
will be displayed on the assignment website, along with the details of any errors that occur. If
debugging is enabled and you are not seeing requests in the debug log after running your code,
then your code is not connecting to the web API correctly.
Question 1 part 2: receive a message [2 marks]
Next, you will use the web API to receive a message that Scholar has sent to you. To do this,
submit a POST request to the following URL:
https://hash-browns.cs.uwaterloo.ca/api/plain/inbox
All requests to the web API are POST requests with the Accept and Content-Type headers set
to application/json; only the URL and the request body changes between questions. The
JSON object in the request body for your inbox request should contain only your api token.
The response to your request is a JSON-encoded array with all of the messages that have been sent
to you. Each array element is an object with id, from, and message keys. The id is a unique
number that identifies the message. The from value is the username that sent the message to you.
The message value contains the base64-encoded message.
Decode the message that Scholar sent you. The message should contain recognizable English
words. The messages from Scholar are meaningless and randomly generated. We use English
words so that it is obvious when your code is correct, but the words themselves are completely
random.
To receive the marks for this part, go to the assignment website and open the “Question Data” page.
This page contains question-specific values for the assignment, and also allows you to submit an-
swers to certain questions. Enter the decoded message that Scholar sent to you in the “Question 1”
section to receive your mark.
Question 2: Pre-shared Key Encryption [5 marks]
In this part, you will extend your code from question 1 to encrypt messages using secret-key
encryption. For now, we will assume that you and Scholar have somehow securely shared a secret
key at some point in the past. You will now exchange messages using that secret key.
Begin by importing an appropriate language binding for libsodium. Since every language uses
https://hash-browns.cs.uwaterloo.ca
https://hash-browns.cs.uwaterloo.ca/questions
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
slightly different notations for the libsodium functionality, you will need to consult the docu-
mentation for your language to find the appropriate functions to call.
Question 2 part 1: send a message [3 marks]
Send a request to the following web API page:
https://hash-browns.cs.uwaterloo.ca/api/psk/send
Here, psk stands for “pre-shared key”. The format of this send request is the same as in ques-
tion 1 part 1, except that the message value that you include in the request body JSON will now
be a ciphertext that is then base64 encoded.
To encrypt your message, you should use the “secret box” functionality of libsodium to per-
form secret-key authenticated encryption. This type of encryption uses the secret key to en-
crypt the message using a stream cipher (XSalsa20), and to attach a message authentication
code (Poly1305) for integrity. libsodium makes this process transparent; simply calling
crypto secretbox easy (or the equivalent in non-C languages) will produce both the ci-
phertext and the MAC, which the library refers to as “combined mode”.
You will need to generate a “nonce” (“number used once”) in order to encrypt the message. The
nonce should contain randomly generated bytes of the appropriate length. The size of the nonce
is constant and included in most libsodium bindings (the libsodium documentation contains
examples). To generate the message, you should base64 encode a concatenation of the nonce
followed by the output of crypto secretbox easy. Some language bindings will automat-
ically do this for you, so check to see if the output of the function contains the nonce that you
passed into it.
Abstractly, your request body should look something like this:
{“api token”: “3158a1a33bbc…9bc9f76f”, “to”: “Scholar”, “message”:
base64encode(concat(nonce, secretbox(plaintext, nonce, key)))}
To receive marks for this part, send an encrypted message to Scholar using the secret key found
in the “Question 2” section of the “Question Data” page. Note that the secret key is given in
hexadecimal notation; you will need to decode it into a binary string of the appropriate length
before passing it to the libsodium library.
https://hash-browns.cs.uwaterloo.ca/questions
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Question 2 part 2: receive a message [2 marks]
Scholar has sent an encrypted message to you using the same format and key. Check your inbox
by requesting the following web API page in the usual manner:
https://hash-browns.cs.uwaterloo.ca/api/psk/inbox
You will need to decrypt this message by decoding the base64 data, extracting the
nonce (unless your language binding does this for you), and calling the equivalent of
crypto secretbox easy open. Enter the decrypted message in the “Question 2” section
of the “Question Data” page to receive your marks. The decrypted message contains recognizable
English words.
Question 3: Digital Signatures [5 marks]
In most common conversations, the communication partners do not have a pre-shared secret key.
For this reason, public-key cryptography (also known as asymmetric cryptography) is very useful.
The remaining questions focus on public-key cryptography.
In this question, you will send an unencrypted, but digitally signed, message to Scholar.
Question 3 part 1: upload a public verification key [2 marks]
The first step in public-key communications is key distribution. Everyone must generate a secret
signature key and an associated public verification key. These verification keys must then be dis-
tributed somehow. For this assignment, the web API will act as a public verification key directory:
everyone can upload a verification key, and request the verification keys that have been uploaded
by other users.
libsodium implements public-key cryptography for digital signatures as part of its sign func-
tions. Before sending a message to Scholar, you will need to generate a signature and verifica-
tion key (together called a key pair). Generate this pair using the equivalent of the C function
crypto sign keypair in your language. You should save the secret signature key somewhere
(e.g., a file), because you will need it for the next part. To receive marks for this part, upload the
verification key to the server by sending a POST request with the usual headers to the following
web API page:
https://hash-browns.cs.uwaterloo.ca/api/signed/set-key
https://hash-browns.cs.uwaterloo.ca/questions
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
The request body should contain a JSON object with a public key value containing the base64
encoding of the verification key. For example, your request body might look like this:
{“api token”: “3158a1a33bbc…9bc9f76f”,
“public key”: “CazwYZnnnYqMI6…wTWk=”}
Upon success, the server will return a 200 HTTP status code with an empty JSON object in the
body. If you submit another set-key request, it will overwrite your existing verification key.
Question 3 part 2: send a message [3 marks]
Now that you have uploaded a verification key, others can use it to verify that signed messages
really were authenticated by you (or someone else with your secret key). Send an unencrypted and
signed message to Scholar by sending a request to the following web API page in the usual way:
https://hash-browns.cs.uwaterloo.ca/api/signed/send
The message value in your request body should contain the base64 encoding of the plaintext
and signature in “combined mode”. In the C library, you can generate the “combined mode”
signature using the crypto sign function. Scholar will be able to verify the authenticity of your
message using your previously uploaded verification key.
Question 4: Public-Key Authenticated Encryption [5 marks]
While authentication is an important security feature, the approach in question 3 does not pro-
vide confidentiality. Ideally, we would like both properties. libsodium supports authenticated
public-key encryption, which allows you to encrypt a message using the recipient’s public key, and
authenticate the message using your secret key. Note, that for authenticated encryption the public
key is used for both encryption and for verification while the secret key is used for both decryption
and for signing.
The libsodium library refers to an authenticated public-key ciphertext as a “box” (in contrast
to the “secret box” used in questions 2). Internally, libsodium performs a key exchange be-
tween your secret key and Scholar’s public key to derive a shared secret key. This key is then
used internally to encrypt the message with a stream cipher and authenticate it using a message
authentication code.
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Question 4 part 1: verify a public key [2 marks]
One of the weaknesses of public key directories like the one implemented by the web API in this
assignment is that the server can lie. If Scholar uploads a public key and then you request it from
the server, the server could send you its public key instead. If you then sent a message encrypted
with that key, then the server would be able to decrypt it; it could even re-encrypt it under Scholar’s
actual public key, and then forward it along (acting as a “man in the middle”).
To defend against these attacks, “end-to-end authentication” requires that you somehow verify that
you received Scholar’s actual public key. This is a very difficult problem to solve in a usable way,
and is the subject of current academic research. One of the most basic approaches is to exchange
a “fingerprint” of the real public keys through some other channel that an adversary is unlikely to
control (e.g., on business cards, or through social media accounts).
For this part, you must download Scholar’s public key from the web API, and then verify that you
were given the correct one. Submit a POST request in the usual way to the following web API
page:
https://hash-browns.cs.uwaterloo.ca/api/pke/get-key
Here, pke means “public-key encryption”. Your request body should contain a JSON object with
a user key containing the username associated with the public key you’re requesting (in this
case, Scholar). The server’s response will be a JSON object containing user (the requested
username) and public key, a base64 encoding of the user’s public encryption key.
To verify that you received the correct public key, you should derive a “fingerprint” by passing
the key through a cryptographic hash function. Use the BLAKE2b hash function provided by
libsodium for this purpose. The C library implements this as crypto generichash, but
other languages might name it differently. Do not use a key for this hash (it needs to be unkeyed
so that everyone gets the same fingerprint). Remember to base64 decode the public key before
hashing it! The resulting hash is what you would compare to the one that Scholar securely gave
to you. To get the marks for this part, enter the hash of the public encryption key, in hexadec-
imal encoding, into the “Question 4” section of the “Question Data” page. Keep in mind this
hash/fingerprint is not the same as the public key itself.
Question 4 part 2: send a message [2 marks]
Before sending a message to Scholar, you will first need to generate and upload a public key. While
the key pairs generated in question 3 were generated with the sign functions of libsodium, the
key pairs for this question must be generated with the box functions. This difference is because
the public encryption keys for this question will be used for authenticated encryption rather than
digital signatures, and so different cryptography is involved.
https://hash-browns.cs.uwaterloo.ca/questions
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Generate a public and secret key using the equivalent of the C function crypto box keypair
in your language. Then, using the same request structure as in question 3 part 1, upload your public
key to the following web API page:
https://hash-browns.cs.uwaterloo.ca/api/pke/set-key
Once you have successfully uploaded a key (indicated by a 200 HTTP status code and an empty
JSON response), you can send a message to Scholar. Encrypt your message using the equivalent
of the C function crypto box easy in your language. This function takes as input Scholar’s
public key (which you downloaded in the previous part, the value retrieved from a request to
api/pke/get-key after it is base64-decoded), your secret key, and a nonce. The function outputs the
combination of a ciphertext and a message authentication code.
You should generate the nonce randomly and prepend it to the start of the ciphertext, in the same
way that you did for question 2 part 1. Encode the resulting data with base64 encoding. Ab-
stractly, your request body should look something like this:
{“api token”: “3158a1a33bbc…9bc9f76f”, “to”: “Scholar”,
“message”: base64encode(
concat(nonce, box(plaintext, nonce, Scholar public, your secret))
)}
Finally, send the message to Scholar in the usual way using the following web API page:
https://hash-browns.cs.uwaterloo.ca/api/pke/send
Question 4 part 3: receive a message [1 mark]
To receive the mark for this part, you will need to decrypt a message that Scholar has sent to you.
Check your inbox in the usual way with a request to the following web API page:
https://hash-browns.cs.uwaterloo.ca/api/pke/inbox
To decrypt the message from Scholar, you will need your secret key and Scholar’s public
key. After base64 decoding the message, decrypt it using the equivalent of the C function
crypto box open easy in your language. Provide the decrypted message in the “Question 4”
section of the “Question Data” page.
https://hash-browns.cs.uwaterloo.ca/questions
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Question 5: Forward Secrecy [4 marks]
The protocols in all of the previous questions share a problem: if an eavesdropper passively records
all of the encrypted messages and later steals one of the secret keys, then they can retroactively
decrypt any messages that they previously stored. If we stop this from happening, then we achieve
forward secrecy (sometimes called perfect forward secrecy).
The “trick” for forward secrecy is to encrypt messages using temporary secret keys and authen-
ticate them using long-term secret signature keys. Stealing long-term secret signature keys that
are only used for authentication does not affect previous conversations, since they have already
concluded. It is also generally more difficult to steal secret keys that are erased quickly than it is
to steal secret keys that must be kept around for a long time.
The protocol for this question shares aspects of the signed messages protocol in question 3, and the
public-key encryption in question 3. However, in this question, every user will upload two public
keys to the server: a public identity verification key, and a signed prekey.3 The identity verification
key is used for authentication via digital signatures. It is produced in the same way as in question 3.
The signed prekey is used for encryption. It is produced in the same way as in question 4, with the
exception that it is also signed by the identity verification key.
Unlike identity verification keys, signed prekeys are meant to be changed regularly. Once both
the sender and receiver of a message have deleted their old signed prekeys, the message cannot be
retroactively decrypted by stealing secret keys.
When sending a message to Scholar in question 4, the “box” was created using Scholar’s public
encryption key and your secret signature key, both of which are long-lived. Here, the “box” will
be created using Scholar’s signed prekey and the secret decryption key for your signed prekey.
Question 5 part 1: upload a signed prekey [1 mark]
In this first part, you will generate and upload a signed prekey so that others can send messages to
you.
The first step is to generate and upload an identity verification key in the same manner as ques-
tion 3 part 1. Produce a signature and verification key using the equivalent of the C function
crypto sign keypair in your language. Upload the verification key in the usual way (en-
coded in base64 within the public key property of a JSON object in the POST request)
through the following web API page:
3A“prekey” is just an ordinary public encryption key with a short lifetime. This terminology was introduced by the
secure messaging application called Signal.
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
https://hash-browns.cs.uwaterloo.ca/api/prekey/set-identity-key
If the upload was successful, you’ll receive a 200 HTTP status code in response.
Next, generate a prekey using the same technique as question 4 part 2. Since prekeys will be used
for public-key encryption, you should generate your prekey using the equivalent of the C function
crypto box keypair in your language.
To produce a signed prekey, use your identity signature key to sign the public encryption key in
the same way as in question 3 part 2. Use the equivalent of the C function crypto sign in
“combined mode” to produce the signed prekey. Finally, base64 encode the signed prekey and
send it in the public key property of a JSON object to the following web API page:
https://hash-browns.cs.uwaterloo.ca/api/prekey/set-signed-prekey
If you receive a 200 HTTP status code in response, then you have received the mark for this part.
Question 5 part 2: send a message [2 marks]
Now that you have uploaded a signed prekey, you are ready to send a message to Scholar. Down-
load Scholar’s identity verification key sending a request containing a JSON object with Scholar
in the user key to this web API page:
https://hash-browns.cs.uwaterloo.ca/api/prekey/get-identity-key
Your request body should look similar to this:
{“api token”: “3158a1a33bbc…9bc9f76f”, “user”: “Scholar”}
You should receive the base64-encoded identity verification key in the public key key of a
JSON object in the response.
Using the exact same technique, request Scholar’s signed prekey by sending a request to this web
API page:
https://hash-browns.cs.uwaterloo.ca/api/prekey/get-signed-prekey
This time, you should receive Scholar’s signed prekey, encoded using base64, in the public key
property of the JSON object. You should now verify the signature on this prekey, and extract the
public encryption key, by using the equivalent of the C function crypto sign open in your
language. If the signature is valid, this function will return the public key to use for encryption.
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Finally, you can encrypt a message to send to Scholar. Encrypt the plaintext using Scholar’s
prekey as the public encryption key, and secret signature key associated with your prekey that
you generated in part 1. Use these keys for public-key authentication using the equivalent of
the C function crypto box easy in your language. This is the same public-key authenticated
encryption technique that you used in question 4 part 2. As before, you should include a newly
generated random nonce in your message.
Send the nonce and the ciphertext to Scholar by sending a request in the usual manner to the
following web API page:
https://hash-browns.cs.uwaterloo.ca/api/prekey/send
Abstractly, your request body should look something like this:
{“api token”: “3158a1a33bbc…9bc9f76f”, “to”: “Scholar”,
“message”: base64encode(
concat(nonce, box(plaintext, nonce, Scholar prekey, your prekey secret))
)}
If Scholar is able to successfully decrypt your message, you will receive a 200 HTTP status code
in the response indicating that you have been awarded the marks for this part.
Question 5 part 3: receive a message [1 mark]
Finally, you will need to receive a message sent to you by Scholar using the same encryption
scheme as the previous part. Check your inbox in the usual manner using the following web API
page:
https://hash-browns.cs.uwaterloo.ca/api/prekey/inbox
When you receive a message, you should look up the identity verification key and signed prekey
of the sender (if you have not done so already). You can do this by submitting requests to
https://hash-browns.cs.uwaterloo.ca/api/prekey/get-identity-key and
https://hash-browns.cs.uwaterloo.ca/api/prekey/get-signed-prekey as
described in part 2. Using Scholar’s prekey and the secret signature key associated with your
prekey, decrypt the ciphertext using the equivalent of the C function crypto box open easy
in your language. This is the same decryption function that was used in question 4 part 3.
Once you have decrypted the message sent to you by Scholar, enter the message in the “Question 5”
section of the “Question Data” page to receive the mark for this part.
https://hash-browns.cs.uwaterloo.ca/questions
CS 458/658
UNIVERSITY OF WATERLOO
Cheriton School of Computer Science
Computer Security and Privacy — Assignment 3 Fall 2021
Freedom Environment
If you successfully complete every question in the programming part, then you will be given access
to the “freedom” environment. Here, you can use the code that you wrote for question 5 to com-
municate with other students who have also completed all of the parts, assuming that you know
their WatIAM username and they have uploaded keys in the environment. To communicate, use
the following web API pages:
https://hash-browns.cs.uwaterloo.ca/api/freedom/get-identity-key
https://hash-browns.cs.uwaterloo.ca/api/freedom/set-identity-key
https://hash-browns.cs.uwaterloo.ca/api/freedom/get-signed-prekey
https://hash-browns.cs.uwaterloo.ca/api/freedom/set-signed-prekey
https://hash-browns.cs.uwaterloo.ca/api/freedom/send
https://hash-browns.cs.uwaterloo.ca/api/freedom/inbox
https://hash-browns.cs.uwaterloo.ca/api/freedom/message id/delete
To delete messages from your inbox, send a POST request in the usual manner to the delete web
API page listed above. The message id in the URL is the id value of the message provided
in the response to an inbox request. A 200 HTTP status code in the response indicates that the
message has been removed from your inbox.
Programming Question [24 marks]
libsodium documentation
Choosing a programming language
Ugster availability
Question 1: Using the API [5 marks]
Question 1 part 1: send a message [3 marks]
Question 1 part 2: receive a message [2 marks]
Question 2: Pre-shared Key Encryption [5 marks]
Question 2 part 1: send a message [3 marks]
Question 2 part 2: receive a message [2 marks]
Question 3: Digital Signatures [5 marks]
Question 3 part 1: upload a public verification key [2 marks]
Question 3 part 2: send a message [3 marks]
Question 4: Public-Key Authenticated Encryption [5 marks]
Question 4 part 1: verify a public key [2 marks]
Question 4 part 2: send a message [2 marks]
Question 4 part 3: receive a message [1 mark]
Question 5: Forward Secrecy [4 marks]
Question 5 part 1: upload a signed prekey [1 mark]
Question 5 part 2: send a message [2 marks]
Question 5 part 3: receive a message [1 mark]
Freedom Environment