We prove a new upper bound on the advantage of any adversary for distinguishing the encrypted CBC-MAC (EMAC) based on random permutations from a random function. Our proof uses techniques recently introduced in [BPR05], which again were inspired by [DGH + 04]. The bound we prove is tight — in the sense that it matches the advantage of known attacks up to a constant factor — for a wide range of the parameters: let n denote the block-size, q the number of queries the adversary is allowed to make and ℓ an upper bound on the length (i.e. number of blocks) of the messages, then for ℓ ≤ 2 n/8 and q≥ł2 the advantage is in the order of q 2/2 n (and in particular independent of ℓ). This improves on the previous bound of q 2ℓΘ(1/ln ln ℓ)/2 n from [BPR05] and matches the trivial attack (which thus is basically optimal) where one simply asks random queries until a collision is found.
Part of this work is supported by the Commission of the European Communities through the IST program under contract IST-2002-507932 ECRYPT.
168 - 179
ICALP: Automata, Languages and Programming
Pietrzak KZ. A tight bound for EMAC. In: Vol 4052. Springer; 2006:168-179. doi:10.1007/11787006_15
Pietrzak, K. Z. (2006). A tight bound for EMAC (Vol. 4052, pp. 168–179). Presented at the ICALP: Automata, Languages and Programming, Springer. https://doi.org/10.1007/11787006_15
Pietrzak, Krzysztof Z. “A Tight Bound for EMAC,” 4052:168–79. Springer, 2006. https://doi.org/10.1007/11787006_15.
K. Z. Pietrzak, “A tight bound for EMAC,” presented at the ICALP: Automata, Languages and Programming, 2006, vol. 4052, pp. 168–179.
Pietrzak KZ. 2006. A tight bound for EMAC. ICALP: Automata, Languages and Programming, LNCS, vol. 4052, 168–179.
Pietrzak, Krzysztof Z. A Tight Bound for EMAC. Vol. 4052, Springer, 2006, pp. 168–79, doi:10.1007/11787006_15.