Subject: [Cfrg] Request For Comments: OCB Internet-Draft

From: Ted Krovetz <[email-masked]>
Date: Wed, 13 Jul 2011 09:42:21 -0700

I have just submitted an internet-draft for OCB to the IETF.

  http://datatracker.ietf.org/doc/draft-krovetz-ocb

I'd appreciate any comments you may have on how to make the draft better.

OCB is a blockcipher-based authenticated-encryption scheme. It is significantly faster than any other blockcipher-based AE scheme that I am aware of. On Intel's current Sandy Bridge processors it encrypts and authenticates 4K messages at 0.9 cpu cycles per byte of message, and processes a weighted mix of message lengths at 1.3 cpb (5% 44B, 15% 552B, 20% 576B, 60% 1500B).

OCB has undegone refinements over the years to allow authentication of associated data and improved performance. This is the second (and last) revision. It was presented at FSE this year

  http://www.cs.ucdavis.edu/~rogaway/papers/ae.pdf

Associated notes and performace data are at

  http://www.cs.ucdavis.edu/~rogaway/ocb/performance

We intend to convert the internet-draft into an RFC and also submit OCB to the NIST blockcipher modes-of-operation project.

There are several patents that may apply to OCB. We are in the process of trying to get all parties to pool their patents and liberalize their use.

Thank you,
Ted Krovetz

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 14 Jul 2011 15:48:49 +1200

OCB is a nice mode, I've always wanted to use it, but:

>There are several patents that may apply to OCB. We are in the process of
>trying to get all parties to pool their patents and liberalize their use.

without the ability to use it without encumbrance I'll stick with CBC+HMAC or
GCM.  I know you can use OCB under the GPL but that's too much of a hassle to
try and sort out for each user, it'd have to be completely unencumbered to
make it useful.

(I'm not saying this out of some rabid anti-patent position but purely an 
anti-headache position, since there are unencumbered, if less efficient, 
alternatives available I'll go with those and avoid the hassle).

Peter.

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 14 Jul 2011 10:00:44 +0200

> I'd appreciate any comments you may have on how to make the draft better.

It would help if you explained (in the security considerations) what
happens if a nonce is repeated.  The question of failure modes of
authenticated encryption modes has come up in several different
contexts.  It turns out that different AEAD modes have different failure
properties.

In particular, you want to address whether repeat of a nonce leads to
immediate key disclosure, or whether the key can be found after some
computation faster than obvious attacks, or whether it can only lead to
recovery of the plaintext, and/or whether it depends on the plaintext as
well (e.g., something interesting happens if the plaintexts are related).

> There are several patents that may apply to OCB. We are in the process
> of trying to get all parties to pool their patents and liberalize
> their use.

Which patents?  According to the patent disclosure search, only these
have been disclosed:

https://datatracker.ietf.org/ipr/559/
https://datatracker.ietf.org/ipr/560/

If you are aware of other patents (or applications) that applies, it
would help if you send in a patent disclosure about it.

Thanks,
/Simon

---

From: Ted Krovetz <[email-masked]>
Date: Thu, 14 Jul 2011 17:35:13 -0700

> It would help if you explained (in the security considerations) what happens if a nonce is repeated.

Nice suggestion. Security is lost if nonces are reused during encryption. We've made this clearer in the ID and have resubmitted it as draft-krovetz-ocb-02.

> If you are aware of other patents (or applications) that applies, it would help if you send in a patent disclosure about it.

IBM and Virgil Gligor have AE patents which may or may not apply to OCB. What we are trying to establish with them is a clear licensing picture for OCB, hopefully with many free usage scenarios. Phil will update the IETF IPR soon.

Thanks,
Ted

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 15 Jul 2011 09:54:23 +0200

Ted Krovetz <[email-masked]> writes:

>> happens if a nonce is repeated.
>
> Nice suggestion. Security is lost if nonces are reused during
> encryption. We've made this clearer in the ID and have resubmitted it
> as draft-krovetz-ocb-02.

Thank you!

Are there any implications for the key if a nonce is repeated?  Let's
say I use the same nonce all the time, and the attacker can do
known-plaintext attacks.  Can the attacker recover the key faster than
he would be able to if the nonces were not repeated?

I'm trying to get AEAD cipher modes to say more than just "the security
properties are lost" when talking about failure modes.  "security
properties are lost" can mean so many things, and it is useful to be
able to rule out some unwanted side effects.

/Simon

---

From: Ted Krovetz <[email-masked]>
Date: Fri, 15 Jul 2011 08:04:08 -0700

> he would be able to if the nonces were not repeated?

No. The only place the OCB key is used is as the key for AES. So, if one were able to recover OCB keys in the way you suggest, one would in effect have an AES key-extraction method. Since we don't think AES is susceptible to key-extraction, neither is OCB.

> able to rule out some unwanted side effects.

In the ID we point out that if a nonce is reused during encryption, "partial information about past plaintexts will be revealed and subsequent forgeries will be possible". That seems specific enough for an RFC, don't you think?

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 15 Jul 2011 17:09:01 +0200

Ted Krovetz <[email-masked]> writes:

> No. The only place the OCB key is used is as the key for AES. So, if
> one were able to recover OCB keys in the way you suggest, one would in
> effect have an AES key-extraction method. Since we don't think AES is
> susceptible to key-extraction, neither is OCB.
>
> In the ID we point out that if a nonce is reused during encryption,
> "partial information about past plaintexts will be revealed and
> subsequent forgeries will be possible". That seems specific enough for
> an RFC, don't you think?

Yes, thank you very much for clarifying!

/Simon

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 15 Jul 2011 08:35:35 -0700

> In the ID we point out that if a nonce is reused during encryption, "partial information about past plaintexts will be revealed and subsequent forgeries will be possible". That seems specific enoug…

If you know how "partial" that is, it would be useful for the draft. One repetition exposing one bit of a past plaintext is quite different than one repetition exposing half the bits, even though both are bad. Also, knowing what more two repetitions brings the attacker over one repetition is also useful from an operational standpoint.

--Paul Hoffman

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Fri, 15 Jul 2011 12:19:44 -0400

Ted, I think you can be rather more specific. 

--
Regards,
Uri

----- Original Message -----
From: Paul Hoffman [mailto:[email-masked]]
Sent: Friday, July 15, 2011 11:35 AM
To: Ted Krovetz <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [Cfrg] Request For Comments: OCB Internet-Draft

--Paul Hoffman

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Ted Krovetz <[email-masked]>
Date: Fri, 15 Jul 2011 09:45:06 -0700

> If you know how "partial" that is, it would be useful for the draft.

> Ted, I think you can be rather more specific. 

In my opinion the point of the nonce-reuse warning is to impress upon security engineers that catastrophe strikes if a nonce is reused during encryption, and so they should make nonce reuse impossible. If nonce reuse is impossible, then it is irrelevant how bad the damage is when nonces are reused.

RFC writers need to walk a fine line: RFCs are primarily a description of technology, but should include enough high-level context to inform against poor usage. I think the current warnings on nonce reuse do this, but if you can suggest a scenario where the current advice is being heeded and yet it is still useful to know how bad not heeding it would be, I'm open to adding some quantifications.

It may be worth adding a few paragraphs to the OCB paper describing and quantifying the damage, but I'm a bit reluctant to do so in the ID.

---

From: Jack Lloyd <[email-masked]>
Date: Fri, 15 Jul 2011 13:38:35 -0400

On Fri, Jul 15, 2011 at 09:45:06AM -0700, Ted Krovetz wrote:

> In my opinion the point of the nonce-reuse warning is to impress
> upon security engineers that catastrophe strikes if a nonce is
> reused during encryption, and so they should make nonce reuse
> impossible. If nonce reuse is impossible, then it is irrelevant how
> bad the damage is when nonces are reused.

I think part of the issue is that making something truly 'impossible'
is quite a bit harder than it might sound, especially in the face of
an active attacker who might well decide that the easiest way of
breaking the system is to force it to reuse a nonce somehow (this
seems especially likely in embedded systems, but a general system
might well be susceptible). Some plausible failure modes, like VM
state rollback [1], could even be attacked passively and
opportunistically.

Someone building or deploying a system (ie the sort of person who
would read an i-d or RFC) might well want to understand exactly how
fragile the system is when misused, which lets them make a realistic
and informed judgement of the tradeoffs in choosing between different
options.

Regards,
  Jack

[1] http://www.ietf.org/mail-archive/web/cfrg/current/msg01349.html

---

From: "Rose, Greg" <[email-masked]>
Date: Fri, 15 Jul 2011 17:51:59 +0000

> and informed judgement of the tradeoffs in choosing between different

And don't forget that the attacker gets to reuse nonces all he wants (albeit on presumably invalid packets). This is why there must be an absolute prohibition on using the decryption results of an invalid packet. I haven't had time to read the draft; I trust this is mentioned somewhere. It's particularly important for a mode like OCB where the decryption is already done before you know that the packet was bogus. The data should be cleared before returning failure.

Greg.

---

From: Ted Krovetz <[email-masked]>
Date: Fri, 15 Jul 2011 15:08:04 -0700

> there must be an absolute prohibition on using the decryption results of an invalid packet

Yes, that is made explicit in the ID.

> I think part of the issue is that making something truly 'impossible' is quite a bit harder than it might sound, especially in the face of an active attacker who might well decide that the easiest way of breaking the system is to force it to reuse a nonce somehow

That's a problem. When using a scheme that demands nonce uniqueness, the probability of nonce reuse becomes a lower bound on design strength. The OCB ID suggests using a scheme (like SIV) that tollerates nonce reuse if nonce uniqueness cannot be guaranteed.

---

From: Steven Bellovin <[email-masked]>
Date: Tue, 19 Jul 2011 12:55:19 -0400

> It may be worth adding a few paragraphs to the OCB paper describing and quantifying the damage, but I'm a bit reluctant to do so in the ID.

Also give a reference to a paper that gives more details.

Beyond that, both this issue and the bound on plaintext suggest that
this mode SHOULD NOT be used with manual key management.  You should
say that explicitly, perhaps with a reference to 4107.

Devices that lose dynamic state on reboot -- and in particular, lose
state about which nonces have been used -- are particularly vulnerable
here; this merits an extra warning, especially because many WEP
implementations have fallen victim to precisely this problem.  See
http://www.cs.berkeley.edu/~daw/papers/wep-mob01.pdf for details.

		--Steve Bellovin, https://www.cs.columbia.edu/~smb

---

From: David McGrew <[email-masked]>
Date: Thu, 21 Jul 2011 14:40:25 -0700

Hi Ted,

thanks for this contribution.  I have not yet read it through, but  
after I do I'll send you my thoughts.  I have a comment on the  
security considerations being discussed.  This topic was already  
worked through for GCM and CCM, and it would be best to use similar  
language for OCB.

On Jul 15, 2011, at 9:45 AM, Ted Krovetz wrote:

> RFC writers need to walk a fine line: RFCs are primarily a  
> description of technology, but should include enough high-level  
> context to inform against poor usage. I think the current warnings  
> on nonce reuse do this, but if you can suggest a scenario where the  
> current advice is being heeded and yet it is still useful to know  
> how bad not heeding it would be, I'm open to adding some  
> quantifications.
>
> It may be worth adding a few paragraphs to the OCB paper describing  
> and quantifying the damage, but I'm a bit reluctant to do so in the  
> ID.

The draft should include text like that of Section 5.1.1 of RFC 5116,  
ideally using the same wording where possible, ideally in a subsection  
entitled "Nonce Reuse".  I think this text, adapted from that section,  
is appropriate:
<text>
The inadvertent reuse of the same nonce by two invocations of the OCB  
encryption operation, with the same key, but with distinct plaintext  
values, undermines the confidentiality of the plaintexts protected in  
those two invocations, and undermines all of the authenticity and  
integrity protection provided by that key.  For this reason, OCB  
should only be used whenever nonce uniqueness can be provided with  
assurance.   Note that it is acceptable to input the same nonce value  
multiple times to the decryption operation.   The security  
consequences are quite serious if an attacker observes    two  
ciphertexts that were created using the same nonce and key values,  
unless the plaintext and AD values in both invocations of the encrypt  
operation were identical.  First, a loss of confidentiality ensues  
because he will be able to infer relationships between the two  
plaintext values. Second, a loss of integrity ensues because the  
attacker will be able to recover secret information used to provide  
data integrity. Knowledge of this key makes subsequent forgeries  
trivial.
</text>
Here I am assuming that the newer version of OCB is still vulnerable  
to Fergusen's collision attack (http://www.cs.ucdavis.edu/~rogaway/ocb/fe02.pdf 
); please correct me if I'm wrong.
David