1. Introduction
In this tutorial, we’ll learn about the chosen ciphertext attacks.
We’ll see what this attack is, how it works, and show a couple of ways we can protect against it.
2. What Are Encryption Systems?
Often, it’s important that two parties are able to communicate in a secure manner without the involvement of any unauthorized parties. This is where encryption comes in.
Encryption systems often work in terms of shared secrets – known as encryption keys. These are values that appropriately authorized parties have access to but that we keep secret from anyone else.
Any encryption system’s worth corresponds to how easily someone can attack and break it. If an attacker can easily break a given system, then it isn’t very useful, whereas a system that an attacker can’t break is immensely useful. A broken encryption system typically means an attacker can read encrypted messages or forge new ones.
3. What’s a Chosen Ciphertext Attack?
A chosen ciphertext attack sends a fake ciphertext and retrieves the correctly decrypted message. In particular, an attacker needs the decrypted version of their own ciphertext. If successful at that, the attacker can figure out the keys. This means they can decrypt other parties’ messages and forge new ones.
A system’s vulnerability to this attack depends on the encryption technique and how easy it is for an attacker to eavesdrop and find the plaintext that their ciphertext corresponds to.
4. Example
Let’s check an example. We’ll use the vigenère cipher since it’s especially vulnerable to this attack. This is a modification of the classic Caeser cipher, in which every letter in the plaintext shifts by a different number of letters. So, the key is another string that we share between both parties and whose letters represent the shifts.
4.1. Encrypting a Message
Let’s say our encryption key is BAELDUNG and that we want to encrypt the message “HELLO WORLD”:
So, we use the key in a circular way if a word has more letters than the key. Since B is the second letter of the alphabet, it means shifting by two letters, so H becomes J, etc. Decryption works by shifting in reverse.
By doing this, we get “JFQXS RCYNE” as the encrypted message. Clearly, this is meaningless to anyone without the correct key. However, with the correct key, we can trivially reverse the encryption to get back to the original text:
4.2. Attacking the Encryption
If an attacker intercepts a message between these two parties and replaces it with some malicious ciphertext, the recipient will understand it as meaningless upon decryption. It’s possible that the recipient will then contact the sender to ask what happened.
If the attacker can eavesdrop, they can determine the encryption key as long as the planted message is longer than it.
For example, let’s say the attacker substituted the real message with “FQXSRCYNE”. The recipient will receive this and decrypt it to “DPSGNHKGC”. Seeing that this was garbage, they then send a plaintext email to the sender, including this garbage, and ask what’s going on.
At this point, the attacker has both their own chosen ciphertext and the resulting plaintext for the same message and can trivially use those to work out what the key is:
Normally we’d use the ciphertext and key to get the plaintext. Here we’re using the ciphertext and plaintext to get the key by working out the difference between the letters. For example, the difference between F and D is 2 letters, which means the first letter of the key is a B. Applying the same logic, we get the rest of the key.
5. Protecting Against Chosen Ciphertext Attacks
The best way to defend against this attack is to ensure that there’s no way for a malicious party to decrypt their messages. However, this isn’t always possible to do, especially since some attacks use subtle tricks to get the necessary information. Even if the information extracted isn’t plaintext, it can still give clues. For example, that’s the case with timing attacks or errors returned.
We can also make it too expensive to determine the key(s). For example, in the case of our vigenère cipher, the longer our key, the more effort it will take to break it. Our attacker would somehow need to decrypt a ciphertext that’s at least as long as our key before fully breaking it. Additionally, if the key is just a random string of characters instead of a real word, then the attacker won’t know they’ve successfully broken it until it starts to repeat.
We can also regularly rotate our keys so that if they’re compromised, then it’s only for a short time. This will ensure that the window during which an attacker can eavesdrop on our conversations isn’t longer than our rotation window. However, this adds another layer of complexity since we’ll need to share the new keys in a secure manner.
There are additional measures we can take. For example, if we ensure that the messages are always digitally signed as well as encrypted and that the signing algorithm uses different keys, then we can at least separately prove who the sender was. This won’t make the attacks impossible, but it will stop the attackers from forging new messages.
6. Summary
In this article, we presented the chosen ciphertext attack. It works by the attacker providing their message and waiting for the recipient to decrypt it, thereby allowing enough information for the attacker to determine the encryption key in use. We’ve also discussed a few methods that can be used to protect against this attack.