Why deterministic encryption algorithms do not satisfy multiple-message

Let’s say you have some private-key (symmetric-key) encryption scheme. It takes a key and a message, and outputs a ciphertext. Nobody without the key can decrypt the message using the decrypter. Is that secure? Not if it’s deterministic.

If I’m playing online poker, I often send commands like “Fold” or “Check” to the server. I’d like for that communication to be encrypted so nobody can cheat by listening in on my network connection. Well, if your encryption scheme is deterministic, then the command “Fold” will always encrypt to the same thing. If the attacker figures out (by watching the game) that “Fold” always becomes “JVsPM” and “Check” always becomes “ZjcgP”, then you’re hosed.

This is solved by adding some randomness into the encryption so that even if you encrypt using the same key and message many times, the encryption scheme will give a (pseudo-)random ciphertext. For the receiving party to be able to decrypt the message, the random value is also sent.

The process for doing this is to pick a new random string in the encryption process that’s as long as the message, and then XOR the new random string with the message (thus achieving OTP security). Then, concatenate the random string to the message, and encrypt the whole thing with your deterministic algorithm. The eavesdropper will no longer be able to tell the “Fold” ciphertexts from the “Check” ciphertexts because the ciphertexts look different every time. The decrypter, with the actual key, can still decrypt the message, pull out the random string, and XOR it with the actual message part to read the original message.

Notice that if the attacker could spoof messages from the actual player, the attacker could conduct a replay attack.