[CFRG] [Errata Verified] RFC8439 (6025)

RFC Errata System <rfc-editor@rfc-editor.org> Wed, 17 November 2021 07:31 UTC

To: muir.james.a@gmail.com, ynir.ietf@gmail.com, agl@google.com
From: RFC Errata System <rfc-editor@rfc-editor.org>
Cc: smyshsv@gmail.com, irsg@irtf.org, cfrg@irtf.org, rfc-editor@rfc-editor.org
Content-Type: text/plain; charset="UTF-8"
Message-Id: <20211117073055.249C262BB38@rfc-editor.org>
Date: Tue, 16 Nov 2021 23:30:55 -0800
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ljNCe6kbTLBUNMlzlkFy3Co0DeE>
Subject: [CFRG] [Errata Verified] RFC8439 (6025)
Precedence: list

The following errata report has been verified for RFC8439,
"ChaCha20 and Poly1305 for IETF Protocols". 

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

--------------------------------------
Status: Verified
Type: Technical

Reported by: James Muir <muir.james.a@gmail.com>
Date Reported: 2020-03-21
Verified by: Stanislav Smyshlyaev (IRSG)

Section: 3

Original Text
-------------
A constant-time but not optimal approach would be to naively implement the arithmetic operations for 288-bit integers, because even a naive implementation will not exceed 2^288 in the multiplication of (acc+block) and r.


Corrected Text
--------------
It is possible to create a constant-time, but not optimal, implementation by implementing arithmetic operations for 256-bit integers, because even a naive implementation will not exceed 2^256 in the multiplication of (acc+block) and r (note that we have r < 2^124 because r is "clamped").


Notes
-----
There are two issues 1) 288 bits is too big, and 2) a naive implementation of 288 bit integer arithmetic isn't necessarily constant time.

#1:  288 seems to be tied to the machine int size and assumes 32-bit integers (288 is nine 32-bit integers).  It is probably better to give a number independent of the machine int size. It is possible to compute Poly1305 using 255 bit arithmetic. Padded blocks of the message are in the range 2^8, 2^8 +1,..., 2^129 -1. Assuming that the partial reduction step always reduces the accumulator to 130 bits, we have acc < 2^130, so acc+block < 2^131. r is a 16 byte value, but some of its bits are "clampled", so we have r < 2^124. Thus (acc+block)*r < 2^255; so we can get by with 255 bit big-integer arithmetic (probably 256 bits is more convenient to work with). 

#2:  big-integer arithmetic can be implemented in constant time, but perhaps not in a obvious or naive way.  Keeping things constant time seems to depend on the characteristics of the underlying processor.

--------------------------------------
RFC8439 (draft-nir-cfrg-rfc7539bis-04)
--------------------------------------
Title               : ChaCha20 and Poly1305 for IETF Protocols
Publication Date    : June 2018
Author(s)           : Y. Nir, A. Langley
Category            : INFORMATIONAL
Source              : Crypto Forum Research Group
Area                : N/A
Stream              : IRTF
Verifying Party     : IRSG

[CFRG] [Errata Verified] RFC8439 (6025) RFC Errata System