Cryptology ePrint Archive: Report 2019/1359

Universal Forgery Attack against GCM-RUP

Yanbin Li and GaŽtan Leurent and Meiqin Wang and Wei Wang and Guoyan Zhang and Yu Liu

Abstract: Authenticated encryption (AE) schemes are widely used to secure communications because they can guarantee both confidentiality and authenticity of a message. In addition to the standard AE security notion, some recent schemes offer extra robustness, i.e. they maintain security in some misuse scenarios. In particular, Ashur, Dunkelman and Luykx proposed a generic AE construction at CRYPTO'17 that is secure even when releasing unverified plaintext (the RUP setting), and a concrete instantiation, GCM-RUP. The designers proved that GCM-RUP is secure up to the birthday bound in the nonce-respecting model.

In this paper, we perform a birthday-bound universal forgery attack against GCM-RUP, matching the bound of the proof. While there are simple distinguishing attacks with birthday complexity on GCM-RUP, our attack is much stronger: we have a partial key recovery leading to universal forgeries. For reference, the best known universal forgery attack against GCM requires $2^{2n/3}$ operations, and many schemes do not have any known universal forgery attacks faster than $2^n$. This suggests that GCM-RUP offers a different security trade-off than GCM: stronger protection in the RUP setting, but more fragile when the data complexity reaches the birthday bound. In order to avoid this attack, we suggest a minor modification of GCM-RUP that seems to offer better robustness at the birthday bound.

Category / Keywords: secret-key cryptography / GCM-RUP, partial key recovery, universal forgery, birthday bound

Original Publication (in the same form): CT-RSA 2020

Date: received 26 Nov 2019, last revised 13 Jan 2020

Contact author: mqwang at sdu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20200113:075935 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]