[CFRG] Re: Update RFC 8439 on ChaCha20 and Poly1305 to remove clamping?

[John Mattsson <[e-mail]>]

>The table only includes the maximum tag length in bytes that behaves like an ideal MAC in unicast QUIC.
That was not completely true, GCM_SST_12 was included as an example of truncation and POLY1743-SST has quite a bit of security margin. An 18-byte POLY1743-SST_18 would behave like an ideal MAC in unicast QUIC (POLY1743-SST_16 would also behave as an ideal MAC in TLS with 2^32 bytes records).
https://www.ietf.org/archive/id/draft-ietf-tls-super-jumbo-record-limit-00.html

John

From: John Mattsson <john.mattsson=[e-mail]>
Date: Sunday, 22 December 2024 at 11:08
To: Chris Barber <[e-mail]>, [e-mail] <[e-mail]>
Subject: [CFRG] Re: Update RFC 8439 on ChaCha20 and Poly1305 to remove clamping?
Hi Chris,

That is a good idea. Using the security level numbers in [1]

   POLY1743                161
   POLY1503                137
   GHASH/POLYVAL           128
   POLY1305-NC             125
   POLY1164                107
   POLY1305                103

Where NC is No Clamping, and using the ideas of Nyberg, Gilbert, and Robshaw [2], that are used in GCM-SST [3] and all other universal hash functions in mobile networks, my understanding is that you can get algorithms that work like ideal MACs in security protocols with replay protection as long as tag_length < security_level - log2(ℓ). Expanding Table 3 in [3], which is comparing security in unicast QUIC (ℓ ≈ 2^12).

   +====================+=========+==============+=============+=================+
   | Name               |     Tag |      Forgery |     Forgery | Expected number |
   |                    |  length |  probability | probability |    of forgeries |
   |                    | (bytes) |       before | after first |                 |
   |                    |         |        first |     forgery |                 |
   |                    |         |      forgery |             |                 |
   +====================+=========+==============+=============+=================+
   | POLY1743-SST_16    |      16 |    1 / 2^128 |   1 / 2^128 |       v / 2^128 |
   +--------------------+---------+--------------+-------------+-----------------+
   | POLY1503-SST_15    |      15 |    1 / 2^120 |   1 / 2^120 |       v / 2^120 |
   +--------------------+---------+--------------+-------------+-----------------+
   | GCM_SST_14         |      14 |    1 / 2^112 |   1 / 2^112 |       v / 2^112 |
   +--------------------+---------+--------------+-------------+-----------------+
   | POLY1305-NC-SST_13 |      13 |    1 / 2^104 |   1 / 2^104 |       v / 2^104 |
   +--------------------+---------+--------------+-------------+-----------------+
   | GCM_SST_12         |      12 |     1 / 2^96 |    1 / 2^96 |        v / 2^96 |
   +--------------------+---------+--------------+-------------+-----------------+
   | POLY1164-SST_11    |      11 |     1 / 2^88 |    1 / 2^88 |        v / 2^88 |
   +====================+=========+==============+=============+=================+
   | POLY1305           |      16 |     1 / 2^91 |    1 / 2^91 |        v / 2^91 |
   +--------------------+---------+--------------+-------------+-----------------+
   | GCM                |      16 |    1 / 2^116 |           1 | δ ⋅ v^2 / 2^117 |
   +--------------------+---------+--------------+-------------+-----------------+

The table only includes the maximum tag length in bytes that behaves like an ideal MAC in unicast QUIC. The SST variant can be truncated to any lenght and still behave like ideal MACs. I think it is important to strive for MACs that behaves like ideal MACs. Users and implementors of cryptography expect algorithms to behave like ideal MACs. Universal hash functions can be designed to behave like ideal MACs in unicast security protocols with replay protection. Using 12 byte tags with better security than the current 16 byte tags would also be a significant performance improvement.

Cheers,
John

[1] https://csrc.nist.gov/csrc/media/Presentations/2024/universal-hash-designs-for-an-accordion-mode/images-media/sess-7-degabriele-acm-workshop-2024.pdf

[2] https://csrc.nist.gov/CSRC/media/Projects/Block-Cipher-Techniques/documents/BCM/Comments/general-comments/papers/Nyberg_Gilbert_and_Robshaw.pdf

[3] https://www.ietf.org/archive/id/draft-mattsson-cfrg-aes-gcm-sst-13.html


From: Chris Barber <[e-mail]>
Date: Saturday, 21 December 2024 at 12:02
To: [e-mail] <[e-mail]>
Subject: [CFRG] Re: Update RFC 8439 on ChaCha20 and Poly1305 to remove clamping?
Since the resulting construction would be incompatible with ChaCha20-Poly1305, it provides an opportunity to use Poly1503 and Poly1163 instead of simply removing the clamping step. It would also avoid collisions in algorithm names.

On Sat, Dec 21, 2024 at 10:54 AM John Mattsson <john.mattsson=[e-mail]<mailto:[e-mail]>> wrote:
At the NIST Accordion workshop 2024 [1], Degabriele, Gilcher, Govinden, and Paterson had a presentation on Poly1305 [2]:

“It is known to outperform GCM on CPUs which do not support AES and Carry-Less-Multiplication instructions”

"To enable FPU implementations, 22 bits in the key are ‘clamped’ to zero, resulting in a loss of 22 bits of security (without a performance benefit)."

"However, all modern implementations employ integer arithmetic instead"

While ChaCha20 provides much better confidentiality than e.g., AES-256-CTR, which is vulnerable to distinguishing attack with a complexity of approximately 2^129 / q, where q is the number of invocations of the AES-256 encryption function, Poly1305 is not as strong as one would expect.

Based on that all modern implementations employ integer arithmetic instead, I think CFRG should update RFC 8439 and register a version of ChaCha20-Poly1305 without clamping. In addition, I think the update should use the ideas in GCM-SST [3], which improves the integrity advantage from vl / 2^t to (vl / 2^128 + v / 2^t) [4]. The easiest way to improve security is to make smaller improvements to already deployed algorithms. But note that even with clamping ChaCha20-Poly1305 provides better integrity that AES-GCM in e.g., unicast QUIC. While ChaCha20-Poly1305 always behaves like an ideal MAC of length 91 bits, AES-GCM can be as weak as an ideal MAC of length 64.4 bits. BSI states that an ideal MAC with a 96-bit tag length is considered acceptable for most applications [5].

Cheers,
John

[1] https://csrc.nist.gov/events/2024/accordion-cipher-mode-workshop-2024

[2] https://csrc.nist.gov/csrc/media/Presentations/2024/universal-hash-designs-for-an-accordion-mode/images-media/sess-7-degabriele-acm-workshop-2024.pdf

[3] https://www.ietf.org/archive/id/draft-mattsson-cfrg-aes-gcm-sst-13.html

[4] https://eprint.iacr.org/2024/1928.pdf

[5] https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.html



On 2018-06-19, 08:12, "[e-mail]<mailto:[e-mail]>" <[e-mail]<mailto:[e-mail]>> wrote:
A new Request for Comments is now available in online RFC libraries.


        RFC 8439

        Title:      ChaCha20 and Poly1305 for IETF Protocols
        Author:     Y. Nir,
                    A. Langley
        Status:     Informational
        Stream:     IRTF
        Date:       June 2018
        Mailbox:    [e-mail]<mailto:[e-mail]>,
                    [e-mail]<mailto:[e-mail]>
        Pages:      46
        Characters: 88847
        Obsoletes:  RFC 7539

        I-D Tag:    draft-nir-cfrg-rfc7539bis-04.txt

        URL:        https://www.rfc-editor.org/info/rfc8439

        DOI:        10.17487/RFC8439

This document defines the ChaCha20 stream cipher as well as the use
of the Poly1305 authenticator, both as stand-alone algorithms and as
a "combined mode", or Authenticated Encryption with Associated Data
(AEAD) algorithm.

RFC 7539, the predecessor of this document, was meant to serve as a
stable reference and an implementation guide.  It was a product of
the Crypto Forum Research Group (CFRG).  This document merges the
errata filed against RFC 7539 and adds a little text to the Security
Considerations section.

This document is a product of the Crypto Forum Research Group of the IRTF.


INFORMATIONAL: This memo provides information for the Internet community.
It does not specify an Internet standard of any kind. Distribution of
this memo is unlimited.

This announcement is sent to the IETF-Announce, rfc-dist and IRTF-Announce lists.To subscribe or unsubscribe, see
  https://www.ietf.org/mailman/listinfo/ietf-announce
  https://mailman.rfc-editor.org/mailman/listinfo/rfc-dist
  https://www.irtf.org/mailman/listinfo/irtf-announce

For searching the RFC series, see https://www.rfc-editor.org/search
For downloading RFCs, see https://www.rfc-editor.org/retrieve/bulk

Requests for special distribution should be addressed to either the
author of the RFC in question, or to [e-mail]<mailto:[e-mail]>.  Unless
specifically noted otherwise on the RFC itself, all RFCs are for
unlimited distribution.


The RFC Editor Team
Association Management Solutions, LLC


_______________________________________________
CFRG mailing list -- [e-mail]<mailto:[e-mail]>
To unsubscribe send an email to [e-mail]<mailto:[e-mail]>