Paper 2019/1359

Universal Forgery Attack against GCM-RUP

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


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. CT-RSA 2020
GCM-RUPpartial key recoveryuniversal forgerybirthday bound
Contact author(s)
mqwang @ sdu edu cn
2020-01-13: revised
2019-11-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yanbin Li and Gaëtan Leurent and Meiqin Wang and Wei Wang and Guoyan Zhang and Yu Liu},
      title = {Universal Forgery Attack against GCM-RUP},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1359},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.