Protocols and Step-Ladders

Chris Grant

I'm not sure how many of you out there have heard of the resend attack against Public Key Encryption, but for those who haven't I'll try to explain. This transaction description is pretty much copied wholesale out of Bruce Schneier's Applied Cryptography. The point of this article is not the attack itself, but the implications, which I'll go into at the end.

If you are not familiar with the principles of Public Key Encryption then this article won't make much sense to you. There are a variety of big vendors out there selling Public Key Encryption products. Two of the biggest are Certicom, and RSA. You can learn about Public Key Cryptography from a variety of sources, and I would recommend Bruce Schneier's book as an excellent place to start.

The Ground Rules

The resend attack is an attack against signed, publicly encrypted messages. To set the stage for the attack, both parties have agreed on a certain protocol to be followed when exchanging messages. The ground rules are as follows:

  1. The digital signature algorithm is the same as the encryption algorithm. This is quite common, although by no means universal. The signing works like this: if the sender "decrypts" (or signs) a message using his or her private key, then "encrypting" the message with the sender's public key will reveal its contents. Since only the sender is in posession of the private key, the message can be deemed authentic.
  2. As a matter of course, any message that a recipient decodes, he or she signs, encrypts and replies to the sender. This step was introduced for several reasons. First, the sender can compare the message returned with the message sent and verify that the transmission was correct. In addition the sender has proof the recipient received the message. The recipient can not deny at a later date that they received the message.

With these conditions in place, the message exchange is performed.

The Transaction

Alice composes a message intended for Bob.

Alice: “I love you Bob”

Alice signs and encrypts the message to Bob.

Alice: EB(DA("I love you Bob"))

Alice sends the message to Bob. Meanwhile Mallory has been wondering what Alice and Bob have been talking about so she nabs a copy of the message as it goes through the network. Note that Alice's message is encrypted so Mallory can't read it at this point.

Bob, Mallory: EB(DA("I love you Bob"))

Bob decrypts the message using his private key, and encrypts the message using Alice's public key (thereby verifying that Alice sent the message). Bob can now read the message.

Bob: EA(DB(EB(DA("I love you Bob")))) = "I love you Bob"

Because the protocol dictates that he should, Bob now signs this same message with his key and encrypts it with Alice's public. He then sends this message back to Alice.

Bob: EA(DB("I love you Bob"))

Alice can now decrypt Bob's response, verify his signature, compare the two messages, and rest assured that Bob received Alice's message intact, and in private (or so she thinks).

Here's the tricky bit. Mallory still wants to know what Alice sent Bob so she waits for a while and then resends Alice's original message to Bob pretending that she was the author of the message.

Bob: EB(DA("I love you Bob"))

Bob, receiving an encrypted message from Mallory, does the obvious and attempts to decrypt the message and verify Mallory's signature. The result is of course gibberish because Mallory never signed the message. This was a copy of Alice's message.

Bob: EM(DB(EB(DA("I love you Bob")))) = EM(DA("I love you Bob"))

Bob sees that the signatures don't match, and does what the protocol tells him to. He signs the gibberish Mallory sent him, encrypts it back to Mallory and sends the reply. In effect he is say, “Hey, you sent me this junk. There must have been a transmission error.”

Mallory: EM(DB(EM(DA("I love you Bob"))))

You'll note that Bob unwittingly decrypted his private message from Alice and sent it back to Mallory signed and secured. Mallory simply needs to decrypt the message with her private key, verify Bob's signature, decrypt the message a second time, and then verify Alice's signature. Mallory now knows Alice loves Bob. To cover her tracks, Mallory can now send Bob a different message saying "Let's do lunch." Bob writes the first message off as user error or bit-rot and is never the wiser. Meanwhile, back at the ranch, Mallory is stirring up a scandalous office rumour...

The Lesson

You'll note that nowhere in this transaction does Mallory apply any fantastic cryptanalysis, and at no point did she have to borrow the NSA's 10 billion dollar massively parallel, super computing, deluxe model PGP DecryptomaticTM to decrypt the message. In fact, the encryption algorithm and implementation can be perfectly secure and this attack will still work if the two criteria laid out in the ground rules are adhered to. This is a classic case of the algorithm being solid, the implementation perfectly secure, and the application absolutely insecure.

Huh? But if all the components were secure, where did we go wrong?

Here's the lesson I would take out of this example: any security application needs to be viewed in its entirety. This applies to everything ranging from encryption to physical security. I was recently on a job where gaining access to the server room required being buzzed through a locked door, passing a receptionist, passing through an open office space, passing though a door secured with a magnetic card reader, walking through the tech team's office space, and finally passing through another restricted door accessed via a magnetic card reader. This all seems quite secure until you realize that you are standing in a server room that is right beside a public hallway. You guessed it. The server room's ceiling consisted of removable white panels. If I wanted to break into that particular server room I would not try to technologically defeat, or social engineer my way past the various security barriers. I would simply buy a step ladder, set it up in the hallway and pop over the wall.

This is what I like to think Mallory was doing in the replay attack. The protocol was designed to stop people from getting through the front door. Unfortunately Mallory decided to use a step-ladder.

I suppose the corollary to this could be that ceiling tiles and public key cryptosystems have more in common than you might guess.

Hmmm, I'll have to work on that theory. I think I might have something there....

Chris Grant

pintday.org » Fresh every Tuesday.