程序代写代做代考 Hive database dns scheme cache algorithm IOS CS 458/658

CS 458/658
UNIVERSITY OF WATERLOO Cheriton School of Computer Science
Computer Security and Privacy Fall 2016 Sergey Gorbunov and Urs Hengartner
ASSIGNMENT 3
Assignment due date: Friday, December 2nd, 2016 3:00 pm
Total Marks: 58
Written Response Questions TA: Peiyuan Liu (Office hours: Tuesday 3:30 pm-4:30 pm in DC 3332) Programming Questions TA: Navid Nasr Esfahani (Office hours: Friday 9:30 am-10:30 am in DC 3332)
Please use Piazza for all communication. Ask a private question if necessary. The TAs’ office hours are also posted to Piazza for reference. You are expected to follow the expected Academic Integrity requirements for Assignments; you can find 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 [31 marks]
Note: For written questions, please be sure to use complete, grammatically correct sentences where appropriate. You will be marked on the presentation and clarity of your answers as well as the content.
1. [5 marks total] Variants of RSA
In RSA, the public key is a pair of integers (n, e), where n = pq for large primes p and q. The private key is the triple (p, q, d) where de ≡ 1 mod (p − 1)(q − 1). The encryption ofamessagemtoyieldtheciphertextcisc=me modnandthedecryptionism≡cd mod n.
A key part of making RSA secure is to choose appropriate primes numbers. It is often stated that text-book RSA is weak because there are no restrictions on how to choose these primes. In this problem, we will investigate a variation of RSA that puts restrictions on the primes p and q.
Let us assume the genius security expert, Ensei Tankado, thinks that the following way of generating prime would be a good idea: choose the numbers g, b, and a such that p = 2ga+1 and q = 2gb + 1 are prime. Ensei first puts an implicit restriction that the greatest common
1

divisor of a and b is 1 (greatest common divisor of two integers is the largest integer that divides both the numbers).
He also adds the restriction that the term 2gab + a + b should be prime (in retrospect, this decision proves important for the security of the encryption scheme). Much like in text-book RSA, he then sets n = pq. During a round of beer, he boasts to his arch enemy Commander Trevor Strathmore that his scheme is secure (that it is impossible to factor n into primes p and q in polynomial time).
Mr. Strathmore never took this (or any security) course and blindly believes that Ensei has devised an “unbreakable” encryption scheme. To impress another security expert, Susan Fletcher, he gets involved in a bet with her that this scheme is unbreakable, even if given the values of a and b. Susan is intelligent, so after seeing the encryption scheme closely, she asks Trevor to give her any two values of a and b that fit the scheme. Blinded by incomplete knowledge, the commander gives Susan the values of a and b. We will see how Susan can factor n in time that is polynomial in the bit length of n and win the bet.
(a) [2 marks] Write the number n in terms of g, a and b.
(b) [2 marks] Use the above relation to give a closed formed expression for g.
(c) [1 marks] Write in one sentence, how the above information helps you in finding the factors of N.
The characters involved in this problem are taken from Dan Brown’s Digital Fortress. 2. [12 marks total] TLS
(a) [3marks]MallorysetsupaPhishingwebsite,https://www.cibc.mallory.ca, to steal the login information of CIBC customers. She lures a victim to her website with a Phishing email that contains a link to the website. During the TLS connection setup process, she has her server send the original CIBC certificate, which she retrieved ear- lier from the real CIBC website, to the victim’s browser. Will the browser notice the Phishing attack? Explain.
(b) [3marks]Mallorynoticesthatthevictim’sDNSserverhasnotbeenpatchedagainstthe severe vulnerability that led to a worldwide emergency upgrade of all DNS servers (see http://unixwiz.net/techtips/iguide-kaminsky-dns-vuln.html, not a required reading). She manages to execute a DNS cache poisoning attack. The victim’s host now maps www.cibc.ca to the IP address of a server controlled by Mal- lory. As before, the server will return the original CIBC certificate to a browser. Will the victim’s browser notice the Phishing attack when connecting to www.cibc.ca? Explain.
2

(c) [3 marks] When looking at the public verification key in the CIBC certificate, Mallory notices that it (and the private signing key) were generated on a machine affected by an OpenSSL vulnerability that made the machine’s ”random” number generator and hence all generated keys predictable (see https://en.wikipedia.org/wiki/ Random_number_generator_attack#Debian_OpenSSL, not a required read- ing). Mallory recomputes CIBC’s signing key and makes her server use it. (She also poisons the victim’s DNS cache, as explained earlier.) Will the victim’s browser notice the Phishing attack? Explain.
(d) [3 marks] Even if the victim’s browser notices the Phishing attack in one of the scenar- ios above, why is the attacker still quite likely to succeed, at least with older versions of Firefox and Internet Explorer? (Assume that certificates are properly processed by a browser, i.e., software bugs is not a valid answer.)
3. [8 marks total] GnuPG
A GnuPG public key for p69liu@uwaterloo.ca is provided along with the assignment on the course website (p69liu.asc). Perform the following tasks. You can install GnuPG on your own computer, or use the version we have installed on the ugster machines.
(a) [2 marks] Generate a GnuPG key pair for yourself. Use the RSA and RSA algorithm option, your real name, and an email address of your-userid@uwaterloo.ca. Export this key using ASCII armor into a file called key.asc. [Note: older versions of GnuPG might not have the RSA and RSA algorithm 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.]
(b) [2marks]Usethiskeytosign(notlocal-sign)thep69liu@uwaterloo.cakey.Itstruefin- gerprint is: 7132 FAA5 D507 77DE 63B4 94A6 ADE8 4F18 A0F0 BCC9. Export your signed version of the p69liu key into a file called p69liu-signed.asc; be sure to use ASCII armor. [Note: signing a key is not the same operation as signing a message.]
(c) [2 marks] Create a message containing your userid and name. Sign it using the key you generated, and encrypt it to the p69liu 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 file called message.asc.
(d) [2 marks] Briefly explain the importance of fingerprints in GnuPG. In particular, ex- plain how users should check fingerprints and what type of attacks are possible if users do not follow this procedure properly.
4. [6 marks total] Inference Attacks
The Human Resources department of FrobozzCo International has a table called Employee, with N records, in its database. This table stores the following information about each em- ployee:
3

• Name: The employee’s first name, which is unique for every employee in the database.
• Birthdate: The employee’s year of birth.
• Occupation: The position the employee fills at the company. An employee with an occupation other than “Staff” is considered a specialist.
• Allegiance: The realm the employee swears their allegiance to. Although FrobozzCo is located in the land of Quendor, they believe that a diverse work force is beneficial to the production of magical products and employ workers from as far away as Antharia and Kovalli.
• Salary (in Zorkmids): the amount of hard-earned cash each employee takes home over the course of the year.
Below is an excerpt (not the entire table):
Table 1: Part of Employee Table
Name
Birthdate
Occupation
Allegiance
Salary
John Lucille Natalie Ralph Frank Leonardo Jill Matthew Rachel
725
788
770
737
741
731
738
722
760
Founder Enchanter
Staff
Public Relations Staff
Director of Design Navigation Expert Staff
Staff
Quendor Quendor Quendor Quendor Antharia Quendor Antharia Kovalli Kovalli
15,000 10,225 5,000 13,721 4,908 12,000 10,426 5,923 4,907
To deter employees from comparing their earnings and complaining about the amount of Zorkmids they take home to their families, 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. Wewillusek= N.
8
(a) [3 marks] Use a tracker attack, as defined in class, to design a tracker and a set of three queries based on this tracker that will let you infer Lucille’s salary. Both the tracker and the three queries need to be of the form
SELECT SUM(Salary) FROM Employee …
4

Assume that employees’ names are unique and not known to the attacker (apart from Lucille’s) and that the attacker has no additional information about Lucille (not even her status as a specialist). The only knowledge the attacker knows about the underlying distribution of the database is that FrobozzCo International hires an equal number of specialists (i.e. with an occupation other than “Staff”) and staff employees. In your solution, you should give 1) your tracker, and 2) the set of three queries.
(b) [3 marks] Cornelius Flathead, the Human Resources Director of FrobozzCo Interna- tional becomes aware of the tracker attack and forbids SUM(Salary) queries. Instead the Human Resources Department allows 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 rejected.) How would you use queries of this type to learn Rachel’s salary? You may assume that no one in the database makes more than 200,000 Zorkmids and that all salaries are non- negative.
5

Programming Questions [27 marks]
Background
In this section we will study padding oracle attacks. Block ciphers operate on a fixed 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 fre- quently 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
6

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=”JKAlO6GB1bOtJ1I/VzlhbJQ+MirfsnUrk9HzzunQxvQ=”
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 specified in RFC 3548. The padding scheme used by the web application is as follows: for a padding of length n, the padding starts with a byte that has value n (the length of the padding), followed by n − 1 bytes with value 0. There is always at least one byte of padding, so 1, 20, 300, and 4000 are valid examples
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 behavior 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
1. [2 marks] What are the average case and worst case number of padding oracle calls required to perform this attack?
2. [3 marks] What cryptographic tool could be used to fix this vulnerability? Which of the CIA properties {Confidentiality, Integrity, Authenticity} does it provide? How does it fix the vulnerability? Assume that the web server must return a different response for users with valid versus invalid cookies.
3. [3 marks] How would you modify the attack described in the paper to account for the dif- ferent 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.
4. [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
7

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 file named src.tar. For evaluation, this file will be extracted and we will attempt to run a script at the top level with ./decrypt . 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=
5. [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 files should be included in the same src.tar file. For this question, we will attempt to run a script at the top level with./encrypt