OFFICIAL COMMENT: FlexAEAD

[Maria Eichlseder]

Dear all,

We think that the FlexAEAD candidate permits forgery attacks with higher
success probability than 2^-tagsize.

Based on our understanding of the specification, we suggest the following:

Target variants:
FlexAEAD128b128 (128-bit key, block, nonce, tag)
FlexAEAD256b256 (256-bit key, block, nonce, tag)

Consider two associated data blocks AD_i and AD_j.
Their contribution to the checksum is PF_K2(S_i+AD_i) + PF_K2(S_j+AD_j),
where S_k is generated from the nonce N and key K3 as S_k =
PF_K3(INC32^k(PF_K3(N))) and INC32 increases each 32-bit chunk of its
input N' = PF_K3(N) by 1 (addition mod 2^32), in little endian notation
(i.e., 1 = 0x01,0x00,0x00,0x00).
With probability 2^-4 (resp. 2^-8), these 4 (resp. 8) modular additions
correspond to XORs. In the following, let j = i+16, with similar reasoning.

Assume we have a 6-round (resp. 7-round) differential for 128-bit (resp.
256-bit) PF_K3 with input difference
Delta_in = 10000000 10000000 10000000 10000000 (or 2x the same)
and some Delta_out with probability p > 2^-124 (resp. 2^-248).

With prob. 2^-4 (resp. 2^-8), the input difference to PF_K3 in INC32(N')
between some AD_i and AD_j is Delta_in, and then, with probability p,
the output difference in S_i, S_j is Delta_out.

Query the tag for some plaintext with associated data of at least j+1
blocks with AD_i + AD_j = Delta_out.
With prob. p*2^-4 (resp. p*2^-8), AD_i + AD_j + S_i + S_j = 0, so S_i +
AD_i = S_j + AD_j, so the contribution to the checksum is
PF_K2(S_i+AD_i) + PF_K2(S_j+AD_j) = 0.
If we swap AD_i and AD_j, with the same reasoning, the contribution will
also be 0, so the old tag is valid for the modified associated data with
swapped blocks.

This forgery attack is successful with probability p*2^-4 (resp. p*2^-8).

Now we need to find a suitable differential characteristic for
(Delta_in, Delta_out).

For FlexAEAD128b128, a suitable differential with probability p = 2^-79
is given by

10000000 10000000 10000000 10000000 = Delta_in
00000000 00005000 00000000 00003000 = Delta_out

The resulting forgery attack has a success probability of 2^-83.


For FlexAEAD256b256, a suitable differential with probability p = 2^-108
is given by

10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000
= Delta_in
00000000 00000000 00009000 00000000 00000000 00000000 00000000 00000000
= Delta_out

The resulting forgery attack has a success probability of 2^-116.


The corresponding characteristics are illustrated in the attached PDF file.
Note that the cipher is an Even-Mansour construction without round keys,
so the real probability might differ.

Is this interpretation of the specification correct?

Best regards,
Maria Eichlseder, Daniel Kales, Markus Schofnegger