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 >
- [Cfrg] How to handle block counter wrap in IETF's… Jeffrey Walton
- Re: [Cfrg] How to handle block counter wrap in IE… Paterson, Kenny
- Re: [Cfrg] How to handle block counter wrap in IE… Stanislav V. Smyshlyaev
- Re: [Cfrg] How to handle block counter wrap in IE… James Cloos
- Re: [Cfrg] How to handle block counter wrap in IE… Taylor R Campbell
- Re: [Cfrg] How to handle block counter wrap in IE… Yoav Nir