Chosen-ciphertext Attack what’s it like?

Question

I’m reading about CCA but I can’t understand in any site I’m looking for, how this attack works and how to possibly avoid it?

Answer 1

The Chosen-ciphertext Attack ("chosen cipher attack") can refer both to an attack on an encryption system undocumented (i.e. that only cares about the confidentiality but forgets the integrity and authenticity) as to a method of Criptanalysis.

Attack

Encryption alone only ensures the confidentiality of communication (i.e. that someone who is watching - Eavesdropping - communication, but not altering - tampering - find out what is being reported), not its integrity. This means that in many cases, even though the attacker does not know the entire content of the communication, he can modify this communication in transit (for example) to get a number of advantages. In some cases, even getting the original message.

I’ll give an arbitrary example, but similar to some scenarios found in practice: let’s say you have a messaging server, where Alice, Bob and Mallory have accounts. This server uses AES-CBC encryption to communicate with clients, so if Alice wants to send a message to Bob she has to do the following:

• She chooses the recipient and puts it in the header: to: roberto. from: alice.;
• She puts the content in the body of the message: mensagem: blá, blá, blá;
• It chooses a random IR and makes the encryption using a shared key between it and the server (it can be a single session key, negotiated during login).

The result would be (for example):

{"iv":"2e6b036434e9dc857ee34476a618f0cb", "ct":"u0LGWohZ9ce05XkV2A3W2o8xbwp49nHtRXMivpfmULwfDjDMvkjr237fDrXpg/JgTYHkcWu5y3ACxmDGuamyVw=="}

When this string is sent to the server, it decrypts using the common key, reads the recipient’s name in the header, and then places the message in the recipient’s inbox. What could be wrong if the integrity of the message is not checked?

• Mallory intercepts the encrypted message; she does not know its contents, does not know the encryption key, but for some reason suspects that the recipient is Bob;
• She takes the IV from the message and does two operations on the same:
  1. XOR of this IV with which she suspects to be the recipient Bob: IV = IV ^ \0\0\0\0roberto\0\0\0\0\0;
  2. XOR of this result with its own username: IV = IV ^ \0\0\0\0mallory\0\0\0\0\0;

The message, with IV switched, is sent to the server instead of the original:

{"iv":"2e6b03642be7d28c63e55276a618f0cb", "ct":"u0LGWohZ9ce05XkV2A3W2o8xbwp49nHtRXMivpfmULwfDjDMvkjr237fDrXpg/JgTYHkcWu5y3ACxmDGuamyVw=="}

When it is decrypted, the result is:

to: Mallory. from: Lice. message: blah, blah, blah

So the server puts in Mallory’s inbox the message that should go to Bob...

var chave = CryptoJS.lib.WordArray.random(128/8);

$("button:eq(0)").click(function() {
  var mensagem = "to: roberto. from: alice. mensagem: " + $("input").val();
  $("code:eq(0)").text(mensagem);
  
  var iv = CryptoJS.lib.WordArray.random(128/8);
  $("code:eq(1)").text(iv);
  $("code:eq(3)").text(iv);
  
  var encrypted = CryptoJS.AES.encrypt(mensagem, chave, { iv:iv });
  $("code:eq(2)").text(encrypted);
  
  var bob = CryptoJS.enc.Utf8.parse("\0\0\0\0roberto\0\0\0\0\0");
  $("code:eq(4)").text(bob);
  
  var mallory = CryptoJS.enc.Utf8.parse("\0\0\0\0mallory\0\0\0\0\0");
  $("code:eq(5)").text(mallory);

  encrypted.iv.words[0] ^= bob.words[0] ^ mallory.words[0];
  encrypted.iv.words[1] ^= bob.words[1] ^ mallory.words[1];
  encrypted.iv.words[2] ^= bob.words[2] ^ mallory.words[2];
  encrypted.iv.words[3] ^= bob.words[3] ^ mallory.words[3];
  $("code:eq(6)").text(encrypted.iv);

  var decrypted = CryptoJS.AES.decrypt(encrypted, chave, { iv:encrypted.iv });
  $("code:eq(7)").text(CryptoJS.enc.Utf8.stringify(decrypted));
});

.mallory {
  background-color: #FFDDDD;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<script src="https://crypto-js.googlecode.com/svn/tags/3.1.2/build/rollups/aes.js"></script>
<p>Mensagem: <input value="Blá, blá, blá"> <button>Cifrar</button></p>
<table>
<tr><td>PT: </td><td><code></code></td></tr>
<tr><td>IV: </td><td><code></code></td></tr>
<tr><td>CT: </td><td><code></code></td></tr>
<tr class="mallory"><td>IV: </td><td><code></code></td></tr>
<tr class="mallory"><td>⊕: </td><td><code></code></td></tr>
<tr class="mallory"><td>⊕: </td><td><code></code></td></tr>
<tr class="mallory"><td>=: </td><td><code></code></td></tr>
<tr><td>PT: </td><td><code></code></td></tr>
</table>

To prevent this attack, it is necessary to use a authenticated mode of operation or - if it is impossible to do so - apply a Message Authenticator (MAC) to cipher, so the attacker can’t modify the encrypted data without it being noticed.

But this is not enough: if your protocol is not very well thought out, even if the attacker can’t produce a "valid" cipher, it can still negatively interfere with it. The video suggested by @Intruso in his reply, for example, he talks a little about the subject (although this other video which is part of same course better example). One of the examples is the same quoted earlier in this answer, and the other is a simplified form of attack POODLE - where the mere information on why a particular cipher has been rejected (incorrect MAC or padding incorrect) is sufficient to allow an attacker to decipher an entire message (by submitting arbitrary ciphers to the server and verifying which error message has been returned, or how long it took for the server to file an error).

For cryptography to work it is therefore necessary that none information is given to the opponent both on the key and the message but also on the status of the cipher. That is, when the decryption fails, do everything in your power not to let your opponent know why she failed (and that’s a lot harder than it looks...).

Cryptanalysis

In the context of Cripatalysis, the CCA in general aims to discover a secret key used by an adversary. In it the attacker has - for a limited or unlimited time - the ability to send ciphers (ciphertext) of their choice for the user to decipher, and receive back the message (plaintext) or, in a more limited scenario, only know if the sent cipher is valid or not (a "oracle validation").

In one of its variants, the attacker can continue to do this after receiving the reply, choosing new ciphers to be sent based on current results (Adaptive CCA), in another he has to choose all ciphers beforehand, and after receiving the results he loses the ability to execute the attack (ie, she needs to try to decipher the key only with the information he has until then).

The exact mechanism by which Criptanalysis is made varies from algorithm to algorithm. Some are designed to be resistant to this type of attack, others are admittedly vulnerable and do not participate in processes in which this type of attack is expected (i.e. designs the cryptographic protocol so that the attacker can never obtain useful information from arbitrary ciphers).

The key point is that the vast majority (all?) of cryptographic systems can be "broken" (have their key recovered with less effort than a brute force attack) if the attacker has a certain number of pairs plaintext/ciphertext. Let me give you an example using Cifra de Vigenère, a historical cipher (i.e. no longer used in practice) that can be broken with a single known pair.

Suppose General A is sending messages to General B using a Vigenère cipher with an unknown key. The enemy somehow intercepts the message and replaces it with some completely random letters of his own choice, say NLLCJOVFXXHMLY. General B deciphers this and gets AKRUWNBXKWNEYX, which makes no sense. Caught off guard, and not thinking this nonsense is worth keeping secret, he picks up an unsafe phone and calls General A: "What do you mean by AKRUWNBXKWNEYX? Did you happen to change the key without telling me?" But the enemy has a bug on that line, and now he knows that NLLCJOVFXXHMLY deciphers to AKRUWNBXKWNEYX. He can then subtract the two texts (each meaningless by itself) to obtain MATHMATHMA, and now he knows the key [and can intercept future communications on the previously secure channel].

_{Source: this answer in Crypto.SE}

Resistance to Criptanalysis via CCA is important because in practice it is very difficult to prevent an attacker from discovering a few message/cipher pairs. An example would be if I sent you a file by email, you saved it encrypted somewhere and I then figured out a way to look at the resulting cipher. How I sent you plaintext, I’ll know that PT matches that CT. The above example is "forced", but demonstrates the need for this feature for an encryption algorithm to be considered secure.

Answer 2

CCA is an attack pattern, the way you can execute it usually depends on the scenario you are trying to protect (or attack).

A video with basic concepts can be found here: https://www.youtube.com/watch?v=AHQySAd8yvQ