## 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

**About the constants problem**- stackexchange about the CMAC problem
- Newsgroup about the CMAC problem
**Test vectors for OMAC and EAX**- test vectors for CMAC-AES
- test vectors of Crypto++ for EAX-AES
- Adders OMAC online test for several ciphers and block sizes of 8, 16, 32, 64, 128, 256 or 512
**OMAC implementation for more than two block sizes**- Bouncy Castles Java implementation of CMAC for block size of 64, 128, 160, 192, 224, 256, 320, 384, 448, 512, 768, 1024, 2048 bits
- PHP implementation of CMAC for block size of 8, 16, 32, 64, 128, 256 or 512
- Source code of Crypto++ library, supports 8, 16, 32 byte blocks (not time-constant)
- Source code of Botan library, supports 8, 16, 32 , 64 byte blocks (not time-constant)
**About block ciphers, OMAC and EAX**- About block ciphers and their design
- The OMAC page
- The OMAC NIST submission
- Crypto++ article about EAX
**Helpful stuff**- A list of low-weight binary irreducible polynomals in the range from 2 up to 10,000 (pdf). I used them here