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

From: Phillip Rogaway <[email-masked]>
Date: Mon, 3 Jun 2013 12:41:42 -0700 (Pacific Daylight Time)

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

---

From: "Manger, James H" <[email-masked]>
Date: Tue, 4 Jun 2013 10:08:46 +1000

Phil Rogaway said:
> "ciphertext core" meaningfully vary with the tag length. 
...
> the change, Ted and I will make it.

I'm +1 on making this change.
I would also add text saying "any given key MUST only be used with one tag length" -- since the aim of the change isn't to promote using one key with multiple tag lengths, but to add a measure of robustness even if a decryptor fails to properly enforce once-key-one-tag-length.

--
James Manger

---

From: David McGrew <[email-masked]>
Date: Tue, 04 Jun 2013 13:08:32 -0400

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

---

From: Dan Brown <[email-masked]>
Date: Tue, 4 Jun 2013 17:49:06 +0000

> -----Original Message-----
> Phillip Rogaway
> Sent: Monday, June 03, 2013 3:42 PM
> To: [email-masked]

[DB] Perhaps mistakenly (*), I interpreted some of the emails on this thread
as saying that the spec allows one to vary tag lengths with a single key.  

If the intent of the OCB spec is not to allow variable tag lengths, then I
think the spec needs greater emphasis, especially in view of some IETF
common practices and viewpoints (**).  So, the spec should somewhere say
that "a single key MUST not be used with multiple parameter sets" and "a
decryptor MUST reject a ciphertext if it uses different parameters than for
the key indicated".  

(*) I may have taken the emails out of context (i.e. without studying the
spec first): maybe the emails meant that somebody might contradict the spec.

(**) For example, TLS allows one public key per multiple different cipher
suites (not sure if it allows pre-shared key with different cipher suites).
For another example, PKIX did not accept proposals that allowed, as
optional, detailed algorithm restrictions in certificates.

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Tue, 4 Jun 2013 14:39:44 -0400

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

---

From: "Jack Lloyd" <[email-masked]>
Date: Tue, 4 Jun 2013 15:01:04 -0400

> common practices and viewpoints (**).  So, the spec should somewhere say
[...]
> suites (not sure if it allows pre-shared key with different cipher suites).

To address TLS-PSK specifically - using a single PSK with several
different cipher suites is allowed, though as the actual symmetric
keys are derived from both the PSK and the client and server nonces
(and, optionally, a DH/ECDH key exchange), the actual OCB key would
never be reused in a different context, or even in a different session
with the same parameter set.

-Jack

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Wed, 12 Jun 2013 13:48:00 +0000

OK, it looks like the debate working the tag length into AEAD
encryption has reached either consensus or exhaustion.
Here is where I think we stand:

1) Working the tag length into either the KDF or encryption
   process is a prudent precaution because, at the very least,
   it simplifies the security analysis and guards against
   implementation errors.  Future AEAD modes should STRONGLY 
   consider doing this.

2) OCB is too widespread to make such a substantive change at
   this late date.

3) The changes made in the current OCB draft aren't substantive,
   they merely correct errors in the exposition.

Therefore I want to make a RG last call on draft-irtf-cfrg-ocb-02.
I'll start of the discussion by putting on the floor a motion that 
the RG accept draft-irtf-cfrg-ocb-02 as it stands. Discussion?
Don't be shy. How do the RG and the authors feel about Dan Brown's 
suggestion to insert some text explicitly prohibiting using the same 
key with different OCB lengths?

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Jack Lloyd
> Sent: Tuesday, June 04, 2013 3:01 PM
> To: [email-masked]
> Subject: Re: [Cfrg] Attacker changing the tag length in OCB
>

---

From: Ted Krovetz <[email-masked]>
Date: Wed, 12 Jun 2013 07:08:27 -0700

Thanks Kevin for pushing OCB along.

> 2) OCB is too widespread to make such a substantive change at this late date.

Actually, Phil and I have decided to make the change. We agree that it is a good idea, and since we figured out how to do it without affecting existing users of 128-bit tags, we think it's worth the break.

A draft that makes the change will be posted later today or tomorrow. It will not need much changing over -02, so hopefully it won't take much further review.

-Ted

---

From: David Jacobson <[email-masked]>
Date: Wed, 12 Jun 2013 09:46:55 -0700

> A draft that makes the change will be posted later today or tomorrow. It will not need much changing over -02, so hopefully it won't take much further review.
[snip]

And just an only semi-relevant little point:  The key derivation 
functions in SP 800-108 all include the number of output bits in the 
computation.  So if you use exactly the same key, label, and context, 
and generate a 128 bit key and a 256 bit key, the two keys are 
completely different.  They could have not done that and instead made 
the argument that people should know better than to... .  I think that 
mixing the output length into the computation of both KDFs and 
authentication tags is good.

     --David