Collision Attacks against AEZ-PRF for Authenticated Encryption AEZ

Tairong Shi*, Chenhui Jin, Jie Guan

Information Science and Technology Institute, Science Avenue, High-Tech Zone, Zhengzhou, Henan 450001, China

I. INTRODUCTION

Authenticated encryption algorithm [1] combines encryption with authentication, providing both confidentiality and authenticity simultaneously and has been widely used in security protocols such as SSL/TLS [2]. In order to accelerate the development of authenticated encryption, CAESAR competition [3],a large-scale cryptographic competition like AES [4], and e-STREAM [5] supported by the US National Institute of Standards and Technology (NIST) , was launched in 2014. The goal of this competition is to find robust and efficient authenticated encryption algorithms that offer advantages over AES-GCM and are suitable for widespread adoptions. Fifty-seven candidates were submitted to the CAESAR competition. Now, 15 remaining third-round submissions are going through an intensive review, analysis and comparison progress.With excellent performance in security and efficiency, the third-round candidates were very competitive and therefore attracted many researchers [6, 7, 8].

AEZ [9], a particularly notable authenticated encryption scheme designed by Hoang,Krovetz and Rogaway, was selected as a thirdround candidate of the ongoing CAESAR competition. The authors also defined the security notion of RAE (Robust Authenticated Encryption), and AEZ was claimed to achieve this security notion [10]. In this paper, we focus on AEZ v4.2, the latest version of AEZ, as proposed on the crypto-competition mailing list.

When a message is transformed to protect both its confidentiality and authenticity, there may be additional information, such as a packet header that travels alongside the message or the ciphertext (at least conceptually) and must get authenticated. The additional information is noted as associated data, and this kind of authenticated encryption scheme is called authenticated-encryption with associated-data（AEAD) scheme[11].AEZ, like many entries in the CAESAR competition, is an AEAD-scheme. Three AEZ models, i.e., AEZ-core, AEZ-tiny and AEZ-prf are recommended in different message lengths. Strings of 32 bytes or more are enciphered using AEZ-core, while those of 1–31 bytes are enciphered using AEZ-tiny. The AEZ-prf is only used for the special case of enciphering the empty message. In other words, AEZ-prf is used to authenticate the associated data. AEZ claims security when its nonce is reused or misused.We focus on AEZ-prf with only associated data in the nonce-reuse setting. Collision attacks are given in both the quantum setting(using Simon’s quantum algorithm [12, 13]and the classical world.

Simon’s quantum algorithm (the simplest quantum period finding algorithm) is very important in quantum algorithm theory. Previously, there has been considerable work in the application for the context of symmetric cryptography. Simon’s quantum algorithm was first used to break the security of the 3-round Feistel construction [14] and then to prove that the Even-Mansour construction [15] is not secure with superposition queries [16]. While Simon’s problem (that solved by Simon’s quantum algorithm) is a promise question to find a quantum period, Simon’s quantum algorithm is a quantum period finding algorithm.In this sense, collision attack on authenticated encryption can be performed with superposition queries by Simon’s quantum algorithm.Recently, Kaplan et al. [17] presented attacks on several widely used modes of operation for authentication and authenticated encryption in their security model.

In the previous work, Kaplan et al. [17] has given a guess on the original version AEZ in quantum world, in which the nonce is not used to process the associated data. Our analysis focuses on AEZ v4.2, in which designers have made major changes and corrections compared with previous versions. In particular, our attack is more specific and captures the characteristic of AES-prf for AEZ v4.2, demonstrating the analysis in both quantum and classical settings.

Our Contribution.

In this paper, we initiate the collision attack of AES-prf for AEZ v4.2 in the progressing of associated data. For any associated dataAwith 256 bits, we prove that there is ans,such thatder the same key and same nonce. In this way,we use Simon’s quantum algorithm withO(n)quantum superposition queries to recover the real value ofswith a low complexity and success probability close to 1. We can also getBunder classical settings with the assumption that attackers possess the key.

In other words, without quantum techniques, a user or sender who masters the keyKwould make use of the collision to perform a spite attack, denying the information which has been authenticated. What is more, a malicious sender can manipulate the associated data to obtain the collision of the tag and therefore can frame a forged message accepted as legitimate. That is, a potential threat has been indicated.

Finally, we give a brief analysis of what is responsible for collision attack in conclusion. To the best of our knowledge, there is no cryptanalysis of AEZ v4.2 proposed so far.Our results can also be applied to AEZ v3,which has been published on Eurocrypt 2015,and presented as one of the honorable mentions for the best papers award [10].

Organization.

This paper is organized as follows. The Section 2 provides a brief description of AEZ v4.2. In the Section 3, we recall some funda-mental quantum knowledge and introduce the Simon’s quantum algorithm. In the Section 4,we deduce the collision attack against AEZ-prf in both quantum setting and classical world.We extend collision attacks to AEZ v3 in Section 5, followed by a conclusion in Section 6.

II. DESCRIPTION OF AEZ V4.2

AEZ v4.2 takes as argument or parameters:a keyK∈{0,1}k, a public sequence numberN∈{0,1}n, an associated dataA∈{0,1}*and authenticator lengthτ∈{0,1}*thatτdetermines how much longer a ciphertext is than its plaintext. In particular, AEZ v4.2 allows a vector-valued input, that is to say, it can authenticate a sequence of strings.

Hereafter we are only interested in the AEZ-prf model, i.e., the processing of authenticated data without any message. In this case,AEZ turns into a variant of PMAC [18], and the security claim becomes the usual MAC security definition. Without specification, all AEZ refers to AEZ v4.2 in the rest of paragraphs.

Step 1.DivideAintonportions:

(A1,A2,…,An)←A.

Step 2.Connect τ,NwithA:

Step 3. Use AEZ-hash to hashT:

Δ←AEZ-hash(K,T).

Step 4.ReturnTag:TagA=(EK1(Δ⊕3·J)).

For convenience, AEZ-prf(K,N,A,τ)is called AEZ-prf(A) for a fixed series ofK,N,τ. The function AEZ-hash(K,T) can be described as follows:

Step1. (T1,T2,… ,Tt)←T,Δ=0. //For simplicity, we consider

Step2. Fori=1 totdo

Step3.Return Δ.

A complete description of AEZ can be found in [9].

III. PRELIMINARY

In this section, we revisit some basics of quantum operations in advance, as well as Simon’s problem and the quantum algorithm for efficiently solving it.

3.1 A Brief introduction of Hadamard gate

An important transform will be used later in Simon’s quantum algorithm is the Hadamard gate [19]. It’s represented by the following matrixH:

The Hadamard gate is one of the most useful quantum gates. It turnsinto(first column ofH), a ‘halfway’ betweenand turnsinto(second column ofH), which is also a ‘halfway’ between

More generally, the Hadamard gateH?napplied on ann-qubit statewithx∈{0,1}nand gives

3.2 Running functions in superposition

Attacking specific classical cryptosystems requires a precise definition for the operations that the adversary is allowed to perform. In addition to local quantum operations, an adversary is permitted an access to a possible remote cryptographic oracle in superposition[6] of the inputs, and gains the corresponding superposition of the outputs.

In more detail, if the encryption function is depicted byf:are twon-qubit states expressed in the computational basis, then the adversary can make standard quantum queries, runningfonmeans to apply the unitary transformation,Uf, such that

where ⊕ is bitwise XOR.

More generally, any superpositionis a valid input to the quantum oracle, and an adversary can receive the follow result:

3.3 Simon’s quantum algorithm and attack strategy

The input of Simon’s problem includes a functionf. To run Simon’s quantum algorithm, it is required that the functionfcan be queried quantum-mechanically.

Simon’s problem:Suppose there is a multiple output Boolean functionf:and assume that there exists uniqueif and only ifThe goal is to finds.

Heresis regarded as the period off. This problem can be solved by searching for collisions classically, but its complexity is 2n.Whereas, the Simon’s quantum algorithm is simple, it consists essentially ofO(n) repetitions of the following five quantum steps.

Step 1. Beginning with a 2n-qubit stateone applies the Hadamard transformH?nto the first register to obtain the quantum superposition.

Step 2.A quantum query to the functionUfmaps this to the state

Step 3.Measure the second register in the computational basis yields a valuef(z) and collapses the first register to the state:

Step 4.Apply the Hadamard transformH?nagain to the first register, and get:

Step 5.Measure the state in the computational basis, and yields a random vectorywithy·s=0.

By repeating this subroutineO(n) times,one can obtainsn-1 independent vectorsuiorthogonal toswith high probability, andscan be recovered by means of basis linear algebra. So Simon’s quantum algorithm finds the period using superposition queries with a low complexity.

The following theorem 1 gives the compromise between the repeated times of the subroutine and the success probability of Simon’s quantum algorithm.

For a cryptography problem, the conditions onfin Simon’s problem is not true usually. We shall consider a weak limit onfas following.

The generalized Simon’s assumption:

Theorem 1then the Simon’s quantum algorithm returnsswithcnqueries, with a probability

Consequently, it ensures that we can getswith a probability exponentially close to 1.

Note that the Simon’s quantum algorithm is nothing but a tool used tond collisions in our research, we do not need to understand it in detail.

IV. COLLISION ATTACKS AGAINST AEZPRF FOR AEZ V4.2

A collision occurs, if a function within a cryptographic algorithm progresses different inputs, but returns an equal output. Therefore,we take two different associated dataAandBinto consideration, and give collisions of AEZ-prfrstly.

4.1 The collision form of AEZ-prf for AEZ v4.2

In order to mount a powerful collision attack on AEZ-prf with the authenticator lengthτand nonceN, we consider the associated dataAwith two arbitrary blockswhere “||” is bit connection. This is illustrated by Figure 1 (which denote the generation ofτ,NasαN).

In particular, we have:

Now we compute another associated dataand

Fig. 1. The AEZ-prf model (no message, for associated data strings A1 ||A2).

From 12⊕4=8 and 10⊕11=1, we know that

4.2 Collision attack on AEZ v4.2 in quantum setting

We now illustrate an application of Simon’s quantum algorithm to AEZ-prf concretely.According to Simon’s quantum algorithm, a function that satises the generalized Simon’s assumption should be constructed atrst. Here we define functionfor a random nonceNwith an arbitrary constantsδ∈{0,1}128. For anyx∈{0,1}128, let

From the above analysis of collision form in Section 4.1,it is obvious to see thatwhich results thathas the identical tag withunder the same key and same nonce.

2. The same tag is valid fornamely

Complexity and success probability:

Simon’s quantum algorithm makes the attack complexity almost negligible. Theorem 1 guarantees the collision attack with a success probability close to 1. Thus, the collision attack in the quantum setting is practical.

4.3 Collision attack in classical setting

In this section, we analyze the collision in usual classical setting. With the result thathas the same tag withtwo classical attacks on AEZ-prf exist as follows.

Case 1:For adversary who knows theK(including message user, sender).

As a malicious user who masters the secretK, the whitening keysL,Jare available to him. In this case, the attacker may deny the already authenticated associated dataand claiming that the untreated associated datais the associated data sent. Thus AEZ-pdf algorithm can’t facilitate non-repudiation.In our settings, we assume that the key is known. This is not necessarily true for an external attacker. However, the sender has access to the secret key and allowing the sender to create collisions is not a desirable property either. For AEZ-prf, the sender can find a collision for any given key, initialization vector(nonce) and input associated data with 256 bits, thereby compromising the authenticity component of the authenticated encryption. A malicious sender can manipulate the associated data to obtain the collision of the tag and therefore can frame a forged message accepted as legitimate.

Case 2: For an adversary who doesn’t know theK.

Once we find two collided associated datait is possible with a large probability thatandSo we can immediately reveals the value of 12·L⊕J. Thus we can find an collision ofwithfor anyandD2=C1⊕12·L⊕J.This means that from one collision of AEZ-prf, we can constructed a collision for any associated data with 256 bits, which is an unexpected property in the processing of authenticated data AEZ-prf.

It should be mentioned that, the security claims of AEZ are given in the CAESAR competition submission document [9] and academic paper corresponding to this submission[10], stating that:

“With a scheme for robust authenticated-encryption a user can select an arbitrary valueλ≥0 and then encrypt a plaintext of any length into a ciphertext that’sλcharacters longer. The scheme must provide all the privacy and authenticity possible for the requestedλ.”

“AEZ achieves nonce-reuse misuse-resistance”.

Clearly, through above analysis, the AEZ algorithm does not have the security properties when only authenticates the associated data in the nonce-reuse setting. with 256 bits, where

V. COLLISION ATTACK ON AEZ-PRF FOR AEZ V3

In this section, we extend our collision attacks to AEZ v3. For simplicity, we consider AEZ v3 only with a set of associated datawith 256 bits, then the tag is computed as:

VI. CONCLUSIONS

In this article, we evaluate the security of CAESAR candidate AEZ in both the post quantum world and classical world. Namely,we have constructed collision attacks on the processing of the associated data. Our results show that AEZ is not provided integrity fully which do not violate the security proof of the AEZ. In addition, a kind of deny of authenticated message is proposed, which is not a desirable property for authenticated encryption.

We also analyze the reasons that cause those attacks. The way AEZ-prf generates tag is a little simple, while the tag only operates on the linear connection of each previous offsets. There is not enough mutual feedback in the process of authentication. Increasing some nonlinear transformation between the final inputs may be helpful to authenticated encryption.

Although our analysis focuses only on AEZ, it is important to note that the goal of post-quantum cryptography is to resist quantum adversaries. With the advance of the competition, authenticated encryption receives more attentions and develops rapidly. More authenticated encryption algorithms might be broken following the same models. This is the part of future work.

ACKNOWLEDGMENT

This work was supported by the National Natural Science Foundation of China(Grant No.61572516, No.61272041 and No.61272488).

[1] M. Bellare and C. Namprempre, “Authenticated encryption: Relations among notions and analysis of the generic composition paradigm,”Journal of Cryptology, vol. 21, no. 4, 2008, pp.469-491.

[2] K. Hickman and T. Elgamal, “The SSL protocol,”Netscape Communications Corp, 1995. http://www.webstart.com/jed/papers/HRM/references/ssl.html, [2017-04-13].

[3] D. J. Bernstein, “Caesar: Competition for authenticated encryption: Security, applicability, and robustness,” 2015. http://competitions.cr.yp.to/caesar.html, [2017-04-13].

[4] J. Daemen and V. Rijmen, “The Design of Rijndael: AES-the advanced encryption standard,”Springer, Berlin, pp. 31-50, 2002.

[5] ECRYPT, European Network of Excellence in Cryptology: “The Stream Cipher Project: eSTREAM,” IST-2002-507932. http://www.ecrypt.eu.org/stream, [2017-04-13].

[6] C. Dobrauning, M. Eichlseder and F. Mendel,“Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates,”Proc. ASIACRYPT 2015, 2015, pp. 490-509.

[7] T. Peyrin, S. M. Sim, L. Wang,et al., “Cryptanalysis of JAMBU,”Proc. FSE 2015, 2015, pp. 264-281.

[8] M. Salam, H. Bartlett, E. Dawson,et al.,“Investigating Cube Attack on the Authenticated Encryption Stream Cipher ACORN,”Proc ATIS 2016, 2016, pp. 15-26.

[9] V. T. Hoang, T. Krovetz, and P. Rogaway, “AEZ v4.2: Authenticated Encryption by Enciphering,” 2016. http://competitions.cr.yp.to/round3/aezv42.pdf , [2017-04-13].

[10] V. T. Hoang, T. Krovetz, and P. Rogaway, “Robust authenticated-encryption: AEZ and the problem that it solves,”Proc. EUROCRYPT 2015, 2015, pp.15–44.

[11] P. Rogaway, “Authenticated-Encryption with Associated-Data,”Proc. 9th ACM conference on Computer and communications security, 2002,pp. 98-107.

[12] D. R. Simon, “On the power of quantum computation,”SIAM Journal on Computing, vol. 26,no. 5, 1997, pp. 1474–1483.

[13] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,”SIAM Journal on Computing, vol. 26, no. 5, 1997, pp. 1484–1509.

[14] H. Kuwakado and M. Morii, “Quantum distinguisher between the 3-round Feistel cipher and the random permutation,”Proc. International Symposium on Information Theory and its Applications, vol. 41, no. 3, 2010, pp. 2682–2685.

[15] H. Kuwakado and M. Morii, “Security on the quantum-type Even-Mansour cipher,”Proc. International Sympsium Information Theory and its Applications, 2012, pp. 312–316.

[16] I. Damg?rd, J. Funder, J. B. Nielsen,et al.,“Superposition attacks on cryptographic protocols,”Proc. International Conference on InformationTheoretic Security, 2013, pp. 142–161.

[17] M. Kaplan, G. Leurent, A. Leverrier,et al., “Breaking Symmetric Cryptosystems using Quantum Period Finding,”Proc. CRYPTO 2016, 2016, pp.207-237.

[18] PR J. Black, “A block-cipher mode of operation for parallelizable message authentication,”Proc.EUROCRYPT 2002, 2002, pp. 384–397.

[19] M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information,” Cambridge University Press, .New York, NY, USA,2011, pp. 16-20.

[20] T. Fuhr, G. Leurent and V. Suder, “Collision Attacks against CAESAR Candidates Forgery and Key-Recovery against AEZ and Marble,”Proc.ASIACRYPT 2015, 2015, pp. 510-532.