Problems with large block cipher sizes for EAX mode and the Mac algorithm OMAC / CMAC

EAX, CMAC, OMAC

EAX mode is a common mode of operation for block ciphers which allows confidentiality, integrity, and authenticity (Authenticated Encryption). EAX mode bases on the message authentication code OMAC (OMAC1 became a recommendation by NIST called CMAC).

Block Size of Ciphers

Block cipher operate internally on blocks, a fixed size of bits. For example AES candidates were required to support a block size of 128 bits, most of the earlier cipher operates on 64 bits. In general a block size must be chosen so that it is not feasible to pre-compute and store all plaintext-ciphertext pairs. For performance and implementation reasons most block ciphers uses a multiple of 32 bits.

EAX is the only common mode which is suitable for various block sizes. It's more flexible than, for example, the (faster) GCM mode.
It is especially hard to perfom an authenticated encryption for block ciphers that are not vulnerable to chache-timining attacks like Shacal-2 or Threefish. The CAESAR Competition for Authenticated Encryption runs until 2017. Then, we have probably better options for authenticated encryption.

Block Size Problems

Although CMAC is not restricted to any block size of a cipher, most implementations support only the two most common block sizes 64 bits and 128 bits. The reason for this is probably that all of the papers about EAX or CMAC (OMAC) only specify the 64/128 bit related constants. Only the NIST paper presents also the constant for 256 bit (pdf ). There are several other block ciphers whose block size does not comply with the usual lengths 64 and 128 bits, most of them allow variable block sizes.

This is a short list of block sizes and more or less common block ciphers:
  • 32 bits: RC5 (not suggested, but possible), Simon, Speck
  • 48 bits: Simon, Speck
  • 64 bits: Blowfish, DES, Triple-DES, CAST-128, IDEA, RC2, Skipjack, TEA, XTEA, GOST, Misty1, RC5, Simon, Speck
  • 96 bits: Simon, Speck
  • 128 bits: AES, Serpent, Twofish, Camellia, CAST-256, SEED, Mars, RC6, RC5, Rijndael, Simon, Speck
  • 160 bits: Shacal-1, Rijndael
  • 192 bits: Rijndael
  • 224 bits: Rijndael
  • 256 bits: Shacal-2, Threefish, Rijndael
  • 512 bits: Threefish
  • 1024 bits: Threefish

RC5 has variable block size: 32, 64 or 128 bits (64 suggested).
Threefish has variable block size ( = key size): 256, 512, 1024.
Rijndael (origin of the AES) allows block sizes of 128, 160, 192, 224 and 256.
XXTEA allows variable, not limited block sizes.
Simon and Speck allow 32, 48, 64, 96 or 128 bits.

Now, the Bouncy Castle Java Crypto APIs (Release: 1.53, 2015, October 10) support several block sizes:
64, 128, 160, 192, 224, 256, 320, 384, 448, 512, 768, 1024, 2048.
But as far as I know, this is the only library, that supports so many block sizes.

Descriptions

The description how to get the subkey constant can be found in the papers about the EAX mode and the CMAC algorithm.
However theses descriptions are not very helpful for most people.

NIST Special Publication 800-38B “Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication” (pdf): The NIST description of the EAX tells us in chapter 5.3:
One of the elements of the subkey generation process is a bit string, denoted Rb, that is completely determined by the number of bits in a block. In particular, for the two block sizes of the currently approved block ciphers, R128 = 012010000111, and R64 = 05911011. In general, Rb is a representation of a certain irreducible binary polynomial of degree b, namely, the lexicographically first among all such polynomials with the minimum possible number of nonzero terms. If this polynomial is expressed as ub+cb-1ub-1+...+c2u2+c1u+c0, where the coefficients cb-1, cb-2, ..., c2, c1, c0 are either 0 or 1, then Rb is the bit string cb-1cb-2...c2c1c0.

Get a Constant

How can we compute a "representation of a certain irreducible binary polynomial of degree b, namely, the lexicographically first among all such polynomials with the minimum possible number of nonzero terms"? Programmers of cryptographic algorithms are not necessarily mathematician. Fortunately we don't need to compute by ourself, there is a list available here.
We can find for example for the 64 bit block 64,4,3,1, which means 2^64 + 2^4 + 2^3 + 2^1 (our polynomial). To get an OMAC constant, we cut the first term (2^64) and add 1. 2^64 + 2^4 + 2^3 + 2^1 becomes the constant 27, hexadecimal 0x1B ( 2^4 + 2^3 + 2^1 + 1).

This is a small list of CMAC constants for some block sizes
(this includes at least all common cipher block sizes)

Block size Calculation Polynomal (hex) Polynomal (bit)
32 2^7+2^3+2^2+1 0x8D 10001101
48 2^5+2^3+2^2+1 0x2D 101101
64 2^4+2^3+2^1+1 0x1B 11011
96 2^10+2^9+2^6+1 0x641 11001000001
128 2^7+2^2+2^1+1 0x87 10000111
160 2^5+2^3+2^2+1 0x2D 101101
192 2^7+2^2+2^1+1 0x87 10000111
224 2^9+2^8+2^3+1 0x309 1100001001
256 2^10+2^5+2^2+1 0x425 10000100101
320 2^4+2^3+2^1+1 0x1B 11011
384 2^12+2^3+2^2+1 0x100D 1000000001101
448 2^11+2^6+2^4+1 0x851 100001010001
512 2^8+2^5+2^2+1 0x125 100100101
768 2^19+2^17+2^4+1 0xA0011 10100000000000010001
1024 2^19+2^6+2^1+1 0x80043 10000000000001000011
2048 2^19+2^14+2^13+1 0x86001 10000110000000000001

Related links