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

Colin Perkins <csp@csperkins.org> Mon, 08 June 2020 22:50 UTC

Return-Path: <csp@csperkins.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 84A4A3A0889 for <cfrg@ietfa.amsl.com>; Mon, 8 Jun 2020 15:50:05 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level:
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=csperkins.org
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 1Xh5fXvSZF6A for <cfrg@ietfa.amsl.com>; Mon, 8 Jun 2020 15:50:03 -0700 (PDT)
Received: from haggis.mythic-beasts.com (haggis.mythic-beasts.com [IPv6:2a00:1098:0:86:1000:0:2:1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D8DDF3A0885 for <cfrg@ietf.org>; Mon, 8 Jun 2020 15:50:02 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=csperkins.org; s=mythic-beasts-k1; h=To:Date:From:Subject; bh=sVkorlTCWdQz5/4P/eVYE7YXx+HO/ObebojQoM/qGAw=; b=xrj2pbcInVxjk/h/ANQolbRe7F L6QW3e0tMmgm8kGo1Bkgj+NllUBK+2xVlxkJ0Vo+mBT2NUh6fBrZe2tps7Bb4KQHUbzWKFAUlQkLy BNMLc257ijHIul+nBV3CC+gAGRIesp8OB58IAHp3gK7dpj6RHX3OTJm2xxaSk12M6K0NWscmwqAL2 dssmW+bmMeEaYhbfoajYDyZ35gCfsmeK4jVtvBKFjFqiWWjQtRLgcu1hzHqQQpRbIfpvOgE8N94m0 HxY4CSYG7fJQ6kocF02Qlum4psyETb5/9AOBr+uGj9fIHzZ6Fvzcg1sZWf68oH0uhi9+YdzqlxVWu qmhxpIiQ==;
Received: from [81.187.2.149] (port=37031 helo=[192.168.0.80]) by haggis.mythic-beasts.com with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92.3) (envelope-from <csp@csperkins.org>) id 1jiQaa-0008JF-0Q; Mon, 08 Jun 2020 23:49:56 +0100
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.14\))
From: Colin Perkins <csp@csperkins.org>
In-Reply-To: <de5d811e-f233-066f-fa23-eeffd3fae905@gmail.com>
Date: Mon, 8 Jun 2020 23:49:50 +0100
Cc: Yoav Nir <ynir.ietf@gmail.com>, James Muir <muir.james.a@gmail.com>, Adam Langley <agl@google.com>
Content-Transfer-Encoding: quoted-printable
Message-Id: <1BBFC85E-7086-4B52-9A85-40180A312584@csperkins.org>
References: <20200321174647.625DAF40704@rfc-editor.org> <de5d811e-f233-066f-fa23-eeffd3fae905@gmail.com>
To: cfrg@ietf.org
X-Mailer: Apple Mail (2.3445.104.14)
X-BlackCat-Spam-Score: 4
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/zBJ0nNOagl8ZT4zAzMxTumlIadY>
Subject: [Cfrg] [Technical Errata Reported] RFC8439 (6025)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 08 Jun 2020 22:50:06 -0000

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 <muir.james.a@gmail.com> 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 <muir.james.a@gmail.com>
>> 
>> 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/