The Oribatida v1.3 Family of Lightweight Authenticated Encryption Schemes

1.1 Permutation-based Modes

Permutation-based modes have been established for various applications of symmetric-key cryptography during the previous decade. Keyless modes have been standardized as the hash function SHA-3 and its derivative SHAKE for the extendable-output functions [36]. Keyed modes are used for authentication [51] or encryption [13]. Moreover, permutation-based schemes have found widespread adoption for authenticated encryption, as the CAESAR co-selection Ascon [34], or many more candidates have shown, e.g., PRIMATES [6], NORX [9], Ketje [19], or Keyak [20].

The sponge [17] and duplex [15] modes transform an internal n-bit state iteratively with a public permutation. Both modes absorb an input stream block-wise to generate a pseudo-random output stream. While sponges separate the input (absorption) and output (squeezing) phases, the duplex mode generates the i-th output block directly after the i-th input block has been absorbed. In both modes, an n-bit permutation absorbs the data in r-bit chunks, where the outer part of the state r < n is called the rate. The hidden inner part of the state of c = n − r bits is called the capacity, where r and c are a trade-off between performance and security.

Keyed Sponge Variants were introduced by Bertoni et al. [18] and can be categorized into inner-keyed, outer-keyed, and full-keyed variants (cf. [48]); recently, Dobraunig and Mennink added the suffix-keyed sponge [35]. The inner-keyed sponge [28] initializes the inner part with the key, (0 ‖ K), whereas the outer-keyed sponge [18] (so-dubbed by [8]) concatenates key and message K ‖ M for the output. The full-keyed sponge [16] employs the full state in the absorption phase; the suffix-keyed sponge uses a keyed function only at the end.

Permutation-based modes are analyzed mostly in the ideal-permutation model. For authenticated encryption, an adversary A shall distinguish between two worlds consisting of two oracles: each world has (1) a construction oracle that A can ask encryption and verification queries to and (2) a primitive oracle that provides access to the internal permutation. The former oracle represents on-line queries, whereas the latter represents off-line queries. A can ask q_e encryption queries, q_v verification queries, and q_p construction queries; σ usually denotes the number of blocks over all construction queries.

Sponge Modes for Authenticated Encryption started with the Duplex construction and the AE scheme SpongeWrap [15] and MonkeyDuplex [16], and led to a considerable corpus of analysis, e.g., [8, 32, 37, 49, 52]. Early, Bertoni et al. [14] showed that the sponge is indifferentiable from a random oracle [47] for up to O(2^c/2) calls to the permutation. Their follow-up work [18] improved the bounds for the unkeyed sponge to O(qpσ2c+qc2k) if σ ≪ 2^c/2. For SpongeWrap, Bertoni et al. [15] had shown a privacy bound of O(q2k+σ22c) and an authenticity bound of O(q2k+σ22c+q2τ) .

Jovanovic et al. [41] improved the asymptotic authenticity bound, although under the limitation of at most σ ≪ 2^c/2 decryption queries. Summarizing many previous results, Mennink [48] showed that keyed sponges achieve PRF security of around O(qc2+qcqp2c)+AdvΠKP . He coined the final term the key-prediction security, e.g., O(qp2k) for full-keyed sponges and k < n. The recent duplex-based AE scheme Beetle [25] added a transform to the output so that the plaintext input that is added to the inner part and to the ciphertext output block differ. As a result, Beetle offered a bound of O(rqp+rσ2c+qv+qp2r+σ2+qp22n) . Table 1 summarizes some of the most noteworthy results in the past. Improvements to those general bounds appear hard, which motivates the search for novel constructions.

Correct Authenticated Decryption requires the entire plaintext to be buffered until the tag has been verified. On certain architectures, this requirement can exceed the available storage and induce unacceptable latency. Andreeva et al. [7] introduced notions for privacy and integrity under the release of unverified plaintext material. Security guarantees such as Int-RUP represent valuable additional levels of robustness.

1.2 Research Gap

While Beetle improved the bound for nonce-based authenticated encryption, this bound does not hold in the Int-RUP setting: as we will outline, there exists an attack with an advantage of O(qpqv2c) . The naturally arising question is whether one can achieve higher Int-RUP security. This is motivated by a practical demand: while the primary advantage of sponges is simplicity, they are also useful for lightweight applications in resource-constrained environments. In such contexts, buffering multi-block decryption outputs is likely infeasible, which renders Int-RUP security advantageous. For example, the ongoing NIST lightweight competition [53] requests 112-bit integrity security for AE schemes and support of at least 2⁵⁰ − 1 encrypted bytes of data. Inserting them into Mennink’s bound [48] of qc2+qcqp2c , the NIST requirements would imply permutation sizes of at least 172 bits plus a plausible rate. A higher Int-RUP security could lead to smaller permutations, reducing area, and energy consumption simultaneously.

1.3 Contribution

This work contains three contributions: First, it answers the question above in the affirmative by showing a sponge with dynamic s-bit masks that achieves nAE security of O(qp2k+qd2τ+qpσ2c+s+σ22n) . Replacing the terms by the NIST requirements of k ≥ 128, τ ≥ 64, q_p ≤ 2¹¹² and σ ≥ 2⁵⁰, a trade-off could use c + s ≥ 162, or better c + s ≥ 192 bits to be secure for up to σ ∈ O(2⁶⁴) blocks and q_p ≤ 2¹²⁸ primitive queries. Thus, the rate could be reduced considerably compared to the bound from [48]. We prove that the Int-RUP advantage is at most O(qd2/2c) , i.e., depends solely on the number of on-line queries, contrasting the bound of O(q_dq_p/2^c) for the generic duplex and previous constructions. The difference may seem minor; though, eliminating the dependency of off-line (i.e., primitive) queries is a valuable gain. We propose a novel permutation-based AE scheme Oribatida that applies dynamic masks to the outputs and provides the NIST security bounds with permutation sizes of only 192 bits. As our second contribution, we show that the bound provided by our proposal is tight with an attack that matches the proved bound. Moreover, we show that it applies also to other duplex-based designs in general if masks would be added.

1.4 Outline

After a brief recall of the necessary preliminaries, Section 3 motivates our proposal by showing Int-RUP attacks on the duplex mode and other existing schemes. Section 4 describes Oribatida in general. We close the parenthesis of Int-RUP attacks on Oribatida and other duplex-based modes when in Section 5. We analyze the security on Oribatida for the standard nonce-based AE setting in Section 6 and in the Int-RUP setting in Section 7. Next, Section 8 compares it with those second-round NIST lightweight candidates that claim Int-RUP security. Section 9 discusses the slight update from [21] and the associated improvement. Subsequently, Section 10 specifies an instance with a Simon-based permutation, whose security is discussed in Section 11 from previous works. Section 12 reports on the result of a hardware implementation of Oribatida before Section 13 concludes this work.

2.1 General Notations

We use uppercase letters (e.g., X, Y) for functions and variables, lowercase letters (e.g., x, y) for indices and lengths, as well as calligraphic uppercase letters (e.g., 𝒳, 𝒴) for sets and spaces. We write 𝔽₂ for the field of characteristic 2 and 𝔽2n={0,1}n for the set of vectors over 𝔽₂, i.e., strings of n bits. |X| denotes the number of bits of X. Given X∈𝔽2n , we write X[i] for the i-th bit of X, and define the bit order by X = (X[n − 1] ‖ . . . ‖ X[1] ‖ X[0]). For t ≤ n, we use msb_t(X) = (X[n − 1]. . . X[n − t]) to return the t rightmost (or most significant when interpreting X as integer) and lsb_t(X) = (X[t − 1] . . . X[1]X[0]) to return the t leftmost (or least significant when interpreting X as integer) bits of X. We write ∅ for the empty set and ε for the empty string.

We denote by X[x..y] the range of X[x], . . . , X[y] for non-zero integers x and y. Given binary strings X and Y, we denote their concatenation by X ‖ Y and their bitwise XOR by X ⊕ Y when |X| = |Y|. For positive integers x and y and bit strings of different lengths X∈𝔽2x and Y∈𝔽2y with x ≥ y, we define X ⊕_y Y =^def X ⊕ (0^x−y ‖ Y).

We write X ↞ 𝒳 to indicate that X is chosen uniformly at random and independent from other variables from a set 𝒳. We consider Func(𝒳, 𝒴) to be the set of all mappings F : 𝒳 → 𝒴, and Perm(𝒳) to be the set of all permutations over 𝒳. Given an event E, we denote the probability of E by Pr[E]. We denote the invalid symbol by ⊥. Moreover, we denote by (n)k=def∏i=0k-1(n-i) the falling factorial.

For X∈𝔽2* , we denote by (X1,X2,…,Xx)←nX the splitting of X into n-bit strings X₁, ..., X_x−1, and |X_x| ≤ n, in form of X₁ ‖ . . . ‖ X_x = X. For Y∈𝔽2x , we write (X1,X2,…,Xm)←x1,x2,…,xmY for the splitting of Y into X_l = Y[x−1..x−x_l], X₂ = Y[x−x₁−1..x−x₁−x₂],…, X_m = Y[x_m−1..0], where x = x₁ + x₂ + …+x_m holds. For a given set 𝒳 and non-negative integer x, we write 𝒳^≤x for the union set ∪i=0x𝒳i . For a natural x < 2ⁿ, we write 〈x〉_n for its conversion to an n-bit binary string with the most significant bit left, e.g., 〈135〉₈ = (10000111). We omit n if clear from the context.

2.2 Nonce-based Authenticated Encryption

Let 𝒦 be a set of keys, 𝒩 be a set of nonces, 𝒜 a set of associated data, ℳ a set of messages, 𝒞 a set of ciphertexts, and 𝒯 a set of authentication tags. A nonce N ∈ 𝒩 is an input that must be unique for each authenticated encryption query.

A nonce-based AE scheme (with associated data) Π = (ℰ, 𝒟) is a tuple of deterministic encryption algorithm ℰ : 𝒦 × 𝒩 × 𝒜 × ℳ → 𝒞 × 𝒯 and deterministic decryption algorithm 𝒟 : 𝒦 × 𝒩 × 𝒜 × 𝒞 × 𝒯 → ℳ ∪ {⊥} with associated key space 𝒦. The encryption algorithm ℰ takes a tuple (K, N, A, M) and outputs (C, T), where C is a ciphertext and T an authentication tag. We assume that |C| = |M| holds for all inputs (K, N, A, M) and their corresponding ciphertexts. The associated data is authenticated, but not encrypted. The decryption function 𝒟 takes a tuple (K, N, A, C, T) and outputs either the unique plaintext M for which ℰ_K (N, A, M) = (C, T) holds, or outputs ⊥ if the input is invalid. We introduce ℰKN,A(M) as short form of ℰ_K (N, A, M) and 𝒟KN,A(C,T) for 𝒟_K (N, A, C, T), respectively. We assume that AE schemes are correct, i.e., for all (K, N, A, M) ∈ 𝒦 × 𝒩 × 𝒜 × ℳ, it holds that 𝒟KN,A(ℰKN,A(M))=M .

The ideal AE scheme provides two oracles $ : 𝒩 × 𝒜 × ℳ → 𝒞 × 𝒯 and ⊥ : 𝒩 × 𝒜 × 𝒞 × 𝒯 → ℳ ∪ {⊥} that offer access to encryption and verification. We overload the ⊥ notation to mean the oracle and the symbol of invalid decryption. Given (N, A, M), the ideal encryption oracle outputs ciphertext-tag tuples (C, T) that are random bits of the expected length. The ideal decryption oracle ensures correctness, i.e., given an input (N, A, C, T) where (C, T) had been the output to a previous encryption query (N, A, M), the decryption oracle outputs the corresponding message M. Otherwise, the decryption always returns the invalid symbol ⊥ for every new decryption query that had not been the answer to an earlier encryption query.

Since this work studies schemes based on public permutations, we employ the usual security notions in the ideal-permutation model. So, the adversary always has an additional oracle π^± that provides access to the public permutation π in forward and backward direction. We write Π[π] and ℰ[π], 𝒟[π], etc. to indicate that an authenticated-encryption scheme Π and its algorithms are based on a primitive π ↞ Perm(ℬ), where ℬ = {0, 1}ⁿ is some block space. Note that in the analysis, the permutation is chosen uniformly at random from the set of all permutations over ℬ. Though, the model is an adaption of the ideal-cipher model [60], and not of the random-oracle model [12]. We write Δ_A(𝒪¹; 𝒪²) for the advantage of A to distinguish between 𝒪¹ and 𝒪².

2.3 H-coefficient Technique

We will need a proof method in the later parts, where we opt for Patarin’s well-suited H-coefficient technique in the variant by Chen and Steinberger [30, 54]. The results of the interaction of an adversary A with its oracles are collected in a transcript τ. The oracles can sample randomness before the interaction (often a key or an ideal primitive that is sampled beforehand), and are then deterministic throughout the experiment [30]. The challenge of A is to distinguish the real world 𝒪_real from the ideal world 𝒪_ideal. We denote by Θ_real and Θ_ideal random variables that represent the distribution of transcripts in the real and the ideal world, respectively. In general, a transcript τ is called attainable if the probability to obtain τ in the ideal world – i.e. over Θ_ideal – is non-zero. The Fundamental Lemma of the H-coefficients technique, the proof to which is given in [30, 54], states that we can partition the set of all attainable transcripts into two disjoint sets GoodT and BadT.

Note that in all our analyses, we consider information-theoretic distinguishers A, where we assume idealized primitives. Thus, their resources are bounded only in terms of their maximal numbers of queries and blocks that they can ask to their available oracles. One can derive the computation-theoretic counterparts easily by adding a parameter of the distinguishers’ maximal computational efforts.

3.1 Int-RUP Attack on The Duplex Mode

Let us consider the Sponge-Wrap mode [15].

1. The adversary A asks q_d decryption queries (N, A¹, C), (N, A², C), . . . , (N, A^q_d, C), and receives M¹, M², . . ., M^q_d. The associated data Aⁱ consist of a single block, the ciphertexts C = (C₁, C₂) are fixed to the same two blocks for each query.

2. Now A can follow the generic idea to complete the attack.

The attack complexity is q_dq_p ≈ O(2^c).

3.2 Int-RUP Attack on Beetle

Beetle [25] is a recent permutation-based light-weight AE scheme. From now onward, we consider the updated variant [26] that fixed the proof and details (such as no double call to the permutation). An overview of the encryption process is provided in Figure 1. The map ρ : {0, 1}^r × {0, 1}^r → {0, 1}^r × {0, 1}^r computes ρ(I1,I2)=def(shuffle(I1)⊕I2,I1⊕I2) for all inputs I₁, I₂ ∈ {0, 1}^r, where shuffle(x) =^def (lsb_r/2 (x) || lsb_r/2 (x) ⊕ msb_r/2 (x)). The results of ρ are ordered as (X_a+i, C_i) ← ρ(Y_a+i, M_i) and (Y_a+i, M_i) ← ρ⁻¹(X_a+i, C_i), respectively.

1. The adversary A asks q_d encryption queries (N¹, A¹, M), (N², A², M), . . . , (N^q_d, A^q_d, M) to the encryption oracle, and receives C¹, C², . . . , C^q_d. Size of M and Aⁱ is one block for each i.

2. Then, A asks q_d decryption queries (N¹, A¹, C^1′), (N², A², C^2′), …,(N^q_d, A^q_d, C^q′_d) to the decryption oracle where Ci'←Y2i⊕shuffle(Y2i) . This ensures that the first r bits of the input to the third permutation always equal zero.

3. Now A can follow the generic idea to complete the attack.

The attack complexity is again q_dq_p ≈ O(2^c).

Figure 1

The Beetle authenticated encryption scheme.

3.3 Int-RUP Attack on SPoC

SPoC (see Figure 2a) is a permutation-based NIST Lightweight candidate [5]. that uses the capacity to derive ciphertext outputs from, while it still absorbs the message in the rate. In SPoC, the adversary cannot fix any part of the state in contrast to SpongeWrap and Beetle– though, there is a similar attack:

1. A asks q_d queries (N, A, C¹), (N, A, C²), . . ., (N, A, C^q_d) to the decryption oracle and receives M¹, M² , . . ., M^q_d. The associated data A and ciphertext Cⁱ consist of a single block for every i. This ensures that the first r bits of the input to the third permutation always equal M¹ ⊕ C¹.

2. Now A can follow the generic idea to complete the attack.

So, the attack needs q_dq_p ∈ O(2^c) to work, as before.

Figure 2

3.4 Int-RUP Attack on A Hybrid of Beetle and SPoC

We can generalize our attacks to hybrid modes of Beetle and SPoC as well. Such a hybrid would use both modes Beetle and SPoC in parallel to process the queries. We illustrate it in Figure 2b. Each message block (say M) is parsed into two sections (say M¹ and M²), where |M¹| = r₁ and |M²| = r₂. M¹ is processed with Beetle to a ciphertext block C¹; M² with SPoC to a ciphertext block C²; The final ciphertext block becomes C ← C¹ ‖ C², and the associated-data blocks and the ciphertext blocks for decryption are treated in a similar manner. Note that the hybrid mode is parameterized by r₁, r₂ and c with the condition c ≥ r₂. The size of rate and capacity of the Beetle part are r₁ and c − r₂; the size of both rate and capacity of the SPoC part is r₂. As a result, the size of rate and capacity of the hybrid mode is r = r₁ + r₂ and c. When r₂ = 0, the hybrid mode translates to the Beetle mode. Similarly, when r₁ = 0, the hybrid mode is equivalent to the SPoC mode.

An Int-RUP attack on such modes could be defined as follows:

1. A asks q_d decryption queries (N, A¹, C), (N, A², C), . . ., (N, A^q_d, C) to the decryption oracle and receives M¹, M², . . . , M^q_d. The ciphertext C and associated data Aⁱ consist of a single block for every i.

2. There exists at least one value of the last r₂ bits of the input to the third permutation which remains same for at least q=qd2r2 queries. Suppose q such queries are (N, A^1′, C), (N, A^2′, C), . . ., (N, A^q′, C).

3. A can detect the previous step as it knows the value of the last r₂ bits of the input to the third permutation because that will be equal to the last r₂ bits of C ⊕ Mⁱ.

4. A retains those q queries and discards the rest.

5. For each of the above queries, A updates the value of the first r₁ bits of the ciphertext to Y₂ ⊕ shuffle(Y₂) and varies the remaining r₂ bits. This ensures that the first r₁ bits of the input to the third permutation always equal zero.

6. In the way mentioned above, A can ask q_d more decryption queries to the decryption oracle. This time, a total of r bits (first r₁ bits and last r₂ bits) of the input to the third permutation are fixed and known to A.

7. Then, A can follow the generic idea to complete the attack.

The attack needs again q_dq_p ∈ O(2^c) as before.

3.5 Discussion

As a takeaway from this section, the unmasked sponge-based AE schemes allow Int-RUP attacks whose advantage can depend linearly on the number of off-line primitive queries. We think that any AE construction which uses linear feedback is vulnerable to such an attack (q_dq_p ∈ O(2^c)) unless it uses more state. The next section defines Oribatida that masks its ciphertexts for higher Int-RUP resistance. After its definition, we will get back to attacks on it and on strengthened versions of the schemes sketched here to show that they can be similarly extended by a ciphertext masking.

4.1 Initialization

Each variant of Oribatida uses a fixed-size nonce N, whose length ν is such that k + ν = n bits. N is concatenated with the key K to initialize the state: N ‖ K: (X₀, Y₀) ← (N ‖ K) ⊕_d 〈d_N〉_d. The domain d_N is XORed to the d least significant bits of the initial state. The first value S₁ results from S₁ ← P(U₀ ‖ V₀); V₁ is stored for masking the first block of ciphertext later.

Figure 3

Authenticated encryption of a-block associated data A and m-block message M with Oribatida.

4.2 Processing Associated Data

After the initialization, the associated data A is split into r-bit blocks and is absorbed in the rate. If its length is not a multiple of r bits, A is padded with a 10^*-padding if |A| mod r ≢ 0 such that its length becomes the next highest multiple of r bits. If the associated data is empty, it is padded to one full block 10^r−1. In this case, we denote the length of the padded associated data A in blocks also as a = 1. The padded A is split into r-bit blocks (A₁, . . ., A_a). Given (Ui,Vi)←r,cSi is XORed to the rate of the state: X_i ← U_i ⊕ A_i, for 1 ≤ i < a. For all non-final blocks of A, the capacity of the permutation output, V_i, is simply forwarded to that of the subsequent input to the permutation P: Y_i ← V_i. The state is updated with P afterwards, for all 1 < i < a (that is, except the final a-th block of A): S_{i + 1} ← P(X_i ‖ Y_i). When the final block A_a is processed, a domain d_A is XORed to the least significant byte of the capacity.

4.3 Encryption

After A has been processed, the message M is encrypted. Similarly as for the associated data, if its length is not a multiple of r bits, M is padded with a 10^*-padding such that its length after padding becomes the next highest multiple of r bits. An empty message M = ε will not be padded.

After M is split into r-bit blocks (M₁, . . ., M_m) (after padding if necessary), the blocks M_i are processed one after the other. Given the state value (Ua+i,Va+i)←r,cSa+i , the current block M_i is XORed to the rate U_a+i: X_a+i ← M_i ⊕ U_{a + i}. The capacity is simply forwarded: Y_{a + i} ← V_{a + i}. Then, (X_{a + i} ‖ Y_{a + i}) is used as input to a call to P to derive the next state value S_{a + i +1} ← P(X_{a + i} ‖ Y_{a + i}).

The ciphertext blocks C_i are computed from a sum of the current rate, the current plaintext block, and a (partial) earlier mask value from the capacity. The first ciphertext block is computed from C₁ ← X_{a + i}⊕_s lsb_s(V₁). If C₁ is the final ciphertext block, it is computed as C₁ ← msb_ℓE(X_{a + i} ⊕_s lsb_s(V₁)), where ℓ_E denotes the length of M before padding. Non-final ciphertext blocks C_i, 1 < i < m are computed from C_i ← X_{a + i} ⊕s lsb_s(V_{a + i−1}), for 1 < i < m. If m > 1, the final ciphertext block results from C_m ← msb_ℓEmod r(X_{a + m}⊕_s lsb_s(V_{a + m−1})). For the final message block, a domain d_E is XORed to the least significant byte of the capacity: Y_{a + m} ← V_{a + m}⊕_d 〈d_E〉_d. Similar as for A, d_E uses three pairwise distinct domains depending on whether M was empty, non-empty and required no padding, or non-empty and has been padded. P is called another time to derive S_{a + m +1} ← P(X_{a + m} ‖ Y_{a + m}). Its rate is XORed with the most significant τ bits of the key V_{a + m}, and – truncated to τ bits if necessary – is released as the authentication tag: T ← msb_τ(S_{a + m +1}) ⊕_s lsb_s(V_{a + m}). Note that, for s = τ as for our instantiations, the tag is masked as the ciphertext output blocks, which unifies this process.

4.4 Decryption

The decryption takes a tuple (K, N, A, C, T). The initialization with K and N as well as the processing of the associated data A is performed in the same manner as for encryption. If |C| mod r ≠ 0, the decryption pads C with a 10^*-padding to the next multiple of r bits. In all cases, it splits C into r-bit blocks (C₁, . . ., C_m−1) plus a final block C_m. If m > 1, the plaintext block is computed as X_{a + i} ← C_i ⊕_s lsb_s(V) and M_i ← (U_{a + i} ⊕ X_{a +i}), where V = V₁ for i = 1, and V = V_a+i−1 otherwise. The capacity is simply forwarded to the next call of the permutation: Y_{a + i} ← V_{a + i}. The subsequent state is then (U_a+i+1 ‖ V_a+i+1) ← S_a+i+1 ← P(X_a+i ‖ Y_a+i).

The final plaintext block is computed from the padded ciphertext block C_m as X_a+m ← C_m ⊕s lsb_s(V) and M_m ← lsb_x(U_a+m ⊕ X_a+m), where x ← ℓ_E mod r. For the final block, the domain d_E is XORed to the least significant byte of the capacity: Y_a+m ← V_a+m⊕_d 〈d_E〉_d. The would-be tag T′ is derived by computing (T′ ‖ Z) ← P(X_a+m ‖ Y_a+m) ⊕_s lsb_s(V_a+m), and using only its most significant τ bits: T′ ← msb_τ(T′ ‖ Z) as for the encryption If T = T′, the ciphertext is considered valid, and M = (M₁ ‖ . . . ‖ M_m) is released as plaintext. Otherwise, the ciphertext is deemed invalid, and ⊥ is returned.

4.5 Domain Separation

For domain separation, Oribatida defines constants d_N, d_A and d_E. The domains are XORed with the least significant byte of the state at three stages. Domains are encoded as d-bit strings, where d = 4 bits suffice in practice. The value depends on the presence of A and M and whether their final blocks are absent, partial, or integral to prevent trivial collisions of inputs to P among blocks of A and M. The constants are determined by four bits (t₃, t₂, t₁, t₀) that reflect inputs in the hardware API, similar to, e.g., [25]:

1. EOI: t₃ is the end-of-input control bit. This bit is set to 1 if the current data block is the final block of the input. Note that if the associated data is empty, then the created 10^r−1-block is never treated as the final block of the input.

2. EOT: t₂ is the end-of-type control bit. This bit is set to 1 if the current data block is the final block of the same type, i.e., it is the last block of the nonce/associated data/message. Note that if both the associated data and the message are empty, then neither the nonce nor the created 10^r−1-block of the associated data is considered as the final block of its type.

3. Partial: t₁ is the partial-control bit. This bit is set to 1 if the size of the current block is less than the block size. Note that if the associated data is empty and the message is non-empty, then the created 10^r−1-block is treated as a partial block.

4. Type: t₀ is the type-control bit, identifying the type of the current block. For the nonce and the final message block, t₀ = 1. If the associated data is empty and the message is non-empty, then t₀ = 1 for the created 10^r−1-block of the associated data. For all other cases, t₀ = 0.

While processing a data block, the domains are set as the integer representation of t₃ ‖ t₂ ‖ t₁ ‖ t₀. For example, processing the nonce (which is always a complete r-bit block) with empty associated data and non-empty message yields d_N = (t₃t₂t₁t₀) = (0101)₂ = 5. Details are provided in Algorithm 2; ℓ_A denotes the length of A and ℓ_E that of M in bits before padding. An overview is given in Table 3.

5.1 The Generic Int-RUP Attack on Oribatida (Masked Duplex)

Here, we consider an attack on Oribatida that shows that our Int-RUP bound of O(qd2/2c) will be tight, so the attack will be successful for qd2≈O(2c) :

1. A asks q_d decryption queries (Nⁱ, Aⁱ, Cⁱ, Tⁱ), where Nⁱ and Cⁱ is static for all queries. We assume that the associated data Aⁱ are pairwise distinct and consist of a single block for all queries. A obtains Mⁱ from the encryption oracle, for 1 ≤ i ≤ q_d. The rate X2i←C1i⊕slsbs(V1i) is constant for all queries.

2. For q_d ≈ O(2^c/2), A can expect a collision in the capacity of the input: V2i←V2j for some distinct i ≠ j, i, j ∈ [1.. q_d]. Then, this collision leads to a full-state collision that can be detected when M1i=M1j .

3. A asks encryption queries (N, Aⁱ, Mⁱ) and obtains (Cⁱ, T) for some tag T.

4. (N, A^j, Cⁱ, T) is a valid forgery and yields M^j.

5.2 Int-RUP Attack on The Masked Beetle

1. The adversary A asks q_d encryption queries (N¹, A¹, M), (N², A², M), . . . , (N^q_d, A^q_d, M) to the encryption oracle, and receives C¹, C², . . ., C^q_d. The associated data Aⁱ consist of a single block for each i; the message M contains ⌈cr⌉ blocks.

2. A asks q_d − 1 decryption queries, one for each encryption query except the first encryption query, to the decryption oracle. The decryption query of the i-th encryption query is (Nⁱ, Aⁱ, C^i′), where Ci'=Y21⊕Y2i⊕shuffle(Y21)⊕shuffle(Y2i) . A can calculate the r.h.s. as shuffle(Y21)⊕shuffle(Y2i)=C1⊕Ci , and Y21⊕Y2i directly from shuffle(Y21)⊕shuffle(Y2i) with the definition of shuffle. So, the first r bits of the input to the third permutation call always equal those of the first encryption query.

3. Afterwards, A repeats Step 2 to 6 from Section 5.1 to complete the attack.

The attack is successful for qd2≈O(2c) . However, the attack strategy differs for SPoC.

5.3 Int-RUP Attack on The Masked SPoC

Here, A has to perform the attack in two stages.

1. First, A asks q_d decryption queries (N, A¹, C), (N, A², C), . . . , (N, A^q_d, C) to the decryption oracle, and receives M¹, M², . . ., M^q_d. The associated data Aⁱ consists of a single block for each i; the ciphertext C consists of two blocks.

2. When q_d ≈ 𝒪(2r), A expects a collision in the first r bits of the input to the third permutation call. A can detect this collision by looking at the first message block because it will be equal only for the two colliding queries.

3. Suppose the associated data of the two colliding queries are Aⁱ and A^j.

4. A makes q₁ queries (N, Aⁱ, C¹), (N, Aⁱ, C²), . . . , (N, Aⁱ, C^q₁), and q₂ queries (N, A^j, C¹), (N, A^j, C²), . . ., (N, A^j, C^q₂) to the decryption oracle.

5. When q₁ · q₂ ≈ 𝒪(2^r), A expects a full state collision at the input to the third permutation, between one query with associated data Aⁱ and another query with associated data A^j.

6. Suppose the two ciphertexts corresponding to the two colliding queries are C^p and C^q, and the corresponding messages are M^p and M^q.

7. A identifies those pairs of queries (N, Aⁱ, C^x), (N, A^j, C^y), 1 ≤ x ≤ q₁ and 1 ≤ y ≤ q₂, for which the sum of the second message blocks equals that of the first message blocks. For each such pair, A updates C^x and C^y by appending ⌈cr⌉-1 ciphertext blocks to each s.t., C2x=C2y,…,C⌈cr⌉x=C⌈cr⌉y , and makes decryption queries with the updated ciphertexts. For k < 2, Mkp will equal Mkq .

8. Next, A asks (N, Aⁱ, M^p) to the encryption oracle; suppose, the tag is T.

9. Then, A successfully forges with the query (N, A^j, C^q, T).

Again, the probability for forgeries becomes non-negligible when qd2≈O(2c) .