Known-plaintext attacks – Secgroup Ca' Foscari

So far, we have considered attackers that only know the ciphertext y and try to find either the plaintext x or the key k. In practice, it is often the case that an attacker can guess part of the plaintext. Think of encrypted messages: a message always have a standard header in a certain format and it is often easy to guess part of the information in it. Thus if a message is split into blocks which are encrypted under the same key, it is reasonable to assume that an attacker can deduce part of the plaintext. Also, if a key is reused to encrypt many plaintexts, it can occur that in the future one of the plaintext is leaked (because its security is no more relevant). This gives the attacker knowledge of a pair (x,y) plaintext, ciphertext.

For these reasons, in cryptography we often consider so-called known-plaintext attacks, i.e., we assume the attacker knows some pairs (x’,y’), (x”,y”) …. of plaintexts/ciphertexts. The challenge, given y, is to find the relative x or the k.

We illustrate this kind of attacks on a classical cipher.

The Hill cipher

This cipher is polyaplphabetic and generalizes the idea of Vigenére by introducing linear transformations of blocks of plaintext. We have ${\cal P} = {\cal C} = \mathbb{Z}_{26}^m$ , while ${\cal K} = \{ K \ | \ K$ is an invertible mod 26 matrix $m\times m\}$ . Encryption and decryption are as follows:

$\sf \begin{array}{rcl} E_{K}(x_1, \ldots, x_m) & = & (x_1, \ldots, x_m) K \mbox{ mod } 26 \\ D_{K}(y_1, \ldots, y_m) & = & (y_1, \ldots, y_m) K^{-1}\mbox{ mod } 26 \end{array}$

Example

Let $K = \begin{bmatrix} 5 & 11 \\ 8 & 3 \end{bmatrix}$ . We have that

$K^{-1} = det^{-1}(K)\begin{bmatrix} 3 & -11 \\ -8 & 5 \end{bmatrix}\mbox{ mod } 26$ $=det^{-1}(K)\begin{bmatrix} 3 & 15 \\ 18 & 5 \end{bmatrix}\mbox{ mod } 26$ .

Now

$det(K)=5\times3 - 11\times 8 \mbox{ mod } 26=15-88\mbox{ mod } 26= -73\mbox{ mod } 26=5$ .

In order to find the inverse mod 26 of 5 we need to find a number in the interval [0,25] that multiplied by 5 mod 26 gives 1. This number exists and is 21. In fact $21\times 5\mbox{ mod }26=105\mbox{ mod }26=1$ . Notice that it is not always the case that the multiplicative inverse modulo exists. We will discuss this more in detail when introducing public key cryptography and RSA. We have $K^{-1} = 21 \begin{bmatrix} 3 & 15 \\ 18 & 5 \end{bmatrix}\mbox{ mod }26=\begin{bmatrix} 11 & 3 \\ 14 & 1 \end{bmatrix}$ .

Consider the plaintext $(5,9)$ . We have,

$E_K(5,9) = (5,9) \begin{bmatrix} 5 & 11 \\ 8 & 3 \end{bmatrix}\mbox{ mod } 26=(5\times 5+9\times 8,5\times 11 + 9\times 3)\mbox{ mod } 26$ $=(19,4)$

$D_K(19,4)=(19,4)\begin{bmatrix}11&3\\14 &1\end{bmatrix}=(19\times 11+4\times 14,19\times 3+4\times 1)\mbox{ mod } 26$ $=(5,9)$ .

Cryptoanalysis

Assume, now, that the attacker has m pairs of plaintexts/ciphertexts, where m is the block length. We know that:

$\sf \begin{array}{rcl} (y^1_1, \ldots, y^1_m) & = & (x^1_1, \ldots, x^1_m) K \mbox{ mod } 26 \\\ldots&\ldots&\ldots\\ (y^m_1, \ldots, y^m_m) & = & (x^m_1, \ldots, x^m_m) K\mbox{ mod } 26 \end{array}$

which can be written as $Y = XK\mbox{ mod } 26$ with $X=\begin{bmatrix}x^1_1 &\ldots &x^1_m\\ \ldots&\ldots&\ldots\\x^m_1 &\ldots &x^m_m\end{bmatrix}$ and $Y=\begin{bmatrix}y^1_1 &\ldots &y^1_m\\ \ldots&\ldots&\ldots\\y^m_1 &\ldots &y^m_m\end{bmatrix}$ .

It is now clear that if $X^{-1}$ exists (see the above discussion about inverse modulo) we obtain $X^{-1}Y\mbox{ mod } 26=X^{-1}XK\mbox{ mod } 26$ from which $K=X^{-1}Y\mbox{ mod } 26$ .

Lesson learned

The Hill cipher is a linear transformation of a plaintext block into a cipher block. The above attack shows that this kind of transformation is easy to break if enough pairs of plaintexts and ciphertexts are known. Modern ciphers, in fact, always contain a non-linear component to prevent this kind of attacks.