ASSIGNMENT 3 SOlution

Total Marks: 50




Written Response Questions TA: Jason Cao y243cao@uwaterloo.ca




(O ce hours: Tuesdays 12:00 {1:00 pm in DC 3333)




Programming Questions TA: Bailey Kacsmar bkacsmar@uwaterloo.ca




(O ce hours: Friday 1:30 pm{2:30 pm in DC 3333)




Please use Piazza for all communication. Ask a private question if necessary. The TAs' o ce hours are also posted to Piazza for reference. You are expected to follow the expected Aca-demic Integrity requirements for Assignments; you can nd them here: https://uwaterloo. ca/library/get-assignment-and-research-help/academic-integrity/academic-integrity-tutorial. Strict penalties will be enforced on students for any Academic Integrity violations.



Written Response Questions [23 marks]







Note: Please ensure that written questions are answered using complete and grammatically correct sentences. You will be marked on the presentation and clarity of your answers as well as on the correctness of your answers.







[9 marks] Cryptosystems



[5 marks] One-Time Pad (OTP)



OTP is de ned as follows: C = P K, where ciphertext C, plaintext P and key K are bit strings of the same length, and is bitwise XOR. OTP is not secure if the key is reused.




[1 mark] Suppose two plaintext strings of the same length, P1 and P2, are padded with the same key K to produce ciphertexts C1 and C2. Describe how you can obtain P1 P2, given C1 and C2 (but not P1, P2, or K). Prove the correctness of your solution.



[2 marks] Now suppose P1 and P2 are English ASCII texts, where every eight bits represent either a letter or whitespace. Describe how you can obtain P1 and P2, given P1 P2.



[2 marks] Given C1 and C2, and after recovering the plaintexts using the two previous steps, can you determine the key K, and why?



[4 marks] (Textbook) RSA



Consider the following usage of RSA (known as \Textbook RSA"). For simplicity, the process of key generation is omitted here.




Bob generates 3 positive integers according to the key generation algorithm: n, e, and d. He publicly announces n and e on his webpage (public key), and keeps d to himself (private key).




When Alice wants to send message M to Bob, she calculates C = Me mod n, and sends C to bob.




When Bob receives C from Alice, he recovers M by calculating M = Cd mod n.




Based on this de nition, answer the following questions.




i. [1 mark] Is this scheme secure against replay attacks? If so, explain why; otherwise, give a simple countermeasure.




[2 marks] If the total number of possible messages is limited (for example, M is 32-bit), can an attacker recover a plaintext M given the corresponding ciphertext C and the public key (n and e)? Explain why. Also, if such an attack is possible, design a countermeasure.



[1 mark] What measure can we add to this encryption scheme, such that Bob can authenticate Alice when he receives C?


2. [8 marks] GnuPG




A GnuPG public key for y243cao@uwaterloo.ca is provided along with the assignment on the course website (y243cao.asc). Perform the following tasks. You can install GnuPG on your own computer, or use the version we have installed on the ugster machines.




[2 marks] Generate a GnuPG key pair with 2048 bits for yourself. Use RSA as the encryption algorithm, your real name, and your uwaterloo university email address. Export this key using ASCII armor into a le called key.asc. [Note: older versions of GnuPG might not have the RSA option, so check that the version you are using has this option. The ugster machines have a new enough version, but the student.cs machine may not.]



[2 marks] Use this key to sign (not local-sign) the y243cao@uwaterloo.ca key. Its true ngerprint is: FA4F 2ED6 347C B3A0 EE8F CDD1 82A0 9499 C648 596B. Export your signed version of the y243cao@uwaterloo.ca key into a le called y243cao-signed.asc; be sure to use ASCII armor. [Note: signing a key is not the same operation as signing a message.]



[2 marks] Create a message containing your userid and name. Sign it using the key you generated, and encrypt it to the y243cao@uwaterloo.ca key. You should do both the encryption and signature in a single operation. Make sure to use ASCII armor, and save the output in a le called message.asc.



[2 marks] Brie y explain the importance of ngerprints in GnuPG. In particular, explain how users should check ngerprints and what type of attacks are possible if users do not follow this procedure properly.


[6 marks] Data Privacy


[3 marks] A hospital has in its database a table called Employees, which contains N records. This table stores the following information for each employee:



ID: A unique alphanumerical string that is used to identify each employee in the table.




Type: The employee's job type. All employees in this hospital are classi ed into three categories: Doctor, Nurse and Non-medical.




Description: Additional description of the employee's job.




Salary: Amount of money earned by the employee per month.




Table 1 shows some sample entries that are randomly drawn from the table.




ID
Type
Description
Salary








a45smith
Nurse
intensive care
8742
r1krold
Non-medical
accountant
6479
k5park
Nurse
emergency response
6059
j1diego
Doctor
brain surgeon
65000











Table 1: Samples drawn from the Employee table




To prevent users of this database from learning the salary of other employees, the database is con gured to suppress the Salary eld in the output of queries. However, users can execute queries in the following form:




SELECT SUM(Salary) FROM Employee [WHERE ...]




In addition, queries that match fewer than k or more than N k but not all N records are rejected.




Among all the authorized users of the hospital's database, Eve is particularly curious and wants to know the salary of a particular employee whose ID is \jdoe". She also has the following background knowledge about the hospital and the database:




The composition of the hospital sta is approximately 20% doctors, 60% nurses and 20% non-medical workers.




The exact value of k is unknown, but is believed to be in the range of (0:05N; 0:25N).




Nothing else is known about \jdoe", other than this employee ID.




Given the above information, describe how Eve can use a tracker attack to query the database and derive the salary of \jdoe". In your solution, you should present




the tracker, 2) three additional queries, and 3) how to derive the salary of \jdoe" based on the query results. (Note: answers that do not point out the tracker will lose 1 mark.)





[3 marks] The hospital is releasing some patient information in a public report. Table 2 is the full table that the hospital intends to include in the report.



Age
Gender
Disease






81
F
Flu
65
M
Flu
63
M
Heart disease
81
M
Heart disease
78
F
Heart disease
73
M
Heart disease
67
M
Heart disease
74
F
Cancer
70
M
Cancer
84
F
Cancer
77
M
Alzheimer's









Table 2: Full patient information table before anonymizing




To protect the privacy of the patients included, the hospital decides to modify the table such that it is 3-anonymous. In particular, the hospital declares that \age" and \gender" elds are identi ers, and further poses the following constraints during the anonymization process:




The age eld cannot be masked (e.g. changing \64" to \6*" is not allowed). However, it can be modi ed to another integer within the range of 5 (e.g. \64" can be changed to any integer within the range [59, 69]).




The gender eld cannot be masked or modi ed.




Please present a 3-anonymous solution satisfying the above constraints, and give the value l for which your solution is l-diverse. You may reorder the records in any way for your convenience.
Programming Questions [27 marks]






Background







In this section we will study padding oracle attacks. Block ciphers operate on a xed number of bits, such as 64 (DES) or 128 (AES). To encrypt longer messages, a mode of operation such as CBC can be used (see Figure 1). However, this still requires that the message length be a multiple of the block size. To accommodate arbitrary-length messages, a padding scheme is used. The decryption routine will need to check that the message padding is valid. Unfortunately, information about the validity of the padding can easily be leaked to an attacker. This \padding oracle" can allow the attacker to decrypt (and sometimes encrypt) messages without knowing the encryption key.




The padding oracle attack was originally described in a 2002 paper by Serge Vaudenay. This paper is available at https://www.iacr.org/archive/eurocrypt2002/23320530/cbc02_ e02d.pdf and will serve as your reference for this attack. Note that the author frequently uses the term \word" where we would usually say \byte". Padding oracle attacks have continued to be relevant since their inception, with new attacks being discovered regularly. Some recent examples are the POODLE attack discovered in 2014 and the DROWN attack discovered in March 2016, both attacking SSL and TLS (not required reading).



Figure 1: CBC Mode Encryption










Application Description







A simple web application is running at http://localhost:4555 on each ugster machine. To view this application in your web browser, you can use http://ugsterNN.student. cs.uwaterloo.ca:4555 (instructions for working from home are the same as with previous



assignments). However, please use http://localhost:4555 in your programs to ensure that they run quickly no matter which ugster machine we test them on.




When you visit the web application it will set a cookie named user in your browser. In other words, the HTTP response will contain a Set-Cookie header like the following:







Set-Cookie: user="K/wLMO+V8Qbo5B4spv6/PP98W1mofu7vQT83dbascyLcyc9mlFi4qzLyYjsyTLWF"










The value of this cookie is encrypted with AES using a key known only to the web server. AES is used in CBC mode, and the randomly chosen IV is prepended to the ciphertext. The result is then Base64 encoded to form the cookie value. Base64 is a standard way of encoding binary data into printable ASCII characters. It is implemented in many programming languages and the base64 Unix utility, and is speci ed in RFC 3548. The padding scheme used by the web application is the one suggested by NIST referred to in Section 4 of the padding oracle paper. The rst byte of the padding has the value 0x01, and all other padding bytes have the value 0x00. There is always at least one byte of padding.




When you visit the web application again, your browser will send the cookie back to the server. This is done with a Cookie header with the same form as the Set-Cookie header above. This behaviour can of course be emulated programmatically. The web server will use its encryption key to attempt to decrypt any cookie sent to it. If the decryption is successful the HTTP response will contain a 200 (OK) response code. However, if the decryption fails a 500 (Internal Server Error) response code will be returned. See the section below titled \HTTP with curl" for more information on working with HTTP.










Questions




[2 marks] What are the average case and worst case number of padding oracle calls required to perform this attack?



[3 marks] What cryptographic tool could be used to x this vulnerability? Which of the



CIA properties fCon dentiality, Integrity, Authenticityg does it provide? How does it x the vulnerability? Assume that the web server must return a di erent response for users with valid versus invalid cookies.



[3 marks] How would you modify the attack described in the paper to account for the di erent padding scheme used by the web server? List the lines in Sections 3.1 and 3.2 that require changes and show how they should be changed.



[12 marks] Write a program called decrypt that implements the padding oracle attack on the web application described above. Your program will be called with a single
command line argument containing a Base64-encoded cookie value to be decrypted. These cookies will have at least two 16-byte blocks (the IV and at least one ciphertext block), but may not have the same number as those returned by the server. Your program should generate the appropriate cookie values, send them to the web server using HTTP, and observe its response codes in order to decrypt the given cookie value. It should print the resulting plaintext (without padding) to stdout, which will consist of only printable ASCII characters. You can print debug output to stderr if you like. Your program should run in a maximum of 10 minutes for inputs up to 10 blocks long.




You may use any programming or scripting language available on the ugster machines. If your preferred language is not available, we may be able to accommodate requests. Many programming languages have built-in libraries for making HTTP requests and encoding and decoding Base64. You can also use third party libraries for these tasks if necessary. Another option is to call the curl and base64 programs as described in the section below titled \HTTP with curl". You will submit a single le named src.tar. For evaluation, this le will be extracted and we will attempt to run a script at the top level with ./decrypt <cookie. This script could be your program itself, or it could be a script that compiles and then runs your program. In either case it should start with an appropriate shebang line. Your submission should not contain any compiled executables. For the example cookie shown above, the invocation would be:




./decrypt JKAlO6GB1bOtJ1I/VzlhbJQ+MirfsnUrk9HzzunQxvQ=




[7 marks] Write a program called encrypt that encrypts arbitrary cookie values such that they will be correctly decrypted by the web application. Your program does not need to know the web application's encryption key. It will be called with a single command line argument containing a printable ASCII plaintext to be encrypted. Your program should generate the appropriate cookie values, send them to the web server using HTTP, and observe its response codes in order to encrypt the given value. It should print the resulting Base64-encoded ciphertext to stdout. You can print debug output to stderr if you like. Your program should run in a maximum of 10 minutes for inputs up to 10 blocks long.



Submission is similar to the previous question. Your program source les should be included in the same src.tar le. For this question, we will attempt to run a script at the top level with ./encrypt <plaintext.




Hint: In CBC mode there are three stages a block goes through in decryption. It starts as a ciphertext, the ciphertext is decrypted by the block cipher to an intermediary value, and then the intermediary value is XORed with the previous ciphertext block (or the IV for the rst block) to form the nal plaintext value. If we know the intermediary value for a given ciphertext block, we can manipulate the IV to gain complete control over what that block will be decrypted to. If we want to produce a plaintext x, then the IV should be x XORed with the intermediary value. This idea can easily be extended to multi-block messages. Start from the last block and move backwards. Pick any



value to be the ciphertext for the last block and decrypt it (using your method from the previous question) to nd the corresponding intermediary value. Then calculate the IV required to produce the desired plaintext. This IV will be the ciphertext for the second-last block, and so on.










HTTP with curl







HTTP (Hypertext Transfer Protocol) is a simple protocol for transferring text over a network. If you've used the Internet, you've used HTTP. In this protocol, a client makes a request to a server and the server replies with a response. A request generally asks for a resource located at a particular URL, and the response provides that resource. These resources are often HTML web pages, but here we'll be using mostly plain textual content. Let's see an example of a request and a response:







curl -v http://localhost:4555 GET / HTTP/1.1



User-Agent: curl/7.19.7




Host: localhost:4555




Accept: */*









< HTTP/1.1 200 OK




< Content-Length: 37




< Set-Cookie: user="8hIOODzClpAhMw/0dAalk+YrwZqmZPmuCyOmRpzyfH+fnJ0dKBtOL+NaHufa1 MQw1XE8KtKXp2ARNcIvUVFruw=="




< Server: TornadoServer/4.3




< Etag: "4b44c375286c4a668502645e4da51dd29441e4e9"




< Date: Wed, 02 Nov 2016 17:33:32 GMT




< Content-Type: text/html; charset=UTF-8




<




Hello! I'll remember when I saw you.










Note that some extra debug output from curl has been omitted. The lines starting with \" are the client talking to the server, and lines starting with \<" show communication in the other direction. The HTTP request starts with a method; we'll only be using GET. It then speci es the requested path and the protocol version. The following lines contain headers which specify additional information. These are present in both requests and responses. The response starts by con rming the protocol version. It then presents the status code, which is essential for us as it is the source of our padding oracle. The main response header of interest to us is the Set-Cookie header. We can use the base64 utility to decode it, although it will likely result in unprintable characters, so we'll display the binary data as a hex dump with xxd:








echo "8hIOODzClpAhMw/0dAalk+YrwZqmZPmuCyOmRpzyfH+fnJ0dKBtOL+NaHufa1 MQw1XE8KtKXp2ARNcIvUVFruw==" | base64 -d | xxd
00000000: f212 0e38 3cc2 9690 2133 0ff4 7406 a593 ...8<...!3..t...




00000010: e62b c19a a664 f9ae 0b23 a646 9cf2 7c7f .+...d...#.F..|.




00000020: 9f9c 9d1d 281b 4e2f e35a 1ee7 dad4 c430 ....(.N/.Z.....0




00000030: d571 3c2a d297 a760 1135 c22f 5151 6bbb .q<*...`.5./QQk.










You can see that this cookie contains four 16-byte blocks. The rst is the IV, and the next three are ciphertext blocks. To send the cookie back to the server, we can do the following:







curl -v -b user=8hIOODzClpAhMw/0dAalk+YrwZqmZPmuCyOmRpzyfH+fnJ0dKBtOL+NaHufa1 MQw1XE8KtKXp2ARNcIvUVFruw== http://localhost:4555



GET / HTTP/1.1




User-Agent: curl/7.47.0




Host: localhost:4555




Accept: */*




Cookie: user=8hIOODzClpAhMw/0dAalk+YrwZqmZPmuCyOmRpzyfH+fnJ0dKBtOL+NaHufa1 MQw1XE8KtKXp2ARNcIvUVFruw==






< HTTP/1.1 200 OK




< Date: Wed, 02 Nov 2016 17:38:13 GMT




< Content-Length: 47




< Etag: "86190721ce68176612428946d30ccc0d6e5a99ec"




< Content-Type: text/html; charset=UTF-8




< Server: TornadoServer/4.3




<




Hello! I first saw you at: 2016-11-02 13:33:32










It would be best to use an HTTP library for your programming language when writing your solutions, but you can call the curl program directly as a last resort. curl is also very useful for manually debugging web applications.










What to hand in







Using the \submit" facility on the student.cs machines (not the ugster machines or the UML virtual environment), hand in the following les:







a3.pdf: A PDF le containing your answers to the written response and relevant program-ming questions. a3.pdf must contain, at the top of the rst page, your name, UW userid, and student number.









10



src.tar: A tar archive directly containing your decrypt, encrypt program source les. (Please notice that these programs need to be executables, and without any extensions, e.g., decrypt.sh is wrong and should be sent as decrypt. To create the tarball, cd to the directory containing your code and run the command







tar cvf src.tar .




(including the .) in the directory where you have your les, not the parent directory.






































































































































































11