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

[David McGrew <[e-mail]>]

Hi Phil,

I agree, there is a lack of appropriate definitions, but it seems like
it would be possible to develop them.  This has been a fruitful
discussion.

I do have a comment on the broader security goals.  Using an
authentication scheme that provides two sizes of authentication tag with
a single key makes sense only if there are (at least) two categories of
messages that are being authenticated, one of which requires only the
short authentication tag, another of which needs stronger
authentication.  When this cryptographic scheme is used, both the sender
(tag generator) and the receiver (message/tag verifier) need to
determine the appropriate category for each message, and the receiver
needs to discard messages that are authenticated with a short tag, but
which are in a stronger-authentication category.  If the
post-verification enforcement is omitted, then there is no security
advantage in using the variable-tag-length scheme, as compared to just
using a short tag.  This does not have any bearing on the soundness of
the cryptographic model, but it does have bearing on how such schemes
would be used in practice.  It would be important to ensure that the
users of the scheme understood how it fits into an overall security
system.

Perhaps the best place for us to look for applications of
variable-authentication-strength mechanisms would be low power wireless
devices, where the cost of transmission creates pressure to minimize tag
length, and there is a desire to minimize state (e.g. the number of
keys).  IEEE 802.15.4, for example, defines the use of tag lengths
between 4 and 16 bytes, if I recall correctly.  

An aside: OCB does not seem like the ideal scheme to use with short (or
variable length) authentication tags, because of the property that an
attacker who can cause a single forgery can use information thus learned
to perpetrate other forgeries.  

David

On Mon, 2013-06-03 at 12:41 -0700, Phillip Rogaway 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