The Design and Evolution of OCB

Schemes for authenticated encryption (AE) symmetrically encrypt a message in a way that ensures both its confidentiality and authenticity. OCB is a well-known algorithm for achieving this aim. It is a blockcipher mode of operation, the blockcipher usually being AES.

There are three main variants of OCB. The first, now called OCB1 (2001) [39], was motivated by Charanjit Jutla’s IAPM [24]. A second version, now called OCB2 (2004) [18, 38], added support for associated data (AD) [37] and redeveloped the mode using the idea of a tweakable blockcipher [30]. OCB2 was recently found to have a disastrous bug [17]. The final version of OCB, called OCB3 (2011) [26], corrected some missteps taken with OCB2 and achieved the best performance yet. It is specified in RFC 7253 [27] and was selected for the CAESAR final portfolio [7].

This paper is about OCB3: its definition, development, security, and software performance. We update the proceedings paper on OCB3 [26], freshening all of the experimental results, expanding the proof, and placing the entire enterprise in context. When we speak of OCB in this paper, we will henceforth mean OCB3.

OCB encryption protects both the confidentiality and authenticity of a plaintext M and, additionally, the authenticity of an associated data A and nonce N. The nonce, a string of 120 or fewer bits, must be unique to each encryption call. OCB does its work using a 128-bit blockcipher E. Encryption needs at most \(m+a+2\) blockcipher calls, where \(m = \lceil |M|/128\rceil \) is the block size of the plaintext and \(a = \lceil |A|/128\rceil \) is the block size of the AD. If the nonce is implemented as a counter and the implementation caches a secret 16-byte value with each message encrypted, then \(63/64\approx 98\%\) of the time the number of blockcipher calls can be reduced to \(m+a+1\). If the AD is fixed during a session, then after processing it the first time, there is effectively no computational cost for subsequent authentications of it and the addend of a should be ignored. OCB requires a single key K for the underlying blockcipher, and all blockcipher calls are keyed with it. OCB is online in the sense that one need not know the length of A or M to proceed with encryption, nor need one know the length of A or the ciphertext C to proceed with decryption. OCB is fully parallelizable: almost all of its blockcipher calls can be performed simultaneously. Computational work beyond blockcipher calls is restricted to a small number of logical operations per call.

OCB enjoys provable security: the mode is a secure AE scheme, under the standard definition [37, 39], assuming that the underlying blockcipher E is secure as a strong pseudorandom permutation (PRP). As with many modes of operation, security degrades quadratically in the number of blocks processed.

The starting point for all versions of OCB was to insist on a parallelizable design based on a 128-bit blockcipher, presumably AES. We aimed to minimize overhead, understood as any work beyond a single AES-call per input block. As time has gone on, this starting point has only come to seem better. This is because a growing fraction of general-purpose CPUs include hardware support for AES, and the quality of AES acceleration has been steadily improving. On an Intel Cannon Lake processor, we see peak speeds for OCB of about 0.43 cpb (cycles per byte). On an ARM Cortex-A73 processor, we see peak speeds of about 1.14 cpb. These speeds are about 30% and 40% faster, respectively, than what we observe for GCM [10]. Securely encrypting at such speeds on a general-purpose processor might have seemed unrealistic even a decade ago.

We now move on to provide some preliminaries on blockciphers and AE schemes. We then give two equivalent descriptions of OCB—the first based on a conventional blockcipher, like AES, the second based on a tweakable blockcipher [30] constructed from an ordinary blockcipher. Next we describe some of the design choices underlying OCB, trying to sketch how the mechanism came to take its final form. After that, we describe our experimental work, comparing the software performance of OCB and five other AE schemes. Our experiments were carried out on three disparate platforms. Our performance study is limited to software; for hardware studies of CAESAR candidates, including OCB, see the work from Kris Gaj’s lab at GMU [8, 15]. Then comes a proof of security. We conclude with some comments about OCB and its significance, identifying some of the lessons learned along the way.

We begin with a few preliminaries, defining blockciphers, tweakable blockciphers, and AE schemes, and how we will measure the security of each.

Blockciphers. A blockcipher is a function \(E\!:\mathcal {K}\times {\{0,1\}}^n\!\rightarrow \!{\{0,1\}}^n\) where the key space \(\mathcal {K}\) is a finite nonempty set, the block size \(n\!\ge 1\!\) is a number, and \(E(K,\cdot )=E_K(\cdot )\) is a permutation for each \(K\in \mathcal {K}\). Define \(E^{-1}\!: \mathcal {K}\times {\{0,1\}}^n\rightarrow {\{0,1\}}^n\) from E by saying that \(E^{-1}(K,Y)=E^{-1}_{K}(Y)\) is the unique point X such that \(E(K,X)=Y\).

OCB requires a blockcipher E with a block size of \(n=128\) bits. It is possible to define OCB for other block sizes [25], but this paper does not. We usually have in mind that OCB’s blockcipher E is AES (which always has a block size of \(n=128\) bits). All of our performance studies assume that E is AES-128, the version of AES with key space \(\mathcal {K}={\{0,1\}}^{128}\).

We next define the PRP (pseudorandom permutation) and strong-PRP security for a blockcipher E. With \(E\!:\mathcal {K}\times {\{0,1\}}^n\!\rightarrow \!{\{0,1\}}^n\) a blockcipher and \(\mathscr {A}\) an adversary (an algorithm with access to one or more oracles), define the strong-PRP security of E aswhere \(K\twoheadleftarrow \mathcal {K}\) is selected uniformly from \(\mathcal {K}\) in the experiment underlying the left-hand addend and \(\pi (\cdot )\twoheadleftarrow \mathrm {Perm}({n})\) is selected uniformly from \(\mathrm {Perm}({n})\), the set of all permutations on \({\{0,1\}}^n\), in the experiment underlying the right-hand addend. When we write \(\mathscr {A}^{\mathcal{O}_1,\mathcal{O}_2,\cdots }\Rightarrow 1\), we mean the event that \(\mathscr {A}\) with the specified oracles outputs the bit 1 and halts. Define the (ordinary) PRP-security of E asby removing the second oracle in each experiment.

The ideal blockcipher of block size  n is the blockcipher \(\mathbb {E}^{n}:\mathcal {K}\times {\{0,1\}}^n\rightarrow {\{0,1\}}^n\) where each key \(K\in \mathcal {K}\) names a distinct permutation. In this blockcipher, the key space \(\mathcal {K}\) has \(2^n!\) keys, each corresponding to a table specifying an n-bit permutation.

Tweakable blockciphers. Liskov, Rivest, and Wagner (LRW) put forward the notion of a tweakable blockcipher [30], and they demonstrated that an OCB1-like construction could more easily be designed and proven secure based on this abstraction than a conventional blockcipher. Our work builds on this insight, viewing OCB as based either on a blockcipher or on a tweakable blockcipher (in which case we adjust the name to \({\Theta \text {{CB}} } \)).

A tweakable blockcipher (TBC) is a function \({\smash {\widetilde{E}}}\!: \mathcal {K}\times \mathcal{T}\times {\{0,1\}}^n\rightarrow {\{0,1\}}^n\) where the key space \(\mathcal {K}\) is a finite nonempty set, or a set that otherwise has an understood distribution on it; the tweak space \(\mathcal{T}\) is a nonempty set; and the block size \(n\ge 1\) is a number. We insist that \({\smash {\widetilde{E}}}(K,T,\cdot )\) be a permutation on \({\{0,1\}}^n\). Its inverse \({\smash {\widetilde{D}}}={\smash {\widetilde{E}}}^{-1}\) is defined by letting \({\smash {\widetilde{D}}}(K,T,Y)=X\) when \({\smash {\widetilde{E}}}(K,T,X)=Y\). We may write \({\smash {\widetilde{E}}}_K^T(\cdot )={\smash {\widetilde{E}}}(K,T,X)\) and \({\smash {\widetilde{D}}}(K,T,Y)={\smash {\widetilde{D}}}_K^T(Y)\).

For a granular notion of security for the TBC \({\smash {\widetilde{E}}}\!: \mathcal {K}\times \mathcal{T}\times {\{0,1\}}^n\rightarrow {\{0,1\}}^n\), we identify each tweak as either a unidirectional tweak (only forward queries are allowed for it) or as a bidirectional one. (Both forward and backward queries are allowed.) Intuitively, this distinction is useful because, when making a TBC from a conventional blockcipher, unidirectional tweaks only need tweak-dependent “pre-whitening” but bidirectional tweaks need “post-whitening” too [30, 38]. Formally, one names the subset \(\mathcal{B}\subseteq \mathcal{T}\) of bidirectional tweaks, understanding that the remaining tweaks \(\mathcal{U}=\mathcal{T}\setminus \mathcal{B}\) are unidirectional. We associate with the TBC \({\smash {\widetilde{E}}}\!:\mathcal {K}\times \mathcal{T}\times {\{0,1\}}^n\!\rightarrow \!{\{0,1\}}^n\) and the subset of tweaks \(\mathcal{B}\subseteq \mathcal{T}\) the partitioned-tweakspace PRP measurewhere \(K\twoheadleftarrow \mathcal {K}\) is chosen uniformly at the beginning of the left-hand experiment, where \(\pi \twoheadleftarrow \mathrm {Perm}({\mathcal{T},n})\) is chosen uniformly at the beginning of the right-hand experiment, and where adversary \(\mathscr {A}\) may not ask any decryption (second-oracle) query (T, Y) with \(T\in \mathcal{T}\setminus \mathcal{B}\). Any such (invalid) query would get empty-string response. By \(\mathrm {Perm}({\mathcal{T},n})\) we mean the space of all permutations \(\pi (T,\cdot )\) on \({\{0,1\}}^n\), one for each \(T\in \mathcal{T}\).

The partitioned-tweakspace PRP notion above unifies tweakable-PRP and strong-tweakable-PRP security: with \({\smash {\widetilde{E}}}\!:\mathcal {K}\times \mathcal{T}\times {\{0,1\}}^n\!\rightarrow \!{\{0,1\}}^n\) a TBC we can resurrect the notion for a strong-tweakable-PRP [30] by defining \({\mathbf \mathbf{Adv}}_{{\widetilde{E}}}^{\smash {\pm \mathrm {prp}}}(\mathscr {A}) = {\mathbf \mathbf{Adv}}_{{\widetilde{E}}}^{{{\mathcal{T}}\text{- }\mathrm {prp}}}(\mathscr {A})\). We can realize the conventional (not strong) version [30] by defining \({\mathbf \mathbf{Adv}}_{{\widetilde{E}}}^{\mathrm {prp}}(\mathscr {A}) = {\mathbf \mathbf{Adv}}_{{\widetilde{E}}}^{{{\emptyset }\text{- }\mathrm {prp}}}(\mathscr {A})\). Going a step further, the PRP and strong-PRP security notions for a conventional blockcipher \(E\!:\mathcal {K}\times {\{0,1\}}^n\!\rightarrow \!{\{0,1\}}^n\) can be recovered by regarding the tweak space as a singleton set.

The ideal TBC with tweak space \(\mathcal{T}\) and block size  n is the TBC \({\smash {\widetilde{\mathbb {E}}}}^{\mathcal{T},n}:\mathcal {K}\times \mathcal{T}\times {\{0,1\}}^n\rightarrow {\{0,1\}}^n\) where each key \(K\in \mathcal {K}\) and \(T\in \mathcal{T}\) names a distinct permutation \({\smash {\widetilde{\mathbb {E}}}}^{n}(K,T,\cdot )\) on \({\{0,1\}}^n\).

AE schemes. Following traditions rooted in prior work [4, 28, 37, 39], we regard an AE scheme (meaning a nonce-based AE scheme with associated-data, sometimes referred to as an AEAD scheme [37]) as a triple \(\Pi =(\Pi .\mathcal {K},\Pi .\mathcal {E},\Pi .\mathcal {D})=(\mathcal {K},\mathcal {E},\mathcal {D})\). The key space \(\mathcal {K}\) is a finite nonempty set (or a set that otherwise has an understood distribution). The encryption algorithm \(\mathcal {E}\) takes in a key \(K\in \mathcal {K}\), a nonce \(N\in {\{0,1\}}^*\), a string of associated data \(A\in {\{0,1\}}^{*}\), and a plaintext \(M\in {\{0,1\}}^*\). It returns, deterministically, a string \(C=\mathcal {E}(K,N,A,M)\) that is either a string \(C\in \mathcal{C}={\{0,1\}}^*\), the ciphertext, or the symbol \({\bot }\). The former must happen if and only if \((K,N,A,M)\in \mathcal {K}\times \mathcal{N}\times \mathcal{M}\times {\mathcal {A}}\) for nonempty sets \(\mathcal{N}\), \({\mathcal {A}}\), and \(\mathcal{M}\), the nonce space, AD space, and message space of \(\Pi \). The decryption algorithm \(\mathcal {D}\) takes in a tuple \((K,N,A,C)\) and deterministically returns a value \(\mathcal {D}(K,N,A,C)\) that is either a string M or the distinguished symbol \({\bot }\). The latter must happen if \((K,N,A,C)\not \in \mathcal {K}\times \mathcal{N}\times {\mathcal {A}}\times \mathcal{C}\). We require that \(\mathcal {D}(K,N,A,C)=M\) when \(C=\mathcal {E}(K,N,A,M)\) is a string. We require of the message space \(\mathcal{M}\) that \(M\in \mathcal{M}\) implies \(M'\in \mathcal{M}\) when \(|M'|=|M|\). We require that \(|\mathcal {E}(K,N,A,M)|=|\mathcal {E}(K,N,A,M')|=|M|+\tau \) when the encryptions are strings and \(|M|=|M'|\). We call \(\tau \) the tag length or expansion of the AE scheme. We may write \(\mathcal {E}(K,N,A,M)\) as \(\mathcal {E}_K(N,A,M)\) or \(\mathcal {E}_K^{N,A}(M)\), and similarly for \(\mathcal {D}\).

Let \(\Pi =(\mathcal {K},\mathcal {E},\mathcal {D})\) be an AE scheme with tag length \(\tau \). Given an adversary \(\mathscr {A}\), we measure how well it breaks the privacy of (here meaning the confidentiality) of \(\Pi \) by the real numberThe first addend is the probability that \(\mathscr {A}\) outputs 1 when given the oracle \(\mathcal {E}_K(\cdot ,\cdot ,\cdot )\). The experiment begins by uniformly selecting a key \(K\twoheadleftarrow \mathcal {K}\). Then, when the adversary asks a query (N, A, M), the oracle responds with \(\mathcal {E}_K(N,A,M)\). The second term is the probability that \(\mathscr {A}\) outputs 1 when given the oracle \(\$(\cdot ,\cdot ,\cdot )\). This oracle, on input \((N,A,M)\), returns a uniformly random string of length \(|M|+\tau \). We demand that \(\mathscr {A}\) never asks two queries with the same first component (the N-value) and that it never asks a query outside of \(\mathcal{N}\times \mathcal{A}\times \mathcal{M}\). Any such adversary query is invalid.

Next we define authenticity. With \(\Pi \) and \(\mathscr {A}\) as before, letOnce again the experiment implicitly begins by selecting a key \(K\twoheadleftarrow \mathcal {K}\). We say that the adversary forges if it outputs a value \((N,A,C)\in \mathcal{N}\times \mathcal{A}\times \mathcal{C}\) such that \(\mathcal {D}(K,N,A,C)\ne {\bot }\) yet there was no prior query (N, A, M) that returned C. We demand that \(\mathscr {A}\) never asks two queries with the same N-value (the first component) and never asks a query outside of \(\mathcal{N}\times \mathcal{A}\times \mathcal{M}\).

Informally, an AE scheme \(\Pi \) is secure if any adversary \(\mathscr {A}\) with “reasonable” resources has “small” priv-advantage and small auth-advantage. Following the concrete-security tradition, and in view of the fact that we will only be defining OCB for use with an \(n=128\) bit blockcipher, we refrain from making any absolute or asymptotic definition of security.

An alternative definition of AE security merges privacy and authenticity to get a unified security measureThe adversary is given either a pair of “real” encryption and decryption oracles or, alternatively, a pair of “fake” encryption and decryption oracles. The former begin by choosing a random \(K\twoheadleftarrow \mathcal {K}\). After, the first oracle (the encryption oracle) responds to a query (N, A, M) with \(\mathcal {E}(K,N,A,M)\), while the second oracle (the decryption oracle) responds to a query (N, A, C) with \(\mathcal {D}(K,N,A,C)\). The \(\$(\cdot ,\cdot ,\cdot )\) oracle, on query (N, A, M), just returns \(|M|+\tau \) uniformly random bits, where \(\tau \) is the tag length of \(\Pi \). The \(\bot (\cdot ,\cdot ,\cdot )\) oracle, on query (N, A, C), always returns \(\bot \). The adversary may not repeat the first component, N, to its encryption oracle; it may not ask a decryption query of (N, A, C) following an encryption query of (N, A, M) that returned C; and it may only ask encryption queries in \(\mathcal{N}\times {\mathcal {A}}\times \mathcal{M}\) and decryption queries in \(\mathcal{N}\times {\mathcal {A}}\times \mathcal{C}\).

The ae-security notion is essentially equivalent to the conjunction of priv-security and auth-security [41, Section 7]. In our proof of OCB’s security, we will use one direction of this claim.

We say that AE schemes \(\Pi =(\mathcal {K},\mathcal {E},\mathcal {D})\) and \(\Pi '=(\mathcal {K}',\mathcal {E}',\mathcal {D}')\) coincide if their encryption and decryption algorithms compute identical functions: \(\mathcal {E}(K,N,A,M)=\mathcal {E}'(K,N,A,M)\) and \(\mathcal {D}(K,N,A,C)=\mathcal {D}'(K,N,A,C)\) for all K, N, A, M, and C. This implies \(\mathcal {K}=\mathcal {K}'\), too.

We note that our priv and ae security notions demand indistinguishability from random bits (sometimes denoted IND$) instead of indistinguishability from the encryption of random (or fixed) bits. This notion goes back to OCB1 [39]. There are several reasons for it. First, this notion of privacy is stronger, yet is achieved by OCB (and most other real-world AE schemes). At the same time, it is also what is most convenient to prove. Also, the encryption algorithm of an AE scheme meeting IND$-security can be used as a pseudorandom generator (PRG), which might be convenient, in some cases, for the user. Perhaps most significantly, IND$-security implies a form of anonymity [1] where one demands that ciphertexts be indistinguishable whether they are constructed from one hidden key K or are, instead, constructed using either of two hidden keys \(K_0,K_1\), which one being selected by the adversary.

We now define OCB (meaning OCB3). Given a blockcipher \(E{:\;}\mathcal {K}\times {\{0,1\}}^{128}\rightarrow {\{0,1\}}^{128}\) and a tag length \(\tau \in [0{..}128]\), Fig. 1 defines from E and \(\tau \) the AE scheme \(\Pi = {\text {OCB} }[E,\tau ] = (\mathcal {K},\mathcal {E},\mathcal {D})\). The nonce space \(\mathcal{N}=\mathcal{N}_{\text {OCB} }={\{0,1\}}^{\le 120}\) is the set of all binary strings with at most 120 bits. The message space \(\mathcal{M}={\{0,1\}}^*\) and AD-space \({\mathcal {A}}={\{0,1\}}^*\) are all binary strings. The \(\mathrm {Setup}\) procedure of Fig. 1 is implicitly run on or before the first call to \(\mathcal {E}\) or \(\mathcal {D}\). The variables it defines are understood to be global. While line 114 is written as an infinite loop, it is sufficient to compute \(L[0],L[1],\ldots , L[d]\) where \(2^d\) upper bounds the number of 128-bit blocks in any plaintext M, ciphertext C, and associated data A. We write \({\mathrm {ntz}({i})}\) for the number of trailing zeros in the binary representation of positive integer i (e.g., \({\mathrm {ntz}({1})}\!=\!{\mathrm {ntz}({3})}\!=\!0\) and \({\mathrm {ntz}({4})}\!=\!2\)). We write \({\mathrm {msb}}(X)\) for the first (most significant) bit of the string X. We write \(A\wedge B\) for the bitwise-and of the equal-length strings A and B. We write \(A{\ll }i\) for the shift of A by i positions to the left (maintaining string length, leftmost bits falling off, zero-bits entering at the right). We write either \(A\; B\) or \(A\;\Vert \;B\) for the concatenation of strings A and B. At line 121 we write \([a]_7\) for \(a\in [0..127]\) encoded as a 7-bit string, while at line 126 we regard the variable \(\mathrm {Bottom}\) as a number instead of a string.

For reasons of generality, OCB is defined to operate on bit strings. But for reasons of simplicity and efficiency, most implementations will assume that all strings operated on are strings of bytes, with a byte being eight bits.

Figure 2 illustrates encryption under OCB. Function \(\text {Inc}\) implicitly depends on the key K, with \(\text {Inc}_i(\Delta ) \!=\! \Delta \oplus L[{\mathrm {ntz}({i})}]\), \(\text {Inc}_\$(\Delta )\! =\! \Delta \oplus L_{\$}\), \(\text {Inc}_*(\Delta ) \!=\! \Delta \oplus L_*\), and the (zero-argument) \(\text {Init}\!=\! 0^{128}\). Here \(L_*\!=\! E_K(0^{128})\), \(L_{\$}= 2\cdot L_*\!=\! \mathrm {double}({L_*})\), and \(L[i] = 2^{2+i}\cdot L_*\) for all \(i\ge 0\), the multiplication in \({{\smash {{\mathrm {GF}}(2^{128})}}}\). Here we write \(2=0^{126}10 = \texttt {x}\) to denote a particular nonzero point of the finite field. The diagrams should be read left to right and then top to bottom: first set \(\Delta \) to be \(\text {Init}_K(N)\); then modify \(\Delta \) with \(\text {Inc}_1\); then compute \(C_1\) using the blockcipher E with pre- and post-whitening with \(\Delta \); then modify \(\Delta \) with \(\text {Inc}_2\); and so on.

In this section, we generalize OCB by describing the construction in terms of a tweakable blockcipher (TBC). We show that this alternative description really is a generalization of OCB by explaining how to recover the definition of OCB with a particular choice for its TBC.

We now explain some of the design choices made for OCB, simultaneously sketching the mode’s history.

Development of ocb1. The initial reason for developing OCB1 [39] was to improve the efficiency of authenticated encryption. Prior work by Jutla [24], and also by Katz and Yung [28] and Gligor and Donescu [11], had evidenced that tightly integrating privacy and authenticity let one get by with less work than what one would see from generically composing separate privacy and authenticity mechanisms. Attending to “low-level” concerns, we aimed to create a blockcipher-based AE scheme that would push the efficiency bar. OCB1 handles plaintexts of any length and produces ciphertexts \(\tau \)-bits longer. It uses a near-minimal number of blockcipher calls and minimizes work beyond those calls. It allows nearly all blockcipher calls to be performed in parallel. It assumes a nonce, not a random IV. It is deterministic. A single key underlies all blockcipher calls. It is online, making a single pass over the plaintext or ciphertext, whose length may not be known in advance.

Development of ocb2. A series of devastating attacks on 802.11 (WiFi) security created an urgent need to replace its confidentiality mechanism. Jesse Walker, Nancy Cam-Winget, and others advocated replacing it with OCB1. But they explained to Rogaway that there would need to be some way to authenticate but not encrypt header information. Formalizing and achieving this end led to the idea of associated data and to the paper by Rogaway that introduced it [37].

A couple years later, a different paper by Rogaway [38] proposed adjusting the offsets used in OCB1, going from the Gray-code ordered \(L, 3L, 2L, 6L, 7L, 5L, \ldots \) to the powering-up ordered \(L, 2L, 2^2L, 2^3L, 2^4L, \dots \). OCB2 does this, and also accommodates the AD. It was adopted as an ISO standard in 2009 [18]. As mentioned already, the scheme has a major error [17].

ocb1’s speed questioned. In 2004 McGrew and Viega wrote a paper claiming that GCM [10] was about as fast, if not faster, than OCB1 [31]. They suggested that two design issues underlie this. First, OCB1 uses \(m+2\) blockcipher calls to encrypt a message of \(m=\lceil |M|/128\rceil \) blocks. In contrast, GCM makes do with \(m+1\). Second, OCB1 twice needs the result of one AES computation before another AES computation can proceed. Both in hardware and in software, this can degrade performance. Still, we suspected that these two matters would have only a minor impact on performance. The timing studies were misleading, we believed, because McGrew and Viega had compared a reference implementation of OCB with an optimized implementation of GCM. Even that was irreproducible due to McGrew and Viega’s use of proprietary GCM code.

We decided to revise OCB1/OCB2 to address and assess the two efficiency concerns above. We integrated scheme development and performance measurements. The result of our work was the definition of OCB3 and a comparative study of the performance of CCM [9], GCM, and the OCB triplet [26]. We found that, across a variety of platforms, all versions of OCB were considerably faster than both CCM and GCM. The performance differences among OCB1, OCB2, and OCB3 were small. OCB3 had the best performance, but OCB2’s performance was actually worse than OCB1’s. We now look at some of the OCB3 changes over OCB1/OCB2.

Reduced latency. Suppose that the message \(M=M_1\cdots M_m\, M_*\) being encrypted is not a multiple of 128 bits: it has a final block \(M_*\) of 1–127 bits. With OCB1 and OCB2 one makes an \(M_m\)-dependent blockcipher call to compute a ciphertext block \(C_m\) that is in turn used to create a Checksum that is enciphered with another blockcipher call. This can result in a pipeline stall [31]: one blockcipher call must finish before the next one can begin. For OCB3 we restructure the algorithm so that the Checksum does not depend on any ciphertext block: we simplify the Checksum to \(M_1\oplus M_2\oplus \cdots \oplus M_{m}\) when there is a full final block \(M_m\), and \(M_1\oplus M_2\oplus \cdots \oplus M_{m}\oplus M_*10^*\) otherwise.

Incrementing offsets. In OCB1, each noninitial offset is computed from the prior one by xoring in some key-derived value: the ith offset is \(\Delta \!\leftarrow \!\Delta \oplus L[{\mathrm {ntz}({i})}]\). In OCB2, each noninitial offset is computed from the prior one by multiplying it, in \({{\smash {{\mathrm {GF}}(2^{128})}}}\), by a constant: \(\Delta \!\leftarrow \! (\Delta {\ll }1)\oplus ({\mathrm {msb}}(\Delta )\cdot \text {135})\), an operation we think of as doubling. The first approach turns out to be faster [39]. While doubling can be coded in five Intel x86-64 assembly instructions, it still runs more slowly. In some settings, doubling loses big: it is expensive on 32-bit machines, and some compilers do poorly at turning C/C++ code for doubling into machine code that exploits the available instructions. On Intel x86, the 128-bit SSE registers cannot be efficiently shifted one position to the left. Finally, the doubling operation is not endian neutral: if we must create a bit pattern in memory to match the sequence generated by doubling, we will effectively favor big-endian architectures. We can trade this bias for a little-endian one by redefining \(\mathrm {double}({})\) to include a byteswap. But one is still favoring one endian convention over the other, and not just at key-setup time. For all of these reasons, OCB3 reverts to the OCB1 method incrementing offsets.

In the development of OCB3, we tried a variety of other methods to generate the needed offsets, exploring word-oriented LFSRs (linear feedback shift registers) of various designs [39, Appendix B]. No alternative performed significantly better, even in isolation, than the method used in OCB1.

Trimming a blockcipher call. OCB1 and OCB2 took \(m+2\) blockcipher calls to encrypt an m-block string M: one to map the nonce N into an initial offset \(\Delta \); one for each block of M; and one to encipher the final Checksum. The first of these is easy to eliminate if one is willing to replace a blockcipher call by, say, \(K_1\cdot N\), the product in \({{\smash {{\mathrm {GF}}(2^{128})}}}\) of nonce N and a variant \(K_1\) of K. But such a change would necessitate implementing a \({{\smash {{\mathrm {GF}}(2^{128})}}}\) multiply. We use a different method to trim the extra blockcipher call, most of the time, for a counter-based nonce: we employ a new xor-universal hash function, which we call the stretch-then-shift hash. The initial offset \(\Delta \) is \(\Delta = H_K(N) = (\mathrm {Stretch}{\ll }\mathrm {Bottom})[1{..}128]\) where \(\mathrm {Bottom}\) is the last six bits of N and the \((128\!+\!64)\)-bit string \(\mathrm {Stretch}\) is made by a process involving enciphering N with its last six bits zeroed out. (This description ignores the inclusion of the tag length \(\tau \) along with N.) The technique ensures that when the nonce N is a counter, the initial offset \(\Delta \) can be computed without a new blockcipher call about \(63/64\approx 98\%\) of the time. In this way we reduce cost from \(m+2\) blockcipher calls to an amortized \(m\!+\!1.02\) blockcipher calls. Note, however, that achieving this reduction requires an implementation to cache the value of Ktop (line 124) and to notice, when true, that it need not be recomputed. And there are security considerations in doing this, for it is essential that the adversary not have access to the cached value.

Incorporating tag length. The algorithm of this paper coincides with that of RFC 7253 [27] but differs from the algorithm in the proceedings paper [26] in one minor way: the tag length is used in computing the initial offset \(\Delta \) (line 121). A change in this direction was requested during the RFC review process in order that a ciphertext created for one value of the tag length \(\tau \) should not be of value in forging a ciphertext for a different value of \(\tau \). The change is heuristic, as security claims associated with OCB assume \(\tau \) to be fixed. Subsequent work by Reyhanitabar, Vaudenay, and Vizár demonstrated that the manner in which we incorporate \(\tau \) does not work to improve the security notion to one where the same key is used for multiple tag lengths [36].

Representing field points. A low-level choice where OCB and GCM [10] part ways is in the representation of field elements. In GCM the polynomial \(a_{127}\mathtt {x}^{127}+\cdots a_1\mathtt {x}+ a_0\) corresponds to the string \(a_{0}\ldots a_{127}\) rather than the string \(a_{127}\ldots a_{0}\). The usual convention on machines, whether big-endian and little-endian, is that the msb is the leftmost bit of any register. One advantage of following that convention is that a left shift by one can be implemented by adding a register to itself, an operation that is sometimes faster than a 1-bit logical shift. For example, on an ARM Cortex-A57 addition has one cycle latency but logical shift has two.

Endian issues. While we expect the majority of processors running OCB will be little-endian, the mode’s definition does nothing to favor this convention. Endian issues arise when “register oriented” and “memory oriented” values interact. These are the same on big-endian machines, but are opposite on little-endian ones. One could, therefore, favor little-endian machines by building into the algorithm byte swaps that mimic those that would occur naturally each time memory and register oriented data interact. We experimentally adapted our implementation to do this but found that it made very little performance difference. One reason for this is the efficient byte-reversal capability on most modern processors (e.g., the pshufb instruction can reverse 16 bytes on x86 machines in a single cycle). Also, the OCB1-based approach for incrementing offsets allows precomputed values to be endian-adjusted at key-setup time, removing most endian-dependency for subsequent encryption or decryption calls. Since it makes little difference to performance, and big-endian specifications are conceptually easier, OCB does not make any gestures toward little-endian orientation.

Figures 6, 7, and 8 compare the performance of OCB and several other AE schemes. The OCB alternatives were chosen based on their popularity and salience. The TLS 1.3 specification [35] mentions three AE algorithms—GCM [10, 31], CCM [9, 43] and Chacha20-Poly1305 [5, 32]. These schemes are well established and probably represent the bulk of AE in use today. So we begin with these three schemes. Then, in the recently concluded CAESAR competition, AEGIS-128 [44] and OCB were winners of the “high-performance” category. So we include AEGIS-128 as a fourth point of comparison. Finally, on the 64-bit Intel architecture we include AES-GCM-SIV, as specified in RFC 8452 [13] (2018). The AES-GCM-SIV mechanism builds on Rogaway and Shrimpton’s SIV [41] to add nonce-reuse misuse-resistance, the most important security property, in our view, that is not delivered by OCB or the other alternatives we have named. AES-GCM-SIV is benchmarked only on the 64-bit Intel architecture because, at the time of writing, that is the only high-quality implementation available.

We ran experiments on three different architectures. The most important architectures today are 64-bit Intel x86 for servers, desktops and laptops, and 64-bit ARM for high-performance embedded applications such as smartphones and tablets. We therefore benchmark on CPUs fitting these descriptions. For 64-bit Intel we use a recent Intel Core i3-8121U (“Cannon Lake”). For 64-bit ARM we test on a high-performance Cortex-A73. As a catch-all for architectures not falling into either of these categories, we also benchmark on an older 32-bit ARMv5 processor (Marvell 88FR131 “Feroceon”). The Feroceon results capture how much work each algorithm needs when the unit of work is a 32-bit RISC assembly instruction and the processor lacks hardware acceleration such as an AES unit or vector registers. The Feroceon is also a reasonable stand-in for what can be expected from ARM’s current M-series embedded processors.

Source code. A problem sometimes seen in performance comparisons is to include implementations of uneven quality. To avoid this, we considered for benchmarking the best-performing version of each scheme among several sources. OpenSSL, Libgcrypt, and WolfSSL all provide open-source cryptographic libraries with significant assembly-language acceleration targeting multiple architectures. For each algorithm implemented by each library, we identified its peak speed on multiple architectures. In every case OpenSSL’s library was the fastest. This is not surprising: OpenSSL has a longer record of producing good-quality assembly than the others. As a sanity check, whenever possible we also verified that speeds reported on the SUPERCOP benchmarking website [42] were not faster that the speeds we found.

The AEGIS-128 implementation we used for benchmarking is a modified version of the optimized one placed on the SUPERCOP benchmarking website by the AEGIS designers. The AES-GCM-SIV implementation we used is from Google’s BoringSSL library. We ourselves have supplied the OCB code. The AEGIS-128 and OCB codes were written in C (with AES intrinsics when available) and all other AE algorithms have their kernels written in assembly. All non-library code was compiled with both Clang 8.0 and GCC 8.3 or 9.1, using both optimization levels 2 and 3, and whichever combination performed best is reported. The OpenSSL and BoringSSL libraries were built using the library’s build script with the addition of architecture-specific flags. We found that changing which compiler or optimization level was used to compile the libraries made no measurable difference in our tests, no doubt because the time-critical code was already in assembly, thus unaffected by compiler options.

The relative speeds of these algorithms are easy to explain. OCB and AEGIS-128 were designed to have little marginal overhead beyond calls to the AES round function. On systems with a hardware AES unit, this results in outstanding peak performance. Although CCM and GCM can also take advantage of a hardware AES unit, the computation of GHASH for GCM and the CBC-MAC for CCM, in addition to the counter-mode encryption each performs, is enough to separate them from the speed leaders. Chacha20-Poly1305 does not use AES or carryless multiplication, instead depending on integer addition, rotation, and xor; it gets no benefit from AES hardware support. Chacha20-Poly1305 is designed to benefit from vectorized instructions, like AVX on Intel and NEON on ARM, but these do not have enough accelerative power to keep up with the AES unit’s capabilities.

On a system without an AES unit, we see that AEGIS-128 is about twice as fast as OCB (because it computes about half as many AES rounds, per byte of input, as OCB), and OCB is about twice as fast as CCM (because it computes about half as many AES rounds as CCM). GCM is somewhere between OCB and CCM because GCM substitutes a less expensive GHASH computation for CCM’s CBC-MAC. The simplicity of the Chacha20-Poly1305 design leads to its superior performance on simpler systems.

Looking toward newer architectures, Intel is currently rolling out its AVX-512 architecture. Our Cannon Lake testbed has some previously developed 512-bit vector instructions, which are used by Chacha20-Poly1305, but Intel’s Ice Lake architecture brings more significant improvements. Its AES unit doubles throughput and shaves 25% off latency which will benefit OCB much more than the other AE algorithms. AEGIS-128 has a serial component—it cannot start the first AES round of an input block until the first AES round of the prior block has completed—implying that its performance is limited by AES round latency. This should result in a 25% speed increase between Cannon Lake and Ice Lake architectures, but that is less than the potential doubling of OCB speed. GCM will see a doubling in AES throughput, but carryless multiplication will maintain its throughput, limiting any performance increase. CCM’s serial CBC-MAC computation will be 25% faster on Ice Lake than on Cannon Lake, but will continue to keep CCM’s performance slowest of the group. Chacha20-Poly1305’s AVX-512 speed improvements are already reflected in this study and should see no significant improvement on Ice Lake. Preliminary results on an Ice Lake system, completed as we go to press, show an OCB peak throughput of 0.19 cpb, which is very close to the predicted doubling.

Testing methodology. The number of CPU cycles needed to encrypt a message is divided by the length of the message to arrive at the cost per byte to encrypt messages of that length. This is done for every message length from 1 to 2048 bytes. So as not to have performance results overly influenced by the memory subsystem of a host computer, we arrange for all code and data to be in level-1 cache before timing begins. Two timing strategies are used: the clock function of C and the x86 time-stamp counter. In the clock version, the ANSI C clock() function is called before and after repeatedly encrypting the same message, on sequential nonces, for a little more than one second. The clock difference determines how many CPU cycles were spent on average per processed byte. This method is highly portable, but is time-consuming when collecting an entire dataset. On x86 machines there is a “time-stamp counter” (TSC) that increments once per CPU cycle. To capture the average cost of encryption, the TSC is used to time encryption of the same message 64 times on successive counter-based nonces. The TSC method is not portable, working only on x86, but it is fast. The TSC read instruction might be executed out of order, in some cases it has high latency, and it continues counting when other processes run. To reduce the impact of these problems, we read the TSC once before and after encrypting the same message 65 times and then read the TSC once before and after encrypting the same message once more. Subtracting the second timing from the first gives us the cost for encrypting the message 64 times, and mitigates the out-of-order and latency problems. To avoid including context-switches, we run experiments multiple times and keep only the median timing.

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 information-theoretic setting. Passing to the complexity-theoretic setting for the final result is then standard.

Limitations. There are three limitations on OCB that we would like to emphasize. The first is that OCB’s security crucially depends on the encrypting party not repeating a nonce. The mode should never be used in situations where that can’t be assured; one should instead employ a misuse-resistant AE scheme [41]. These include AES-GCM-SIV [13, 14], COLM [2], and Deoxys-II [23]. A second limitation of OCB is its birthday-bound degradation in provable security. This limitation implies that, given OCB’s 128-bit block size, one must avoid operating on anything near \(2^{64}\) blocks of data. The RFC on OCB [27] asserts that a given key should be used to encrypt at most \(2^{48}\) blocks (4 petabytes), including the associated data. Practical AE modes that avoid the birthday-bound degradation in security are now known [14, 19, 20, 23, 40]. Finally, OCB uses both the forward and the backward direction of its underlying blockcipher. Minematsu has devised an elegant approach for avoiding use of a blockcipher’s inverse in an OCB-like construction [33].

The OCB2 bug. We mentioned in the Introduction the devastating bug on OCB2 discovered by Inoue, Iwata, Minematsu, and Poettering [17]. What was the root cause of this bug [17], and why does OCB3 escape it? We offer two high-level explanations.

One is to claim that OCB2—and OCB1 and OCB3 as well—are over-optimized. In particular, the constructions twice omit post-whitening xors [38], switching from the XEX construction to the XE construction [30, 38] for enciphering the Checksum and for Vernam-style encrypting the final block of plaintext. (OCB2 and OCB3 also use XE for processing the AD.) Shaving off these two xors increased conceptual complexity and proof complexity for an insignificant improvement in speed.

But the intermixing of XE and XEX constructions is not by itself a problem; what made this turn out so badly for OCB2 was the muddy (and therefore error-prone) abstraction boundary for dealing with TBCs that combine XE and XEX [38, Section 8]. Rather than partitioning the tweak space into unidirectional and bidirectional tweaks, as we did with OCB3, a one-bit tag was appended to each tweak—but then the tag was not treated as an intrinsic part of the tweak. This failed to properly capture the intent that things like \(\varvec{\pi }_4^N\) (with a bold \(\varvec{\pi }\)) and \(\bar{\pi }_4^N\) (with a bar over the \(\pi \)) and \(\pi _4^N\) in [38, Fig. 1] all need to be instantiated so as to approximate independent permutations. Properly formalizing a partitioned-tweakspace PRP helped steer us clear of the error to which OCB2 succumbed.

ISO standardization. The OCB2 bug was made more significant because it had been standardized in ISO/IEC 19772 [18]. Unfortunately, nobody on that standardization committee had told us that they were planning to standardize this scheme. Had they, we would have explained that we had already abandoned OCB2 in favor of a cleaner and more empirically informed redesign, OCB3, an unpublished draft of which already existed. The same ISO standard included another faulty AE scheme: a badly misspecified version of encrypt-then-MAC [34]. These two problems suggest, to us, that a rather insular standardization process was then in place.

Patents. At present, OCB is not widely used. This is largely due to there having been potentially relevant patents held by multiple parties. This was the reason that OCB1 fell out of being a mandatory mechanism of 802.11 [16], and the reason it was not subsequently selected for a NIST Special Publication. The limited adoption of OCB exemplifies the often poisonous impact of patents on cryptographic practice.

The second author, who held the patents most directly reading against OCB, has renounced all OCB-relevant IP; all OCB-relevant patents of his have been placed in the public domain. While Rogaway had previously licensed all open-source software and all software for non-military use, IP concerns did not go away.

Final remark. As explained in Sect. 5, the initial reason for developing OCB1 was to improve the efficiency of authenticated encryption. But it soon became clear to us that AE schemes had a second benefit: that they could improve usability. By moving closer to what an ideal encryption scheme would deliver (and, also, by adjusting an encryption-scheme’s syntax to include AD and avoid per-message randomness) one could make symmetric encryption less prone to misuse and less reliant on fussy composition techniques [4, 34]. OCB, and AE more broadly, helped birth a reconceptualization of symmetric encryption. One abandons weak security notions and schemes that are hard to correctly use and moves toward strong security notions and schemes that are easier to use well. This, not speed, may be the lasting legacy of AE.