At the beginning of OCB's white paper [pdf], OCB is compared to other modes, and non-malleability is one of the properties advertised.

At the end of the paper, it is mentioned the MAC length can be chosen by users according to their needs.

Was long MACs assumed in the claim of non-malleability, or is the property still holding with short/no MACs ?


The answer to your question is contained in the Authenticity bound (Theorem 5.1). This is because Authenticity implies non-malleability (see e.g. http://eprint.iacr.org/2011/092.pdf). Note that only one term in the bound refers to the length of the tag (referred to by the variable $\tau$):

$$\mathbf{Adv}_{OCB}^{auth}[\mathrm{Perm}(n), \tau] (A) \leq \dfrac{1.5\overline{\sigma}^2}{2^n}+\dfrac{1}{2^{\tau}},$$

where $\overline{\sigma} = \sigma + 2q + 5c + 11$, such that $q$ is the number of chosen plaintext queries of aggregate length $\sigma$ blocks, and $c$ is the total length in blocks of the attempted forgery.

As you can see, the length of the tag only matters for the last term. So if the tag is 128 bits then the last term adds $\frac{1}{2^{128}}$ to the total Adversarial advantage. But if the tag is truncated to only 32 bits then the advantage will increase by $\frac{1}{2^{32}}$, which is about 1 in 4 billion. Depending on your risk tolerance and threat model, the latter increase in Adversarial advantage might be acceptably small in exchange for the space savings of shorter tags.

  • 1
    $\begingroup$ Of course, that inequality is trivial when $\: \tau = 0 \:$ (i.e., there is no MAC). $\;\;\;$ $\endgroup$
    – user991
    Jan 12 '14 at 23:07
  • $\begingroup$ Indeed. As Ricky points out, $1/2^0 = 1/1 = 1$, and 1 is the maximum possible Advantage. So the upper bound on Adversarial advantage described in Theorem 5.1 doesn't really do any 'bounding' when there is no tag at all. $\endgroup$
    – J.D.
    Jan 12 '14 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.