Partitioning attacks on Grain128-AEAD

Grain128-AEAD is a stream cipher, which has reached round 2 in the light-weight cryptography competition organized by NIST. The authenticated version is designed by Hell, Johansson, Meier, Sönnerup and Yoshida. In particular, the cipher consists of two main blocks: an LFSR and an NFSR. The authentication works by extracting bits from the keystream, which are exclusively used for the authentication tag, via an accumulator. A nice consequence of this, is that the security of the tag — in some regard — can be reduced to the security of the cipher.

The authentication tag is computed as

$\begin{bmatrix}t_0\\t_1\\ \vdots \\ t_{w-1}\end{bmatrix} = \begin{bmatrix}k_{-1} & k_{0} & k_{1} & \cdots & k_{L-2}\\ k_{-2} & k_{-1} & k_{0} & \cdots & k_{L-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ k_{-w} & k_{-w+1} & k_{-w+2} & \cdots & k_{L-w-1}\end{bmatrix} \begin{bmatrix}m_0\\m_1\\ \vdots \\ m_{w-1}\end{bmatrix}$

So, given the matrix $K$ , we can solve the equations to find a message which has any tag $\mathbf t$ we want. If we have a set of keys, say ${a,b}$ , we can compute the corresponding key matrices $K_a, K_b$ . Note that since we know ${a,b}$ , we can make the dimension of them arbitrarily large.

Construct $K' = \begin{bmatrix} K_a & K_n\end{bmatrix}$ and solve the equation system $\mathbf t = K' \mathbf m$ for any arbitrary $\mathbf t \in \mathbb F_2^{64}$ . Now, we have solved the problem of the same message evaluating to the same tag. But this not exactly what we want — instead we want equal ciphertexts to evaluate to the same tag. If we denote the keystream used for encryption as $\mathbf z$ and the ciphertext $\mathbf c = \mathbf z + \mathbf m$ , then we can rewrite the above as

$\mathbf t = K' (\mathbf c + \mathbf z) \iff \mathbf t + K' \mathbf z = K' \mathbf c$

and we solve for $c$ . We now get two equal ciphertexts (and same IV), but different decrypted messages which evaluate to the same arbitrary tag. Of course, we can extend this to an arbitrary amount of messages. Compared to GCM and Poly1305, which both have a nice structured matrix allowing for $n^2$ complexity, the inclusion of non-linear bits in Grain makes the solving part a bit more expensive and ends up around $n^3$ .

In the context of partition oracles, we typically assume that the keys were generated using a KDF from a large set of passwords which we like to probe for using limited queries.

For instance, the block

$\begin{array}{rcl}c &=& \texttt{0000110100011001110111110101101000110001} \\ && \texttt{1111101000111010101010101001110101000010}\\ && \texttt{0100010010000110111101111010110000010111}\\ && \texttt{0011001010000000000000000000000000000000}\\ \\t & = & \texttt{0000000000000000000000000000000000000000000000000000000000000000}\end{array}$

decrypts successfully (i.e. tag is valid) under both keys

$\begin{array}{rcl}a & = & \texttt{0000000000000000000000000000000000000000000000000000000000000000} \\ && \texttt{0000000000000000000000000000000000000000000000000000000000000000}\\\\b & = & \texttt{1000000000000000000000000000000000000000000000000000000000000000} \\ && \texttt{0000000000000000000000000000000000000000000000000000000000000000}\end{array}$

So, using the above cipertext and tag we can simultaneously test for two passwords such that $\textsf{KDF}(\texttt{hunter2}) = a$ and $\textsf{KDF}(\texttt{123456}) = b$ using an oracle which validates the tag. The response can be error based, timing based or some other measurable information.

grocid.net

scribbles from past, present and possibly future

Partitioning attacks on Grain128-AEAD

Leave a Reply Cancel reply

Menu

grocid.net

scribbles from past, present and possibly future

Share this:

Like this:

Leave a Reply Cancel reply

Menu