OCB: Background

  1. What is OCB?
  2. Who invented OCB?
  3. Can you please describe OCB?
  4. What are some of OCB's properties?
  5. What papers deal with OCB?
  6. What is a tweakable blockcipher and what does it have to do with OCB?
  7. Is the notion of authenticated-encryption something new?
  8. Is it safe to combine privacy and authenticity?
  9. What does the name stand for?
  10. What blockcipher should I use with OCB?
  11. Should one write "OCB-AES" or "AES-OCB"?
  12. Is OCB in standards?
  13. What did Jutla do?
  14. What did Gligor and Donescu do?
  15. What is a nonce and why do you need one?
  16. Can you compare OCB and PMAC?
  17. Is there an "old version" of OCB?
  18. Is there code available? Is it free?
  19. Are OCB test vectors available?
  20. Is it safe to mandate a new algorithm in a product / standard?
  21. Are there competing one-pass authenticated-encryption proposals?"
  22. Are there competing two-pass authenticated-encryption proposals?"
  23. Is OCB patented?

What is OCB?

OCB is a shared-key encryption mechanism, built from a blockcipher, 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 essentially the same amount of time as other modes, like CBC, achieve privacy alone; or about half the time as "conventional" modes, like CCM, achieve privacy+authenticity. 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 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 header or the associated data, that is authenticated but not encrypted. The nonce-based part of the name means that OCB requires a nonce, such as a counter value, to encrypt each message. OCB does not require random value to encrypt; a counter, say, will work fine. Unlike many other modes, the plaintext provided to OCB can be of any length, as can the associated data, and OCB will encrypt it without first padding it to some convenient-length string (an approach that yields a longer ciphertext).

OCB was designed largely in response to NIST's modes-of-operation activities. OCB was motivated by Charanjit Jutla's mode IAPM, which was the first one-pass authenticated-encryption mode in the cryptographic literature.

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 in this way is about the cost to encrypt plus the cost to MAC. If one is encrypting and MACing in a conventional way, like CBC encryption plus the CBC MAC, the cost for privacy-and-authenticity is about twice the cost for privacy alone. Thus people have often hoped for a simple and cheap way to get message authenticity as an incidental adjunct to message privacy.

Who invented OCB?

I did (Phil Rogaway). But I had help from Mihir Bellare, John Black , and Ted Krovetz. Among other important contributions, they helped to shoot down my earlier, buggy attempts, and to work out the highly technical proofs.

Who am I? I'm a Professor in the Department of Computer Science at the University of California, Davis. I am also a regular visitor to the Department of Computer Science, Faculty of Science, at Chiang Mai University. For the last 15 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 highly appropriate for standards, and several of my schemes have found their way into cryptographic standards. In particular, I am co-inventor on the schemes known as CMAC, DHIES, OAEP, PSS, and XEX, which are in recommendations, standards, or draft standards of ANSI, IEEE, ISO, NIST, PKCS, SEC, and SET.

Can you please describe OCB?

The specification document is easy to read, but I'll describe the algorithm here and draw a pretty picture. Assume you're using a blockcipher of E=AES. (You can choose whichever key length you want.) First a bit of notation. When S is a 128-bit string I'll write S<<1 for the left shift of S by 1 bit (where the first bit vanishes and a 0 comes into the last bit). Let 2S ("double S") be S<<1 if the first bit of S is 0, and let it be (S<<1) xor 0x00000000000000000000000000000087 if the first bit of S is 1. Let 3S be 2S xor S, and let 5S be (2(2S)) xor S. For those of you for whom this means something, 2S, 3S, and 5S amount to multiplication of S by x, x+1, and x2+1 within the field with 2128 elements; 2, 3, and 5 name points in the finite field with representations 00...010, 00...011, and 00...101. Let len(x) be the 128-bit string that encodes, in binary, the length of the string x. If S is a string of at most 128 bits, let S 0* be the 128-bit string you get by appending enough 0-bits to get to a 128-bit string.

Let M be the message you want to encrypt, let H be an optional message header associated to M, let K be the OCB encryption key, which is just an AES key, and let N be a 128-bit nonce (also called an IV). First break M into 128-bit chunks M1...Mm-1 and a final chunk Mm that may have fewer than 128-bits. Encryption then works as shown in the following picture. Read each column top-to-bottom, and then go across left-to-right. The xor of Pad and Mm means to xor Mm with the first |Mm| bits of Pad. The Checksum is the value M1 xor M2 xor ... xor Mm-1 xor (Cm0* xor Pad). We'll describe the value Auth in moment. You can ignore it for now, which is exactly what happens if H is empty.

The result of encrypting M using K, H, and N is the "ciphertext core" C = C1 ... Cm together with the tag Tag: The ciphertext is (C, Tag) = OCBK(N,M). If one wants to save some bits of ciphertext, it is fine to use a prefix T of Tag and send (C, T).

To decrypt a ciphertext (C, T), do the reverse process, making sure that T is as expected. If not, regard the presented ciphertext as invalid.

Now I will describe how to compute Auth. This string is just 0, the string of 128 zero bits, if the header H is empty. Otherwise, we'll use an algorithm called PMAC. Break the header H into blocks H1...Hm where all but first of these blocks is 128 bits, and Hm has at most 128 bits. If Hm is a full 128-bits, then do the algorithm shown on the left-hand-side of the picture below. If Hm has fewer than 128-bits, do the algorithm on the right-hand-side of the picture below. The algorithms are identical until what happens at the very end (so one doesn't need to |Hm| in advance). The notation Hm10* means to append a 1 bit and then the minimum number of 0-bits to get to 128 bits.

What are some of OCB's properties?

OCB has been designed to simultaneously have lots of desirable properties. These include the following.
  1. 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 needed. No bits are wasted in the ciphertext due to padding.
  2. OCB allows an arbitrary header H to be specified when one encrypts or decrypts a string. This string will be authenticated but not encrypted.
  3. When message M is encrypted in the presence of H, the resulting ciphertext core C has same length as M. There is also generated an n-bit authentication tag Tag, where n is the blocklength of the blockcipher. If desired, the tag can be truncated to a string T having a smaller number t of bits. The ciphertext is (C,T).
  4. Encryption and decryption depend on an n-bit 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.
  5. OCB encryption protects the privacy and authenticity of M and the authenticity of H and N. The degree of authenticity protection depends on t, the number of bits used in the tag.
  6. OCB uses m + h + 2 blockcipher calls, where m is the blocklength of M and h is the blocklength of H.
  7. If the header H is fixed during a session then, after preprocessing, there is effectively no cost to have H authenticated: the mode will use m+2 blockcipher calls regardless of |H|.
  8. OCB uses a single key K for the underlying blockcipher, and all blockcipher calls are keyed by K.
  9. OCB is on-line: one need not know the length of H or M to proceed with encryption, and one need not know the length of H or C to proceed with decryption.
  10. OCB is parallelizable: the bulk of its blockcipher calls may be performed simultaneously. Thus OCB is suitable for encrypting messages in hardware at the highest network speeds.
  11. The main computational work beyond the blockcipher calls consists of one doubling operation and three xors for each n-bit block. Doubling consists of one shift and one conditional xor.
  12. If the header H is empty, no key-setup is necessary or useful for OCB. If the header H is nonempty, key-setup is a single blockcipher call.
  13. OCB needs very little memory to run.
  14. OCB avoids 128-bit addition (which is endian-biased and can be expensive in software or dedicated hardware). It uses xors instead.
  15. OCB is nearly endian-neutral.
  16. OCB respects word-alignment in the message and the header.
  17. OCB enjoys provable security. One must assume that the underlying blockcipher is secure in the customary (strong PRP) sense. Security falls off in s2/2n where s is the total number of blocks one acts on.
  18. 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.
  19. OCB is simple to understand and prove correct if one learns the underlying theory. It uses GF(2128) arithmetic but it all comes down to some xors and shifts. One doesn't have to understand the mathematics to implement the scheme.
  20. OCB is parameterized by a blockcipher. Any blockcipher can be used. I suggest AES128. A blocksize of less than 128 bits is not recommended.

What papers deal with OCB?

OCB was developed over a sequence of four academic papers, published between 2001 and 2004: The papers and a spec are available on the documentation web page.

While OCB is not a contribution I am particularly known for, it's still a reasonably well-known algorithm, with about 250 references in the literature.

What is a tweakable blockcipher and what does it have to do with OCB?

In its current (but not initial) form, OCB uses the idea of a tweakable blockcipher, described by [Liskov, Rivest, and Wagner] and further developed in [offsets]. In a nutshell, the idea is to design a mode of operation assuming that one has available a blockcipher that depends not only on a key and an input block, but also on a tweak. Later, this "tweakable" blockcipher is instantiated using a conventional blockcipher. Tweaks are arranged to increase monotonically. I will not explain the idea further, since it is not needed to understand OCB, but for those who already understand the idea, I will re-draw OCB using the tweakable-blockcipher abstraction:

The first set of tweakable-blockciphers (in purple) need to be secure against chosen-ciphertext attack. OCB uses the construction XEX to realize these. The second set of tweakable-blockciphers (in orange) only need to be secure against chosen-plaintext attack. OCB uses the construction XE for these. Below I redraw the PMAC portion of OCB using the same tweakable-blockcipher abstraction.

Is the notion of authenticated-encryption something new?

Yes and no. The general idea to combine privacy+authenticity is folklore, and lots of attempts can be found in the security literature and in systems. Nobody was solving this problem correctly, but nobody in the cryptographic community was paying any attention. Bellare and I finally presented definitions for the goal in an ASIACRYPT 2000 paper, while the same definitions independently appeared in a EUROCRYPT 2000 paper by Katz and Yung. The ASIACRYPT 2000 paper by . Bellare and Namprempre looks at the notion in greater depth. It's pretty common that a folklore cryptographic goal may fail to get a proper cryptographic treatment for a long time.

Is it safe to combine privacy and authenticity?

Some people think that it's "dangerous" to try to combine privacy and authenticity. They believe that you won't get the expected degree of authenticity from the combined privacy/authenticity transformation. This belief springs from the history of wrong attempts in trying to add in authenticity to encryption schemes. It also comes from the realization that many people (including some well-known security folks) used to believe, wrongly, that standard ways to get privacy, maybe with "redundancy" thrown in, already implied authenticity.

Anyway, these past errors have nothing to do OCB. There, privacy and authenticity are correctly combined. This is proven. There's no danger involved when you correctly combine privacy and authenticity. But there's a big danger if you try to do this at home. This is a very tricky problem, and a home-grown solution will invariably be wrong.

What does the name stand for?

It stands for offset codebook. That's a (highly abbreviated) operational description of what is going on in the mode: for most message blocks, one offsets the block, applies the blockcipher, and then offsets the result once again.

What blockcipher should I use with OCB?

You can use OCB with any blockcipher that you like. But the obvious choice is AES.

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 232 blocks (as with all well-known modes that use a 64-bit blockcipher).

Should one write "OCB-AES" or "AES-OCB"?

I prefer OCB-AES (or OCB-AES128), going from high-level protocol on down. Just like HMAC-SHA1.

Is OCB in standards?

OCB 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.

OCB was submitted to NIST but has, so far, not been adopted as a NIST Recommendation. According to William Burr, NIST didn't want to standardize an authenticated-encryption blockcipher mode with associated IP.

What did Jutla do?

I am not the first to give a one-pass authenticated-encryption mode of operation. That honor falls on Charanjit Jutla, from IBM Research. Jutla was the first to publicly describe a correct blockcipher 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.

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?

Virgil Gligor and Pompiliu Donescu have also described an authenticated-encryption mode, XCBC, in [Gligor, Donescu; 18 August 2000] (Postscript or pdf, from Gligor's homepage). The mode is not similar to OCB, but it is similar to Jutla's IACBC. We do not know the history of Gligor and Jutla in devising their schemes, but Jutla's scheme was publicly distributed before Gligor's. OCB was invented after both pieces of work made their debut.

From my reading of the papers, the main new contribution of [Gligor, Donescu] is the suggested use of mod-2n 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 128-bit nonce each time you want to encrypt a string (assume we're using a 128-bit blockcipher). When you decrypt, you need to present the same nonce. The nonce doesn't have to be random or secret or unpredictable. A counter will work well. It does have to be something new with each message you encrypt. 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 counter makes a perfectly good nonce, as does a random value.

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 lower 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, has been developed to solve this problem. But it's a conventional two-pass authenticated-encryption scheme: half the speed of OCB. SIV makes a nice alternative to two-pass modes like CCM or EAX, offering comparable performance but a better security guarantee.

Can you compare OCB and PMAC?

OCB provides privacy and authenticity, whereas PMAC gets you authenticity alone. PMAC is used internally inside of OCB, to authenticate the message header.

Is there code available? Is it free?

Yes there's code and yes it's free. See the OCB home page.

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.

Is there an "old version" of OCB?

There is. The "original" version of OCB, which I sometimes call OCB 1.0, is different from the "current" version of OCB, which is OCB 2.0. I don't like to change an algorithm I've put out, but there were compelling reasons to do so: There were no security issues that motived the change from OCB 1.0 to OCB 2.0.

OCB 2.0 was first specified in late 2003, when I released a spec for it on these web pages. This FAQ focuses on OCB 2.0.

I had for a brief period of time been calling OCB 2.0 by the name "AEM", for "advanced encryption mode" or "authenticated-encryption mode". But I stopped using that name. Please call the algorithm OCB.

Are OCB test vectors available?

Yes, for OCB-AES128. See the OCB home page.

Is it safe to mandate a new algorithm in a product / standard?

In the past, one had to wait years before using a new cryptographic scheme; one needed to give cryptanalysts a fair chance to attack the thing. Assurance in a scheme's correctness sprang from the absence of damaging attacks by smart people, so you needed to wait long enough that at least a few smart people would try, and fail, to find a damaging attack. But this entire approach has become largely outmoded, for schemes that are not true primitives, by the advent of provable security. With a provably-secure scheme assurance does not stem from a failure to find attacks; it comes from proofs, with their associated bounds and definitions. Our work includes a proof that OCB-E is secure as long as blockcipher E is secure (where E is an arbitrary block cipher and "secure" for OCB-E and secure for E are well-defined notions).

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 one-pass authenticated-encryption proposals?

Yes, there are proposed schemes from Charanjit Jutla (IBM) and from Virgil Gligor and Pompiliu Donescu (VDG). In my view, there is no realistic one-pass alternative to OCB, and no one-pass proposal besides OCB has gotten any "traction" in products or standards. But various two-pass schemes are reasonable alternatives to OCB when speed or power consumption are a secondary concern.

Are there competing two-pass authenticated-encryption proposals?

Absolutely. The traditional approach for achieving authenticated-encryption was to use generic composition. Using separate keys, you should encrypt the plaintext and then MAC the resulting ciphertext. You can use any encryption scheme and any MAC that you like, and the composite scheme is guaranteed to do what it should do. To offer the same basic "service" as OCB you'll need, in the end, to do something like this. For privacy, use CBC mode with ciphertext-stealing and an IV derived by enciphering the nonce. For authenticity, use the CBC MAC variant known as CMAC. Use standard key separation to make all the needed keys. Make sure the MAC is taken over the IV of the encryption scheme.

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 go 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, GCM, and SIV. There's also a nice scheme called EAX, but I consider it to have been supplanted by SIV. All of these modes comprise IP-free means of performing authenticated encryption with associated data. I'll describe the point of each mode in turn.

The main advantage of OCB over the above is speed; it's roughly twice as fast as CCM or SIV. In a low-power environment, it will use roughly half the power. For high-performance environments, OCB is parallelizable. OCB is faster than GCM, but it is hard to say by how much; it could be more than a factor of two or less, because implementations of GF(2128) arithmetic will vary enormously. OCB has some further advantages over competing two-pass schemes. For a fuller comparison of OCB to CCM see the Rogaway and Wagner critique of CCM and the EAX paper by Bellare, Rogaway, and Wagner.

Is OCB patented?

 Yes, it is. Two patents on OCB have been granted so far: US patent 7,046,802 (Rogaway, May 16, 2006), and its CIP 7,200,227 (Rogaway, April 3, 2007), both titled "Method and Apparatus for Facilitating Efficient Authenticated Encryption". I did not file for patent protection outside of the USA. If you want to use OCB in a commercial product sold in the US, you'll need to get a license from me. I license OCB under fair, reasonable, and non-discriminatory terms. Licensees pay a modest one-time fee. A few companies have bought licenses.

Some years back I wrote a patent grant to try to ensure that IP of mine wouldn't be an obstacle to using OCB within code released under GNU GPL. If you have another use for OCB in mind where you believe that a paid-up license would be inappropriate, please write to me to explain.

There are three other known US patents dealing with authenticated encryption: US patent 6,963,976 (Jutla, IBM, Nov 8, 2005); US patent 6,973,187 (Gligor and Donescu, VDG Inc., Dec 6, 2005); and US patent 7,083,126 (Jutla, IBM, Aug 15, 2006). It's probably not my place to advise on this web page if any of these patents might read against OCB.


Back to the OCB homepage