Selected plaintext attack

Chosen-plaintext attack ( CPA ) is one of the main methods of cryptanalytic opening . A cryptanalyst has a certain number of plaintexts and corresponding ciphertexts , in addition, he has the ability to encrypt several previously selected plaintexts ^[1] .

Description

A cryptanalyst , according to the Kirkhoffs principle , has all the information about the encryption system used, except for a certain set of parameters called a key . The task of the cryptanalyst is to find the key or create an algorithm that allows you to decrypt any message encrypted using this key.

Given: $P_{1},C_{1}=E_{k}(P_{1}),\,P_{2},C_{2}=E_{k}(P_{2}),\,...\,P_{i},C_{i}=E_{k}(P_{i}),$ ${\ displaystyle P_ {1}, C_ {1} = E_ {k} (P_ {1}), \, P_ {2}, C_ {2} = E_ {k} (P_ {2}), \ ,. .. \, P_ {i}, C_ {i} = E_ {k} (P_ {i}),}$ $P_{1},C_{1}=E_{k}(P_{1}),\,P_{2},C_{2}=E_{k}(P_{2}),\,...\,P_{i},C_{i}=E_{k}(P_{i}),$

Where $P-$ ${\ displaystyle P-}$ $P-$ a clear text selected by a cryptanalyst, $C-$ ${\ displaystyle C-}$ $C-$ ciphertext, $E-$ ${\ displaystyle E-}$ $E-$ encryption function $k-$ ${\ displaystyle k-}$ $k-$ key.

Receive: Either $k$ ${\ displaystyle k}$ $k$ or algorithm how to get $P_{i+1}$ ${\ displaystyle P_ {i + 1}}$ $P_{i+1}$ of $C_{i+1}=E_{k}(P_{i+1}).$ ${\ displaystyle C_ {i + 1} = E_ {k} (P_ {i + 1}).}$ $C_{i+1}=E_{k}(P_{i+1}).$ ^[one]

The ability to conduct an attack based on selected plaintext is quite common. For example, an attacker could bribe someone who encrypts the selected message. The following situation is also possible: the attacker sends a message to the ambassador of a certain country, and he sends it to his homeland in encrypted form ^[2] .

Selected plaintext attack refers to active attacks on cryptosystems. Such attacks violate the integrity and confidentiality of the transmitted information ^[3] .

Fig. 1 Selected plaintext attack

Figure 1 shows the attack scheme based on selected plaintext. Attacker (A) receives ciphertext $C=E(P,K)$ ${\ displaystyle C = E (P, K)}$ $C=E(P,K)$ from user (C). The attacker's task is to “guess” the plaintext $P^{'}=P$ ${\ displaystyle P ^ {'} = P}$ $P^{'}=P$ . Since the attacker has access to the encryption block $E$ ${\ displaystyle E}$ $E$ he has the ability to encrypt his messages $P_{i}$ ${\ displaystyle P_ {i}}$ $P_{i}$ and analyze the resulting ciphertexts. $C_{i}=E(P_{i},K)$ ${\ displaystyle C_ {i} = E (P_ {i}, K)}$ $C_{i}=E(P_{i},K)$ . As a result, the attacker picks up a message $P^{'}$ ${\ displaystyle P ^ {'}}$ $P^{'}$ and forwards it to the user.

Attack Types

There are two types of attacks based on selected plaintext:

autonomous ( born batch chosen-plaintext attack ) - a cryptanalyst prepares a set of plaintexts in advance, before receiving encrypted texts.
operational or attack based on adaptively chosen plaintext attack (CPA2 ) - the cryptanalyst selects the following plaintexts based on the ciphertexts already received. Since the previous results are taken into account when choosing subsequent blocks sent for encryption, feedback arises that gives an attack based on adaptively selected plaintext an advantage over other types of attacks. The implementation of this type of attack is possible, for example, if the cryptanalyst has access to the encryption device for a sufficiently long time to analyze the results ^[4] .

Comparison with other types of attacks

According to Bruce Schneier , there are 4 main methods of cryptanalytic opening ^[1] :

Ciphertext attack
Well-known plaintext attack
Selected plaintext attack
Adaptive Selected plaintext attack

In the case of an attack based on a ciphertext, a cryptanalyst has access only to encrypted text. This is the most difficult type of attack, due to the small amount of information available.

In an attack based on known plaintext, a cryptanalyst knows open and encrypted texts. This type of attack is more effective than an attack based on ciphertext due to more known information about the cryptosystem.

Selected plaintext attack is a more powerful type of attack than a known plaintext attack. The ability to preselect plaintext provides more options for extracting a system key. It is also true that if the cryptosystem is vulnerable to an attack based on known plaintext, then it is vulnerable to an attack based on selected plaintext ^[5] .

In History

An attack based on selected plaintext was used during the Second World War .

In 1942, U.S. Navy cryptanalysts intercepted an encrypted order from the Japanese command. Having decrypted part of the message, American cryptanalysts learned about the impending attack on the mysterious "AF", but they could not find out the place of the attack. Assuming that most likely the goal of the Japanese is Midway Island , the Americans went to the trick. They made a report that the island lacked fresh water and sent it through an unprotected canal. A few days later, American intelligence agents intercepted a Japanese ciphertext which reported that there was little fresh water on the AF. Thus, the American command knew in advance about the impending offensive on the Midway Atoll ^[6] .

British cryptanalysts from Bletchley Park successfully used an attack based on selected plaintext to decrypt German correspondence. The British provoked the enemy to use certain words and names in the message texts. For example, if the Germans recently freed a section of coastal waters from mines, the British intelligence services could announce that the area was again mined. This provoked a stream of encrypted messages from the German command, including the word "mines" and the name of the territory. Thus, the British could quite effectively select plaintext and analyze ciphertexts to crack German ciphers. This attack can be qualified as an attack based on adaptively selected plaintext , as British cryptanalysts could select the next plaintext to be encrypted based on the results already obtained ^[7] .

Attack Examples

Private Key Cryptosystems

Affinity Cipher Attack

Consider a simple example of an attack on an affine cipher using Latin characters from A to Z.

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	one	2	3	four	five	6	7	eight	9	ten	eleven	12	13	14	15	sixteen	17	18	nineteen	20	21	22	23	24	25

Encryption Function: $y=mx+n\ mod\ 26.$ ${\ displaystyle y = mx + n \ mod \ 26.}$

A cryptanalyst performs an attack based on selected plaintext. The selected plaintext is “HAHAHA”, the corresponding ciphertext is “NONONO”. The goal of the cryptanalyst is to find the explicit form of the encryption function, i.e. to calculate the coefficients $m$ ${\ displaystyle m}$ and $n$ ${\ displaystyle n}$ .

Using the resulting plaintext - ciphertext pair, we compose a system of equations:

${\begin{cases}m\cdot 7+n\equiv 13\ mod\ 26\\m\cdot 0+n\equiv 14\ mod\ 26\end{cases}}$ ${\ displaystyle {\ begin {cases} m \ cdot 7 + n \ equiv 13 \ mod \ 26 \\ m \ cdot 0 + n \ equiv 14 \ mod \ 26 \ end {cases}}}$

Solving the system, we find: $n=14,\ m=11.$ {\ displaystyle n = 14, \ m = 11.}

Encryption Function: $y=11x+14\ mod\ 26.$ ${\ displaystyle y = 11x + 14 \ mod \ 26.}$ ^[eight]

Differential Cryptanalysis

An attack based on selected plaintext is used in the differential cryptanalysis method proposed by Israeli cryptanalysts Eli Biham and Adi Shamir in 1990 to crack the DES cryptosystem. The method is based on the study of ciphertexts, open texts of which have certain differences. Analyzing the evolution of the difference in ciphertexts during the passage of DES rounds, a list of possible keys is determined, and a probability is assigned to each possible key. In the process of analyzing the following pairs of ciphertexts, one of the keys will become the most probable ^[9] . Subsequently, the method of differential cryptanalysis was extended to cryptosystems such as FEAL , Khafre , Lucifer , LOKI, and others ^[10] ^[11] .

Let be $P$ ${\ displaystyle P}$ , $P^{'}-$ ${\ displaystyle P ^ {'} -}$ selected open texts $C$ ${\ displaystyle C}$ , $C^{'}-$ ${\ displaystyle C ^ {'} -}$ corresponding ciphertexts. The difference between plaintext and ciphertext is determined by the XOR operation : $\Delta P=P\oplus P^{'},\Delta C=C\oplus C^{'}.$ ${\ displaystyle \ Delta P = P \ oplus P ^ {'}, \ Delta C = C \ oplus C ^ {'}.}$ To describe possible changes in value $\Delta C$ ${\ displaystyle \ Delta C}$ when going through the DES steps, the concept of a round characteristic is introduced , made up of differences in plain text $\Delta P$ ${\ displaystyle \ Delta P}$ ciphertext $\Delta C$ ${\ displaystyle \ Delta C}$ and a set of round differences (differences in ciphertexts after each intermediate round) $C_{\lambda }=(\lambda _{1},\lambda _{2}...\lambda _{n})$ ${\ displaystyle C _ {\ lambda} = (\ lambda _ {1}, \ lambda _ {2} ... \ lambda _ {n})}$ . Each characteristic is assigned the probability that a random pair of plaintexts with a difference $\Delta P$ ${\ displaystyle \ Delta P}$ will cause round differences and differences in ciphertexts corresponding to the characteristic. after passing the appropriate round of encryption. A pair of plaintexts, the passage of which through the DES round is exactly described by the characteristic, is called a “correct pair” , otherwise - a “wrong pair”. ^[9]

To determine the key, an attack is performed based on selected plaintext. At the data collection stage , the cryptanalyst sends a large number of plaintext pairs for encryption with certain differences that correspond to the characteristic with probability $p$ ${\ displaystyle p}$ (i.e., among all pairs of plaintexts there is $p$ ${\ displaystyle p}$ right pairs). Then, at the stage of data analysis, a set of possible round keys is determined, for each possible key the differences of the corresponding ciphertexts are calculated. During the last round of encryption, a complete search of the possible keys takes place. For incorrect round keys, the probability of a difference in ciphertexts corresponding to the characteristic will be very small, for a correct round key, the probability will be of the order of $p$ ${\ displaystyle p}$ or higher. Thus, the correct key of the system ^[9] ^[12] can be determined.

It is worth noting that the differential cryptanalysis method is quite impractical due to the high requirements for time and data volume. For example, breaking a 16 round DES requires $2^{47}$ ${\ displaystyle 2 ^ {47}}$ selected plaintexts and $2^{55}$ ${\ displaystyle 2 ^ {55}}$ operations ^[9] .

Linear Cryptanalysis

In 1993, Mitsuru Matsui, a Japanese cryptanalyst, proposed a linear cryptanalysis method for opening block ciphers such as DES. The method is based on the construction of linear relationships between plaintext, ciphertext and key: $P_{i_{1}}\oplus P_{i_{2}}\oplus \dots \oplus P_{i_{a}}\oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \dots \oplus K_{k_{c}}$ ${\ displaystyle P_ {i_ {1}} \ oplus P_ {i_ {2}} \ oplus \ dots \ oplus P_ {i_ {a}} \ oplus C_ {j_ {1}} \ oplus C_ {j_ {2}} \ oplus \ dots \ oplus C_ {j_ {b}} = K_ {k_ {1}} \ oplus K_ {k_ {2}} \ oplus \ dots \ oplus K_ {k_ {c}}}$ ,

Where $P_{n},C_{n},K_{n}$ ${\ displaystyle P_ {n}, C_ {n}, K_ {n}}$ - nth bits of text, ciphertext and key, respectively. Such relations are called linear approximations.

The essence of the method is to calculate the probability of occurrence of linear approximations. If the probability $p$ ${\ displaystyle p}$ different from $1/2$ ${\ displaystyle 1/2}$ , it is possible to extract key information using plaintext-ciphertext pairs. Initially, for each individual round, a linear approximation is found with the highest probability of bias. Then, round approximations are combined into a general linear approximation of the cryptosystem, and using the plaintext-ciphertext pairs, an assumption is made about the values of the key bit ^[13] .

Initially, the linear cryptanalysis method used attack based on well-known plaintext. So, for example, to crack a 16-round DES, it took $2^{43}$ ${\ displaystyle 2 ^ {43}}$ well-known plaintexts and 50 days ^[13] . In 2000, Lars Knudsen proposed a linear cryptanalysis option based on selected plaintexts - it took 12 bits of the key to open $2^{42}$ ${\ displaystyle 2 ^ {42}}$ selected plaintexts ^[14] .

Public Key Cryptosystems

An attack based on selected plaintext can be used to open asymmetric cryptosystems. In such systems, the public key is accessible to any user, which provides the cryptanalyst with complete control over the encryption algorithm. Thus, against cryptosystems with a public key, you can always organize an attack based on selected plaintext ^[15] . For example, if an attacker intercepted ciphertext $C=E_{k}(P)$ ${\ displaystyle C = E_ {k} (P)}$ , to decrypt it is enough to pick up another message $P^{'}$ ${\ displaystyle P ^ {'}}$ and encrypt it using the public key $C^{'}=E_{k}(P^{'})$ ${\ displaystyle C ^ {'} = E_ {k} (P ^ {'})}$ . If a $P\neq P^{'}$ ${\ displaystyle P \ neq P ^ {'}}$ , one more attempt is made ^[16] .

Probabilistic Encryption

Typically, asymmetric cryptosystems are designed to withstand tampering using selected plaintexts ^[15] . For example, the RSA cryptosystem protects against attacks based on matched plaintext based on the difficulty of calculating the root $e$ ${\ displaystyle e}$ degree of ciphertext over a composite integer module $n$ ${\ displaystyle n}$ ^[17] . Another way to eliminate information leakage in public-key cryptosystems is probabilistic encryption , proposed by Shafi Goldwasser and Silvio Mikali . The basic idea of probabilistic encryption is matching the same plaintext $P$ ${\ displaystyle P}$ several randomly selected ciphertexts $C_{1},C_{2},C_{3},\ldots$ ${\ displaystyle C_ {1}, C_ {2}, C_ {3}, \ ldots}$ . Thus, if a cryptanalyst tries to guess the plaintext P for decryption $C=E_{k}(P)$ ${\ displaystyle C = E_ {k} (P)}$ , he will get a completely different ciphertext $C^{'}\neq C$ ${\ displaystyle C ^ {'} \ neq C}$ and cannot verify the correctness of his assumption ^[18] .

Attack on the RSA

Despite the security of the RSA cryptosystem against attacks based on selected text, there are a number of vulnerabilities that allow a cryptanalyst to decrypt ciphertext. Consider the following algorithm for attacking an RSA-based electronic signature system, proposed by George David in 1982. The attack is made under the assumption that the cryptanalyst intercepted the ciphertext $C=M^{e}\ mod\ n$ ${\ displaystyle C = M ^ {e} \ mod \ n}$ . The goal of a cryptanalyst is to get an open message $M$ ${\ displaystyle M}$ . To conduct an attack, a cryptanalyst needs to be able to sign any messages he selects ^[19] ^[20] .

At the first stage of the attack, the ciphertext is decomposed $C$ ${\ displaystyle C}$ by factors (optionally simple): $C=C_{1}C_{2}...C_{t}$ ${\ displaystyle C = C_ {1} C_ {2} ... C_ {t}}$ . It follows that the message $M$ ${\ displaystyle M}$ also representable as a work $t$ ${\ displaystyle t}$ multipliers $M=M_{1}M_{2}...M_{t}$ ${\ displaystyle M = M_ {1} M_ {2} ... M_ {t}}$ , and the equalities are true: $C=C_{1}C_{2}...C_{t}=(M_{1}M_{2}...M_{t})^{e}\ mod\ n=M_{1}^{e}M_{2}^{e}...M_{t}^{e}\ mod\ n$ ${\ displaystyle C = C_ {1} C_ {2} ... C_ {t} = (M_ {1} M_ {2} ... M_ {t}) ^ {e} \ mod \ n = M_ {1 } ^ {e} M_ {2} ^ {e} ... M_ {t} ^ {e} \ mod \ n}$ , and $M_{i}=C_{i}^{d}\ mod\ n$ ${\ displaystyle M_ {i} = C_ {i} ^ {d} \ mod \ n}$ .
Cryptanalyst picks up an open message $X$ ${\ displaystyle X}$ and sends it for signature. He also asks to sign messages $XC_{1}$ ${\ displaystyle XC_ {1}}$ , $XC_{2}$ ${\ displaystyle XC_ {2}}$ $...XC_{t}$ ${\ displaystyle ... XC_ {t}}$ . The signature is as follows: $S=X^{d}\ mod\ n$ {\ displaystyle S = X ^ {d} \ mod \ n} , wherein $S_{i}=(XC)_{i}^{d}\ mod\ n,i=1...t$ ${\ displaystyle S_ {i} = (XC) _ {i} ^ {d} \ mod \ n, i = 1 ... t}$ .
The inverse element is calculated $S^{-1}=X^{-d}\ mod\ n$ ${\ displaystyle S ^ {- 1} = X ^ {- d} \ mod \ n}$ .
Multiplying the resulting expression by $S_{i}$ ${\ displaystyle S_ {i}}$ maybe get $M_{i}$ ${\ displaystyle M_ {i}}$ : $S_{i}S^{-1}=(X)^{-d}(XC_{i})^{d}\ mod\ n=C_{i}^{d}\ mod\ n=M_{i}$ ${\ displaystyle S_ {i} S ^ {- 1} = (X) ^ {- d} (XC_ {i}) ^ {d} \ mod \ n = C_ {i} ^ {d} \ mod \ n = M_ {i}}$ .
As a result, the original message is restored: $M=M_{1}M_{2}...M_{t}\ mod\ n$ ${\ displaystyle M = M_ {1} M_ {2} ... M_ {t} \ mod \ n}$

This method does not allow to open the cryptosystem in the traditional sense, that is, to obtain a private key, but the cryptanalyst is able to decrypt a specific message. Therefore, this attack is weaker than the attack based on selected plaintext for symmetric cryptosystems, which allows to obtain all information about the cryptosystem if successful ^[20] .

Notes

↑ ¹ ² ³ Schneier, 2003 , p. 20.
↑ Schneier, 2003 , p. 21.
↑ Gabidulin , p. 25-28.
↑ Schneier, Ferguson, 2002 , p. 48.
↑ Schneier, Ferguson, 2002 , p. 47-49.
↑ Kahn, 2000 , p. 106-109.
↑ Hinsley, 2001 .
↑ Stinson, 2006 , p. 27-29.
↑ ¹ ² ³ ⁴ Biham, Shamir (DES), 1990 .
↑ Biham, Shamir (FEAL), 1991 .
↑ Biham, Shamir (LOKI), 1991 .
↑ Schneier, 2003 , p. 212-216.
↑ ¹ ² Matsui, 1993 .
↑ Knudsen, 2000 .
↑ ¹ ² Schneier, 2003 , p. 342.
↑ Schneier, 2003 , p. 404.
↑ Mao, 2005 , p. 308.
↑ Schneier, 2003 , p. 404-406.
↑ Davida, 1982 .
↑ ¹ ² Denning, 1984 .

Literature

B. Schneier. Applied cryptography. - Triumph, 2003 .-- 816 p. - ISBN 5-89392-055-4 .
B. Schneier, N. Ferguson. Practical cryptography. - Williams, 2002 .-- 424 p. - ISBN 5-8459-0733-0 .
E. Gabidulin, A. Kshevetsky, A. Kolybelnikov, S. Vladimirov. Protection of information. Tutorial.
D. Kahn. Code crackers. - Centerpolygraph, 2000 .-- 124 p. - ISBN 5-227-00678-4 .
FH Hinsley, A. Stripp. Codebreakers: The Inside Story of Bletchley Park. - Oxford University Press, 2001 .-- 360 p. - ISBN 978-0192801326 .
D. Stinson. Cryptography. Threory and Practice. - Chapman & Hall / CRC, 2006 .-- 611 p. - ISBN 978-1-58488-508-5 .
V. Mao. Modern cryptography. Theory and practice .. - Williams, 2005. - 768 p. - ISBN 5-8459-0847-7 .
E. Biham, A. Shamir. Differential Cryptanalysis of DES-like Cryptosystems . - Journal of Cryptology, 1990 .-- T. 4 .
E. Biham, A. Shamir. Differential Cryptanalysis of Feal and N-Hash . - Advances in Cryptology - EUROCRYPT '91, 1991 .-- T. 547 .
E. Biham, A. Shamir. Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer . - Advances in Cryptology - CRYPTO '91, 1991.
M. Matsui. Linear Cryptanalysis Method for DES Cipher . - Advances in Cryptology - EUROCRYPT '93, 1993.
L. Knudsen, J. Mathiassen. A Chosen-Plaintext Linear Attack on DES . - International Workshop on Fast Software Encryption, 2000.
DE Denning. Digital signatures with RSA and other public-key cryptosystems . - Communications of the ACM, 1984. - T. 27 .
G. Davida. Chosen signature cryptanalysis of the RSA (MIT) public key cryptosystem. - Dept. of Electrical Engineering and Computer Science, Univ. of Wisconsin, 1982.

[_48a0e36523090050-1] ¹ ² ³ Schneier, 2003 , p. 20.

[_48a0e36523090051-2] Schneier, 2003 , p. 21.

[_18bba8b8c3d8d282-3] Gabidulin , p. 25-28.

[_c4e2f21bdce6f4af-4] Schneier, Ferguson, 2002 , p. 48.

[_d28779fd5bcc244b-5] Schneier, Ferguson, 2002 , p. 47-49.

[_10205d6c82e06a27-6] Kahn, 2000 , p. 106-109.

[_05380e4174d1199e-7] Hinsley, 2001 .

[_a192b67f565934df-8] Stinson, 2006 , p. 27-29.

[_62151cf3f3ec4dde-9] ¹ ² ³ ⁴ Biham, Shamir (DES), 1990 .

[_089fa8b0520d3877-10] Biham, Shamir (FEAL), 1991 .

[_7d33e62e472acbac-11] Biham, Shamir (LOKI), 1991 .

[_268fc50523d0ac4c-12] Schneier, 2003 , p. 212-216.

[_4da5befdb1b298fe-13] ¹ ² Matsui, 1993 .

[_da7dae98e9d03463-14] Knudsen, 2000 .

[_72663eda884ea877-15] ¹ ² Schneier, 2003 , p. 342.

[_727738da885d1172-16] Schneier, 2003 , p. 404.

[_fbc298d415474523-17] Mao, 2005 , p. 308.

[_dbda18b66501d992-18] Schneier, 2003 , p. 404-406.

[_558447e4c8dc1070-19] Davida, 1982 .

[_a0e989c80b1d53d0-20] ¹ ² Denning, 1984 .