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

From: Jeffrey Walton <[email-masked]>
Date: Fri, 25 Jan 2019 22:20:38 -0500

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:

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:

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.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sat, 26 Jan 2019 12:06:00 +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 <[email-masked]> wrote:
> 
> Hi Everyone,
> 
> 032CC123482C31711F94C941AF5AB1F4155784332ED5348FE79AEC5EAD4C06C3
> F13C280D8CC49925E4A6A5922EC80E13A4CDFA840C70A1427A3CB699166991A5
> ACE4CD09E294D1912D4AD205D06F95D9C2F2BFCF453E8753F128765B62215F4D
> 92C74F2F626C6A640C0B1284D839EC81F1696281DAFC3E684593937023B58B1D
> 76B8E0ADA0F13D90405D6AE55386BD28BDD219B8A08DED1AA836EFCC8B770DC7
> DA41597C5157488D7724E03FB8D84A376A43B8F41518A11CC387B669B2EE6586
> 9F07E7BE5551387A98BA977C732D080DCB0F29A048E3656912C6533E32EE7AED
> 29B721769CE64E43D57133B074D839D531ED1F28510AFB45ACE10A1F4B794D6F
> 
> 032CC123482C31711F94C941AF5AB1F4155784332ED5348FE79AEC5EAD4C06C3
> F13C280D8CC49925E4A6A5922EC80E13A4CDFA840C70A1427A3CB699166991A5
> ACE4CD09E294D1912D4AD205D06F95D9C2F2BFCF453E8753F128765B62215F4D
> 92C74F2F626C6A640C0B1284D839EC81F1696281DAFC3E684593937023B58B1D
> 3DB41D3AA0D329285DE6F225E6E24BD59C9A17006943D5C9B680E3873BDC683A
> 5819469899989690C281CD17C96159AF0682B5B903468A61F50228CF09622B5A
> 46F0F6EFEE15C8F1B198CB49D92B990867905159440CC723916DC00128269810
> 39CE1766AA2542B05DB3BD809AB142489D5DBFE1273E7399637B4B3213768AAA
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Sat, 26 Jan 2019 15:44:28 +0300

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 <[email-masked]>:

> 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
>
>

---

From: James Cloos <[email-masked]>
Date: Sat, 26 Jan 2019 11:03:41 -0500

There was discussion on one of the ietf lists that the upper 32 bits
should be incremented in such cases.

Ie, treat it as 64/64 instead of 32/96 but with the upper 32 bits of the
counter not always 0.

I do not recall any objections to that at the time.

(It just seemed obvious.)

I'm surprised any implementations do otherwise.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: Taylor R Campbell <[email-masked]>
Date: Sat, 26 Jan 2019 17:15:37 +0000

> Date: Fri, 25 Jan 2019 22:20:38 -0500
> From: Jeffrey Walton <[email-masked]>
> 

You should design your _protocol_ so that

(a) it starts at block counter 0,
(b) it is limited to packets 2^32 blocks long.

If you want to handle larger messages, break them up into multiple
packets with distinct nonces.

The largest packet you are willing to _authenticate_ (you are using it
together with an authenticator like Poly1305 in your protocol, right?)
is an upper bound on the amount of your memory an adversary can waste
in a DoS attack before you can drop it on the floor.

If, on the other hand, you're confined to implementing an existing
protocol, you should implement whatever that protocol prescribes --
and write automatic tests that enshrine the behaviour.

But most protocols don't handle messages that large, partly because
they pose trivial DoS risks.  For example, in TLS, packets (`records')
are limited to 2^14 octets -- far smaller than the 2^32-block limit.

Unless you have an application that actually starts the block counter
in the middle of a message or actually uses >4 GB messages -- if
you're really concerned it might make a difference, make block counter
overflow a fail noisily.

---

From: Yoav Nir <[email-masked]>
Date: Sat, 26 Jan 2019 20:40:14 +0200

Hi

For a little context, if you are using straight ChaCha20 as a cipher, the initial block counter should always be zero. This is true both for Bernstein’s original version (with a 64/64 split of block counter/nonce) and with the RFC 8439 version (with the 32/96 split).

The only reason we made this a parameter is because of the AEAD construction where we use the zero block counter for creating the Poly1305 key, and encryption starts at block counter = 1.

In retrospect we could have made the API simpler by eliminating this parameter and always starting with zero.  Generating the Poly1305 key only requires a unique value for block counter, not any specific one.  We could have,  perhaps should have gone with 0xffffffff.

Unfortunately, by now it’s too late to make this change, as this algorithm is implemented in many libraries. That said, the only thing that is seeing a lot of usage is the AEAD, and for the AEAD the initial block counter is set at 1.

Yoav

> On 26 Jan 2019, at 5:20, Jeffrey Walton <[email-masked]> wrote:
> 
> Hi Everyone,
>