Cryptology ePrint Archive: Report 2018/468

ISO/IEC 9797-1 Revisited: Beyond Birthday Bound

Yaobin Shen and Lei Wang and Dawu Gu

Abstract: The international standard ISO/IEC 9797-1:2011 specifies six versions of MACs, called MAC Algorithm 1-6, and many of these MACs enjoy widespread use in practical applications. However, security guarantees of these MACs are all capped at birthday bound since they all use single CBC-MAC computations. It is recommended in this standard to improve the security level by concatenating outputs of two MACs with independent keys rather than XORing them.$\\$ In this paper, we show such claim is wrong by giving birthday forgery attacks on concatenations of two MACs with independent keys in this standard. Furthermore, we revisit the impact of XORing of two MACs in ISO/IEC 9797-1:2011 and show this operation can only lift up the security level. We give the first two provable-security bounds for XORing of two MAC Algorithm 1 (XMAC1) in ISO/IEC 9797-1:2011 with either padding scheme 3 or 2. We prove that XMAC1 with padding scheme 3 is secure beyond birthday bound with $O(\sigma q^2\ell/2^{2n})$. Note that our result implies that this is the first CBC-type MAC that provably goes beyond birthday barrier with only two secret keys. When instantiated with padding scheme 2, we prove that XMAC1 is secure with birthday bound $O(\sigma^2/2^n)$. Illustrated with Joux et al's attack, this bound is tight up to a constant factor. We also prove that XORing of two MAC Algorithm 5 (XMAC5) is secure with a bound $O(\sigma q^2\ell/2^{2n})$.$\\$ Finally, together with previous results, we give a summary of the impact of XORing of two MACs on ISO/IEC 9797-1:2011 and conclude that such operation can only lift up the security bound.

Category / Keywords: ISO/IEC 9797-1, birthday forgery attack, XMAC1, XMAC5, beyond birthday bound

Date: received 14 May 2018, last revised 22 May 2018

Contact author: yb_shen at sjtu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20180522:130657 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]