[Cfrg] [Technical Errata Reported] RFC8439 (6025)

[Colin Perkins <[e-mail]>]

Hi CFRG,

This relates to https://www.rfc-editor.org/errata/eid6025 and needs input from the RG to verify.

Colin



> On 10 Apr 2020, at 22:26, James Muir <[e-mail]> wrote:
> On 2020-03-21 1:46 p.m., RFC Errata System wrote:
>> 
>> The following errata report has been submitted for RFC8439,
>> "ChaCha20 and Poly1305 for IETF Protocols".
>> 
>> --------------------------------------
>> You may review the report below and at:
>> https://www.rfc-editor.org/errata/eid6025
>> 
>> --------------------------------------
>> Type: Technical
>> Reported by: James Muir <[e-mail]>
>> 
>> Section: 8439
>> 
>> Original Text
>> -------------
>>> From Section 3 (re implementation advice for Poly1305):
>> 
>> 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.
>> 
>> re #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.
>> 
>> You can 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). 
>> 
>> re #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.
>> 
>> 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.
> 
> Perhaps someone could take a few minutes to verify what I reported.
> 
> I see in Section 4 ("Security Considerations") there is some information related to the points I raised.  That text should also be updated.
> 
>> For Poly1305, the operations are addition, multiplication. and
>> modulus, all on numbers with greater than 128 bits.  This can be done
>> in constant time, but a naive implementation (such as using some
>> generic big number library) will not be constant time.  For example,
>> if the multiplication is performed as a separate operation from the
>> modulus, the result will sometimes be under 2^256 and sometimes be
>> above 2^256.  Implementers should be careful about timing
>> side-channels for Poly1305 by using the appropriate implementation of
>> these operations.
> 
> I guess this is the rationale for the 288-bit bound given in Section 3:  256 bits is too small, so add 32 more bits (this must assume a 32-bit word size).  However, 256 bits isn't too small because r is clamped (r < 2^124).
> 
> Even if the partial reduction step only reduces the accumulator to 131 bits, you can still get by with 256 bits.
> 
> I think the Section 4 warning about non-constant time naive implementations is good, but the statement in Section 3 about using a naive implementation needs more context.
> 
> Thank-you for considering this report.
> 
> -James M
> 
> https://www.ccsl.carleton.ca/~jamuir/

-- 
Colin Perkins
https://csperkins.org/