Remark on variable tag lengths and OMD
Maria Eichlseder
Many of the submitted ciphers allow (or even recommend) variable tag
lengths for a fixed key length. In practice, it can be very useful to
support using the same key for different tag lengths.
While the CAESAR framework treats the tag length as part of the
algorithm, some submissions instead include it as part of individual
encryption calls in their specification (e.g., YAES) or otherwise tempt
implementers to allow such features (as it seems both natural and useful).
(Others, like OCB, explicitly forbid or at least discourage it in the
security claims section.)
However, for some ciphers, allowing variable tag sizes for the same key
reduces the integrity provided by the tag to the smallest supported tag
size. This is particularly critical if the cipher *suggests* that using
variable tag lengths is safe by adding countermeasures against trivial
truncation attacks. Two examples:
Trivial attack:
* YAES supports tag lengths t between 64 and 128 bits(*).
The tag length is only used for the final truncation to t bits.
Thus, if the verification oracle supports variable tag lengths, it is
trivial to forge 128-bit tags with effort ~2^64:
1. Guess tag for 64-bit version for the targeted nonce/plaintext/
associated data N,P,A: ~2^64 verification oracle queries
2. Fix first 64 bits of the 128-bit tag version to the above result
and guess the remaining 64 bits independently: ~2^64 queries.
(*) it should be noted that the claimed integrity is only 55 bits.
Less trivial attack with added countermeasures against the above:
* OMD supports tag lengths t between 32 and 256.
To prevent the above attack, the tag length t is included as a
constant in the tag computation, so the smaller-sized tags are no
longer prefixes of the longer-sized tags for the same K,N,A,P.
However, forgeries are nevertheless possible. The problem is that the
final tag is the XOR of two tags: tag_e from the plaintext, and tag_a
from the associated data. Now tag_a depends neither on the nonce
nor on t (except for truncation), both values are only used for the
computation of tag_e.
This leads to the following attack, which queries the encryption
oracle for i-bit tags T_i for N_i,P,A (i=32,64,96,...,256)
and forges T_i* for all N_i,P,A* with ~2^34 decryption queries in
total (practical complexity):
DeltaA = empty
For i=32, 64, 96, ..., 256:
1. Query i-bit tag T_i for fresh nonce N_i, plaintext P, ass.data A
2. Set first i-32 bits of i-bit tag T_i* to those of T_i xor DeltaA
3. Guess the remaining 32 bits of T_i* by ~2^31 verification
queries for N_i,P,A*
4. Set DeltaA = T_i xor T_i*
The attack works because the xor difference between two tags for the
same N, P and different A/A* equals the xor difference of tag_a and
tag_a* and thus depends neither on the nonce nor on the tag length.
Thus, it can be carried over from i to i+1.
Consequently, a simple fix would be to include nonce and t in tag_a
in some way (or, of course, to plainly forbid variable-tag-length
settings).
Best regards,
Christoph Dobraunig, Maria Eichlseder, Florian Mendel, Martin Schläffer
Reza Reyhanitabar
Dear all,
In OMD the tag length ($\tau$) is one of the “parameters” that must be selected and “fixed” before using the algorithms, NOT a variable-length input to the algorithms. Of course this “fixed parameter” can be selected as a number in the range [32, 256] (for OMD-sha256). Never in the description of OMD we have allowed or encouraged a variable length tag to be used with the same key.
This has been made completely clear throughout the description of the algorithm as is in the submission pack to CAESAR, where in more than one place we have explicitly mentioned it.
Although we thought that in many places inside the OMD submission pack it has been made clear that the tag length is a parameter of the algorithm, this will be even more clear from the Reference implementation pack of OMD-sha256 where for each set of recommended values for the parameters “(key length, nonce length, tag length)” (selected from their allowed ranges, i.e., $80 \leq k \leq 256$, $96 \leq |N| \leq 255$, and $32 \leq \tau \leq 256$) we have a different algorithm, for example “omdsha256k128n96tau64v1” and “omdsha256k128n96tau96v1” are two different algorithms which have the same key length (k=128), the same nonce length (n=96) but different tag lengths (\tau=64 and \tau=96).
The attack by Dobraunig et al. is based on mixing up the “flexibility” of OMD in providing different parameter sizes which is a strong point for OMD with what they assume as allowing variable-length inputs. Hence, it is not an attack against the OMD as described in the CAESAR submission.
Dobraunig et al. say that “OMD supports tag lengths t between 32 and 256. To prevent the above attack, the tag length t is included as a constant in the tag computation, so the smaller-sized tags are no longer prefixes of the longer-sized tags for the same K,N,A,P.” This is never said in the description of OMD and its security analysis; in fact, we note that replacing the tag length in the first block with any other constant (e.g. 0) will not affect the security proof of OMD at all.
We also note that Dobraunig et al.’s suggestion to “include
nonce and t in tag_a
in some way” might yield to an interesting new variant of OMD with the extra
feature of supporting variable-length tags, but this (variable-length tag
input) is not something which is supported in OMD.
OMD team