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

"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Sat, 26 January 2019 12:06 UTC

Return-Path: <Kenny.Paterson@rhul.ac.uk>
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 5077812D4EF for <cfrg@ietfa.amsl.com>; Sat, 26 Jan 2019 04:06:07 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.042
X-Spam-Level:
X-Spam-Status: No, score=-2.042 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.142, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 (1024-bit key) header.d=rhul.onmicrosoft.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 RbYWVvXhUAp8 for <cfrg@ietfa.amsl.com>; Sat, 26 Jan 2019 04:06:04 -0800 (PST)
Received: from EUR04-VI1-obe.outbound.protection.outlook.com (mail-eopbgr80053.outbound.protection.outlook.com [40.107.8.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B77881200D7 for <cfrg@irtf.org>; Sat, 26 Jan 2019 04:06:03 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rhul.onmicrosoft.com; s=selector1-rhul-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=jyuhPiM2KVh+vqo+ri8ALK+3uqJD+7ozPeHyRtVyfZM=; b=ab7/kIKMWJi2/5kIORe3aPIQfFTi1F/0hxNssb7k2fDpE3qdhOLXlmDxxYIYf6uNcMQLrwzoDtjxa++vfRAdeW2myXw18pNKnsbSCwt3waM2y/BGdF5V9go5zJWQMvyoCX0Cnv0/McNFjFZB4/JkPnI7HDCVvByUKc+Uz2/3SSg=
Received: from DB7PR03MB3561.eurprd03.prod.outlook.com (52.134.98.30) by DB7PR03MB4779.eurprd03.prod.outlook.com (20.176.236.19) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1558.16; Sat, 26 Jan 2019 12:06:00 +0000
Received: from DB7PR03MB3561.eurprd03.prod.outlook.com ([fe80::8894:68a2:ecba:a321]) by DB7PR03MB3561.eurprd03.prod.outlook.com ([fe80::8894:68a2:ecba:a321%3]) with mapi id 15.20.1558.021; Sat, 26 Jan 2019 12:06:00 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: "noloader@gmail.com" <noloader@gmail.com>
CC: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] How to handle block counter wrap in IETF's ChaCha algorithm?
Thread-Index: AQHUtSY9WqcuBE+phEO1V1ZU55hR+6XBdLRS
Date: Sat, 26 Jan 2019 12:06:00 +0000
Message-ID: <E6862AD6-6F3F-4F0E-A44B-0014CB79BDD8@rhul.ac.uk>
References: <CAH8yC8=0Y6qK0dHauib8fM-ybGozJJRA7b5vKnu8-dPVxwytLQ@mail.gmail.com>
In-Reply-To: <CAH8yC8=0Y6qK0dHauib8fM-ybGozJJRA7b5vKnu8-dPVxwytLQ@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=Kenny.Paterson@rhul.ac.uk;
x-originating-ip: [92.2.118.154]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; DB7PR03MB4779; 6:tYoh4eWl+vG4mecnGGKEvufnI7gRyi+TrvHHL78dpJgbW1hDNhZw3XGz8Pz4myL8VPwOqjmdtZznbLIuGmlU51vnKeLHJfq2SpIKC/aFMy7Z1UBgPGeCLqttS7kqPWsHQt99dhBXIlQAaJWIBZgkv8v2Qq9rFKIT0Z+GcTa5Gh8U4HYIj6pWCJj5CXmiEnv+FWw2JpH4zezuUjC48H03llRK1psj9gNSNdN+SBz8g3SIHf4ppHnRxes565u9lBpIMFSLDqe4iT9taWKrBg93Pmm51ibwwPjyNr+QzJjENg1wtVNQjfrYSL1ynILjeys3FGN7haFyO4GGllUkLiV7OfJJSFYbQdsAyCH38fK+hzfbbgE2HtqAm93e9AvqGCKEmKzIBgZ1aCErltl3XjdDvzFSCrMosW1McCpkiCPeExfudF+vmp4q1hSba0wmos+x5q4gB+fAD2EI8llCaW6thw==; 5:QVJp3MzcXLVRsJjV4Ctqb6pVoSafbub1MrrXWOzmnDJauRpmNMaa7NsZLbb+cne4xCZQGg/pt90utMjrkUXPNcPtHfchHX+EAdcppR6LOgW0sTP4b6SfehlDo/kpC3tjPX10D2S4fRoAUnLA8PaY8GMcan8pp/WP5zrcuZyI9Lme9hFaa++ZmEX+qFV+iP0xm89Rgx5BxIlDqlLqYE5JLQ==; 7:V7kGE3VZLlcIA4synjqK77tH0hQoh3f/aeVEzRFax179cvHKrZ9TFxwITSp0IcLEbZi9j3G5PQSgBjEFg8MFBqgXHH/EGvyxXcBWqesklG1wZxYGPlLEB1+vUQl+f6vqjwHHOGNB933xFKSUOpBH7w==
x-ms-exchange-antispam-srfa-diagnostics: SOS;
x-ms-office365-filtering-correlation-id: da21ebb7-f5b0-4654-8801-08d68386a331
x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600110)(711020)(4605077)(2017052603328)(7153060)(7193020); SRVR:DB7PR03MB4779;
x-ms-traffictypediagnostic: DB7PR03MB4779:
x-microsoft-antispam-prvs: <DB7PR03MB4779E15BDB2CF9143C79EA93BC940@DB7PR03MB4779.eurprd03.prod.outlook.com>
x-forefront-prvs: 0929F1BAED
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(396003)(376002)(346002)(136003)(366004)(39860400002)(51874003)(189003)(199004)(53754006)(476003)(11346002)(446003)(97736004)(82746002)(99286004)(3846002)(102836004)(39060400002)(6116002)(4326008)(33656002)(86362001)(2906002)(186003)(76176011)(26005)(1411001)(6506007)(6246003)(2616005)(53546011)(72206003)(478600001)(36756003)(14454004)(966005)(6512007)(74482002)(2501003)(1730700003)(256004)(6916009)(6486002)(14444005)(1361003)(316002)(81166006)(81156014)(6306002)(25786009)(8936002)(229853002)(6436002)(66066001)(68736007)(71200400001)(5640700003)(71190400001)(8676002)(106356001)(486006)(53936002)(105586002)(305945005)(2351001)(7736002)(786003)(83716004); DIR:OUT; SFP:1101; SCL:1; SRVR:DB7PR03MB4779; H:DB7PR03MB3561.eurprd03.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
received-spf: None (protection.outlook.com: rhul.ac.uk does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam-message-info: uYhW87lwcCR/TkYKKlfarwlPkj153Xm2SQloOBMiAwhv/Nm7oHqJyw7rivHaAn8Kc+HkBVutZQ8Kchp8t0/zOVrLzEiLD/OJOaeq11GEBh663Mx4sNFeBKEFA9uC0XXHd1st3RXMGD7bZvBU+WpUoJ+7CYyPhFgHuOa0nyFXKXZ9MbyhZVnlnP01LwCiMqnxJI2REffUX/tHCG9LQFz5DneVyPandYVJgPNhBTZt88mP0wdIMprLKon91gv2V2k1QsqVlqTrz1+JJLKaOQV66fL2XnJXC4N1Wq3/PLSj45bwkWdpzuRNUhd66/yMmYi4BjQIyceNfE2JWVwrHmJZVvk3FiJNNb3aEeM2VRyU2/HXF9K5lkTLzZsFOudWYQeEBxvOVyDZgsTFswTcZY/5YIOE3ZjwsGp2NINeghlX+Uc=
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
X-MS-Exchange-CrossTenant-Network-Message-Id: da21ebb7-f5b0-4654-8801-08d68386a331
X-MS-Exchange-CrossTenant-originalarrivaltime: 26 Jan 2019 12:06:00.5321 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2efd699a-1922-4e69-b601-108008d28a2e
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB7PR03MB4779
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/nIdjwNkiJnChXVpZIgTWalzp6hY>
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:06:07 -0000

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