RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2025 Volume 16, Issue 2, Pages 25–58 (Mi mvk494)

How to protect integrity of $2^{75}$ blocks using the Magma cipher and a single key?

V. A. Kiryukhinab

a LLC «SFB Lab», Moscow
b JSC «InfoTeCS», Moscow

Abstract: Let the AEAD-mode MGM be used only for integrity protection, and the nonce is fixed. We prove that the obtained algorithm (MGM-PRF) is a pseudorandom function (PRF) and hence a secure MAC (message authhentication code). When using a cipher with a block of $n=64$ bits (“Magma”) and the probability of forgery at most $\pi_{\mathrm{mac}}=2^{-10}$ algorithm MGM-PRF can process $q\leq2^{26}$ messages of $l\leq2^{26}$ blocks each ($q\cdot l\leq2^{52}$) with a single key.
Similarly, but with minor modifications, from the AEAD-mode MGM2 (CTCrypt 2021), we construct the MGM-PRF algorithm, which can protect the integrity of messages up to $l\leq2^{63}$ blocks long ($q\cdot l\leq2^{89}$).
Going beyond the birthday paradox bound (BBB, $q>2^{\frac{n}{2}}$) is possible by doubling the internal state of the cryptoalgorithm. We propose a new BBB-secure PRF MGM-PRF, which essentially consists of applying MGM-PRF twice in parallel to a single message and summing the results. SUM-MGM uses a single encryption key with which it can securely protect $q\leq2^{37}$ messages, up to $l\leq2^{38}$ blocks long ($q\cdot l\leq2^{75}$).
The results are obtained by using the H-coefficient method, PRP-PRF Lemma is not used.

Key words: MGM, PRF, SUM-MGM, provable security, AEAD, H-coefficients.

UDC: 519.719.2

Received 14.X.2024

DOI: 10.4213/mvk494



© Steklov Math. Inst. of RAS, 2025