Computer Security

Assignment 2
Solutions

ECE568, Winter 2011

Introduction
Answer the following questions.
When a word count restriction is given for a question, exceeding it will result in marks being deducted. If your answer is more than twice the maximum length, you will get zero for the question. Please include a word count for all your answers. We recommend that you use a utility like wc on ECF to count the number of words in your answer.
Your answers should be written in proper English, with full sentences. We reserve the right to deduct marks for poor English, unintelligible answers or illegible handwriting. All answers should be written in your own words - no copy-pasting! The completed assignments should be submitted in hardcopy during class on April 4, 2011.
Note that all written assignments should be done individually.

1

DES and differential cryptanalysis
Read http://securespeech.cs.cmu.edu/reports/coppersmith.pdf and answer the following questions:
1. Out of the 3 types of attacks an adversary can mount on a cryptographic algorithm, which ones does differential cryptanalysis utilize? [1 mark]
2. When was differential cryptanalysis first discovered? Which organization had knowledge of it at the time? [2 marks] 3. When did differential cryptanalysis first appear in public literature? List the title and the authors of the paper.
[2 marks]
4. What is an active S-box as described in the article? Why is it important to maximize the number of active
S-boxes? What property, discussed in class, does having the average number of active S-boxes per round be greater than 1 imply? [50 words] [10 marks]

1.1

Solution

1. Chosen Plaintext
2. 1974, IBM and the NSA
3. 1990, Eli Biham, Adi Shamir: Differential Cryptanalysis of DES-like Cryptosystems
4. An S-box is active in a round if the set of 6-bits that are input to the box are not all zero. Having the average number of S-boxes per round be greater than one implies that a large number of S-boxes will be active over the
16 rounds (as explained in the article). This means that there will be a large number of 1’s distributed over the rounds and as a result, any single S-box will cause other S-boxes to be active in later rounds. This implies that the cryptographic algorithm is likely to have good diffusion properties.

2

Rainbow tables

Read http://www.lightbluetouchpaper.org/2007/11/16/google-as-a-password-cracker/ and answer the following questions:
1. Find pre-images the following MD5 hash values [4 marks]:
• dd458505749b2941217ddd59394240e8
• b83b444c23f3d9dd2ddaa82335097548
2. How much disk space is required to store a complete rainbow table for an ideal cryptographic hash function that has a hash value length of n bits? [1 mark]
3. How much disk space is required to store a complete rainbow table for the following hash functions? Use scientific notation and keep 3 significant figures. [4 marks]
Page 1 of 7

Computer Security

Assignment 2
Solutions

ECE568, Winter 2011

• MD5
• SHA-1
• SHA-256
• SHA-512
4. Given a complete rainbow table, what is the cost to perform a preimage attack? What is the probability of success? [2 marks]
5. Given a complete rainbow table, what is the cost to perform a collision attack? What is the probability of success? [2 marks]
6. Is the technique presented in the blog post still relevant in 2011? Justify. [20 words] [5 marks]
7. What is a simple to use defense against rainbow table based attacks? [20 words] [2 marks]

2.1

Solution

Because of the vague wording in this question, answers are provided for your benefit. The quesiton will not be graded.
1. The pre-images are as follows:
• md5(568) = dd458505749b2941217ddd59394240e8
• md5(penguins1) = b83b444c23f3d9dd2ddaa82335097548
2. Note that the question assumed that the rainbow table is a complete table of pre-images for every possible hash value (i.e. no reduction function). In practice, rainbow tables always have reduction functions to make storage for the pre-images feasible. In addition, rainbow tables are typically incomplete so not every hash value will have a pre-image in the table. Since the question implies that the rainbow table is complete, then there must be an entry for each hash value. The question doesn’t specify the size of an entry, so the answer is given as the number of entries in the table, which is just 2h ashs ize.
• MD5: 21 28 entries
• SHA-1: 21 60 entries
• SHA-256: 22 65 entries
• SHA-512: 25 12 entries
3. A pre-image attack requires one look up. Given a complete rainbow table, the probabiility is 100%.
4. A collision attack can be performed by generating a random string, computing the hash of the string and then doing a lookup into the table. The probability of success is also 100%.
5. The technique in the blog is not relevant given the wide availability of rainbow tables on the internet.
6. A simple defense is to salt your password so that the entries in a precomputed rainbow table are not valid.

3

Kerboros versus Public key infrastructure
1. What is the trusted third party called in Kerberos? Briefly describe its functions.[30 words] [5 marks]
2. What is the trusted thirs party called in PKI? Briefly describe its functions.[30 words] [5 marks]
3. Consider a DDOS attack on Kerboros’s central server. Which property of security (confidentiality, availability, integrity) has been violated from the user’s perspective? Explain. [2 marks]
4. Now consider a DDOS attack on a PKI’s central server. Which property of security has been violated from the user’s perspective? Explain. [2 marks]
Page 2 of 7

Computer Security

Assignment 2
Solutions

ECE568, Winter 2011

5. Consider a Kerboros system in which the central server has been silently compromised. Which property of security has been violated from the user’s perspective? Explain. [2 marks]
6. Consider a PKI system in which the central server has been silently compromised. Which property of security has been violated from the user’s perspective? Explain. [2 marks]

3.1

Solution

1. The trusted third party can be called the Key Distribution Center, or Authentication Server and Ticket Granting
Server, which make up the former.
2. A (Root) Certificate Authority.
3. Availability, when the central server is not available, then the user cannot access any resources.
4. None, unavailability of the CA just means new keys cannot be certified. However, existing users with keys are not affected.
5. Confidentiality and/or integrity. Compromising the server means the adversary can eavesdrop on all connections as well as forge new connections.
6. Confidentiality and/or integrity depending on what the certified keys are used for. Confidentiality if they are encryption keys. Integrity if they are signing keys.

4

Public Key Encryption
An alternative public key scheme, based on Diffie-Hellman works as follows:
• Alice selects a large prime number p and a generator g for the field defined by modp. Alice randomly selects a value x, 1 ≤ x ≤ p − 2 and computes g x modp. The tuple {p, g, g x } becomes Alice’s public key, and x is Alice’s private key.
• Bob, who wants to send Alice a message m, get’s Alice’s public key through some certfied method. To encrypt m, he randomly selects a value y, 1 ≤ y ≤ p − 2 and computes A = g y modp and B = m · (g x )y modp and sends
{A,B} to Alice.
• Alice can recover m by computing B/Ax modp

Answer the following questions:
1. Is this scheme secure? If so, what difficult problem must the adversary solve to recover m without Alice’s private key? Explain. [40 words] [4 marks]
2. Why are x and y restricted to the given range? What is wrong with using x, y = 0 or x, y = p − 1? [20 words]
[2 marks]
3. Suppose Bob is lazy and does not use a true random number generator. What weaknesses are introduced if y is not secret? What if the same y is used to encrypt multiple messages? [50 words] [6 marks]
4. How does this scheme compare to RSA in terms of computational requirements for Bob? Assume the same size modulus/key length is used for both. Explain. [20 words] [5 marks]
5. How does this scheme compare to RSA in space requirements for transmitting the encrypted mesage? Assume the same size modulus/key length is used for both. Explain. [20 words] [5 marks]

Page 3 of 7

Computer Security

4.1

Assignment 2
Solutions

ECE568, Winter 2011

Solution

1. The scheme is as secure as Diffie-Hellman. Alice can recover m because she knows the value of x. To do the same, the adversary must recove x, which means thata he must be able to perform discrete log. Discrete log is a problem believed to be computationally hard.
2. x = 0 is not defined in the field of p, i.e. g 0 modp is not permitted. x = p − 1 means that g x modp = 1 via fermat’s little theorem. Thus, the adversary will be able to easily deduce the value of x.
3. By using the same y for several messages, this means that A = g y modp will be the same for all of those messages. Say we have two messages m and m , which encrypt to B and B respectively and the same y is used for both encryptions. Then we can see that m = B/Ax and m = B /Ax or Ax = B /ma . Subsituting this back into the first equation we can recover m = B · m /B .
4. This scheme has roughly double the computational requirements as RSA since it requires two exponentiations, one for A and one for B.
5. This scheme has roughly twice the space requirements since two values of size p must be sent as part of the cipher text.

5

Information Flow Models
Given the following relationships between security categories and levels, answer the questions below:
• Confidentiality levels: T S > S.
• Confidentiality categories: CA , CB , CC .
• Integrity levels: C > N C.
• Subjects:
– SA : (T S, {CA , CB }), N C
– SB : (S, {CC }), N C
– SC : (S, {CA , CC }), C
• Objects:
– OA : (T S, {ø}), N C
– OB : (T S, {CA , CC }), N C
– OC : (S, {CC }), C
1. Ignore the integrity information and list the objects each subject can read and/or write using the Bell-LaPadula
Policy. [6 marks]
2. Ignore the confidentiality information and list the objects each subject can read and/or write using the Biba
Policy. [6 marks]
3. Suppose both confidentiaility and integrity access controls are active simultaneously. Indicate which subjects are then able to access which objects for both read and/or write. [6 marks]

Page 4 of 7

Computer Security

5.1

Assignment 2
Solutions

ECE568, Winter 2011

Solution

Note that the original question was phrased assuming Lipner’s policy, which has integrity categories. However, Lipner’s is no longer covered in the course and we use Biba that does not have integrity categories. Thus, the question will be graded without taking integrity categories into account.
1. Bell-Lapadula:
• SA : Read = {OA }, W rite = {ø}
• SB : Read = {OC }, W rite = {OB , OC }
• SC : Read = {OC }, W rite = {OB }
2. Biba:
• SA : Read = {OA , OB , OC }, W rite = {OA , OB }
• SB : Read = {OA , OB , OC }, W rite = {OA , OB }
• SC : Read = {OC }, W rite = {OA , OB , OC }
3. Combined:
• SA : Read = {OA , }, W rite = {ø}
• SB : Read = {OC }, W rite = {OB }
• SC : Read = {OC }, W rite = {OB }

6

Multi-factor authentication

Bob recently signed up for telephone banking. He was given a dongle which works in conjunction with his PIN.
Answer the following questions.
1. Briefly explain how this security scheme should work.[50 words] [5 marks]
2. Is this scheme secure against theft of the dongle? Explain. [20 words] [5 marks]
3. If the telephone company guarantees that all phone lines are free from eavsdropping, does this eliminate the need for the dongle? Explain. [20 words] [5 marks]
4. List all the cryptographic primitives used in this scheme. Clearly identify which ones reside in the dongle and which ones reside on the bank’s servers.[20 words] [2 marks]
5. There is a serial number on each dongle. What purpose does this serve? [10 works] [1 mark]
6. Does this serial number need to be randomly generated? Does this serial number need to be kept secret by
Bob? Explain. [30 words] [5 marks]
Page 5 of 7

Computer Security

6.1

Assignment 2
Solutions

ECE568, Winter 2011

Solution

1. The security token contains a secret key that is used to run a stream cipher continuously. Since the the server share the same stream cipher and the same secret key, the output of the stream cipher is identical and thus can be used as a shared secret between Bob and the Bank.
2. Yes, if the security token is lost or stolen Bob simply needs to report the loss and the bank will assign him a new one. With multi-factor authentication the compromise of a single factor does not compromise the entire system. 3. Yes, security token, along with Bob’s PIN number helps to authenticate Bob as Bob. Even if a secure channel exists the bank has no way of verifying the person using the secure channel is indeed Bob.
4. A stream cipher is used in this scheme. The same cipher is used on both the security token and the authentication server.
5. The serial number serves to identify the secret stream cipher key of each authentication token.
6. The serial number does not need to be random as it reveals no information about the key (which shoudl be random). It merely serves as an identifier so it only needs to be unique. As a result, it also does not need to be kept secret. It servers no purpose after the token has been activiated.

7

Web Security
1. Explain the same origin policy. What attacks does it prevent?[40 words] [5 marks]
2. What are drive-by downloads? What are some defenses against it?[30 words] [5 marks]

7.1

Solution

• The same origin policy allow scripts originating from the same site to interact with each other and the site contents, but prevents them from accessing contents and scripts originating from other sites. It prevents attacks that aim to steal private user information.
• Drive-by downloads is a category of attacks that download malicious files unto a user’s computer without consent. Drive-by download attacks either exploit unpatched browser vulnerabilities, or trick the user into clicking on a malicious link. The best defenses are to keep the browser up to date, use a pop-up blocker, and avoid visiting suspicious sites.

8

Covert Channels

Acme Corporation ships a proprietary web browser that contains a back-door which ”phones home” periodically with private user information. Unfortunately for Acme, a group of security researchers discovered all the covert channels used in their malicious browser. The covert channels used were:
• Altering inter-packet timing
• Encoding data in the packet size
• Encoding data in the HTTP header
• Changing the browser User-Agent
• Sending extraneously packets
Now Acme hired you to fix their mistakes. Suggest 2 new covert channel schemes.[50 words] [10 marks]

Page 6 of 7

Computer Security

8.1

Assignment 2
Solutions

Solution

• Some possible alternatives are:
– Encoding data in the TCP Initial Sequence Number field
– Encoding data in the size of the TCP window
– Re-order the sequence in which images are requested from the web server
– Encoding data in the HTTP header only within SSL sessions
– Modulate the transfer speed of the browser’s download manager

Page 7 of 7

ECE568, Winter 2011