Re: [Cfrg] Attacker changing the tag length in OCB

[Phillip Rogaway <[e-mail]>]

Hi everyone,

Dan Brown wrote:
> can (or has) somebody formalize(d) the problem here, and
> prove[] that some method actually fixes solve the problem[?]
> ...
> let's not tweak OCB until we're certain of why and how.

To the best of my knowledge, the question that has arisen on this 
mailing list does not correspond to any already formalized security 
notion.  Here's one approach to formalizing the aim. First, the 
syntax for for an encryption algorithm E and decryption algorithm D 
are augmented by a new argument, taglen.  We require that
|E_K(N,A,P,taglen)| = |P|+taglen.  Then game defining security 
is adjusted to:

"Real" oracle pair. Select a random key K.
    Encrypt(N,A,P,taglen): return E_K(N,A,P,taglen)
    Decrypt(N,A,C,taglen): if taglen<TAGLEN return \bot
                           return D_K(N,A,C,taglen)
"Fake" oracle pair.
    Encrypt(N,A,P,taglen): return |P|+taglen random bits.
    Decrypt(N,A,C,taglen): return \bot 
Queries that allow a trivial wins are disallowed.

But the notion above is not without issues.  First, once you countenance 
variable-length tags, it seems good to consider arbitrarily short ones. 
That's not happening above because we effectively "give up" -- the adversary 
wins -- on first forgery.  This motivates the minimum taglen, TAGLEN, used
above.    Relatedly, nowhere above is captured the idea that, say, 
a 128-bit tag is harder to forge than a 32-bit one. These issues can 
be addressed, but only by major definitional changes.

The immature definitional story aside, I do think there's a simple and 
generic approach that likely achieves what people have in mind, at least 
for OCB: just drop the tag length into the nonce.  This generalizes what
James Manger, who started this discussion, wrote.   Ted has suggested 
to me that, in the context of OCB, we could do it like this:

    (1) Require the nonce N to be 120 or fewer bits (right now,
        we allow up to 127 bits);

    (2) In the definition of OCB, replace the step
          Nonce = zeros(127-bitlen(N)) || 1 || N
        by
          Nonce = taglen || zeros(120-bitlen(N)) || 1 || N
        where taglen is the 7-bit binary representation of (TAGLEN mod 128)

I think it's a good approach, designed to ensure that there's no change 
to OCB when the tag length is 128 bits (which we think is the the 
customary choice).   And "conventional" AEAD security is trivially 
maintained.

There are arguments both for and against making such a change: 
(+1) I think it does add a measure of robustness to have the 
"ciphertext core" meaningfully vary with the tag length. Folding the 
tag length into the nonce seems like the sort of "crypto engineering" 
choice that has not-well-characterized value beyond what our usual 
definitions speak to. 
(+2) Algorithmically, the change is cheap and easy, and it clearly 
retains "conventional" AEAD security. 
(+3) We suspect that those using OCB are using 128-bit tags, as 
MOSH does.  The change, as described above, wouldn't impact them. 
On the other hand, 
(-1) There are already OCB implementations that handle tags 
of length other than 128 bits. These would have to change. 
(-2) The OCB spec is quite clear that TAGLEN, like the 
underlying blockcipher, is a system parameter; the user has 
no more business letting it vary in the course of a session 
than he has letting the underlying blockcipher vary during a session.
(-3) I worry that trying to engineer things so that one can safely 
use varying tag lengths with a single key might send a message that 
this is an OK thing to do, contradicting the spec.  Someone might 
even think it appropriate to accept a ciphertext with _any_ provided 
tag length, as long as the ciphertext is deemed valid.  For most 
contexts, that would be disastrous. 
(-4) As indicated above, the definitional and provable-security
story that ought to accompany such a change is immature.
(-5) I find it pleasant that, currently, the algorithm of the 
published paper and the spec are exactly the same.

When I weigh the pluses and minuses, I'm of the opinion that it 
is reasonable to go either way.   Ted leans towards making 
the change.   Neither of us feels strongly about it. 
If there is a consensus on this mailing list in favor of 
the change, Ted and I will make it.  For now, I would 
consider this a heuristic measure that appears to buy a 
tiny measure of misuse resistance, and which provably 
does not damage standard AE security.

Rene Struik wrote: 
> The observation that some AEADs have the property [that ciphertexts
> look like C || T where C does not depend on the tag length] ... was 
> brought up by Rogaway and Wagner in their 2003 "Critique on CCM" paper
> (Section 3.4). It is therefore kind of interesting to see that the same
> observation applies to the OCB mode.

I looked back to see what David and I concluded back then --

   Does the attack above mean that the tag length \tau should have been used for
   computing the ciphertext core C?  In our opinion, the answer is: "not necessarily."
   Rather, the attack highlights that the specification [of CCM] has made it unclear
   what the goal is with respect handling a multiplicity of tag lengths.
   We suggest that the tag length parameter \tau should be fixed at key-negotiation time,
   bound securely to the key, and negotiated authentically between both parties. Once a
   session has begun, there should be only a single value \tau that will be accepted
   by the receiver, and this should remain unchanged throughout the lifetime of the
   session. The receiver shouldn't accept a new \tau in the middle of a session
   any more than it would accept a new block cipher E.

I would say that the OCB spec is perfectly in line with this conclusion.



Best,
phil