Subject: Re: [TLS] Data volume limits

From: Samuel Neves <[email-masked]>
Date: Fri, 1 Jan 2016 11:18:48 +0000

On 01/01/2016 06:35 AM, Aaron Zauner wrote:
> This might be a good time to point again to my existing AES-OCB
> draft that hasn't really seen a lot of discussion nor love lately.
> It expired but I've recently updated the draft (not yet uploaded
> to IETF as I'm waiting for implementer feedback from two particular
> sources). The update has something to do with how GCM is implemented
> in some stacks though, see:
> https://github.com/azet/draft-zauner-tls-aes-ocb/commit/26c2fff7808fc88bf47e5d097f2ff5ca23201029

OCB is, if anything, worse than GCM when it comes to data volume limits. It has the same confidentiality bounds as GCM
(slightly worse, in fact), but once you hit a collision you also lose authenticity and enable simple forgeries [1].

The real issue here is the block size of AES, not the security bounds of particular modes. Those are by and large all
limited by the birthday bound. You could go with more exotic beyond-birthday modes, but there don't seem to be any being
proposed for TLS. The simple solution to the birthday blues is, of course, to use a larger block.

[1] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/General_Comments/papers/Ferguson.pdf

---

From: Aaron Zauner <[email-masked]>
Date: Fri, 1 Jan 2016 17:01:38 +0100

Hi Samuel,

> (slightly worse, in fact), but once you hit a collision you also lose authenticity and enable simple forgeries [1].

If I understand correctly the same is true for GCM?

I did not say that OCB provides beyond-birthday bound security. I'm
well aware that the mode does not really affect this issue in that
particular case.

> proposed for TLS. The simple solution to the birthday blues is, of course, to use a larger block.

Sure. Agreed.

Thanks for the feedback,
Aaron

---

From: [email-masked]
Date: Fri, 01 Jan 2016 17:16:30 +0000

Quoting Aaron Zauner <[email-masked]>:

>> OCB is, if anything, worse than GCM when it comes to data volume  
>> limits. It has the same confidentiality bounds as GCM
>> (slightly worse, in fact), but once you hit a collision you also  
>> lose authenticity and enable simple forgeries [1].
>>
>

The contention with GCM in this thread has been, so far, focused on  
confidentiality. This is because, by a result of Bernstein [1] (see  
also Appendix C of [2]), after q = 2^60 messages sent, plus q' = 2^60  
attempted forgeries by an attacker with messages at most l_A = 2^16  
blocks long, the probability of an attacker to forge a message is  
still ~2^-52. This does not present a data volume problem at the  
moment for the authentication part of AES-GCM.

On the other hand, after 2^60 OCB messages of 2^16 blocks (and thus  
2^76 total blocks), a block collision is almost guaranteed to have  
happened, enabling the aforementioned forgeries.

What you may be thinking of is the GCM behavior on _nonce reuse_. In  
this case, we are able to recover the authentication key by root  
finding and forge messages at will. This is also the case with  
OCB---on nonce reuse, we can forge any message that has the same  
checksum as a valid message.

[1] http://cr.yp.to/antiforgery/securitywcs-20050227.pdf
[2] https://eprint.iacr.org/2012/438

---

From: Aaron Zauner <[email-masked]>
Date: Fri, 1 Jan 2016 19:25:22 +0100

Hi,

* [email-masked] <[email-masked]> [01/01/2016 18:19:26] wrote:
> confidentiality. This is because, by a result of Bernstein [1] (see also
> Appendix C of [2]), after q = 2^60 messages sent, plus q' = 2^60 attempted
> forgeries by an attacker with messages at most l_A = 2^16 blocks long, the
> probability of an attacker to forge a message is still ~2^-52. This does not
> present a data volume problem at the moment for the authentication part of
> AES-GCM.
> 

Interesting - I was not aware of that. Thanks for taking the time to
explain.

> On the other hand, after 2^60 OCB messages of 2^16 blocks (and thus 2^76
> total blocks), a block collision is almost guaranteed to have happened,
> enabling the aforementioned forgeries.

Sure. Would you see any way to improve this situation in the draft,
i.e. give implementation recommendations or similar?

> What you may be thinking of is the GCM behavior on _nonce reuse_. In this
> case, we are able to recover the authentication key by root finding and
> forge messages at will. This is also the case with OCB---on nonce reuse, we
> can forge any message that has the same checksum as a valid message.

No. Nonce-reuse is a seperate issue, the one I addressed in my
commit on the draft linked to in an earlier message. The
construction used in the chacha20/poly1305 draft is very elegant I
think: if you do not implement a proper nonce the implementation
will not interoperate with other implementation conforming to spec.

Thanks again,
Aaron

---

From: Samuel Neves <[email-masked]>
Date: Fri, 01 Jan 2016 19:01:59 +0000

> i.e. give implementation recommendations or similar?

I think the FAQ you quoted before (itself quoting RFC 7253) suggesting  
the limitation of blocks processed to 2^48 is reasonable. Depending on  
the consensus here on what an acceptable success probability for an  
attacker is, you may want to bring that down to 2^32, as is being  
suggested for GCM.

P.S.: Apologies. I had interpreted your diversion into OCB as  
suggesting it as an alternative to GCM to address the data volume  
limitation in question. On a second read, that turned out not to be  
the case, and you were only asking for help.