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

["Blumenthal, Uri - 0558 - MITLL" <[e-mail]>]

I think the change you propose is good, and would enhance security & add
robustness. I vote for making it, and wish such a change would/could be
done to all AEAD modes with variable tag size.

I don't know what to do, or how to answer your points (-3) and (-5).

Tnx!
--
Regards,
Uri Blumenthal




On 6/3/13 15:41 , "Phillip Rogaway" <[e-mail]> wrote:

>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
>_______________________________________________
>Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg