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.
Grain building blocks.
The authentication tag is computed as
So, given the matrix , we can solve the equations to find a message which has any tag we want. If we have a set of keys, say , we can compute the corresponding key matrices . Note that since we know , we can make the dimension of them arbitrarily large.
Construct and solve the equation system for any arbitrary . 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 and the ciphertext , then we can rewrite the above as
and we solve for . 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 complexity, the inclusion of non-linear bits in Grain makes the solving part a bit more expensive and ends up around .
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
decrypts successfully (i.e. tag is valid) under both keys
So, using the above cipertext and tag we can simultaneously test for two passwords such that and using an oracle which validates the tag. The response can be error based, timing based or some other measurable information.
