Assignment 5 (COMP 4109: Applied Cryptography)

Last update: 25 Mar. 2004, 11:30pm (check course web site for most recent update)

Due: Wed. March 31 (in class) Alternatively: hand the assignment in at 2:30pm on Mon. Apr.5 at a special review class, in the usual class room (Prof. Van Oorschot will be available to answer specific review questions by students).

1. Table 10.2 (HAC, p.392) gives the time to exhaustively search some password spaces for specified parameters. CPUs are now much faster than 1995 when the table was created.

a) Update the entire table for the following situation. Assume password verification uses MD5, with an iteration count t = 1000; assume a processor speed of 3.2GHz, and optimized MD5 code taking 3.66 cycles/byte of input. (Hint: an MD5 password verification involves processing the equivalent of 64 bytes of input, due to preprocessing and padding of shorter inputs to a full block, as given in HAC.)

b) Separate from part a) above, now assume the attacker uses 1000 CPUs. Recompute the table row for n=8 under this additional assumption. (Aside: this is like 1 CPU and t=1.)

c) Why not use a larger value t, e.g. t = 10⁹, to slow down attacks?

2. Give a clear explanation of the following statement (HAC, p.393, paragraph one):

“Dictionary-style attacks are not generally successful at finding
[i.e. aren’t guaranteed to efficiently find] a particular user’s password,
but find many passwords in most systems”.

3. The SKID3 protocol is outlined on p.402 of the text (HAC). Note the resemblance to the protocol at the top of p.402. In a real implementation, assume that in each message, the senders also include a cleartext field asserting their identities (i.e. “B” and “A”). Suppose this official protocol description was modified to allow the rB within the scope of the keyed hash h_K in message (3) to be a random number different from rB in the first two messages, with this distinct number also sent cleartext in message (3). Explain how the modified protocol can be “broken” by an active attacker (i.e. when the protocol ends, either A or B has a false belief about who the other party in the authentication was); and explain what false belief results.
[Hint: review related attacks on pp.530-531.]

4. Explain, in detail, any relationship between the fraudulent amateur in the grandmaster postal-chess problem (Remark 10.42, HAC), and the “intruder-in-the-middle” attacker for Diffie-Hellman key agreement (p.530, HAC).

5. In STS (Protocol 12.57, HAC), assume the variation where each party sends the other its own public key certificate within the protocol. Suppose the protocol specification is officially modified so that the exponentials are not encrypted (i.e. they are only signed) in messages (2) and (3).

a) Since the exponentials are public information, an active attacker C (Charlie) could then replace the signed exponential in message (3) by his own signature. What else must Charlie change for party B’s “normal” execution of the protocol to “successfully” occur?

b) What beliefs would parties A and B have at the end of the protocol exchange?

c) Would Charlie be able to determine the resulting shared Diffie-Hellman key k?

d) Is this a “real” attack, i.e. an attack we should worry about? Explain. (Hint: assume B is a bank, and this protocol is used for identification of A, prior to making a bank deposit.)