OMAC : Padding on empty string

Question

I started to implement some MAC since last week with the specifications given here. I'm currently testing the OMAC (one-key CBC) with test vectors. In the OMAC specifications at page 4, they explain how the padding works. Just below that, they said :

[...] Where the empty string counts as one block.

This is strange, because the block is empty and that cause me a problem. How could I use M[i] and Xor it with Y[i-1] if M[i] is empty ? (see the algorithm definition at page 8)

Following this question, should I pad the message to get a full block before working with M even if the padding is applied after the for-loop ? I think this would be logic but am I right with this logic ?

A clear explanation of that will be very appreciated. Thanks for all help I'll got.

Answer 1

What the specification is saying is that prior to processing, the message is padded to a full block length, with the empty message padded to a single block.

The spec on page 4 describes the input into the algorithm as:

• Define $||a||_n = max\{1, \lceil|a|/n\rceil \}$, where the empty string counts as one block
• Let $m = ||M||_n$
• Partition $M$ into $M[1] ... M[m]$, where $|M[i]| = n$ for $ 1 \le i < m$

i.e. The number of blocks of size $n$ in a message $M$ is rounded up, and must be at least 1 before it can be passed to the $CBC{-}MAC$ portion of the algorithm.

The padding applied to the last block (which is an empty block for the empty message) is defined in formula $(1)$. In byte terms it translates to:

• Set the first byte to $0x80$ (i.e. set the high bit)
• Set all remaining bytes to $0$

In implementation terms, this means that you would buffer up to (and including) a complete block, and only process that block when either more data arrives, or the MAC is finalised - an empty message is thus treated as a 0 byte block that needs padding, and a full last block is not padded.

If you're not trying to implement from the spec as an exercise, the Bouncy Castle CMAC implementation should make the buffer/padding scheme clear (CMAC being the NIST standarised name for OMAC1).