Subject: [TLS] [Technical Errata Reported] RFC7905 (5251)

From: RFC Errata System <[email-masked]>
Date: Thu, 1 Feb 2018 05:59:47 -0800 (PST)

The following errata report has been submitted for RFC7905,
"ChaCha20-Poly1305 Cipher Suites for Transport Layer Security (TLS)".

--------------------------------------
You may review the report below and at:
http://www.rfc-editor.org/errata/eid5251

--------------------------------------
Type: Technical
Reported by: Xavier Bonnetain <[email-masked]>

Section: 4. Security

Original Text
-------------
   Poly1305 is designed to ensure that forged messages are rejected with
   a probability of 1-(n/2^107), where n is the maximum length of the
   input to Poly1305.  In the case of (D)TLS, this means a maximum
   forgery probability of about 1 in 2^93.

Corrected Text
--------------
   Poly1305 is designed to ensure that forged messages are rejected with
   a probability of 1-(n/2^106), where n is the maximum length of the
   input to Poly1305.  In the case of (D)TLS, this means a maximum
   forgery probability of about 1 in 2^92.

Notes
-----
The security claimed on poly1305 is slightly beyond what was proven by the designer (see https://cr.yp.to/mac/poly1305-20050329.pdf), and the trivial forgery attempt with a message of length 1 succeeds with probability 2^{-106}.

Instructions:
-------------
This erratum is currently posted as "Reported". If necessary, please
use "Reply All" to discuss whether it should be verified or
rejected. When a decision is reached, the verifying party  
can log in to change the status and edit the report, if necessary. 

--------------------------------------
RFC7905 (draft-ietf-tls-chacha20-poly1305-04)
--------------------------------------
Title               : ChaCha20-Poly1305 Cipher Suites for Transport Layer Security (TLS)
Publication Date    : June 2016
Author(s)           : A. Langley, W. Chang, N. Mavrogiannopoulos, J. Strombergson, S. Josefsson
Category            : PROPOSED STANDARD
Source              : Transport Layer Security
Area                : Security
Stream              : IETF
Verifying Party     : IESG

---

From: Adam Langley <[email-masked]>
Date: Mon, 12 Feb 2018 15:30:11 -0800

On Thu, Feb 1, 2018 at 5:59 AM, RFC Errata System <[email-masked]
> wrote:

> Original Text

I'm not sure that this errata report is correct.

The full formula is beyond email HTML to express, but see the "Security
Guarantee" section of  https://cr.yp.to/mac/poly1305-20050329.pdf

The section seems to be talking about blind forgeries, so C = 0. D = 1
because this is a per-attempt measure. Then we have 8*L/16 on the top of
the fraction, which is 1/2 * L (where L = byte length of a message). If we
multiply top and bottom by two, we get L / 2^107. For (D)TLS, with a
maximum encrypted plaintext length of ~2^14, that gives 2^{-93}.

Cheers

AGL

---

From: Xavier Bonnetain <[email-masked]>
Date: Tue, 13 Feb 2018 01:22:42 +0100 (CET)

----- Mail original -----

> De: "Adam Langley" <[email-masked]>
> À: "RFC Errata System" <[email-masked]>
> Cc: "Wan-Teh Chang" <[email-masked]>, "Nikos Mavrogiannopoulos"
> <[email-masked]>, "Joachim Strömbergson" <[email-masked]>, "Simon
> Josefsson" <[email-masked]>, "Kathleen Moriarty"
> <[email-masked]>, "Eric Rescorla" <[email-masked]>, "Joseph
> Salowey" <[email-masked]>, [email-masked], "xavier bonnetain"
> <[email-masked]>, [email-masked]
> Envoyé: Mardi 13 Février 2018 00:30:11
> Objet: Re: [Technical Errata Reported] RFC7905 (5251)

> On Thu, Feb 1, 2018 at 5:59 AM, RFC Errata System < [email-masked]
> > wrote:

> because this is a per-attempt measure. Then we have 8*L/16 on the top of the
> fraction, which is 1/2 * L (where L = byte length of a message). If we
> multiply top and bottom by two, we get L / 2^107. For (D)TLS, with a maximum
> encrypted plaintext length of ~2^14, that gives 2^{-93}.

> AGL

If we are in the situation C = 0, D = 1 and L=2^{14} for (D)TLS, the forgery probability may indeed not be affected (and may even be smaller). However, the explanation "Poly1305 is designed to ensure that forged messages are rejected with a probability of 1-(n/2^107), where n is the maximum length of the input to Poly1305." is presenting Poly1305 as slightly stronger than it really is (and there is an attack with success probability 2^{-106} with C=1, D=1, L=1, as the hashing key r has 106 effective bits). 

Regards, 
Xavier

---

From: Adam Langley <[email-masked]>
Date: Thu, 22 Feb 2018 13:32:08 -0800

> If we are in the situation C = 0, D = 1 and L=2^{14} for (D)TLS, the forgery probability may indeed not be affected (and may even be smaller). However, the explanation "Poly1305 is designed to ensu…

I don't believe that this contradicts the equation. While it's true
that r only contains 106 bits, knowing r isn't sufficient to forge a
message unless one also has a legitimate message from which to
calculate the masking value. In the C = 0 situation, the attacker does
not have such a message. As the attacker gathers samples of legitimate
messages, their success probability does, indeed, increase.

I suspect that any simplification of the security equation is going to
have these issues.

Cheers

AGL