Re: [Cfrg] How to handle block counter wrap in IETF's ChaCha algorithm?

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Sat, 26 January 2019 12:45 UTC

Return-Path: <smyshsv@gmail.com>
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 F3CAC1311B5 for <cfrg@ietfa.amsl.com>; Sat, 26 Jan 2019 04:45:35 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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=gmail.com
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 sf4jDvRVq2FD for <cfrg@ietfa.amsl.com>; Sat, 26 Jan 2019 04:45:32 -0800 (PST)
Received: from mail-qt1-x834.google.com (mail-qt1-x834.google.com [IPv6:2607:f8b0:4864:20::834]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 56D1F123FFD for <cfrg@irtf.org>; Sat, 26 Jan 2019 04:45:32 -0800 (PST)
Received: by mail-qt1-x834.google.com with SMTP id e5so13603803qtr.12 for <cfrg@irtf.org>; Sat, 26 Jan 2019 04:45:32 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=nRKDqjz9h3L9uabdDaP9GxXmyxuLtrixKYxuJMd8pdA=; b=BuIiGlMwI+uN3dFS9yy03AGyrnC/6lfBiiRalBWu2q4cAIetW8O0hsveB+oLYqNciA XDwN7hl4xIKIvQImi1wYvoCeNcBcRJyIu6c+6sZS3pztYS0A4w+9puXvMt1X2yBSgmIE rLO9fuBd0OwVB96hhrDtpQyGAmYYna7D2zP7ulMtbdAeOqe4prCfcxfrgQq9A6ZrYxIb ZKnfONjSDcclO4I5Gvk8DqK4/nb4zd5ZWselZDslig8hXXYKoDT/s1f4qX4jcb+JOWfe M8sE6lZU9kwDRr/zdlIlAiaEvScyl4rPZZSyXFIqLbXq5omb8mRlD59obx6nnetHf5f1 HEVA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=nRKDqjz9h3L9uabdDaP9GxXmyxuLtrixKYxuJMd8pdA=; b=QK9n3FbPPSlJf96RnaHKm517H/d99RBI0GJVDynGs3mkOdGShafGwVBuSSohibMmNx BTF/G/inc6EaZBfhjFm9nQxHWW1zFMBHm+2im6kXKF7xjT+YmITSS4vA3LrSrg/JyQXD J5pM1IQ/YRPvMT4mTu8P4D5fy73a5nNw6jrygxiBfHAipA7VFyPDwcTm3AwwT0OvlHLf hFSDfpEmTS6lNT878agvoGWeqONd+iuXrmT1+nTi/FfYoP9TIIoRnoEPZ9T9K/SZSILy ncbv2BtD/j367vLE/7SRpZ2yLCW7Jd3EbXlSlWwgJrxhIe11tlvcCP+c5snzUR8TEh4O xKog==
X-Gm-Message-State: AJcUukdbaSnrwgh9UvUNMhfgu1co5mVVO2En6Ink952Nqe0B/tQuAdGf so6T5iNDyh4h6UpxUkDRimhDe2PbI4sNkHX2BHA=
X-Google-Smtp-Source: ALg8bN6RLcs21S8gIy2jApKOt9AyWcv+li26/rH5le5L/Sp475b0r3NsVWnrn2FBvZLG4fwfs3EJ+m+eCw0YTITE5oY=
X-Received: by 2002:ac8:4709:: with SMTP id f9mr14439518qtp.58.1548506731245; Sat, 26 Jan 2019 04:45:31 -0800 (PST)
MIME-Version: 1.0
References: <CAH8yC8=0Y6qK0dHauib8fM-ybGozJJRA7b5vKnu8-dPVxwytLQ@mail.gmail.com> <E6862AD6-6F3F-4F0E-A44B-0014CB79BDD8@rhul.ac.uk>
In-Reply-To: <E6862AD6-6F3F-4F0E-A44B-0014CB79BDD8@rhul.ac.uk>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
Date: Sat, 26 Jan 2019 15:44:28 +0300
Message-ID: <CAMr0u6kr5zTUuoPnrx9z2No41pTj6XyWnys9QSYX-xhatDf6yA@mail.gmail.com>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
Cc: "noloader@gmail.com" <noloader@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000a5f3f205805bd131"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/4WycJ43nsU7U9RC-Z3hSpPd7kws>
Subject: Re: [Cfrg] How to handle block counter wrap in IETF's ChaCha algorithm?
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: Sat, 26 Jan 2019 12:45:36 -0000

Dear Jeff, Dear Kenny,

I totally agree with Kenny, that the best practice here seems to be
returning an error in the case of reaching maximal value, disallowing
wrapping (and starting the blockcounter at 0 or 1 for each fresh nonce).
In all secure crypto applications that I'm aware of such a check exists,
protecting both from repeating the value of a counter (for the same key and
nonce) and from exceeding the limit for key lifetime (some information on
that issue can be found in
https://datatracker.ietf.org/doc/draft-irtf-cfrg-re-keying/).
In terms of CryptoAPI, the CryptEncrypt function may return FALSE with an
error code of NTE_BAD_KEY if it is called in such a way that the total
plaintext size processed with the used key exceeds a certain limit.

Regarding the calling application, it should be aware of limits for
plaintext size to be encrypted (such a limit should be defined in the
documentation for a library, e.g. when describing error codes and their
meaning) and prevent unlimited usage of a single symmetric key.

Best regards,
Stanislav Smyshlyaev

сб, 26 янв. 2019 г. в 15:06, Paterson, Kenny <Kenny.Paterson@rhul.ac.uk>:

> Hi Jeff,
>
> As you'll know it's crucial to avoid using repeated (blockcounter, nonce)
> combinations under the same key for this algorithm.
>
> In my view, the best way to do that is for implementations to return an
> error in the event of any overflow of blockcounter, and to ensure that this
> is a rare event by always starting blockcounter at 0. I don't see any
> reason not to start with this value (you might use 1 rather than 0 in a
> specific situation like building an AEAD if value 0 was already being used
> to generate keys for Poly1305, but you're still really starting your new
> ChaCha20 context with 0 there too).
>
> This is possible to enforce if, for example, there's a wrapper around the
> raw ChaCha20 algorithm that does not expose the blockcounter to the calling
> application, but that instead manages it internally on a per context basis.
> To me, this seems like a sensible way to handle the issue (but then I'm not
> a pro crypto developer).
>
> If you really must wrap blockcounter then I'd argue that it should be done
> without touching the nonce. The reason is that this new nonce (created by
> incrementing the existing nonce or whatever) could legitimately be used in
> a different ChaCha instance under the same key, and your code may have no
> control over what blocknumbers would be used with that nonce value, thereby
> increasing the risk of reuse of (blockcounter,nonce) pairs. But you'd still
> need checks to make sure there were no blockcounter repeats if you just
> wrapped without touching the nonce. Hence better to start low and disallow
> wraps (which is after all just such a check!).
>
> I'm interested to know what other people think. I see it as really being a
> tricky (if common) crypto API design issue.
>
> Cheers,
>
> Kenny
>
>
> > On 26 Jan 2019, at 03:21, Jeffrey Walton <noloader@gmail.com> wrote:
> >
> > Hi Everyone,
> >
> > This question is moved from another list to CFRG. It was suggested
> > CFRG is a better forum for the question.
> >
> > I'm working on test vectors for an implementation of the IETF's
> > version of ChaCha from RFC 8439. According to Section 2.4, page 9
> > (https://tools.ietf.org/html/rfc8439#section-2.4):
> >
> >   The inputs to ChaCha20 are:
> >      o  A 256-bit key
> >      o  A 32-bit initial counter.  This can be set to any number, but
> will
> >         usually be zero or one...
> >      o  A 96-bit nonce.  In some protocols, this is known as the
> >         Initialization Vector.
> >      o  An arbitrary-length plaintext
> >
> > Now a test vector. We set:
> >
> >    Key - All 0's
> >    IV - All 0's
> >    Initial Counter Block - 0xfffffffe
> >    Plaintext -  256 bytes of all 0's
> >
> > After the first two 64-bit blocks the counter will wrap around to 0.
> > This is where the problem arises.
> >
> > One implementation I am aware wraps the block counter. It produces a
> keystream:
> >
> > 032CC123482C31711F94C941AF5AB1F4155784332ED5348FE79AEC5EAD4C06C3
> > F13C280D8CC49925E4A6A5922EC80E13A4CDFA840C70A1427A3CB699166991A5
> > ACE4CD09E294D1912D4AD205D06F95D9C2F2BFCF453E8753F128765B62215F4D
> > 92C74F2F626C6A640C0B1284D839EC81F1696281DAFC3E684593937023B58B1D
> > 76B8E0ADA0F13D90405D6AE55386BD28BDD219B8A08DED1AA836EFCC8B770DC7
> > DA41597C5157488D7724E03FB8D84A376A43B8F41518A11CC387B669B2EE6586
> > 9F07E7BE5551387A98BA977C732D080DCB0F29A048E3656912C6533E32EE7AED
> > 29B721769CE64E43D57133B074D839D531ED1F28510AFB45ACE10A1F4B794D6F
> >
> > Another implementation I am aware wraps the block counter, but it also
> > increments the high word of the nonce, similar to the way original
> > ChaCha used a 64-bit block counter. It produces a keystream:
> >
> > 032CC123482C31711F94C941AF5AB1F4155784332ED5348FE79AEC5EAD4C06C3
> > F13C280D8CC49925E4A6A5922EC80E13A4CDFA840C70A1427A3CB699166991A5
> > ACE4CD09E294D1912D4AD205D06F95D9C2F2BFCF453E8753F128765B62215F4D
> > 92C74F2F626C6A640C0B1284D839EC81F1696281DAFC3E684593937023B58B1D
> > 3DB41D3AA0D329285DE6F225E6E24BD59C9A17006943D5C9B680E3873BDC683A
> > 5819469899989690C281CD17C96159AF0682B5B903468A61F50228CF09622B5A
> > 46F0F6EFEE15C8F1B198CB49D92B990867905159440CC723916DC00128269810
> > 39CE1766AA2542B05DB3BD809AB142489D5DBFE1273E7399637B4B3213768AAA
> >
> > I don't believe the issue arises in Bernsein's version of ChaCha
> > because the block counter is 64-bits and always starts at 0. Bernstein
> > does not allow arbitrary values for the initial block counter. The
> > constraint is unstated in Bernstein's paper on ChaCha, but it is
> > obvious when examining his reference implementation (from chacha-ref.c
> > version 20080118):
> >
> >    void ECRYPT_ivsetup(ECRYPT_ctx *x,const u8 *iv)
> >    {
> >        x->input[12] = 0;
> >        x->input[13] = 0;
> >        x->input[14] = U8TO32_LITTLE(iv + 0);
> >        x->input[15] = U8TO32_LITTLE(iv + 4);
> >    }
> >
> > My question is, what should happen when the block counter wraps?
> >
> > Thanks in advance.
> >
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>