“We are under great pressure, Holmes.” Detective Lestrade looked nervous. “We have learned that copies of sensitive government documents are stored in computers of one foreign embassy here in London. Normally these documents exist in electronic form only on a selected few government computers that satisfy the most stringent security requirements. However, sometimes they must be sent through the network connecting all government computers. But all messages in this network are encrypted using a top secret encryption algorithm certified by our best crypto experts. Even the NSA and the KGB are unable to break it. And now these documents have appeared in hands of diplomats of a small, otherwise insignificant, country. And we have no idea how it could happen.”
“But you do have some suspicion who did it, do you?” asked Holmes.
“Yes, we did some routine investigation. There is a man who has legal access to one of the government computers and has frequent contacts with diplomats from the embassy. But the computer he has access to is not one of the trusted ones where these documents are normally stored. He is the suspect, but we have no idea how he could obtain copies of the documents. Even if he could obtain a copy of an encrypted document, he couldn’t decrypt it.”
“Hmm, please describe the communication protocol used on the network.” Holmes opened his eyes, thus proving that he had followed Lestrade’s talk with an attention that contrasted with his sleepy look.
“Well, the protocol is as follows. Each node N of the network has been assigned a unique secret key Kn. This key is used to secure communication between the node and a trusted server. That is, all the keys are stored also on the server. User A, wishing to send a secret message M to user B, initiates the following protocol:
1. A generates a random number R and sends to the server his name A, destination B, and E(Ka, R).
2. Server responds by sending E(Kb, R) to A.
3. A sends E(R, M) together with E(Kb, R) to B.
4. B knows Kb, thus decrypts E(Kb, R) to get R and will subsequently use R to decrypt E(R, M) to get M.
You see that a random key is generated every time a message has to be sent. I admit the man could intercept messages sent between the top secret trusted nodes, but I see no way he could decrypt them.”
“Well, I think you have your man, Lestrade. The protocol isn’t secure because the server doesn’t authenticate users who send him a request. Apparently designers of the protocol have believed that sending E(Kx, R) implicitly authenticates user X as the sender, as only X (and the server) knows Kx. But you know that E(Kx, R) can be intercepted and later replayed. Once you understand where the hole is, you will be able to obtain enough evidence by monitoring the man’s use of the computer he has access to. Most likely he works as follows: After intercepting E(Ka, R) and E(R, M) (see steps 1 and 3 of the protocol), the man, let’s denote him as Z, will continue by pretending to be A and . . . Finish the sentence for Holmes.