# CPA distinguisher for matrix multiplication in GF(256) with randomized padding

What is the best CPA distinguisher for the function $F_k:\{0,1\}^{8n}\to\{0,1\}^{16n}$ described below?

Let $E_k$ be a $2n\times2n$ matrix with elements in $GF(2^8)$, selected by generating bit strings of length $32n^2$ using a predefined function $PRF_k$, until one is found that is invertible e.g. using Gaussian elimination.

To encode an input bit string $M$, generate random bit string $Pad$ of length $8n$. Let the $2n$ element vector $T$ correspond to the concatenation $M|Pad$. Calculate the vector $C$ using the formula $E_kT^T=C^T$.

The decoding function is given by the $n\times2n$ matrix corresponding to the first $n$ rows of $E_k^{-1}$.

Obviously, you need no more than $4n$ chosen cipher texts and access to a decryption oracle, to be able to derive the decoding matrix. But is there a better CPA distinguisher than statistical analysis of the skew caused by a constant $M$ for a relatively large number of $Pad$ values?

-

Split the matrix $E_k$ into four $x \times n$ blocks like this: $$E_k = \begin{bmatrix}P & Q \\ R & S\end{bmatrix}$$

Let $C = [A, B]$, where $A$ and $B$ are $n$ elements vectors. If $M$ is an $n$ element null vector $[0, 0, \dotsc, 0]$, the $P$ and $R$ matrices won't affect the result, and we thus have $Q^{-1} A^T = Pad^T = S^{-1} B^T$.

Collect $n$ of these $(A,B)$ pairs by repeatedly encrypting the null vector, and solve the linear system $SQ^{-1} A_i^T = B_i^T$ for $SQ^{-1}$. If you're unlucky and don't get a unique solution, obtain a few more pairs and try again.

You will now be able to distinguish encryptions of the null vector from those of other plaintexts.

(The approach above works as long as at least one of $S$ and $Q$ is invertible. Even if neither can be inverted, it should still be possible to calculate a pseudoinverse by solving the system in the least squares sense, and thus obtain a partial distinguisher.)

-
Here's an even easier distinguisher; just ask for $n+1$ encryptions of the null (all zeros) vector, and check to see if the resulting $n+1$ vectors of $2n$ elements are linearly independent; with this cipher, they never will be independent (the cipher has only $n$ degrees of freedom in this case); for a random output, they (with high probability) will be independent. –  poncho Apr 9 '12 at 16:25

While Ilmari answered the specific question you asked (Chosen Plaintext Distinguishers), I would like to note that the attack can be sharpened into a Known Plaintext Key Recovery attack (where, by key recovery, I don't mean recovering the $E_k$ matrix, but instead allowing an attacker to reconstruct enough information to decrypt arbitrary texts).

One straightforward way to see this is to observe that the decryption process is entirely linear; that is, if we know that:

$Decrypt(C_1) = P_1$ and $Decrypt(C_2) = P_2$

then

$Decrypt(aC_1 + bC_2) = aP_1 + bP_2$ for $a, b \in GF(2^8)$

So, all the attacker needs to do is collect $2n$ linearly independent ciphertexts with corresponding known plaintexts:

$Decrypt(C_1) = P_1$

$Decrypt(C_2) = P_2$

...

$Decrypt(C_{2n}) = P_{2n}$

Then, do decrypt an arbitrary ciphertext $C_x$, he solves the linear equation for $a_1, a_2, \ldots a_{2n}$:

$C_x = \sum_i a_i C_i$

and then he knows that

$Decrypt(C_x) = Decrypt( \sum_i a_i C_i) = \sum_i a_i P_i$

-
That's an excellent answer — much better than mine, really. –  Ilmari Karonen Apr 8 '12 at 21:39
Thanks, very good answer, as always. However, as you seem to have noted yourself, Ilmari described a CPA distinguisher that (most of the time) requires only half the number of queries to the encryption oracle, so I am giving the accept to him. –  Henrick Hellström Apr 8 '12 at 21:56
@HenrickHellström: not a problem; as I said, Ilmari did give an answer (and I believe that it is in fact the best possible answer, that it, the minimum number of queries possible) to your original question. –  poncho Apr 8 '12 at 22:55