The key steps for proving OCB secure are establishing the security of the \(\Theta \)CB construction when based on an idealized TBC, and then showing that our way of creating a tweakable blockcipher, the \(\text {Tw} \)construction, works. Both steps are in the informationtheoretic setting. Passing to the complexitytheoretic setting for the final result is then standard.
Security of the TBCBased Scheme
The following lemma establishes the privsecurity and authsecurity of \(\Theta \)CB when based on an ideal TBC.
Lemma 2
Fix \(n=128\) and \(\tau \in [0..n]\) and \({\smash {\widetilde{\mathbb {E}}}}={\smash {\widetilde{\mathbb {E}}}}^{\mathcal{T}_{\Theta \text {{CB}} },\;n}\). Let \(\Pi ={\Theta \text {{CB}} } [{\smash {\widetilde{\mathbb {E}}}},\tau ]\). Then,

\({\mathbf \mathbf{Adv}}^{\mathrm {priv}}_{\Pi }(\mathscr {A}_{\mathrm {priv}}) =0\) for any adversary \(\mathscr {A}_{\mathrm {priv}}\), while

\( {\mathbf \mathbf{Adv}}^{\mathrm {auth}}_{\Pi }(\mathscr {A}_{\mathrm {auth}}) \le 2^{n\tau }/(2^n1) \le 1.1/ 2^\tau \) for any adversary \(\mathscr {A}_{\mathrm {auth}}\).
Note that in this idealized setting, privacy and authenticity do not degrade with message lengths, AD lengths, or the number of queries: privacy is perfect, while the chance of forging is about \(1/2^\tau \).
Proof
Consulting Fig. 4 will make the proof more understandable. Keep in mind that, in the idealized setting we consider, \({\smash {\widetilde{E}}}_K^{N{\,}i}\), \({\smash {\widetilde{E}}}_K^{N{\,}i{\,}\$}\), \({\smash {\widetilde{E}}}_K^{N{\,}i{\,}*}\), \({\smash {\widetilde{E}}}_K^{N{\,}i{\,}*{\,}\$}\), \({\smash {\widetilde{E}}}_K^{{\,}i}\) and \({\smash {\widetilde{E}}}_K^{{\,}i{\,}*}\) are random permutations on n bits (for all permissible N and i). To emphasize this, we write \(\pi \) in place of \({\smash {\widetilde{E}}}_K\), so \(\pi ^{N{\,}i}\), \(\pi ^{N{\,}i{\,}*}\), \(\pi ^{N{\,}i{\,}\$}\), \(\pi ^{N{\,}i{\,}*{\,}\$}\), \(\pi ^{{\,}i}\) and \(\pi ^{{\,}i{\,}*}\). Any two such permutations are independent of one another as long as their superscripts are distinct. We must argue privacy and authenticity.
Privacy. During the adversary’s attack it asks queries \((N^1,A^1,M^1),\ldots ,(N^q,A^q,M^q)\) and gets responses \({\mathscr {C}}^1,\ldots , {\mathscr {C}}^q\) where \({\mathscr {C}}^j=C^j\,\Vert \,T^j\) and \(C^j = C^j_1\cdots C^j_{m^j}\) or \(C^j = C^j_1\cdots C^j_{m^j}C^j_*\). In general, in this proof we will use a superscript of j on a variables to indicate the value of that variable following the adversary’s jth query. We may do this with any variable appearing in Fig. 4.
Since the \(N^j\)values must be distinct, each permutation of the form \(\pi ^{N^j\cdots }\) is used at most once. We are thus applying independent random permutations to a single point each, so all of these outputs are uniformly random and independent. The bulk of what is returned to the adversary, all the \(C^j_i\) values, are such \(\pi ^{N^j{\,}i}\) outputs. But the \(C_*^j\) and \(T^j\) values are not just permutation outputs but are, instead, \(\pi ^{N^j{\,}m^j{\,}*}\) or \(\pi ^{N^j{\,}m^j{\,}\$}\) or \(\pi ^{N^j{\,}m^j{\,}*{\,}\$}\) outputs that are xored with \(M^j_*\,0^*\) and truncated to \(M^j_*\) bits, or, alternatively, are xored with \(\mathrm {Auth}^j\) and then truncated to \(\tau \) bits. Either way, the result remains uniform and independent of all other outputs, as \(\mathrm {Auth}^j\), \(M^j_*\), and \(\tau \) are independent of \(\pi ^{N^j\cdots }\) outputs. We conclude that each result from the adversary’s \(j^\mathrm {th}\) query is a uniformly random string \({\mathscr {C}}^j\) of length \(M^j+\tau \) that is independent of all other query responses. It follows that the adversary’s privacy advantage is zero.
Authenticity. Before we launch into proving authenticity, consider the following simple game, which we call game G. Suppose that you know that an nbit string \(\mathrm {Tag}\) is not some particular value \(\mathrm {Tag}_0\). All of the \(2^n1\) other possibilities are equally likely. Then, your chance of correctly predicting the \(\tau \)bit prefix of \(\mathrm {Tag}\) is at most \(2^{n\tau }/ (2^n1)\). That is because the best strategy is to guess any \(\tau \)bit string other than the \(\tau \)bit prefix of \(\mathrm {Tag}_0\). The probability of being right under this strategy is \(2^{n\tau }/ (2^n1)\). We will repeatedly use this fact in the sequel.
Now suppose that the adversary asks a sequence of queries \((N^1,A^1,M^1),\ldots , (N^q,A^q,M^q)\) and then makes its forgery attempt \((N,A,{\mathscr {C}})\), where \({\mathscr {C}}= C\,\Vert \,T\), \(C=C_1\cdots C_c\) or \(C=C_1\cdots C_c C_*\). We need to bound the probability that \((N,A,{\mathscr {C}})\) is a successful forgery.
We begin by considering the case where the forgery attempt \((N,A,{\mathscr {C}})\) employs a nonce N that is not among \(\{N^1,\ldots ,N^q\}\). Then to forge the adversary needs to find the correct value of \(T=(\pi ^{N\cdots }({\mathrm {Checksum}})\oplus \mathrm {Auth})[1..\tau ]\) but has seen nothing that depends on \(\pi ^{N\cdots }\). Having no relevant information to use, the adversary’s chance of success is clearly \(2^{\tau }\), which is less than \(2^{n\tau }/(2^n1)\).
Given the above, we can assume that the forgery attempt \((N,A,{\mathscr {C}})\) uses a nonce \(N=N^j\) that coincides with a nonce from some prior query. All the other queries had to employ different nonces and thereby generated information theoretically unrelated to the adversary’s task at hand. We can therefore disregard these other encryption queries and assess the maximal forging probability for a new and simpler game: the adversary asks a single encryption query \((N,A',M')\), getting a response \({\mathscr {C}}'=C'\,\Vert \,T'\), and then it tries to forge, with the same nonce, outputting a triple \((N,A,{\mathscr {C}})\). We must bound the probability that such a forgery is valid. We write \(A'=A'_1\cdots A'_{a'}\) or \(A'=A'_1\cdots A'_{a'} \,A'_*\), \(M'=M'_1\cdots M'_{m'}\) or \(M'=M'_1\cdots M'_{m'}\, M'_*\), \(A =A_1\cdots A_{a}\) or \(A=A_1\cdots A_{a} \,A_*\), \({\mathscr {C}}= C\,\Vert \,T\), \(C = C_1\cdots C_c\) or \(C = C_1\cdots C_c\, C_*\). We proceed by case analysis, relating the form of the forgery attempt \((N,A,{\mathscr {C}})\) to the encryption query \((N,A',M')\). We say that a string is full if it has a multiple of n bits, and partial otherwise.
Case 1: \(A\ne A'\), \(A\ne \varepsilon \ne A'\). We have several subcases to consider. Case 1a. If \(A'\) is full and A is partial, then \(\mathrm {Auth}'\,\Vert \,\mathrm {Auth}\) will be \(U_{2n}\) distributed, the uniform distribution on 2n bits, and the adversary will only be able to forge with probability \(2^{\tau }\). The uniformity of \(\mathrm {Auth}'\,\Vert \,\mathrm {Auth}\) is because \(\mathrm {Auth}'\) will depend on a \(\pi ^a\) output but no \(\pi ^{a{\,}*}\) output, while \(\mathrm {Auth}\) will depend on a \(\pi ^{a{\,}*}\) output. The case when \(A'\) is partial and \(A'\) is full is similar. Case 1b. If \(A'\) and A are full and \(a\ne a'\), then \(\mathrm {Auth}'\,\Vert \,\mathrm {Auth}\) will again be \(U_{2n}\) distributed, whence the forging probability will be \(2^{\tau }\). The uniformity of \(\mathrm {Auth}' \,\Vert \,\mathrm {Auth}\) is because each includes a \(\pi ^1\) output in the xor but only one xors in a \(\pi ^{\max (a,a')}\) output. The case of \(A'\) and A being partial but \(a\ne a'\) is analogous. Case 1c. Suppose \(A'=A'_1\ldots A'_a\) and \(A =A_1 \ldots A_a\) are full, equal in length, but distinct; say \(A'_j\ne A_j\) for some j. Then, even if the adversary were given not only \({\mathscr {C}}'\) but also \(\mathrm {Final}\), all \(\pi ^i(A'_i)\) values, and all \(\pi ^i(A_i)\) values except for \(i=j\), still the value of \(\mathrm {Auth}= \oplus _i\, \pi ^i(A_i) = Z \oplus \pi ^j(A_j)\), and therefore \(\mathrm {Tag}\), would be uniform in a space of \(2^n1\) possible values. We are now in the setting of game G, and the adversary’s chance to predict T, the first \(\tau \) bits of \(\mathrm {Tag}\), is at most \(2^{n\tau }/(2^n1)\). Case 1d. The last case is when \(A'=A'_1\ldots A'_a A'_*\) and \(A =A_1 \ldots A_a A_*\) are partial, equal in length, but distinct. If \(A'_j\ne A_j\) for some j, then proceed as with Case 1c. If \(A'_*\ne A_*\), then \(A'_*10^*\ne A_*10^*\) and proceed as with Case 1c, but with \(\pi ^{a{\,}*}(A_*10^*)\) the unknown value.
Case 2: \(A\ne A'\), \(A=\varepsilon \) or \(A'=\varepsilon \). If \(A'=\varepsilon \ne A\), then \(\mathrm {Auth}'=0^n\), while \(\mathrm {Auth}\) is \(U_n\) distributed and independent of \(\mathrm {Final}\), so \(\mathrm {Tag}\) is uniform and independent of all values the adversary has observed, whence its ability to predict its \(\tau \)bit prefix is at most \(2^{\tau }\). If \(A'\ne \varepsilon =A\) then \(\mathrm {Auth}=0^n\) and the adversary must output the \(\tau \)bit prefix of \(\mathrm {Final}\). It has received no information on any \(\pi ^{N{\,}i {\,}\$}\) or \(\pi ^{N{\,}i {\,}* {\,}\$}\) from its encryption query, as the only such output was masked with \(\mathrm {Auth}'\), formed using a \(\pi ^{a'}\) or \(\pi ^{a'{\,}*}\) output. So the forging probability is again \(2^{\tau }\).
Case 3: \(A=A'\); \(M'\) partial and C full, or the other way around. For this and all remaining cases, we imagine providing the adversary with \(\mathrm {Auth}'=\mathrm {Auth}\). So the adversary must predict the first \(\tau \) bits of \(\mathrm {Final}\). But \(\mathrm {Final}\) is the output of a random permutation \(\pi ^{N{\,}c {\,}\$}\) that has not yet been applied to any point. With no relevant information for carrying out this task, its chance to forge is at most \(2^{\tau }\). For the case with \(M'\) full and C partial, \(\mathrm {Final}\) is, similarly, an output \(\pi ^{N{\,}c {\,}*{\,}\$}\) where this permutation has not yet been applied to any point.
Case 4: \(A=A'\); \(c\ne m'\); \(M'\) and C both full or both partial. the adversary must predict the first \(\tau \) bits of \(\mathrm {Final}\). But \(\mathrm {Final}\) is the output of a random permutation \(\pi ^{N{\,}c {\,}\$}\) (if \(M'\) and C both full) that has not yet been used at even one point. With no relevant information, the adversary forges with probability at most \(2^{\tau }\). Similarly when \(M'\) and C are both partial.
Case 5: \(A=A'\), \(c=m'\), \(M'\) and C full. For the forgery to be valid we must have \(C'\ne C\) so let j to be the smallest value where \(C'_j\ne C_j\). Assume the adversary is given the value of \(\mathrm {Auth}'=\mathrm {Auth}\), all \(\pi ^{N{\,}i}\) permutations where \(i\ne j\), and all \(\pi ^{\cdots \$}\) permutations. Then the adversary will know \({\mathrm {Checksum}}'\) and all the values but one that xored together make \({\mathrm {Checksum}}\). But it will be missing one addend in the xor, and all \(2^n1\) values other than \(M_j\) are equally likely for it, whence \({\mathrm {Checksum}}\) can assume \(2^n1\) values, each equiprobable, and \(\mathrm {Final}\) can assume \(2^n1\) values, each equiprobable. We are in the setting of game G and the adversary’s chance to forge is at most \(2^{n\tau }/(2^n1)\).
Case 6: \(A=A'\), \(c=m\), \(M'\) and C partial. Because \(C\ne C'\) either there is a smallest j where \(C'_j\ne C_j\) or else \(C'_1\cdots C'_c=C_1\cdots C_c\) but \(C'_*\ne C_*\). For the former case, proceed like Case 5. For the latter case the adversary may be able to compute \({\mathrm {Checksum}}' = M'_1\oplus \cdots M'_c \oplus M'_*10^*\) but also \({\mathrm {Checksum}}= M'_1\oplus \cdots M'_c \oplus M_*10^*\). These two values are necessarily distinct, due to the \(10^*\) padding. Even if the adversary is given both and knows \(\mathrm {Final}'\) the image of \({\mathrm {Checksum}}\) under will be a uniformly random among the \(2^n1\) points that are not \(\mathrm {Final}'\). We are again left in the situation of game G, and the adversary’s probability to forge is at most \(2^{n\tau }/(2^n1)\). This completes the proof.
\(\square \)
StretchthenShift Hash
OCB employs a new hash function, “Init” in Fig. 3, to map the nonce N to the initial offset \(\Delta \). We aimed to construct a hash that would need at most one AES computation no matter what Nvalues are presented, but would usually reuse a previously computed AES output, plus a couple of shifts and xors, if N is one more than it was last time around. Our method applies AES to the top 122 bits of N to create an initial value Ktop, but then modifies Ktop in a simple way using the lower six bits of N, call them Bottom. Specifically, we return the first 128 bits of \(H_\mathrm {Ktop}(\mathrm {Bottom}) = (\mathrm {Ktop}\,\Vert \,(\mathrm {Ktop}\oplus (\mathrm {Ktop}\ll 8))) \ll \mathrm {Bottom}\). There is no deep intuition motivating the formula; it is just the simplest method we found that we could prove to work. We start with the needed definitions.
Definition. Let \(\mathcal {K}\) be a finite set and let \(H{:\;}\mathcal {K}\times \mathcal{X}\rightarrow {\{0,1\}}^n\) be a function. We say that H is strongly xoruniversal if for all distinct \(x,x'\in \mathcal{X}\) we have that \(H_K(x) \oplus H_K(x')\) is uniformly distributed in \({\{0,1\}}^{n}\) and, also, \(H_K(x)\) is uniformly distributed in \({\{0,1\}}^n\) for all \(x\in \mathcal{X}\). The first requirement is the usual definition for H being xoruniversal and the second we call universal1.
The technique. We aim to construct strongly xoruniversal hashfunctions \(H{:\;}\mathcal {K}\times \mathcal{X}\rightarrow {\{0,1\}}^n\) where \(\mathcal {K}={\{0,1\}}^{128}\), \(\mathcal{X}=[0{..}\mathrm {domSize}1]\), and \(n=128\). We want \(\mathrm {domSize}\) to be at least some modestsize number, say \(\mathrm {domSize}\ge 64\), and intend that computing \(H_K(x)\) be extremely fast. Computation of H should not require large tables, preprocessing of K, or special hardware support.
The method we propose is to stretch the key K into a longer string \(\textit{stretch}(K)\) and then extract its bits \(x+1\) to \(x+128\). Symbolically, \(H_K(x)= (\textit{stretch}(K))[x+1\;{..}\; x+128]\) where \(S[a{..}b]\) denotes bits a through b of S, indexing beginning with 1. Equivalently, \(H_K(x)=(\textit{stretch}(K){\ll }x)[1{..}128]\). We call this a stretchthenshift hash.
How to stretch K? It seems natural to have \(\textit{stretch}(K)\) begin with K, so let us assume that \(\textit{stretch}(K) = K\;\Vert \;s(K)\) for some function s. It is easy to see that \(s(K)\!=\! K\) and \(s(K){\ll }c\) will not work, but \(s(K) = K \oplus (K {\ll }c)\), for some constant c, looks plausible. We now demonstrate that, for wellchosen c, this function does the job.
Analysis. To review, we are considering the hash functions \(H^c_K(x) = (\mathrm {Stretch}{\ll }x)[1{..}128]\) where \(\mathrm {Stretch}=\textit{stretch}(K)=K \;\Vert \;(K\oplus (K{\ll }c))\) and \(c\in [0{..}127]\). We would like to know the maximal value of \(\mathrm {domSize}\) for which \(H_K(x)\) is xoruniversal on the domain \(\mathcal{X}=[0{..}\mathrm {domSize}(c)\!\!1]\). This can be calculated by a computer program, as we now explain. Fix c and consider the \(256 \times 128\) entry matrix \(A=\left( \!\!\begin{array}{c} I\\ J \end{array}\!\! \right) \) where I is the \(128\times 128\) identity matrix and J is the \(128\times 128\)bit matrix for which \(J_{ij}=1\) iff \(j=i\) or \(j= i+c\). Let \(A_i\) denote the \(128\times 128\) submatrix of A that includes only A’s rows i to \(i+127\). Then \(H^c_K(x) = A_{x+1} K\), the product in \({{\smash {{\mathrm {GF}}(2)}}}\) of the matrix \(A_{i+1}\) and the column vector K. Let \(B_{i,j} = A_i + A_j\) be the indicated \(128\times 128\) matrix, the matrix sum over \({{\smash {{\mathrm {GF}}(2)}}}\). We would like to ensure that, for arbitrary \(0\le i<j<\mathrm {domSize}(c)\) and a uniform \(K\in {\{0,1\}}^{128}\) that the 128bit string \(H^c_K(i) + H^c_K(j)\) is uniform—which is to say that \(A_{i+1} K + A_{j+1} K = (A_{i+1} + A_{j+1}) K = B_{i+1,j+1}K \) is uniform. This will be true if and only if \(B_{i,j}\) is invertible in \({{\smash {{\mathrm {GF}}(2)}}}\) for all \(1\le i<j\le \mathrm {domSize}(c)\). Thus \(\mathrm {domSize}(c)\) can be computed as the largest number \(\mathrm {domSize}(j)\) such that \(B_{i,j}\) is full rank, over \({{\smash {{\mathrm {GF}}(2)}}}\), for all \(1\le i<j\le \mathrm {domSize}(j)\). Recalling the universal1 property we also demand that \(A_{i}\) have full rank for all \(1\le i\le \mathrm {domSize}(c)\). Now for any c, the number of matrices \(A_{i,j}\) to consider is at most \(2^{13}\), and finding the rank in \({{\smash {{\mathrm {GF}}(2)}}}\) of that many \(128\times 128\) matrices is not a difficult calculation.
Our results are tabulated in Fig. 9. The most interesting cases are \(H^5\) and \(H^8\), which are strongly xoruniversal on \(\mathcal{X}=[0{..}123]\) and \(\mathcal{X}=[0{..}84]\), respectively. We offer no explanation for why these functions do well and various other \(H^c\) do not. As both \(H^5\) and \(H^8\) work on \([0{..}63]\) we select the latter map for use in OCB and single out the following result:
Lemma 3
Let \(H{:\;}{\{0,1\}}^{128}\times [0{..}63]\rightarrow {\{0,1\}}^{128}\) be defined by \(H_K(x) = (\mathrm {Stretch}{\ll }x)[1{..}128]\) where \(\mathrm {Stretch}= K \;\Vert \;(K\oplus (K{\ll }8))\). Then, H is strongly xoruniversal.
Efficiency. On 64bit computers, assuming \(K \;\Vert \;(K\oplus (K{\ll }8))\) is precomputed and in memory, the value of \(H_K(x)\) can be computed by three memory loads and two multiprecision shifts, requiring fewer than ten cycles on most architectures. If only K is in memory then the first 64 bits of \(K\oplus (K{\ll }8)\) can be computed with three additional assembly instructions.
Instantiating the TBC
We show that \({\smash {\widetilde{E}}}\!=\!\text {Tw} [E,\tau ]\) is a good TBC if E is a good blockcipher. In formalizing this, bidirectional tweaks are those of the form (N, i). Our result is again, for now, in the informationtheoretic setting.
Lemma 4
Fix \(n=128\) and \(\tau \in [0..n]\) and \(E=\mathbb {E}^{n}\). Let \({\smash {\widetilde{E}}}= \text {Tw} [E,\tau ]\) and \(\mathcal{B}= \mathcal{N}\times {\mathbb {N}_1}\). Let \(\mathscr {A}\) be an adversary that asks at most q queries, all with ivalue less than \(2^{120}\). Then \({\mathbf \mathbf{Adv}}^{{{\mathcal{B}}\text{ }\mathrm {prp}}}_{{\widetilde{E}}}(\mathcal{A}) \le 6q^2/2^n\).
Proof
We generalize the adversary’s capabilities in attacking \(\text {Tw} [E,\tau ]\); see Fig. 10 for the construction we will call \(\text {TW} \). There we write \(\pi \) instead \({{\widetilde{E}}}_K\). The adversary, which we still refer to as \(\mathscr {A}\), may now ask queries we will refer to as being of TYPE1, TYPE2, TYPE3a, TYPE3b. In other words, the adversary’s queries may take any of the forms \((1, W,\lambda )\), \((2, W,\mathrm {Top},\mathrm {Bottom},\lambda )\), \((\text{3a },W,\mathrm {Top},\mathrm {Bottom},\lambda )\), or \((\text{3b },Z,\mathrm {Top},\mathrm {Bottom},\lambda )\). We insist that the adversary not ask a query with \(\mathrm {Top}\!=\!0\) (we stop to distinguish field points and the corresponding strings) and we demand that any \(\lambda \in {{\smash {{\mathrm {GF}}(2^n)}}}\) asked in a query is used only for queries of one numeric TYPE (it is fine to use the same \(\lambda \) in queries of TYPE3a and 3b). The adversary may not repeat queries nor ask a query with a trivially known answer (a TYPE3b query following the corresponding TYPE3a query, or the other way around). Working in \({{\smash {{\mathrm {GF}}(2^n)}}}\), we sometimes write xor as addition.
As the adversary asks its queries the mechanism makes what we will call internal queries to the randompermutation \(\pi \). For example, the adversary’s TYPE1 query of \((W,\lambda )\) results in an internal type1 query of X. The internal queries come in two flavors, direct and indirect, as show in Fig. 5. Note that the total number of internal queries resulting from the adversary’s q queries is at most \(\sigma \!=\!2q\!+\!1\). The hash function H that we use to compute \(\mathrm {Initial}\) is the map defined and proven secure in Lemma 3. That said, any strongly xoruniversal hash function with the needed domain and range will do. It is important to understand that all of the abilities present in a “real” adversary attacking \(\text {Tw} [E,\tau ]\) are also represented in the abilities of an adversary attacking \(\text {TW} [E,\tau ]\) we have now described.
We aim to show \(\mathscr {A}\) will get small advantage in attacking \(\text {TW} \). The proof involves a gameplaying argument followed by a case analysis of some collision probabilities. We begin with a game 1 that perfectly simulates the \(\text {TW} \)construction. As the adversary \(\mathcal{A}\) asks queries the game grows the permutation \(\pi \) in the usual way, preparing each input for \(\pi \) or \(\pi ^{1}\) exactly as would \(\text {TW} \). The responses to typeA and B queries are stored and looked up as needed. In game 2 we return, in response to each internal query \(\pi \) or \(\pi ^{1}\), a freshly minted uniformly random point of \({{\smash {{\mathrm {GF}}(2^n)}}}\). Note that this results in values returned to the adversary that are, likewise, uniformly random. In game 3 we perfectly simulate an ideal tweakable blockcipher \({\widetilde{\pi }}\) (with the right domain and tweak space). By the “switching lemma” the advantage of \(\mathcal{A}\) in distinguishing games 2 and 3 is at most \(0.5\,q(q\!\!1)/2^n\), so we must only bound the gap between games 1 and 2.
In game 1, consider answering each internal query by uniformly sampling from \({\{0,1\}}^n\) and, hopefully, returning that sample. If we have already used our speculatively generated return value set a flag \(\textit{bad}\) and resample from the corange (for \(\pi \)queries) or codomain (for \(\pi ^{1}\) queries). The above \(\textit{bad}\)setting events occur with probability at most \(0.5\,\sigma (\sigma \!\!1)/2^n\).
When an internal query clashes with any prior commitment made then, to accurately play game 1, we must answer the query according to the prior commitment. Assume we do so, and then set \(\textit{bad}\). Call these \(\textit{bad}\)setting events collisions. We can write games 1 and 2 so as to be identical until \(\textit{bad}\) is set, so we have only to bound the probability of collisions in game 2, the version where we uniformly sample for responding to internal queries. Note that game 2 maintains the invariant that values returned to the adversary are independent of the values L and \(\mathrm {Initial}\) selected internally. Because of this, we can simplify the temporal aspect of the game and replace it by an alternative one in which the adversary chooses all TBC queries, and their responses, at the beginning. Then we make the indirect queries that determine L and \(\mathrm {Initial}\), and determine if a collision has occurred. Excising adaptivity in such a manner has been illustrated in much prior work.
Any potential collision event—e.g., the \(20^{\mathrm {th}}\) internal query colliding with the \(6^{\text {th}}\)—can be summarized by writing something like \({\mathsf {Coll}(\mathrm {3a}, \mathrm {1}) }\), interpreted as saying that first there was a type3a internal query \((W,\mathrm {Top},\mathrm {Bottom},\lambda )\), which generated a \(\pi \)input of X (its value to be determined) and an adversariallyknown response Z, and then the adversary asked a type1 query of \((W',\lambda ')\), which gave rise to a \(\pi \)input of \(X'\) (value to be determined), and an adversariallyknown response of \(Y'\). Now we make the underlying typeA and typeB queries and it so happens that \(X\!=\!X'\). Such an event is unlikely since it implies that \(W + \mathrm {Initial}+ \lambda L = W' + \lambda ' L\), and \(\mathrm {Initial}\) is uniform and independent of all other values named in the formula: we select the typeB output \(\mathrm {Ktop}\) of \(\pi \) uniformly at random, and H is universal1, making \(H_\mathrm {Ktop}(\mathrm {Bottom}) \) uniform, too. The probability of the event happening, for a given pair of indirect queries, is at most \(2^{n}\). The same holds for each of the 36 possible collision types. To avoid tedious repetition, we provide a few examples. We continue to use the same convention as in the last example, priming variables for the second query.

\(\Pr [{\mathsf {Coll}(\mathrm {A}, \mathrm {B}) }]=\Pr [{\mathsf {Coll}(\mathrm {B}, \mathrm {A}) }]=0\) since the adversary is not allowed to query with \(\mathrm {Top}=0\).

\(\Pr [{\mathsf {Coll}(\mathrm {3a}, \mathrm {3a}) }] = \Pr [W+\mathrm {Initial}+\lambda L = W' + \mathrm {Initial}' + \lambda ' L]\). Queries may not be repeated, so \((W,\mathrm {Top},\mathrm {Bottom},\lambda )\ne (W',\mathrm {Top}',\mathrm {Bottom},\lambda ')\). Suppose \(\mathrm {Top}\ne \mathrm {Top}'\). Then \(\mathrm {Ktop}\) and \(\mathrm {Ktop}'\) are uniform and independent, making \(\mathrm {Initial}\) and \(\mathrm {Initial}'\) uniform and independent by the universal1 property of H, so the probability in question is at most \(2^{n}\). Suppose \(\mathrm {Top}=\mathrm {Top}'\) but \(\mathrm {Bottom}\ne \mathrm {Bottom}'\). Then \(\mathrm {Ktop}=\mathrm {Ktop}'\) is uniform and, by the xoruniversality of H, variables \(\mathrm {Initial}\) and \(\mathrm {Initial}'\) are uniform and independent of each other and of every other variables appearing in the formula, making the probability in question at most \(2^{n}\). If \(\mathrm {Top}=\mathrm {Top}'\) and \(\mathrm {Bottom}=\mathrm {Bottom}'\) and \(\lambda =\lambda '\) then we know that \(W\ne W'\) and the probability of collision is 0. Finally, if \(\mathrm {Top}=\mathrm {Top}'\) and \(\mathrm {Bottom}=\mathrm {Bottom}'\) and \(W=W'\) then we know that \(\lambda \ne \lambda '\) and the probability we are considering collapses to \(\Pr [\lambda L = \lambda ' L] = \Pr [cL=0]\) where \(c=\lambda \lambda '\ne 0\). Since L was chosen uniformly at random in the typeA query, only the choice of \(L=0\) results in a collision, which happens with probability \(2^{n}\).

\(\Pr [{\mathsf {Coll}(\mathrm {2}, \mathrm {3b}) }] = \Pr [Y = \mathrm {Initial}'+\lambda ' L]\). This is at most \(2^{n}\) as, for example, \(\mathrm {Initial}'\) is uniform and independent of Y, \(\lambda '\), and L.

\(\Pr [{\mathsf {Coll}(\mathrm {3b}, \mathrm {2}) }] = \Pr [W +\mathrm {Initial}+\lambda L = W'+ \mathrm {Initial}' + \lambda ' L\). Since \(\lambda \)values must be distinct between TYPE2 and TYPE3b the probability is \(\Pr [cL = W + \mathrm {Initial}+ W'+ \mathrm {Initial}']\) for some \(c\ne 0\). Since the RHS side is independent of L and L is uniform, the probability is at most \(2^{n}\).
Continuing in this way one finds that each type of collision occurs with probability at most \(2^{n}\), implying a probability for any collision of at most \(0.5\,\sigma (\sigma \!\!1)/2^n\). Summing with the addends of \(0.5\,\sigma (\sigma \!\!1)\) and \(0.5\,q(q\!\!1)\) and recalling that \(\sigma \le 2q+1\) we conclude that the total adversarial advantage is at most \(4.5q^2 + 1.5q \le 6q^2\), completing the proof. \(\square \)
Wrapping Up
The following concretizes a claim, by now folklore, from Rogaway and Shrimpton [41, Section 7]. It is one half of the equivalence between aesecurity and priv+auth security: an AE scheme that is secure in the priv and auth senses is secure under the allinone definition, too. We include a proof, as we don’t know where else in the literature one appears.
Lemma 5
Let \(\Pi \) be an AE scheme. Let \(\mathscr {A}\) be an adversary that asks at most \(q_{{\mathrm {d}}}\) decryption queries. Then there are adversaries \(\mathscr {A}_{\mathrm {priv}}\) and \(\mathscr {A}_{\mathrm {auth}}\) such that
$$\begin{aligned} {\mathbf \mathbf{Adv}}^{\mathrm {ae}}_\Pi (\mathscr {A})\le {\mathbf \mathbf{Adv}}^{\mathrm {priv}}_\Pi (\mathscr {A}_{\mathrm {priv}}) + q_{{\mathrm {d}}}\cdot {\mathbf \mathbf{Adv}}^{\mathrm {auth}}_\Pi (\mathscr {A}_{\mathrm {auth}})\;. \end{aligned}$$
Adversaries \(\mathscr {A}_{\mathrm {priv}}\) and \(\mathscr {A}_{\mathrm {auth}}\) are explicitly constructed from \(\mathscr {A}\) in the proof of this lemma. They have time and query complexity similar to that of \(\mathscr {A}\).
Proof
Adversary \(\mathscr {A}_{\mathrm {priv}}\) is constructed as follows. It runs adversary \(\mathscr {A}\). When \(\mathscr {A}\) makes a leftoracle query of (N, A, M) adversary \(\mathscr {A}_{\mathrm {priv}}\) asks its own oracle (N, A, M) and gets a response C, which it returns to \(\mathscr {A}\). When \(\mathscr {A}\) makes a rightoracle query of (N, A, C), it returns \(\bot \) to \(\mathscr {A}\). When \(\mathscr {A}\) halts with an output of b, adversary \(\mathscr {A}_{\mathrm {priv}}\) outputs the same bit b and halts.
Adversary \(\mathscr {A}_{\mathrm {auth}}\) is constructed as follows. It selects a random \(j\twoheadleftarrow [1..q_{{\mathrm {d}}}]\). It then runs adversary \(\mathscr {A}\). When \(\mathscr {A}\) makes a leftoracle query of (N, A, M) adversary \(\mathscr {A}_{\mathrm {auth}}\) asks its own oracle (N, A, M) and gets a response C, which it returns to \(\mathscr {A}\). When \(\mathscr {A}\) makes its ith rightoracle query of (N, A, C), adversary \(\mathscr {A}_{\mathrm {auth}}\) returns \(\bot \) if \(i\ne j\), while, if \(i=j\), it outputs (N, A, C) (as its attempted forgery) and then halts.
Omitting oracleargument placeholders \((\cdot ,\cdot ,\cdot )\) for improved readability, we have that
$$\begin{aligned} {\mathbf \mathbf{Adv}}^{\mathrm {ae}}_\Pi (\mathscr {A})= & {} \Pr [\mathscr {A}^{\mathcal {E}_K,\mathcal {D}_K}\Rightarrow 1] \Pr [\mathscr {A}^{\$, \bot } \Rightarrow 1]\\= & {} (\Pr [\mathscr {A}^{\mathcal {E}_K, \mathcal {D}_K}\Rightarrow 1] \Pr [\mathscr {A}^{\mathcal {E}_K, \bot }\Rightarrow 1])\\&+ (\Pr [\mathscr {A}^{\mathcal {E}_K,\bot }\Rightarrow 1] \Pr [\mathscr {A}^{\$, \bot }\Rightarrow 1])\\\le & {} \Pr [\mathsf {SomeForge}] + \mathrm {Adv}_\Pi ^{\mathrm {priv}}(\mathscr {A}_{\mathrm {priv}}) \\\le & {} \sum _{i=1}^{q_{{\mathrm {d}}}}\Pr [\mathsf {FirstForge}_i] + \mathrm {Adv}_\Pi ^{\mathrm {priv}}(\mathscr {A}_{\mathrm {priv}}) \\\le & {} q_{{\mathrm {d}}}\cdot \Pr [\mathsf {FirstForge}] + \mathrm {Adv}_\Pi ^{\mathrm {priv}}(\mathscr {A}_{\mathrm {priv}}) \end{aligned}$$
where \(\mathsf {SomeForge}\) is the event that adversary \(\mathscr {A}\), in the course of its execution with oracles \(\mathcal {E}_K,\mathcal {D}_K\), asks its decryption oracle some query that results in a non\(\bot \) return value; where \(\mathsf {FirstForge}_i\) is the event that \(\mathscr {A}\), in the course of its execution with oracles \(\mathcal {E}_K,\mathcal {D}_K\), gets its first non\(\bot \) oracle response on queryi; and where \(\mathsf {FirstForge}\) is the event that \(\mathscr {A}\), in the course of its execution with oracles \(\mathcal {E}_K,\mathcal {D}_K\), gets its first non\(\bot \) return value in response to its jth query, for j uniform in \([1..q_{{\mathrm {d}}}]\). Our construction of \(\mathscr {A}_{\mathrm {auth}}\) ensures that a decryption query by \(\mathscr {A}\) that gets a first non\(\bot \) response always corresponds to a successful forgery by the adversary \(\mathscr {A}_{\mathrm {auth}}\) we have constructed; that is, \( {\mathbf \mathbf{Adv}}^{\mathrm {auth}}_\Pi (\mathscr {A}_{\mathrm {auth}}) = \Pr [\mathscr {A}_{\mathrm {auth}}^{\mathcal {E}_K} \text{ forges}] \ge \Pr [\mathsf {FirstForge}]\). This completes the proof. \(\square \)
We now have all the needed elements to conclude the security of OCB. First, combining Lemmas 2 and 5 immediately establishes the aesecurity of \({\Theta \text {{CB}} } \) based on an idealized TBC.
Lemma 6
Fix \(n=128\) and \(\tau \in [0..n]\) and \({\smash {\widetilde{\mathbb {E}}}}={\smash {\widetilde{\mathbb {E}}}}^{\mathcal{T}_{\Theta \text {{CB}} },\;n}\). Let \(\Pi ={\Theta \text {{CB}} } [{\smash {\widetilde{\mathbb {E}}}},\tau ]\). Let \(\mathscr {A}\) be an adversary that asks at most \(q_{{\mathrm {d}}}\) decryption queries. Then \({\mathbf \mathbf{Adv}}^{\mathrm {ae}}_{\Pi }(\mathscr {A}) \le 1.001\,q_{{\mathrm {d}}}/2^\tau \).
Next we replace the idealized TBC of \({\Theta \text {{CB}} } [{\smash {\widetilde{\mathbb {E}}}},\tau ]\) by the TBC one gets from the Tw construction applied to an idealized (but not tweakable) blockcipher. Combining Lemmas 4 and 6 then gives the following. In the theorem statement, the number of blocks asked by an adversary refers to the total number of nbit plaintext or ciphertext blocks, any fractional final blocks counting as one block, plus the number of associateddata blocks, any fractional final blocks again counting as one block.
Lemma 7
Fix \(n=128\) and \(\tau \in [0..n]\) and \(\mathbb {E}=\mathbb {E}^n\). Let \(\Pi ={\text {OCB} }[\mathbb {E},\tau ]\). Let \(\mathscr {A}\) be an adversary that asks at most q queries, at most \(q_{{\mathrm {d}}}\) of them decryption queries, and at most \(\sigma \) blocks. Then \({\mathbf \mathbf{Adv}}^{\mathrm {ae}}_{\Pi }(\mathscr {A}) \le 6(\sigma +2q) ^2/2^n + 1.1\,q_{{\mathrm {d}}}/2^\tau \).
Proof
We construct an adversary \(\mathscr {D}\) as follows. It has an oracle for a TBC taking tweaks \(T\in \mathcal{T}_{\Theta \text {{CB}} } \) and inputs \(X\in {\{0,1\}}^n\); and another oracle for the inverse of this TBC, taking tweaks \(T\in \mathcal{T}_{\Theta \text {{CB}} } \) and inputs \(Y\in {\{0,1\}}^n\). Adversary \(\mathscr {D}\) runs adversary \(\mathscr {A}\). When \(\mathscr {A}\) makes an encryption query of (N, A, M) adversary \(\mathscr {D}\) services this query by encrypting M with respect to N and A using the \({\Theta \text {{CB}} } \) algorithm but employing its first oracle in lieu of all forwarddirection blockcipher calls. When \(\mathscr {A}\) makes a decryption query of (N, A, C) adversary \(\mathscr {D}\) services it by decrypting C with respect to N and A using the \({\Theta \text {{CB}} } \) algorithm but employing its first oracle for forwarddirection blockcipher calls and its second oracle for inversedirection blockcipher calls. Note that all calls made by \(\mathscr {D}\) use tweaks from \(\mathcal{T}_{\Theta \text {{CB}} } \) and that inverse calls will only use tweaks of the form (N, i). We may assume that all calls employ ivalues of less than \(2^{64}\), for, otherwise, \(\sigma \ge 2^{64}\) and the result is vacuous. The total number of queries asked by \(\mathscr {D}\) will be at most \(\sigma +2q\), the 2q accounting for the fact that there is one TBC call for the Checksum and one TBC call for the processing of the nonce to produce the initial offset. Now
$$\begin{aligned} {\mathbf \mathbf{Adv}}_\Pi ^{\mathrm {ae}}(\mathscr {A})= & {} \Pr [\mathscr {A}^{{\text {OCB} }[\mathbb {E},\tau ].\mathcal {E},\,{\text {OCB} }[\mathbb {E},\tau ].\mathcal {D}}\Rightarrow 1]  \Pr [\mathscr {A}^{\$,\,\bot }\Rightarrow 1]\\= & {} (\Pr [\mathscr {A}^{{\text {OCB} }[\mathbb {E},\tau ].\mathcal {E},\,{\text {OCB} }[\mathbb {E},\tau ].\mathcal {D}}\Rightarrow 1]  \Pr [\mathscr {A}^{{\Theta \text {{CB}} } [{\smash {\widetilde{\mathbb {E}}}},\tau ].\mathcal {E},\,{\Theta \text {{CB}} } [{\smash {\widetilde{\mathbb {E}}}},\tau ].\mathcal {D}}\Rightarrow 1]) +\\&(\Pr [\mathscr {A}^{{\Theta \text {{CB}} } [{\smash {\widetilde{\mathbb {E}}}},\tau ].\mathcal {E},\,{\Theta \text {{CB}} } [{\smash {\widetilde{\mathbb {E}}}},\tau ].\mathcal {D}}\Rightarrow 1])  \Pr [\mathscr {A}^{\$,\,\bot }\Rightarrow 1])\\= & {} {\mathbf \mathbf{Adv}}^{{{\mathcal{B}}\text{ }\mathrm {prp}}}_{\text {Tw} [\mathbb {E},\tau ]}(\mathscr {D}) + {\mathbf \mathbf{Adv}}^{\mathrm {ae}}_{{\Theta \text {{CB}} } [{\smash {\widetilde{\mathbb {E}}}},\tau ]}(\mathscr {A})\\\le & {} 6(\sigma +2q)^2/2^n + 1.1\,q_{{\mathrm {d}}}/2^\tau . \end{aligned}$$
The first term is by Lemma 4 and the observations made previously concerning adversary \(\mathscr {D}\)’s attack. The second term is by Lemma 6. \(\square \)
Finally we can quantify the security of OCB when instantiated with a “real” blockcipher E.
Theorem 1
Fix \(n=128\) and \(\tau \in [0 {..}n]\) and a blockcipher \(E\!:\mathcal {K}\times {\{0,1\}}^n\rightarrow {\{0,1\}}^n\). Let \(\Pi = \text {OCB} [E,\tau ]\). Let \(\mathscr {A}\) be an adversary that asks at most q queries, at most \(q_{{\mathrm {d}}}\) of them decryption queries, and at most \(\sigma \) blocks. Then there is an adversary \(\mathscr {A}_{\mathrm {prp}}\), explicitly constructed by the proof of this theorem, for which
$$\begin{aligned} {\mathbf \mathbf{Adv}}^{\smash {\pm \mathrm {prp}}}_E(\mathscr {A}_{\mathrm {prp}})\ge & {} {\mathbf \mathbf{Adv}}^{\mathrm {ae}}_\Pi (\mathscr {A})  6(\sigma +2q)^2/2^n  1.1\,q_{{\mathrm {d}}}/2^\tau \;. \end{aligned}$$
Its time complexity is similar to that of \(\mathscr {A}\), and it asks at most \(\sigma +2q\) queries.
Proof
Adversary \(\mathscr {A}_{\mathrm {prp}}\) is constructed as follows. It runs \(\mathscr {A}\). When \(\mathscr {A}\) asks an encryption query of (N, A, M) adversary \(\mathscr {A}_{\mathrm {prp}}\) services this query by using the OCB construction with tag length \(\tau \), but employing its own left oracle in lieu of each forward blockcipher computation. When \(\mathscr {A}\) asks a decryption query of (N, A, C) adversary \(\mathscr {A}_{\mathrm {prp}}\) services this query by using the OCB construction with tag length \(\tau \), but employing its own left oracle in lieu of each forward blockcipher computation and employing its right oracle in lieu of each inverse blockcipher computation. Now
$$\begin{aligned} {\mathbf \mathbf{Adv}}^{\mathrm {ae}}_\Pi (\mathscr {A})= & {} \Pr [\mathscr {A}^{{\text {OCB} }[E,\tau ].\mathcal {E},\,{\text {OCB} }[E,\tau ].\mathcal {D}} \Rightarrow 1]  \Pr [\mathscr {A}^{\$,\bot } \Rightarrow 1] \\= & {} (\Pr [\mathscr {A}^{{\text {OCB} }[E,\tau ].\mathcal {E},\,{\text {OCB} }[E,\tau ].\mathcal {D}} \Rightarrow 1]  \Pr [\mathscr {A}^{{\text {OCB} }[\mathbb {E},\tau ].\mathcal {E},\,{\text {OCB} }[\mathbb {E},\tau ].\mathcal {D}} \Rightarrow 1]) +\\&(\Pr [\mathscr {A}^{{\text {OCB} }[\mathbb {E},\tau ].\mathcal {E},\,{\text {OCB} }[\mathbb {E},\tau ].\mathcal {D}} \Rightarrow 1]  \Pr [\mathscr {A}^{\$,\bot } \Rightarrow 1]) \\\le & {} {\mathbf \mathbf{Adv}}^{\smash {\pm \mathrm {prp}}}_E(\mathscr {A}_{\mathrm {prp}}) + 6(\sigma +q)^2/2^n + 2q_{{\mathrm {d}}}/2^\tau \end{aligned}$$
by the definition of \(\mathscr {A}_{\mathrm {prp}}\) and Lemma 7. The result follows. \(\square \)