Alice wants to talk to Bob, so she sends Bob a message saying, “Hi Bob, this is Alice” and attaches Alice’s certificate. Mallory intercepts the message and replays it to Bob. Bob thinks the message is from Alice and so wants to verify, and generates a challenge and sends it to Mallory saying, “Prove you are Alice”.


Mallory sends the challenge to Alice, who responds correctly. Mallory forwards this response to Bob. Bob is now convinced that Mallory is Alice.


The above is a man-in-the-middle attack. Now that Mallory has proven to Bob that he is Alice, Bob will talk to Mallory thinking Mallory is Alice. Note that we used a certificate (signed by a trusted authority) to do the authentication.


How can this be possible? We know that use of certificates makes m-i-t-m attacks not possible. Briefly show what is wrong with the above logic. (That is, show how Alice and Bob can talk privately in spite of Mallory)



Suppose Alice and Bob want to communicate (or rather set up a secret key) using the Merkle’s Puzzle algorithm. Alice has to send Bob a large number of “puzzles”. Each puzzle must be solvable in a reasonable time and the solution is a number.


  1. Show an example of such a puzzle. Be specific.
  2. Make an estimate as to how long the puzzle you have designed will take to solve.
  3. If a puzzle takes 1 minute to solve, how many puzzles must Alice send to Bob to ensure that Carol does not recover the secret key in 1 day? (1 day = 1440 minutes)
  4. Given the answer for C, what is the best method to redesign the system such that Carol takes 1 year to find the secret key.



Alice writes a digital check for $10 and signs it (using her private key). Then she takes this check to the bank, which checks the check, and Alice’s signature and then signs the check (along with Alice’s signature).


Now Alice e-mails the check to Bob and Carol and Dave.


  1. What information must be on the check before the Bank would sign the check? Suggest a format for the check (assume the check is written in ASCII text).
  2. Who gets to cash the check (Bob, Carol, Dave or nobody)?
  3. Does Alice get caught? If so how and by whom?