OCB: Background

1. What is OCB?
2. Can you describe how OCB works?
3. Are there different versions of OCB?
4. What are some of OCB’s properties?
5. How much faster is OCB than CCM or GCM?
6. What papers deal with OCB?
7. Is the notion of authenticated-encryption something new?
8. What does the name stand for?
9. What blockcipher should I use with OCB?
10. Should one write “OCB-AES” or “AES-OCB”?
11. Is OCB in standards?
12. What did Jutla do?
13. What did Gligor and Donescu do?
14. What is a nonce and why do you need one?
15. Is there code available? Is it free?
16. Are OCB test vectors available?
17. Is it safe to use a new algorithm in a product / standard?
18. Are there competing integrated authenticated-encryption proposals?"
19. Are there competing two-pass authenticated-encryption proposals?"
20. Is OCB patented?
21. Do I need a license?
22. Who is the author of this webpage?

OCB is a blockcipher-based mode of operation that simultaneously provides both privacy and authenticity for a user-supplied plaintext. Such a method is called an authenticated-encryption scheme. What makes OCB remarkable is that it achieves authenticated encryption in almost the same amount of time as the fastest conventional mode, CTR mode, achieves privacy alone. Using OCB one buys privacy+authenticity about as cheaply (or more cheaply—CBC was once the norm) as one used to pay for achieving privacy alone. Despite this, OCB is simple and clean, and easy to implement in either hardware or software. OCB accomplishes its work without bringing in the machinery of universal hashing, a technique that does not seem to lend itself to implementations that are simple and fast in both hardware and software.

Somewhat more precisely, OCB solves the problem of nonce-based authenticated-encryption with associated-data (AEAD). The associated-data part of the name means that when OCB encrypts a plaintext it can bind it to some other string, called the associated data, that is authenticated but not encrypted. The nonce-based part of the name means that OCB requires a nonce to encrypt each message. OCB does not require random the nonce to be random; a counter, say, will work fine. Unlike some modes, the plaintext provided to OCB can be of any length, as can the associated data, and OCB will encrypt the plaintext without every padding it to some convenient-length string, an approach that would yield a longer ciphertext.

The design of OCB was strongly influenced by Charanjit Jutla’s mode IAPM; I consider the papers I’ve written related to OCB to be follow-on work to Jutla’s paper. I took up the design of OCB largely in response to NIST’s modes-of-operation activities: NIST had figured out that not only do we need a modern blockcipher (AES), but one also needs, just as importantly, modern ways to use use the construct well. While NIST still has not put forward a standard for an “integrated” one-pass AEAD mode, I suspect that, eventually, they will.

In the past, when one wanted a shared-key mechanism providing both privacy and authenticity, the usual thing to do was to separately encrypt and compute a MAC, using two different keys. (The word MAC stands for Message Authentication Code.) The encryption is what buys you privacy and the MAC is what gets you authenticity. The cost to get privacy-and-authenticity achieved in this way is about the cost to encrypt (with a privacy-only scheme) plus the cost to MAC. If one is encrypting and MACing in a conventional way, like CTR-mode encryption and the CBC MAC, the cost for privacy-and-authenticity is going to be twice the cost for privacy alone, just counting blockcipher calls. Thus people have often hoped for a simple and cheap way to get message authenticity as an almost “incidental’ adjunct to message privacy.

Can you describe how OCB works?

Let M be the message you want to encrypt. Let A be the associated data (if there isn’t any, regard it as the empty string). Let K be the OCB encryption key, which is just a key for the underlying blockcipher, AES. Let N be the 96-bit nonce—for example, a counter that gets incremented with each message you encrypt.

Let’s first look at the setting when |M| is a positive multiple of 128 bits. Then break M into 128-bit blocks M = M₁...M_m. Encryption then works as shown in the following picture. Read each column top-to-bottom, and then go across left-to-right. We’ll defer describing the Init and Inc functions for just a moment. (These functions depend on K too, but we haven’t reflected that in the notation.) The value Checksum is the 128-bit string Checksum = M₁ ⊕…⊕ M_m. We’ll describe how to compute the value Auth in moment. It’s determined by A and K. The number τ, the tag length of the scheme, is, like the blockcipher E, a parameter of the mode. It is a number 0 ≤ τ ≤ 128. Now the picture:

The ciphertext is the 128m + τ bit string CT = C₁ C₂ … C_m  T.

Let us explain how Init works. (After that, we’ll explain how the function Inc works.) We are given a 96-bit nonce N. We save the last six bits as the number Bottom (a value between 0 and 63) and then we create a 128-bit value Top by prepending to N the the 32-bit constant 0x00000001 and zeroing out the last six bits. Let Ktop = E_K (Top) and let Stretch be the 256-bit string Stretch = Ktop || (Ktop⊕(Ktop<<8)). By S << i we mean the left shift of the 128-bit string S by i positions (leftmost bits vanish, zero bits come in on the right). The value denoted above as Init(N), the initial value for Δ, is the first 128 bits of Stretch << Bottom.

Why all this peculiar stuff? Beyond the fact that one can prove that it does what we want, the intent is very simple: if N is counter, Ktop is going to change only once every 64 calls. As a consequence, if we keep Ktop around as long as needed, then, 63 our of 64 times, all that will be needed to compute Init(N) is a logical operation to extract the lowest six bits of N and then a logical shift of the string Stretch by this many bits. Just a few cycles. The other one time in of 64 we will need a blockcipher call, too. The amortized cost to compute Init, meaning the average cost over a sequence of successive calls, is extremely low, and we don't need to implement anything like a GF(2¹²⁸) multiply.

Now let’s explain how the Inc_i function works. First, for S a 128-bit string, let double(S) = S << 1 if the first bit of S is 0, and let double(S) = (S << 1)⊕135 otherwise (where 135 denotes the 128-bit string that encodes that decimal value). For those of you for whom this means something, double(S) is just the multiplication of S by the field point “x” when using a particular representation for the finite field with 2¹²⁸ points. Given all these K-derived L-values, we set L_∗=E_K(0¹²⁸), L_$=double(L_∗), L[0]=double(L_$), and L[j]=double(L[j]) for all j ≥ 1. Given the above, define Inc_i (Δ) = Δ ⊕L[j] where j = ntz(i) is the number of trailing bits in the binary representation of i. Likewise define Inc_∗(Δ) = Δ⊕L_∗. and Inc_$(Δ) = Δ⊕L_$.

We call the increment function we have described “table-based” because, to implement them, it is natural to precompute a table of 128-bit L_∗, L_$, and L[j]. Then, for each kind of increment, we just xor in the needed value from the table.

Decryption under OCB works in the expected way: given K, N, and CT = C₁ C₂ … C_m  T, recover M in the natural way and recompute the tag T* that “should” be at the end of CT. Regard M as the (authentic) underlying plaintext for CT if T = T*. Regard the ciphertext as invalid if T ≠ T*.

When |M| is not a positive multiple of 128 bit we process the final block a little differently. This time we break the plaintext M into blocks M = M₁...M_m M_∗ where |M_i| = 128 and 0 ≤ |M∗| < 128. Computation works as in the following picture. We redefine Checksum as Checksum = M₁ ⊕…⊕ M_m ⊕ M_∗ 10* where the M_∗ 10* notation means to append a single 1-bit and then the minimum number of 0-bits to get the string to be 128 bits.

Finally, I’ll describe how to compute Auth, the 128-bit string one gets by processing the associated data A. As before, we distinguish two cases, when A is or is not a multiple of 128 bits. The picture below shows the two settings. The increment function Inc is just as before, the only thing that is different is the initial value of Δ, which is Δ = Init = 0¹²⁸. When A is the empty string, the value returned is Auth = 0¹²⁸.

Are there different versions of OCB?

I don’t like to change an algorithm I’ve put out; there should be a compelling reason to do so. Let me describe what was significant with each algorithm in the chain.

OCB1 — From the ACM CCS 2001 paper by Rogaway, Bellare, Black, and Krovetz.

The scheme my team first defined built on the ideas of Charanjit Jutla’s IAPM. OCB1 brought to the table an ability to handle arbitrary-length plaintexts, doing so with minimal expansion in the length of the ciphertext. For make this happen, message padding could not be used. Also, IV requirements were minimized; the IV only had to be a nonce. The number of blockciphers calls was reduced to m+2 for encrypting an m-block message. We made do with a single underlying blockcipher key. The increment function was made simpler and more efficient than what Jutla had described.

OCB2 — From the ASIACRYPT 2004 paper by Rogaway.

Mode OCB1 had a defect that practitioners were quick to point out: it had not been designed to natively handle associated-data (AD). Associated-data refers to stuff, say a message header, that needs to be authenticated but should not encrypted. Thanks to Burt Kaliski, of RSA, for first bringing to my attention the need for good AD support. With OCB2 I added in support for AD. I also implemented a new way of doing the increment (Inc) function, using doubling instead of a table-based approach. I had thought that doing increments by doubling would make for a faster scheme. Finally, I recast things in the tweakable-blockcipher setting that had been suggested earlier by Liskov, Rivest, and Wagner.

OCB3 — From the FSE 2011 paper by Krovetz and Rogaway.

The final version of OCB goes back to a table-based approach for incrementing offsets (the Δ-values); experimental findings made it clear that doubling was not the win that I had thought. Beyond this, we (usually) shave off one blockcipher call and (usually) eliminate the blockcipher latency that we used to suffer two or three times. McGrew and Viega had complained about these two defects in a 2004 paper of theirs. In doing this new work Krovetz and I wanted to demonstrate that the extra blockcipher call and the extra bit of latency were inessential aspects of the basic design. We also wanted to see if these matters actually mattered. We found that our changes did speed things up, although the improvement is not profound.

The changes from OCB1 to OCB2 to OCB3 aren’t really all that big, so why have I bothered to continue to refine this mode?

• One answer is that I regard authenticated-encryption as one of the crucial “outputs” of the cryptographic community; it is one a handful of interfaces and abstractions where a cryptographer can create something that may actually get used and make a difference. Given the primitive’s importance, it seems to me that, in some sense, my community has failed if we do not deliver, and get into popular use, the best AE schemes that we can devise.

• Beyond this, I kind of got obsessed. I wanted to achieve AE just as cleanly and efficiently as could be. Even if a scheme was practical and record-setting fast, it didn’t seem enough if it could be made faster or more elegant. It was an accident—yet it seems a fitting fact—that OCB looks a lot like OCD.

If you implement OCB, please use the final version, OCB3. In time, I hope the name OCB, when understood to be a particular algorithm, will be understood to mean OCB3.

What are some of OCB’s properties?

1. OCB uses an amortized m + a + 1.016 blockcipher calls, where m is the blocklength of the plaintext M and a is the blocklength of the associated data A. This assumes a counter nonce. (In the worst case, when the nonce is not a counter, the 1.016 constant becomes the number 2.)
2. If the header A is fixed during a session then, after preprocessing, there is effectively no cost to have A authenticated: the mode will use m + 1.016 blockcipher calls regardless of |A|.
3. OCB is fully parallelizable: its blockcipher calls may be performed simultaneously. (There is a dependency of the first block on the nonce-associated blockcipher call one time in 64.) Thus OCB is suitable for encrypting messages in hardware at the highest network speeds, and it helps avoid pipeline stalls when implemented in software. This is especially important in the presence of new AES instructions on Intel processors. The parallelizability of OCB makes it suitable for use with bitsliced AES implementations, too.
4. Assuming the underlying blockcipher is not susceptible to timing attack, natural implementations of OCB would not be, either.
5. OCB is on-line: one need not know the length of A or M to proceed with encryption, and one need not know the length of A or C to proceed with decryption.
6. One can truncate the tag T to any number of bits and see the expected behavior. For example, if one wants to use τ=32 bit tags, the adversary will be able to forge each ciphertext with probability 1/2³², but low query-complexity or low computing-time attacks will not exist—in contrast, say, to GCM (see the Ferguson attack).
7. OCB can encrypt messages of any bit length. Messages don’t have to be a multiple of the blocklength, and no separate padding regime is ever used. No bits are wasted in the ciphertext due to padding; ciphertexts of of “minimal” length.
8. OCB allows arbitrary associated-data A to be specified when one encrypts or decrypts a string. This string will be authenticated but not encrypted.
9. Encryption and decryption depend on a nonce N, which must be selected as a new value for each encryption. The nonce need not be random or secret. A counter will work fine. Nonces may have any number of bits less than 128. The recommendation is to always use a 96-bit nonce.
10. OCB uses a single key K for the underlying blockcipher, and all blockcipher calls are keyed by K.
11. The main computational work beyond the blockcipher calls consists of three 128-bit xors per block.
12. Key-setup would typically involve just a single blockcipher call and some doubling operations.
13. OCB can be implemented to run in very little memory.
14. OCB avoids 128-bit addition, which is endian-biased and can be expensive in software or dedicated hardware. In general, OCB is nearly endian-neutral.
15. OCB respects word-alignment in the message and the header.
16. OCB enjoys provable security. One must assume that the underlying blockcipher is secure in the customary (strong PRP) sense. Security falls off in s²/2¹²⁸ where s is the total number of blocks one acts on. A very strong form of privacy is achieved: nonce-based indistinguishability from random bits. Likewise, a very strong from of authenticity is achieved: nonce-based authenticity of ciphertexts.
17. OCB nicely supports incremental interfaces. The processing of each 128-bit block of plaintext is independent of whether or not this is the final block of plaintext.
18. The only parameters of OCB are the blockcipher E and the tag length τ. The message space and nonce space are independent of these choices.

• The original OCB paper. The proceedings version is in ACM CCS (2001) and the journal version is in ACM TISSEC (2003).
• A paper about dealing with associated data. Appears in ACM CCS (2002).
• A paper to develop the message authentication code, PMAC, that shaped the way AUTH is computed in OCB. Appears in EUROCRYPT (2002).
• A paper about efficiently realizing tweakable blockciphers, and about using tweakable blockcipher to improve OCB. Appears in ASIACRYPT (2004).
• Finally, a timing study about AE modes, along with refinements to get to the final version of OCB. Appears at FSE 2011.

AES actually comes in three flavors: AES128, AES192, and AES256. I like AES128.

If you use OCB with a blockcipher having a 64-bit blocklength instead of a 128-bit blocklength, beware that you’ll get a worse security bound. You’ll need to change keys well before you encrypt 2³² blocks (as with all well-known modes that use a 64-bit blockcipher).

Should one write “OCB-AES” or “AES-OCB”?

• OCB1 is an optional method in the IEEE 802.11i standard, where it is now called WRAP (Wireless Robust Authentication Protocol). The old name was AES-OCB.
• OCB2 is specified in ISO/IEC 19772:2009. (The standard also includes AE schemes CCM, GCM, EAX, and two further schemes.)
• OCB3 is an Internet Draft; it has not yet been officially adopted.

What did Jutla do?

I am not the first to give an integrated authenticated-encryption mode of operation. Charanjit Jutla, from IBM Research, was the first to publicly describe a correct blockcipher-based mode of operation that combines privacy and authenticity at a small increment to the cost of providing privacy alone. Jutla’s scheme appears as IACR-2000/39. He went on to publish the work in a EUROCRYPT 2001 paper. A Journal of Cryptology version appeared in 2008.

Jutla actually described two schemes: one is CBC-like (IACBC) and one is ECB-like (IAPM). The latter is what OCB builds on. OCB uses high-level ideas from Jutla’s scheme but adds in many additional tricks.

What did Gligor and Donescu do?

One of the contributions of [Gligor, Donescu] is the use of mod-2ⁿ arithmetic in this context. In particular, Jutla had suggested the use of mod-p addition, and it was non-obvious that moving into this weaker algebraic structure would be OK. Later versions of [Gligor, Donescu; 18 August 2000] have added in new schemes. Following Jutla, [Gligor, Donescu; October 2000] mention a parallelizable mode of operation similar to Jutla’s IAPM. Following my own work, [Gligor, Donescu; April 2001] updated their modes to use a single key and to deal with messages of arbitrary bit length.

What is a nonce and why do you need one?

In OCB, you must present a nonce each time you want to encrypt a string. When you decrypt, you need to present the same nonce. The nonce doesn’t have to be random or secret or unpredictable. It does have to be something new with each message you encrypt. A counter value will work for a nonce, and that is what is recommended. It doesn’t matter what the counter is initialized to. In general, a nonce is a string that is used used at most one time (either for sure, or almost for sure) within some established context. In OCB, this “context” is the “session” associated to the underlying encryption key K. For example, you may distribute the key K by a session-key distribution protocol, and then start using it. The nonces should now be unique within that session. Generating new nonces is the user’s responsibility, as is communicating them to the party that will decrypt.

A nonce is nothing new or strange for an encryption mode. All encryption modes that achieve a strong notion of privacy need to have one. If there were no nonce there would be only one ciphertext for each plaintext and key, and this means that the scheme would necessarily leak information (e.g., is the plaintext for the message just received the same as the plaintext for the previous message received?). In CBC mode the nonce is called an IV (initialization vector) and it needs to be adversarially unpredictable if you’re going to meet a strong definition of security. In OCB we have a weaker requirement on the nonce, and so we refrain from calling it an IV.

What happens if you repeat the nonce? You’re going to mess up authenticity for all future messages, and you’re going to mess up privacy for the messages that use the repeated nonce. So don’t do this. It is the user’s obligation to ensure that nonces don’t repeat within a session.

We note that all conventional encryption modes fail, usually quite miserably, if you repeat their supplied IV/nonce. Only recently (2006) did cryptographer’s develop a notion for an encryption scheme being maximally “resilient” to nonce-reuse. The notion is due to Tom Shrimpton and me and we developed a nice scheme, SIV, to solve this problem. But it’s a conventional composed scheme: half the speed, or worse, of OCB. SIV makes a nice alternative to a composed scheme like CCM, EAX, offering comparable performance but a better security guarantee.

Is there code available? Is it free?

In correctly coding OCB, I think the biggest difficulty is endian problems. The spec is subtly big-endian in character, a consequence of it’s use of “standard” mathematical conventions. If your implementation doesn’t agree with the reference one, chances are there’s some silly endian error that will take you hours to discover.

Are OCB test vectors available?

Of course it is conceivable that OCB-AES could fail because AES has some huge, unknown problem. But other issues aren’t really of concern. Here we’re in a domain where the underlying definition is simple and rock solid; where there are no “random oracles” to worry about; and where the underlying cryptographic assumptions are completely standard.

Are there competing integrated authenticated-encryption proposals?

• Jutla (2000) propose two modes, IACBC and IAPM. The latter is the parallelizable scheme and is therefore the one to compare to OCB. Various methods are specified for offset generation in IAPM, but none are competitive with OCB. Jutla assumes that messages have a multiple of n bits; padding is used, presumably, to deal with other lengths. Once a padding regime is added, say obligatory 10*-padding, the length of ciphertexts will be longer than OCB ciphertexts any time that the message being encrypted is a non-multiple of 16 bytes. IAPM uses twice the key material of OCB. Associated data is not handled.
• Gligor and Donescu (2000) propose four authenticated-encryption schemes, which the authors call XCBC$-XOR, XCBC-XOR, XCBCS-XOR, and XECBS-XOR. Only the last of these modes is parallelizable. The addition of a parallelizable scheme came subsequent to the publication of Jutla’s work, and XECBS-XOR is similar to Jutla’s IAPM. XECBS-XOR uses mod 2ⁿ addition instead of mod-p addition. This difference might suggest an efficiency improvement, but this is unclear, as [Jutla] uses one mod-p addition and three 128-bit xors while [Gligor, Donescu] uses three 128-bit additions and one 128-bit xor. One expects the use of an additive ring (integers mod 2ⁿ) instead of a field (GF(p) or GF(2ⁿ)) to worsen any possible security bound by at least a log factor. No proof has been given for this mode. Following my own work, [Gligor, Donescu] includes techniques so as to use a single key and to deal with messages of arbitrary bit length. But the techniques are not pushed as far as with OCB and there is ciphertext-expansion for all messages which are a non-multiple of the 16 bytes.

There are various pitfalls people run into when trying to do a homebrewed combination of privacy and authenticity. Common errors include: (1) a failure to properly perform key separation; (2) a failure to use a MAC that is secure across different message lengths; (3) omitting the IV from what is MACed; (4) encrypting the MACed plaintext as opposed to the superior method (at least with respect to general assumptions) of MACing the computed ciphertext. For all of these, I cannot advise people to roll-their-own authenticated-encryption scheme.

To date, the most significant two-pass authenticated encryptions schemes are CCM and GCM. Some other techniques include SIV and EAX. All of these modes comprise IP-free means of performing authenticated-encryption with associated-data. I’ll focus on CCM and GCM:

• CCM is an authenticated-encryption mode designed by Housley, Ferguson, and Whiting. It’s inspired by the generic composition of counter mode encryption and the CBC MAC (but CCM is not in fact an instance of generic composition). CCM was developed as a less-efficient but IP-free alternative to OCB. It is specified in NIST Special Publication 800-38C. It’s kind of a cobbled-up thing, but the it got into 802.11i, and then other standards. The bounds are good an no significant weaknesses are known. Most criticisms focus on efficiency concerns, including the one I wrote with David Wagner, A Critique of CCM.

• GCM is an authenticated-encryption mode designed by McGrew and Viega. It combines a privacy-only encryption mechanism (CTR mode) with a Carter-Wegman MAC, the latter based on multiplication in the finite field with 2¹²⁸ points. The initial purpose of GCM was to have a parallelizable, hardware-efficient, and patent-free AEAD scheme. Being parallelizable means that it is useful for high-speed hardware-based applications. Having to implement multiplies in GF(2¹²⁸) can be slow unless large tables are used, but it’s pretty fast if you use such tables, and hardware chip area for GF(2¹²⁸) multiplication can be low. New Intel chips support a “carryless multiply” instruction meant to help the mode run fast. GCM is specified in Draft NIST publication 800-38D.

We also elaborate on SIV, a deterministic or misuse-resistant authenticated-encryption mode. It was designed by Rogaway and Shrimpton to solve the “key wrap” problem. When used as a nonce-based AEAD scheme, SIV has the unusual property that it doesn’t “break” if a nonce should get reused: all that happens is that repetitions of this exact (nonce, AD, plaintext) are revealed. The mode can also be used without any nonce and, when used as such, all it reveals are repetitions in (nonce, plaintext) pairs. SIV suffers from a latency problem (unavoidable for the deterministic or misuse-resistant AEAD goal): one must not only make two passes over the input, but one cannot output any ciphertext bits until all plaintexts bits are read. SIV is described in a EUROCRYPT 2006 paper and an associated spec.

The main advantage of OCB over CCM, GCM, and other composed schemes is software speed. See the performance page for data.

Is OCB patented?

There are further patents in the AE space. I would single out those of Gligor and Donescu (VDG) and Jutla (IBM): 6,963,976, 6,973,187, 7,093,126, and 8,107,620. Do the claims of these patents read against OCB? It is difficult to answer such a question. In fact, I suspect that nobody can give an answer. It seems extremely subjective.

Do I need a license?

Please see the separate licensing page for information on this question.

Who is the author of this webpage?

I am, Phil Rogaway, a professor in the Department of Computer Science at the University of California, Davis. I have also been a regular visitor to universities in Thailand, most often at the Department of Computer Science at Chiang Mai University.

For 20 years I’ve worked to develop and popularize a style of cryptography I call practice-oriented provable security. This framework is a perfect fit to the problem of designing an authenticated-encryption scheme. One of the “outputs” of practice-oriented provable security has been cryptographic schemes that are well-suited standards. In particular, I am co-inventor on the schemes known as CMAC, DHIES, EAX, OAEP, PSS, and XTS, which are in standards from ANSI, IEEE, ISO, and NIST. The kind of academic work I do can be seen by looking at dblp or google Scholar.