Subject: [CFRG] FYI - NIST Fifth Lightweight Cryptography Workshop (virtual)

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Mar 2022 16:16:10 -0400

Link is:

https://csrc.nist.gov/events/2022/lightweight-cryptography-workshop-2022

Submissions had to be in by March 20.

---

From: John Mattsson <[email-masked]>
Date: Tue, 29 Mar 2022 06:28:32 +0000

Thanks for the heads up!

Reading up on NIST LWC I am getting a bit worried where they are heading. With SHAKE and KMAC, NIST really showed the future of cryptographic interfaces for variable length hash functions, efficient MACs, and KDFs. It would be a bit sad if LWC is big step backwards to the days of SHA-2 and HMAC. As discussed last week, HMAC is an inefficient hack designed to get around the limitation and weaknesses of older hash functions.

Cheers,
John

From: CFRG <[email-masked]> on behalf of Robert Moskowitz <[email-masked]>
Date: Thursday, 24 March 2022 at 21:17
To: IRTF CFRG <[email-masked]>
Subject: [CFRG] FYI - NIST Fifth Lightweight Cryptography Workshop (virtual)
Link is:

_______________________________________________
CFRG mailing list
[email-masked]
https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-40f7d10cf9eb7c69&q=1&e=03730bdd-ae4d-4e81-ab9d-50881e30c30e&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 29 Mar 2022 12:46:34 +0000

John, I concur. 

Other concerns I have with the NIST LWC are
- most (all?) of their finalists support only 128-bit key;
- none (?) of their finalists can deal with none reuse/misuse (this is a BIG one for me). Maybe, Romulus has a variant…

Regards,
Uri

> On Mar 29, 2022, at 02:29, John Mattsson <john.mattsson=[email-masked]> wrote:
> 
> 
> Thanks for the heads up!
>  
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Leo Perrin <[email-masked]>
Date: Tue, 29 Mar 2022 15:51:32 +0200 (CEST)

Hello everyone, 

Obvious conflict of interest: I am a co-author of SPARKLE (one of the finalists). 

> - most (all?) of their finalists support only 128-bit key;

Sparkle supports 128, 192 and 256 bit keys 

> for me). Maybe, Romulus has a variant…

It depends what security you want in case of nonce misuse. As far as I can tell, Ascon only suffers issues in terms of confidentiality in case of nonce-misuse, and only potentially so. Since the key is XORed into the state after the initialization and again before squeezing the tag, an adversary cannot forge a tag. Furthermore, in order for the attacker to be able to actually decrypt ciphertexts beyond their first block, they would need to recover the full capacity first. Indeed, the encryption part of the algorithm is not a simple stream cipher, so the keystream cannot simply deduced from a plaintext/ciphertext pair (except for the first block). Even in the nonce-misuse case, a capacity-recovery attack should be expected to be highly non-trivial at best---and not faster than brute-force at worst. 

For Sparkle, we borrowed from Ascon the key XOR after initialization and before tag generation. However, the capacity is smaller so attacks based on finding collisions in it might seem tempting... But since the capacity is at least equal to the tag length, I don't expect this to have a huge impact. 

I would expect the behaviour of TinyJambu to be similar (i.e. that nonce-misuse wouldn't be such a big deal for it). Its mode is essentially sponge-based, but with a secret-dependent permutation, which would also hinder forgeries. 

I haven't had a close enough look at the other finalists to say what kind of security they offer, so the fact that they are not mentionned here doesn't mean that they are "nonce-misuse brittle". 

Overall, I don't remember nonce-misuse being a property NIST demanded in their initial call, which is probably why it was not given any particular attention. Still, many finalists are sponge-based, and as a result wouldn't collapse in the way GCM does in case of nonce-misuse. 

Cheers, 

/Léo 

> De: "Uri Blumenthal, 0553 - MITLL" <[email-masked]>
> À: "John Mattsson" <john.mattsson=[email-masked]>
> Cc: "cfrg" <[email-masked]>, "Robert Moskowitz" <[email-masked]>
> Envoyé: Mardi 29 Mars 2022 14:46:34
> Objet: Re: [CFRG] FYI - NIST Fifth Lightweight Cryptography Workshop (virtual)

---

From: Thomas Peyrin <[email-masked]>
Date: Tue, 29 Mar 2022 23:36:04 +0800

Hi all,

indeed I think Romulus (full disclosure: I am one of the designers) is the
only remaining candidate of the NIST LWC competition that has a version
(Romulus-M) that claims full nonce-misuse resistance (confidentiality and
authentication). In addition, note that the security notion for Romulus-M
is "nonce Misuse-Resistant Authenticated Encryption" (MRAE), which is very
different and much stronger than what sponge function candidates from the
competition might be offering (most did not claim any). Also, I think
"providing better nonce-misuse resistance than GCM" is maybe a too low
target for a future standard/deployment and we should aim now for higher
robustness such as MRAE.

Since ASCON's nonce-misuse resistance was just mentioned, I would like to
warn that there has been a rump session talk at FSE 2022 that seems to show
a practical nonce-misuse attack (2^40 computations) on the full scheme.

Regards,

Thomas.

Le mar. 29 mars 2022 à 21:52, Leo Perrin <[email-masked]> a écrit :

> - none (?) of their finalists can deal with none reuse/misuse (this is a
> BIG one for me). Maybe, Romulus has a variant…
>
> It depends what security you want in case of nonce misuse. As far as I can
> tell, Ascon only suffers issues in terms of confidentiality in case of
> nonce-misuse, and only potentially so. Since the key is XORed into the
> state after the initialization and again before squeezing the tag, an
> adversary cannot forge a tag. Furthermore, in order for the attacker to be
> able to actually decrypt ciphertexts beyond their first block, they would
> need to recover the full capacity first. Indeed, the encryption part of the
> algorithm is not a simple stream cipher, so the keystream cannot simply
> deduced from a plaintext/ciphertext pair (except for the first block). Even
> in the nonce-misuse case, a capacity-recovery attack should be expected to
> be highly non-trivial at best---and not faster than brute-force at worst.
>
> For Sparkle, we borrowed from Ascon the key XOR after initialization and
> before tag generation. However, the capacity is smaller so attacks based on
> finding collisions in it might seem tempting... But since the capacity is
> at least equal to the tag length, I don't expect this to have a huge impact.
>
> I would expect the behaviour of TinyJambu to be similar (i.e. that
> nonce-misuse wouldn't be such a big deal for it). Its mode is essentially
> sponge-based, but with a secret-dependent permutation, which would also
> hinder forgeries.
>
> I haven't had a close enough look at the other finalists to say what kind
> of security they offer, so the fact that they are not mentionned here
> doesn't mean that they are "nonce-misuse brittle".
>
> Overall, I don't remember nonce-misuse being a property NIST demanded in
> their initial call, which is probably why it was not given any particular
> attention. Still, many finalists are sponge-based, and as a result wouldn't
> collapse in the way GCM does in case of nonce-misuse.
>
> Cheers,
>
> /Léo
>
>
> ------------------------------
>
> *De: *"Uri Blumenthal, 0553 - MITLL" <[email-masked]>
> *À: *"John Mattsson" <john.mattsson=[email-masked]>
> *Cc: *"cfrg" <[email-masked]>, "Robert Moskowitz" <[email-masked]>
> *Envoyé: *Mardi 29 Mars 2022 14:46:34
> *Objet: *Re: [CFRG] FYI - NIST Fifth Lightweight Cryptography Workshop
> (virtual)
>

---

From: Mustafa Khairallah <[email-masked]>
Date: Tue, 29 Mar 2022 23:51:20 +0800

Hi Leo and all,

>> Furthermore, in order for the attacker to be able to actually decrypt ciphertexts beyond their first block, they would need to recover the full capacity first. 

If I understand correctly, I think once you allow nonce repetition, the adversary can decrypt any number of blocks they want using a variant of the CPSS attack: https://eprint.iacr.org/2015/189.pdf <https://eprint.iacr.org/2015/189.pdf>

For example, let the plaintext block size be b, the adversary can decrypt a 3-block message (M_1|M_2|M_3) by repeating the nonce 3 times (I am using Ascon as a reference here, exact values may vary):
1) Ask for the encryption of 0^b, and use it to get M_1
2) Ask for the encryption of M_1|0^b, and use it to get M_2
3) Ask for the encryption of M_1|M_2|0^b, and use it to get M_3

As long as the scheme has the property that the keystream of the i^th block depends only on N, K, and the first i-1 blocks, this is always possible. No need to recover the internal state. This indeed requires r repetitions with chosen plaintexts to decrypt r blocks, but it is much easier than recovering the state.

—Mustafa

> On 29 Mar 2022, at 9:51 PM, Leo Perrin <[email-masked]> wrote:
> 
> Hello everyone,
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 29 Mar 2022 16:04:03 +0000

Thomas, yes, exactly. “Better than GCM” is not the level that I’d want to be aiming at.

Unfortunately, I did not see Romulus-M supporting 256-bit key…?

Leo, yes – NIST did not request (or even mention) nonce misuse resistance. Nor did they bother to standardize any nonce misuse-resistant mode at all. I know AES-GCM-SIV was submitted for standardization – but the NIST seems to have dropped the ball on it, and on the whole nonce misuse thing… <Sigh>

Oh well…

--

V/R,

Uri

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.

The other is to make it so complex there are no obvious deficiencies.

                                                                                                                                     -  C. A. R. Hoare

From: Thomas Peyrin <[email-masked]>
Date: Tuesday, March 29, 2022 at 11:37
To: Leo Perrin <[email-masked]>
Cc: Uri Blumenthal <[email-masked]>, CFRG <[email-masked]>, John Mattsson <john.mattsson=[email-masked]>, Robert Moskowitz <[email-masked]>
Subject: Re: [CFRG] FYI - NIST Fifth Lightweight Cryptography Workshop (virtual)

Hi all, 

indeed I think Romulus (full disclosure: I am one of the designers) is the only remaining candidate of the NIST LWC competition that has a version (Romulus-M) that claims full nonce-misuse resistance (confidentiality and authentication). In addition, note that the security notion for Romulus-M is "nonce Misuse-Resistant Authenticated Encryption" (MRAE), which is very different and much stronger than what sponge function candidates from the competition might be offering (most did not claim any). Also, I think "providing better nonce-misuse resistance than GCM" is maybe a too low target for a future standard/deployment and we should aim now for higher robustness such as MRAE.

Since ASCON's nonce-misuse resistance was just mentioned, I would like to warn that there has been a rump session talk at FSE 2022 that seems to show a practical nonce-misuse attack (2^40 computations) on the full scheme.

Regards,

Thomas.

Hello everyone,

Cheers,

/Léo

---

From: Thomas Peyrin <[email-masked]>
Date: Wed, 30 Mar 2022 00:25:54 +0800

Dear Uri,

indeed, Romulus-M as stated only supports 128-bit key. You can support
256-bit key in a straightforward way by using a larger tweak version of
Skinny, but this is ongoing work :-)

An alternative for you could be Deoxys, there is a MRAE version of Deoxys
with 256-bit key:
https://thomaspeyrin.github.io/web/assets/docs/papers/Jean-etal-JoC2021.pdf
(see Deoxys-II-256 in Table 2). Larger versions of Deoxys-TBC are coming
also, so it will be easy to use larger keys for all Deoxys modes.

Regards,

Thomas.

Le mer. 30 mars 2022 à 00:04, Blumenthal, Uri - 0553 - MITLL <[email-masked]>
a écrit :

> Leo, yes – NIST did *not* request (or even mention) nonce misuse
> resistance. Nor did they bother to standardize *any* nonce
> misuse-resistant mode at all. I know AES-GCM-SIV was submitted for
> standardization – but the NIST seems to have dropped the ball on it, and on
> the whole nonce misuse thing… <Sigh>
>
>
>
> Oh well…
>
> --
>
> V/R,
>
> Uri
>
>
>
> *There are two ways to design a system. One is to make it so simple there
> are obviously no deficiencies.*
>
> *The other is to make it so complex there are no obvious deficiencies.*
>
> *
>                                                                                                                    -
> C. A. R. Hoare*
>
>
>
>
>
> *From: *Thomas Peyrin <[email-masked]>
> *Date: *Tuesday, March 29, 2022 at 11:37
> *To: *Leo Perrin <[email-masked]>
> *Cc: *Uri Blumenthal <[email-masked]>, CFRG <[email-masked]>, John
> Mattsson <john.mattsson=[email-masked]>, Robert Moskowitz <
> [email-masked]>
> *Subject: *Re: [CFRG] FYI - NIST Fifth Lightweight Cryptography Workshop
> (virtual)
>
>
>
> Hi all,
>
>
>

---

From: Maria Eichlseder <[email-masked]>
Date: Tue, 29 Mar 2022 19:12:35 +0200

Hi Thomas, hi all,

Regarding Ascon's nonce-misuse resistance properties and the recent work 
presented in the FSE 2022 rump session by Jules Baudrin, Anne Canteaut, 
and Léo Perrin [1] mentioned by Thomas:
They show that if a nonce is misused about 2^40 times with chosen 
plaintexts, then confidentiality *under this nonce* is compromised. 
Confidentiality under different nonces or authenticity are not affected, 
thanks to the doubly-keyed initialization and finalization of Ascon.

This attack is in a similar setting as the standard "xor" property 
common to sponge/streaming candidates (where the confidentiality of a 
ciphertext under a misused nonce can be compromised using other 
encryptions of chosen plaintexts under the same nonce and thus learning 
the keystream block by block, as summarized by Mustafa Khairallah).
Achieving a substantially stronger notion such as MRAE would require a 
much less efficient construction (e.g., 2-pass) - we think that Ascon's 
trade-off is better suited for lightweight application scenarios.

There are some minor differences between the settings of these two 
nonce-misuse attacks (e.g., the 2^40 attack requires more misuse queries 
but no adaptive queries after receiving the challenge ciphertext, only 
before that under the same nonce), but essentially, it follows the same 
principles: nonce misuse has only "local" effects limited to the misused 
nonce, no "global" effects for the key. Thus, this result does not 
change our understanding of Ascon's nonce-misuse resistance properties.

Indeed, compare this to the claim in the Ascon design document [2]:
"**Limited damage in misuse settings**. Ascon uses nonce-based 
authenticated encryption. As with any nonce-based authenticated 
encryption scheme, repeating nonces is a misuse setting, and implies a 
loss of semantic security. But compared to other sponge-based 
constructions, Ascon provides better robustness in case of a potential 
state recovery, since both initialization and finalization are keyed 
additionally. A recovery of the secret state during data processing does 
not directly lead to a key-recovery or universal forgery."

Best,
Maria
(disclaimer: on behalf of the Ascon design team)

[1] https://fse.iacr.org/2022/program.php#day-2022-03-23

[2] 
https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/finalist-round/updated-spec-doc/ascon-spec-final.pdf 
page 20

On 29.03.22 18:25, Thomas Peyrin wrote:
> Le mer. 30 mars 2022 à 00:04, Blumenthal, Uri - 0553 - MITLL 
> <[email-masked] <mailto:[email-masked]>> a écrit :
> 
>     Leo, yes – NIST did _not_ request (or even mention) nonce misuse
>     resistance. Nor did they bother to standardize _any_ nonce
>     standardization – but the NIST seems to have dropped the ball on it,
>     and on the whole nonce misuse thing… <Sigh>____
> ...
> 
>     *From: *Thomas Peyrin <[email-masked]
>     <mailto:[email-masked]>>
>     ...
>     Since ASCON's nonce-misuse resistance was just mentioned, I would
>     like to warn that there has been a rump session talk at FSE 2022
>     that seems to show a practical nonce-misuse attack (2^40
>     computations) on the full scheme.____
> 
>     Le mar. 29 mars 2022 à 21:52, Leo Perrin <[email-masked]
>     <mailto:[email-masked]>> a écrit :____
> 
>         ...
>         It depends what security you want in case of nonce misuse. As
>         far as I can tell, Ascon only suffers issues in terms of
>         confidentiality in case of nonce-misuse, and only potentially
>         so. Since the key is XORed into the state after the
>         initialization and again before squeezing the tag, an adversary
>         cannot forge a tag. Furthermore, in order for the attacker to be
>         able to actually decrypt ciphertexts beyond their first block,
>         they would need to recover the full capacity first. Indeed, the
>         encryption part of the algorithm is not a simple stream cipher,
>         so the keystream cannot simply deduced from a
>         plaintext/ciphertext pair (except for the first block). Even in
>         the nonce-misuse case, a capacity-recovery attack should be
>         expected to be highly non-trivial at best---and not faster than
>         brute-force at worst.____
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 29 Mar 2022 17:21:53 +0000

indeed, Romulus-M as stated only supports 128-bit key. You can support 256-bit key in a straightforward way by using a larger tweak version of Skinny, but this is ongoing work :-)

Nice to hear that. Any idea (a) when this work would be completed, and (b) whether NIST would accept/augment the current Romulus-M with 256-bit key capability?

An alternative for you could be Deoxys, there is a MRAE version of Deoxys with 256-bit key: https://thomaspeyrin.github.io/web/assets/docs/papers/Jean-etal-JoC2021.pdf (see Deoxys-II-256 in Table 2). Larger versions of Deoxys-TBC are coming also, so it will be easy to use larger keys for all Deoxys modes. 

Deoxys (AFAIK) is not among the NIST LWC finalists, which would make some users shy away from it. I have no power to convince them otherwise (yet? 😉).

Thanks!

Le mer. 30 mars 2022 à 00:04, Blumenthal, Uri - 0553 - MITLL <[email-masked]> a écrit :

Oh well…

--

V/R,

Uri

                                                                                                                                     -  C. A. R. Hoare

Hi all, 

Regards,

Thomas.

Hello everyone,

Cheers,

/Léo

---

From: Thomas Peyrin <[email-masked]>
Date: Wed, 30 Mar 2022 01:48:59 +0800

Hi Uri,

"Nice to hear that. Any idea (a) when this work would be completed, and (b)
whether NIST would accept/augment the current Romulus-M with 256-bit key
capability?"

Regarding (a) this work is completed but under submission at the moment.
Note that you can directly use 192-bit keys with the current Romulus
versions since 64-bit of the tweakey inputs are not used, so you can simply
fill them with 64-bit of extra key material. Regarding (b), I guess this
would have to be asked directly to the NIST (there is a NIST LWC mailing
list), but anyway Romulus is only a finalist at the moment. The decisions
for the NIST LWC competition are apparently going to be disclosed in 2022.
Maybe a good way to proceed would be that once the NIST LWC results are
announced, to start a discussion on how to enable the various properties
that you believe the chosen candidate does not have.

" Deoxys (AFAIK) is not among the NIST LWC finalists, which would make some
users shy away from it. I have no power to convince them otherwise (yet? )."

Indeed ! However, I was mentioning Deoxys (I am one of the designers) since
it is one of the winners of the CAESAR competition (winner of the
security-in-depth portfolio to be more precise).

Regards,

Thomas.

Le mer. 30 mars 2022 à 01:21, Blumenthal, Uri - 0553 - MITLL <[email-masked]>
a écrit :

> Nice to hear that. Any idea (a) when this work would be completed, and (b)
> whether NIST would accept/augment the current Romulus-M with 256-bit key
> capability?
>
>
>
> Deoxys (AFAIK) is not among the NIST LWC finalists, which would make some
> users shy away from it. I have no power to convince them otherwise (yet?
> 😉).
>
>
>
> Thanks!
>
>
>
>
>