Ciphertext Indistinguishability

Ciphertext Indistinguishability ( English for indistinguishability of ciphertexts ) is a term that is used for security proofs of encryption processes. In a method with this property, an attacker cannot distinguish between the ciphertexts of two plaintexts , even if he knows the plaintexts.

motivation

To talk about the security of encryption methods, one must first be clear what exactly is meant by security. The first thought that the attacker should not be able to derive the plaintext from the ciphertext is not enough. This means that it cannot be ruled out that an attacker might receive information about parts of the plain text, even if he cannot derive the entire plain text. The minimum requirement must therefore be that the attacker cannot learn any information from the plaintext. But even this formulation is not sufficient in some circumstances. If a public-key encryption method that is deterministic (that is, with the same input always delivers the same output as the example in the textbook RSA encryption is the case) and can restrict the attacker to the plaintext space he (White z. B., that the encrypted message is either “yes” or “no”), he can encrypt all possible plaintexts with the public key. Then he can determine the associated plaintext by simply comparing the ciphertext with the ciphertext that he himself has generated. It is therefore important to define a security concept for which this is not possible.

IND-CPA

motivation

In general, it does not make sense to speak of “security” in relation to cryptological processes without qualifying them more precisely. A security term says that an attacker cannot achieve a certain goal. The definition therefore consists of two parts: an attacker with precisely described skills and the security goal. Ciphertext indistinguishability (IND) is a security goal, namely that it should not be possible for an attacker to distinguish between the encryption of any two plaintexts of the same length (the encryptions of two plaintexts of different lengths can differ in the length of the cipher, therefore the secrecy of the Length of the plain text is generally not required). To ensure that this also applies if the plaintexts are not chosen, the attacker can choose two plaintexts, one of which is encrypted. Various attacker strengths can be defined for this purpose. As a rule, the attacker is limited in his runtime in order to prevent him from searching the entire key space or solving tasks that are practically unsolvable in the real world, where computing power is not unlimited. In the case of an asymmetric encryption method, it must also always be assumed that the attacker knows the public key. This means that he can encrypt any plaintext of his choice and compare it with the ciphertext in order to learn something about the unknown plaintext. This attack is called the chosen-plaintext attack (CPA). An encryption method thus has the security level IND-CPA (ciphertext indistinguishability under chosen plaintext attacks) if no CPA attacker can achieve the goal IND, i.e. to differentiate between the ciphertexts of two self-chosen plaintexts.

definition

To express this formally, the IND-CPA experiment is defined, which runs in five steps between two probabilistic algorithms with polynomial (in one security parameter ) runtime restriction, attacker A and environment U. ${\ displaystyle k}$

First, the environment generates a key pair from a secret and a public key for the given security parameter. The attacker receives the public key. ${\ displaystyle k}$
Now the attacker can carry out any calculations. At the end of this step it must output two plain texts of the same length and . ${\ displaystyle M_ {0}}$ ${\ displaystyle M_ {1}}$
The environment draws a random bit and encrypts . The attacker now receives this ciphertext. ${\ displaystyle b}$ ${\ displaystyle M_ {b}}$
The attacker, in turn, is allowed to perform any calculations or encryption. At the end it outputs a bit . ${\ displaystyle b '}$
If so, the environment outputs “1”, otherwise “0”. ${\ displaystyle b = b '}$

If the environment outputs a "1", the attacker guessed correctly. An attacker who, in the fourth step, pulls a random bit and outputs it regardless of everything that happened before, is correct with probability 1/2. An encryption method is safely called IND-CPA if no attacker has a probability of success that is significantly higher than 1/2, i.e. if it is negligibly small (if it remains smaller than for every polynomial above a certain size ). A negligible difference must be allowed because it is very easy for an attacker to increase his probability of success above 1/2: He simply guesses a secret key and tries to decrypt the ciphertext with it. The probability of success is very small, but greater than 0. When defining it, it is important that no assumptions are made about the attacker apart from his or her runtime limit. ${\ displaystyle Pr [U = 1] -1/2}$ ${\ displaystyle p}$ ${\ displaystyle k}$ ${\ displaystyle 1 / p (k)}$

The term IND-CPA appeared as early as 1984 at Goldwasser and Micali under the name "polynomial security". The definition given above is formally not entirely correct, because an algorithm in computer science stops after the output. An attacker therefore consists of two algorithms, the first of which outputs the two plaintexts and its status. The second receives the two plaintexts, the status and the ciphertext as input and outputs one bit. By transferring the status, the second algorithm can also be understood as a continuation of the first.

IND-CCA

The CPA attacker introduced above is not the strongest possible. The stronger security term IND-CCA is obtained if the attacker is granted a decryption oracle in addition to the public key. An oracle is an algorithm that only provides output for inputs, but cannot be analyzed. As a result, the secret key contained in the decryption oracle is not accessible to the attacker. The attacker can then decrypt any ciphertext in steps 2 and 4, with the exception of the ciphertext he received in step 3. This attacker model is called an adaptive chosen-ciphertext attack (CCA). Its practical relevance was demonstrated in 1998 when Daniel Bleichenbacher succeeded in conducting a realistic attack in this model against the IND-CPA-safe RSA variant defined in PKCS # 1 .

In the literature, a distinction is sometimes made between CCA1 and CCA2 attackers. The CCA2 attacker is the one described above as CCA, while the CCA1 attacker only has the decryption oracle available in step 2. Because the requests to the decryption oracle cannot depend on the ciphertext in step 3, this attack is also called a non-adaptive chosen-ciphertext attack .

literature

Mihir Bellare, Anand Desai, David Pointcheval and Phillip Rogaway: Relations Among Notions of Security for Public-Key Encryption Schemes . In: Advances in Cryptology - Proceedings of CRYPTO '98 . 1998, p. 26-45 ( ens.fr ).

Individual evidence

↑ Shafi Goldwasser and Silvio Micali: Probabilistic encryption . In: Journal of Computer and System Sciences . tape 28 , no. 2 , 1984, p. 270–299 ( with.edu [PDF; 7,8 MB ]).
^ Daniel Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS # 1 . In: CRYPTO '98 . 1998, p. 1-12 ( bell-labs.com ).

[1] Shafi Goldwasser and Silvio Micali: Probabilistic encryption . In: Journal of Computer and System Sciences . tape 28 , no. 2 , 1984, p. 270–299 ( with.edu [PDF; 7,8 MB ]).

[2] Daniel Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS # 1 . In: CRYPTO '98 . 1998, p. 1-12 ( bell-labs.com ).