The OCB Mode Algorithm

The OCB Mode Algorithm

Introduction

Most authenticated encryption modes do two jobs with two tools. CCM runs a MAC and then encrypts. GCM runs counter mode and then a hash. OCB does both jobs at once, with one tool, and with very little extra work. It takes about one AES call per block of message, plus one for each block of associated data and one more at the end.

The name stands for Offset Codebook. The idea is simple. Every block of the message is XORed with a secret offset, run through AES, and XORed with the same offset again. Each block gets a different offset, so the blocks do not leak patterns the way plain ECB mode does. The offsets come from a few doubled values, which are cheap to compute.

Table of Contents

• History and Patents
• The Offset Idea
• Key-Dependent Values
• From Nonce to Starting Offset
• Associated Data: HASH
• Encryption
• Decryption
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History and Patents

Phillip Rogaway designed OCB, with credit to Mihir Bellare, John Black, and Ted Krovetz. The first version appeared in 2001. A second version, OCB2, followed in 2004 and added associated data, and it was standardized in ISO/IEC 19772. A third version, OCB3, came in 2011 with small speed improvements.

RFC 7253, published in May 2014, specifies OCB3 with AES. Wikipedia notes that this version also encodes the tag length into the nonce. This guide covers the RFC 7253 version.

OCB was patented, and for many years its use was limited by licensing. Rogaway offered free licenses for GPL software, non-commercial and non-military projects, and OpenSSL. According to Wikipedia, he intentionally abandoned the OCB patents in 2021, and the mode is now free for anyone to use.

The Offset Idea

Plain ECB mode encrypts every block the same way, so equal blocks give equal outputs. OCB fixes that by XORing each block with an offset before and after AES:

C_i = Offset_i  xor  AES( P_i  xor  Offset_i )

The offsets are secret and different for every block. Inside OCB, they are built with a trick. The first offset comes from the nonce. Each next offset is the previous one XORed with a value L_ntz(i), where ntz(i) is the number of trailing zero bits of the block number i. That gives a short list of L values that is used again and again:

Block	1	2	3	4	5	6	7	8
ntz(i)	0	1	0	2	0	1	0	3

Every offset can also be computed directly from the starting offset and the L values, so blocks can be processed in parallel. This design is called a tweakable block cipher, and OCB turns plain AES into one by using the offset as the tweak.

Interactive Visualizer

The visualizer above runs this exact algorithm. Pick a tag size, then enter an AES key, a nonce, associated data, and a message in hex. Each row of the log is one AES call, with the offset, the input, and the output. To decrypt, paste the ciphertext and tag into the message box and click Decrypt. Change one hex digit first, and the tag check fails.

Key-Dependent Values

Before anything else, OCB computes a few values from the key alone:

L_*  = AES(K, 0)
L_$  = double(L_*)
L_0  = double(L_$)
L_i  = double(L_(i-1))

The function double multiplies a 128-bit value by x in the field GF(2¹²⁸). It shifts the value left by one bit, and if a one bit fell off the end, it XORs the result with 0x87. The other AEAD guides on this site use the same operation. The values L_* and L_$ serve special purposes for partial blocks and for the tag, and L_0, L_1, and so on provide the offsets.

From Nonce to Starting Offset

The nonce can be 1 to 15 bytes long. OCB first formats it as a 128-bit string. The string holds the tag length mod 128 as a 7-bit number, then zeros, then a single one bit, and then the nonce:

Nonce = num2str(TAGLEN mod 128, 7) || zeros(120 - bitlen(N)) || 1 || N

Putting the tag length into the nonce means that outputs for different tag lengths are unrelated. The last six bits of the formatted nonce are called bottom. The rest, with six zero bits appended, is encrypted to get Ktop. Then OCB stretches Ktop from 128 to 192 bits:

Stretch  = Ktop || (Ktop[1..64] xor Ktop[9..72])
Offset_0 = Stretch[1 + bottom .. 128 + bottom]

The starting offset Offset_0 is a 128-bit window of Stretch, which begins bottom bits in. Two nonces that share all but the last six bits share the same Ktop, so a counter nonce costs only one extra AES call for every 64 messages.

Associated Data: HASH

OCB authenticates associated data with a function called HASH, which is similar to the PMAC mode. It starts at an offset of zero. For each full 16-byte block A_i of associated data, it updates the offset and adds an AES output to a running sum:

Offset_i = Offset_(i-1) xor L_ntz(i)
Sum      = Sum xor AES( A_i xor Offset_i )

A final partial block A_* is padded with a one bit and zeros, and it is offset with L_*. If there is no associated data, the sum is 128 zero bits.

Encryption

Encryption takes each full block P_i, updates the offset, applies the offset-AES-offset step, and XORs the plaintext into a running checksum:

Offset_i   = Offset_(i-1) xor L_ntz(i)
C_i        = Offset_i xor AES( P_i xor Offset_i )
Checksum_i = Checksum_(i-1) xor P_i

A final partial block P_* does not go through AES at all. OCB encrypts the offset Offset_* = Offset_m xor L_* to make a pad, and it XORs the pad with the data. The ciphertext of the partial block is exactly as long as the plaintext. The padded plaintext, P_* followed by a one bit and zeros, goes into the checksum.

The tag then comes from one more AES call over the checksum and the last offset, combined with the hash of the associated data:

Tag = AES( Checksum xor Offset xor L_$ )  xor  HASH(A)

The output is the ciphertext followed by the tag, cut to the chosen tag length.

Decryption

Decryption mirrors encryption, but full blocks need the inverse of AES:

P_i = Offset_i xor AES_decrypt( C_i xor Offset_i )

A partial final block is handled in the same way as in encryption, with the same pad. The receiver rebuilds the checksum from the recovered plaintext, computes the tag, and compares it with the received one. If they differ, the receiver must reveal nothing but the fact that the check failed.

A Worked Example

This is one of the sample results of RFC 7253. The key is 000102030405060708090a0b0c0d0e0f, the nonce is bbaa99887766554433221107, and the associated data and the plaintext are both the 24 bytes 000102030405060708090a0b0c0d0e0f1011121314151617. The tag is 128 bits long. The RFC prints only the final ciphertext for this vector. It does print internal values for another vector, the one with nonce BBAA9988776655443322110F, and my code reproduces those too. The intermediate values below come from my code, which reproduces the RFC output exactly.

Key values. The first value is L_* = AES(K, 0) = c6a13b37878f5b826f4f8162a1c8d879. Doubling it gives L_$ = 8d42766f0f1eb704de9f02c54391b075, then L_0 = 1a84ecde1e3d6e09bd3e058a8723606d and L_1 = 3509d9bc3c7adc137a7c0b150e46c0da.

The starting offset. The tag length 128 is 0 mod 128, so the formatted nonce is 00000001bbaa99887766554433221107. Its last six bits give bottom = 7. Encrypting 00000001bbaa99887766554433221100 gives Ktop = 9862b0fdee4e2dd56dba6433f0125aa2. The stretched window then gives Offset_0 = 31587ef72716eab6dd3219f8092d517d. With a 96-bit tag the formatted nonce would start with c0000001bbaa99887766554433221107, and with a 64-bit tag, 80000001bbaa99887766554433221107.

The header hash. The associated data is one full block and an 8-byte partial block. The offset is L_0 = 1a84ecde1e3d6e09bd3e058a8723606d. The input to AES is 1a85eedd1a38680eb5370f818b2e6e62, and the output is 64a01250ae75280588e97b797a8a0d44. For the partial block, Offset_* = dc25d7e999b2358bd27184e826ebb814, and the padded block is 10111213141516178000000000000000. Its AES output is 55fba8b6da00a819c30a388b4c2e8c30. The XOR of the two outputs is the header hash 315bbae67475801c4be343f236a48174.

The first block. The offset is Offset_1 = Offset_0 xor L_0 = 2bdc9229392b84bf600c1c728e0e3110. The input to AES is 2bdd902a3d2e82b86805167982033f1f, and the output is 377eb25a31e3f8be675a0c3f064eff09. XORing that with the offset gives the first ciphertext block C_1 = 1ca2207308c87c010756104d8840ce19. The checksum is now the first plaintext block, 000102030405060708090a0b0c0d0e0f.

The partial block. The offset becomes Offset_* = ed7da91ebea4df3d0f439d102fc6e969, and its AES output is the pad 42e18460b05db735f1cc5d7e898e4174. The first 8 bytes of the pad, XORed with the 8 plaintext bytes, give C_* = 52f09673a448a122. The padded plaintext is 10111213141516178000000000000000, and the checksum becomes 101010101010101088090a0b0c0d0e0f.

The tag. The input to the last AES call is 702fcf61a1aa782959d595de605a5713, which is the checksum XOR the offset XOR L_$. Its output is f877d8c26424756f1d34b03b3d14610b, and XORing with the header hash gives the tag c92c62241051f57356d7f3c90bb0e07f. The complete output is the ciphertext followed by the tag:

1ca2207308c87c010756104d8840ce1952f09673a448a122c92c62241051f57356d7f3c90bb0e07f

With a 96-bit tag the same inputs give 1d73e5afe027cf258a27ce9baf0bcbde4279d2ebe05e15df5f551abd6df69a5df8093053, and with a 64-bit tag they give ba1ab2466a734885e4804aa823c872f412c2b5bdf3891cecf1e0ecbc89905db1. The ciphertext part is different in each case, because the tag length is part of the nonce.

Python Implementation

This is a complete OCB, working on whole bytes, with nonces of 1 to 15 bytes and tags of 1 to 16 bytes. It uses the same small aes_core.py file as the AES-CCM guide, which has its source. Unlike CCM and SIV, OCB needs AES decryption to decrypt full blocks, and that file includes it.

# ocb.py
#
# OCB, the Offset Codebook mode (OCB3, RFC 7253), with AES.
# OCB encrypts and authenticates in a single pass, using about one block
# cipher call per block of message. Every block is XORed with a secret
# "offset" before and after AES, and the offsets come from a few doubled
# values, so the work can run in parallel. The tag comes from an XOR of all
# the plaintext blocks.
#
# This code works on whole bytes: nonces of 1 to 15 bytes, and tags of 1 to
# 16 bytes. The RFC allows any number of bits.

from aes_core import AES

MASK128 = (1 << 128) - 1


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


def double(block):
    """Multiply by x in GF(2^128): shift left, xor 0x87 when a one falls off the left end."""
    value = int.from_bytes(block, "big")
    carry = value >> 127
    value = (value << 1) & MASK128
    if carry:
        value ^= 0x87
    return value.to_bytes(16, "big")


def ntz(n):
    """Number of trailing zero bits of a positive integer."""
    return (n & -n).bit_length() - 1


class Tables:
    """The key-dependent values L_*, L_$ and L_0, L_1, ..."""

    def __init__(self, aes):
        self.l_star = aes.encrypt_block(bytes(16))
        self.l_dollar = double(self.l_star)
        self.l = [double(self.l_dollar)]

    def get(self, i):
        while len(self.l) <= i:
            self.l.append(double(self.l[-1]))
        return self.l[i]


def check(key, nonce, tag_len):
    if len(key) not in (16, 24, 32):
        raise ValueError("an AES key is 16, 24 or 32 bytes")
    if not 1 <= len(nonce) <= 15:
        raise ValueError("an OCB nonce is 1 to 15 bytes")
    if not 1 <= tag_len <= 16:
        raise ValueError("an OCB tag is 1 to 16 bytes here")


def initial_offset(aes, nonce, tag_len):
    """Offset_0, made from the nonce and the tag length."""
    bits = 8 * len(nonce)
    taglen_bits = (8 * tag_len) % 128
    formatted = (taglen_bits << 121) | (1 << bits) | int.from_bytes(nonce, "big")
    bottom = formatted & 63
    ktop = aes.encrypt_block(((formatted >> 6) << 6).to_bytes(16, "big"))
    top = int.from_bytes(ktop, "big")
    stretch = (top << 64) | (((top >> 64) ^ (top >> 56)) & ((1 << 64) - 1))
    return ((stretch >> (64 - bottom)) & MASK128).to_bytes(16, "big")


def hash_aad(aes, tables, aad):
    """HASH: a PMAC-like checksum of the associated data."""
    total = bytes(16)
    offset = bytes(16)
    full = len(aad) // 16
    for i in range(1, full + 1):
        offset = xor(offset, tables.get(ntz(i)))
        total = xor(total, aes.encrypt_block(xor(aad[16 * (i - 1):16 * i], offset)))
    rest = aad[16 * full:]
    if rest:
        offset = xor(offset, tables.l_star)
        padded = rest + b"\x80" + bytes(15 - len(rest))
        total = xor(total, aes.encrypt_block(xor(padded, offset)))
    return total


def encrypt(key, nonce, plaintext, aad=b"", tag_len=16):
    """Return the ciphertext followed by the tag."""
    check(key, nonce, tag_len)
    aes = AES(key)
    tables = Tables(aes)
    offset = initial_offset(aes, nonce, tag_len)
    checksum = bytes(16)
    out = bytearray()
    full = len(plaintext) // 16
    for i in range(1, full + 1):
        block = plaintext[16 * (i - 1):16 * i]
        offset = xor(offset, tables.get(ntz(i)))
        out += xor(offset, aes.encrypt_block(xor(block, offset)))
        checksum = xor(checksum, block)
    rest = plaintext[16 * full:]
    if rest:
        offset = xor(offset, tables.l_star)
        pad = aes.encrypt_block(offset)
        out += xor(rest, pad[:len(rest)])
        checksum = xor(checksum, rest + b"\x80" + bytes(15 - len(rest)))
    tag = xor(aes.encrypt_block(xor(xor(checksum, offset), tables.l_dollar)), hash_aad(aes, tables, aad))
    return bytes(out) + tag[:tag_len]


def decrypt(key, nonce, data, aad=b"", tag_len=16):
    """Return the plaintext, or raise ValueError if the tag does not match."""
    check(key, nonce, tag_len)
    if len(data) < tag_len:
        raise ValueError("the input is shorter than the tag")
    aes = AES(key)
    tables = Tables(aes)
    ciphertext, received = data[:-tag_len], data[-tag_len:]
    offset = initial_offset(aes, nonce, tag_len)
    checksum = bytes(16)
    out = bytearray()
    full = len(ciphertext) // 16
    for i in range(1, full + 1):
        block = ciphertext[16 * (i - 1):16 * i]
        offset = xor(offset, tables.get(ntz(i)))
        plain = xor(offset, aes.decrypt_block(xor(block, offset)))
        out += plain
        checksum = xor(checksum, plain)
    rest = ciphertext[16 * full:]
    if rest:
        offset = xor(offset, tables.l_star)
        pad = aes.encrypt_block(offset)
        plain = xor(rest, pad[:len(rest)])
        out += plain
        checksum = xor(checksum, plain + b"\x80" + bytes(15 - len(plain)))
    tag = xor(aes.encrypt_block(xor(xor(checksum, offset), tables.l_dollar)), hash_aad(aes, tables, aad))
    difference = 0
    for a, b in zip(tag[:tag_len], received):
        difference |= a ^ b
    if difference:
        raise ValueError("authentication failed")
    return bytes(out)


if __name__ == "__main__":
    key = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
    nonce = bytes.fromhex("bbaa99887766554433221104")
    header = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
    message = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
    sealed = encrypt(key, nonce, message, header)
    print("Key:        " + key.hex())
    print("Nonce:      " + nonce.hex())
    print("Header:     " + header.hex())
    print("Plaintext:  " + message.hex())
    print("Sealed:     " + sealed.hex())
    print("Recovered:  " + decrypt(key, nonce, sealed, header).hex())
    try:
        decrypt(key, nonce, bytes([sealed[0] ^ 1]) + sealed[1:], header)
    except ValueError as error:
        print("Tampered:   " + str(error))

Running it produces this output:

Key:        000102030405060708090a0b0c0d0e0f
Nonce:      bbaa99887766554433221104
Header:     000102030405060708090a0b0c0d0e0f
Plaintext:  000102030405060708090a0b0c0d0e0f
Sealed:     571d535b60b277188be5147170a9a22c3ad7a4ff3835b8c5701c1ccec8fc3358
Recovered:  000102030405060708090a0b0c0d0e0f
Tampered:   authentication failed

I checked this code against several sources before writing it up. It reproduces all 17 sample results in RFC 7253, and it reproduces the internal values the RFC prints for one of them: the L values, bottom, Ktop, Stretch, the offsets, and the checksums. It also reproduces the RFC’s long test, which runs 384 encryptions and checks the final result, for all nine parameter sets: AES-128, AES-192, and AES-256, each with 128, 96, and 64-bit tags. In addition, it agrees with the OpenSSL that ships inside Node.js on 300 random cases that cover all three key sizes, nonces of 1 to 15 bytes, and three tag sizes. Changing any byte of the ciphertext, the associated data, or the nonce makes decryption fail.

Limitations

This is a faithful teaching version of the mode, not a production one:

• Never reuse a nonce. The code does not track nonces. RFC 7253 says that reuse undermines the confidentiality of both messages and all of the authenticity protection under that key.
• Not constant-time. The AES here uses table lookups on secret data, and Python is not suitable for real encryption.
• Whole bytes only. The RFC allows any number of bits for the nonce, the message, and the tag. This code takes bytes.
• Slow on purpose. OCB’s speed comes from parallel hardware and AES instructions, and this code does one block at a time.

Security Status

OCB has a security proof that holds as long as AES is a secure block cipher. The RFC says that confidentiality and authenticity both degrade as s² / 2¹²⁸, where s is the number of blocks the attacker sees. To keep that small, one key should encrypt at most 2⁴⁸ blocks, which is about four petabytes, including the associated data. A forged tag has a chance of 2^-TAGLEN of passing, so short tags are weaker.

An important warning concerns the older version. In October 2018, Inoue and Minematsu published an existential forgery attack on OCB2 that needs only one encryption query. Poettering and Iwata then developed a full plaintext recovery attack. OCB1 and OCB3 are not affected, and RFC 7253 specifies OCB3. OCB2 was standardized in ISO/IEC 19772 and has since been removed from it.

The most important rule is the nonce rule. RFC 7253 says that a repeated nonce lets an attacker infer relationships between the plaintexts and recover secret information that makes later forgeries trivial. OCB is not a nonce-misuse-resistant mode. The formula shows the first problem. Each ciphertext block is Offset_i xor AES(P_i xor Offset_i), and the offsets depend only on the key and the nonce. Two messages under one nonce therefore give identical ciphertext blocks wherever their plaintext blocks match at the same position, which leaks that equality at once. Where nonces cannot be guaranteed unique, the RFC points to AES-SIV.

FAQ

Why is OCB fast?

It needs only about one AES call per block, and a few XORs. The calls for different blocks do not depend on one another, so a processor can run them in parallel. It also needs no polynomial multiplication, unlike GCM.

Is OCB the same as OCB2 or OCB3?

The name covers three versions. RFC 7253 specifies OCB3. OCB2, which was a different version, was broken in 2018. Check which one a library implements before relying on it.

Is OCB online?

The RFC says that one need not know the length of the associated data or the plaintext to start encrypting, nor the length of the associated data or ciphertext to start decrypting. So OCB can handle streams, which CCM and SIV cannot. Online describes the work, not the release of data. The tag comes last, so the decrypted plaintext stays unverified until the end. Hold it back until the tag check passes. Releasing it early is known as the release of unverified plaintext.

Does OCB need AES decryption?

Only when it decrypts full blocks. The tag and the partial block always use AES in the forward direction, and so does all of encryption.

Is OCB free to use?

It is free today. According to Wikipedia, the inventor abandoned the patents in 2021. Before that, free licenses covered open-source software and many other uses.

References

1. Krovetz, T. and Rogaway, P. “The OCB Authenticated-Encryption Algorithm.” RFC 7253, 2014. Available at: https://www.rfc-editor.org/rfc/rfc7253

2. Krovetz, T. and Rogaway, P. “The Software Performance of Authenticated-Encryption Modes.” Fast Software Encryption (FSE) 2011.

3. Rogaway, P., Bellare, M., Black, J., and Krovetz, T. “OCB: A Block-Cipher Mode of Operation for Efficient Authenticated Encryption.” ACM Conference on Computer and Communications Security (CCS) 2001.

4. Inoue, A. and Minematsu, K. “Cryptanalysis of OCB2.” IACR Cryptology ePrint Archive, 2018/1040.

5. Wikipedia. “OCB mode.” Available at: https://en.wikipedia.org/wiki/OCB_mode