Comments on NIST's current standardization plans for Ascon

[John Mattsson]

Hi,

At the Third NIST Workshop on Block Cipher Modes of Operation 2023, NIST presented Ascon and asked for comments.

https://csrc.nist.gov/csrc/media/Presentations/2023/update-on-standardization-of-ascon-family/images-media/sess-6-turan-bcm-workshop-2023.pdf

- I think the current tentative decisions on page 20 sounds great.

- I think publishing as Special Publication (SP) instead of FIPS makes a lot of sense. I think most people want standards as soon as possible.

- I think 64- and 96-bit tags sounds ok. I don’t see a strong need for other sizes in the NIST specification. It would be good if NIST describes the forgery probability as a function of the tag length t in the specification. People might want to use Ascon with 32 bit tags in future radio link layers. But I don’t see a strong need for NIST to add that as an approved mode. If NIST explains that Ascon with t bit tags give t bit security, people and other SDOs can figure out when it is ok to use for their use cases.

- I support changing to little-endian for more efficient implementations.

- “Support for additional functionalities (PRF, MAC, KDF, DRBG etc.)” sounds great. What about Ascon in Ed25519 and ECDSA? I think Robert Moskowitz expressed a very strong interest in that.

- I assume that encryption without message expansion might come later. The Block Cipher Techniques project is looking at that right now but the outcome might not use block ciphers and instead rely on permutation based crypto using SHAKE or TurboSHAKE. A solution for SHAKE/TurboSHAKE would likely be easy to adopt for Ascon.

Cheers,
John

[Mustafa Khairallah]

Hi John,

With respect to your comments on tag sizes and the relation to forgery probability, I would like to point out that short tags do not only allow forgery but also also decrypting partial messages. Please refer to my paper from FSE 2022 [1] and the paper from Hosoyamada et al in FSE 2023 [2].

Using a 32-bit tag sounds risky and I would say the standard should keep at least a variant with 128-bit tag.

[1] https://eprint.iacr.org/2021/648

[2] https://tosc.iacr.org/index.php/ToSC/article/download/9852/9352

—Mustafa

On 6 Oct 2023, at 7:56 PM, 'John Mattsson' via lwc-forum <lwc-...@list.nist.gov> wrote:



--
To unsubscribe from this group, send email to lwc-forum+...@list.nist.gov
Visit this group at https://groups.google.com/a/list.nist.gov/d/forum/lwc-forum
---
To unsubscribe from this group and stop receiving emails from it, send an email to lwc-forum+...@list.nist.gov.

[John Mattsson]

Thanks Mustafa,

I will look at the links you sent.

I notice that I wrote “If NIST explains that Ascon with t bit tags give t bit security”, I don’t know if that is true. It would be good if NIST describes the security achieved with tags shorter than 128 bits. Some algorithms are more suitable to short tags than others. I don’t know how Ascon behaves.

>the standard should keep at least a variant with 128-bit tag

I think NIST plans to add 64 and 96 in addition to 128. I agree that 128 bit tags should be kept.

Cheers,
John

[Mustafa Khairallah]

No worries!

>> “If NIST explains that Ascon with t bit tags give t bit security”

I think this is true if the scheme has no other issues (the security is not actually less than t). What i meant by my email is that this security drop would refer to both privacy and forgery probability, and addressing forgery probability only may not be sufficient.

>> Some algorithms are more suitable to short tags than others. I don’t know how Ascon behaves.

Actually, based on the generic attacks presented in these papers (e.g. [1,Section 3]), any online AE scheme (including Ascon) is vulnerable to this partial decryption attack.

In FSE 2023 rump session, I presented a similar attack on two-pass schemes (eg SIV) and on any scheme that allows both short messages and short tags simultaneously, concluding that a scheme that allows short tags without substantial privacy/decryption issues would almost (but not quite) an enciphering scheme (e.g. AEZ). The paper is still work-in-progress but you can find the rump session slides here, starting at slide 58: https://fse.iacr.org/2023/slides/fserump.pdf 

—Mustafa

On 6 Oct 2023, at 8:17 PM, 'John Mattsson' via lwc-forum <lwc-...@list.nist.gov> wrote:



[Mustafa Khairallah]

Sorry, here is the link https://fse.iacr.org/2023/slides/fserump.pdf

—Mustafa

On 6 Oct 2023, at 8:34 PM, Mustafa Khairallah <khair...@ieee.org> wrote:

No worries!

>> “If NIST explains that Ascon with t bit tags give t bit security”

I think this is true if the scheme has no other issues (the security is not actually less than t). What i meant by my email is that this security drop would refer to both privacy and forgery probability, and addressing forgery probability only may not be sufficient.

>> Some algorithms are more suitable to short tags than others. I don’t know how Ascon behaves.

Actually, based on the generic attacks presented in these papers (e.g. [1,Section 3]), any online AE scheme is vulnerable to this partial decryption attack.

In FSE 2023 rump session, I presented a similar attack on two-pass schemes (eg SIV) and on any scheme that allows both short messages and short tags simultaneously, concluding that a scheme that allows short tags without substantial privacy/decryption issues would almost (but not quite) an enciphering scheme (e.g. AEZ). The paper is still work-in-progress but you can find the rump session slides here: 

[Damian Vizár]

Hello John, Mustafa,

thanks for this interesting discussion!

As you point out in your rump session slides, many AE schemes owe their CCA security to INT-CTXT, so CCA security being forfeit after a forgery would correspond to the indication of "t-bit security".

As John points out, there are legitimate use cases, where 32 bit tags represent an acceptable risk-overhead tradeoff, such as the mentioned (constrained) radio communication.

For some of these use cases, it would be relevant that the AE scheme in question does not lose all security after the first forgery. I.e., re-forgeries should stay difficult and ideally confidentiality damage should be limited (for some meaningful definition). This would allow competent engineers to make an informed, risk-aware design.

My 2 cents.

Best regards,

Damian

[Robert Moskowitz]

Mustafa,

I work in wireless media where a 128-bit tag on top of everything else is a non-starter.

I can be convinced 64 is a problem.

96 is often all that will fit.

We can't have a "do it this way or the highway".  I can't add more capacity to the spectrum.  PHYs are designed the way they are because of this thing called physics.

--
Robert Moskowitz
Owner
HTT Consulting
C:      248-219-2059
F:      248-968-2824
E:      r...@labs.htt-consult.com

There's no limit to what can be accomplished if it doesn't matter who gets the credit

[Mustafa Khairallah]

Sorry, I think there is a confusion, I am not opposed to 64 and 96, I was only commenting on 32 and 128 :)

—Mustafa

On 6 Oct 2023, at 10:40 PM, Robert Moskowitz <r...@labs.htt-consult.com> wrote:

 Mustafa,

[Mustafa Khairallah]

To be clear,

My messages conveys: I think 32-bit is risky. I think we should not abandon 128-bit for the sake of 96-bit. I think we should be clear that the risk is not only a forgery probability risk but a privacy risk as well.

I am aware that physics exists and that others may disagree. I am not the one writing the standard so I don’t see how it is “my way or the highway”.

—Mustafa

> On 6 Oct 2023, at 10:40 PM, Robert Moskowitz <r...@labs.htt-consult.com> wrote:
>

[Robert Moskowitz]

OK.

I am very rushed today, so not giving this the time it deserves!

32 would be REALLY nice considering what we have to do in IETF DRIP with BT4 Broadcast frames!  But those days of inadequate computing power are long gone (I still remember the big show on the first public cracking of DES).

Yes, 64, 96, 128.

[Robert Moskowitz]

My bad. Too rushed and probably should have left this thread for Monday.

Not yours.  Those that control the standard.

But even that, I am too rushed and really should not be doing this today.  I will see about proper response to John's init message Monday.  Or more likely Tuesday with all that has backed up over the Holidays!

[Yaobin Shen]

 Hi, 

Maybe 32-bit is acceptable for some applications if the re-forgeries are still 

as hard as the first forgery (and the re-distinguishability are still as hard as 

the first distinguishable ciphertext) as pointed out by Damian. Then even 

the first forgery happens with probability around 2^{-32}, the second forgery 

still happens with probability around 2^{-32}. Then the probability of two forgeries 

is about 2^{-64}. So for some applications that can tolerate constant number 

of forgeries, 32-bit tag can offer some meaningful security. 

Regards,

Yaobin

[Mustafa Khairallah]

>> Maybe 32-bit is acceptable for some applications if the re-forgeries are still 

as hard as the first forgery (and the re-distinguishability are still as hard as 

the first distinguishable ciphertext) as pointed out by Damian.

Sure if the application can tolerate it, but I would add to that: “if it is OK that x number of messages can be decrypted”.

>> Then even 

the first forgery happens with probability around 2^{-32}, the second forgery 

still happens with probability around 2^{-32}. Then the probability of two forgeries 

is about 2^{-64}.

I think two forgeries cost on average 2^33 forgery attempts, no? If we do q forgery attempts where q > 2^{32} then we would expect about q/2^32 forgeries (assuming best attack is tag guessing). I think the probability of two forgeries is closer to

q^2/2^{64} 

similarily the probability of n forgeries should be on the form

(q/2^{32})^n

Please correct me if I missing something here.

—Mustafa

On 6 Oct 2023, at 11:35 PM, Yaobin Shen <yaobi...@gmail.com> wrote:



[Yaobin Shen]

Hi Mustafa, 

I totally agree with you. These statements hold for traditional MACs. On the other hand, 

there have been some special MACs where the probability for c fresh forgeries is (1/2^{t})^c 

where t is the size of the tag. One example is ProMAC in https://dl.acm.org/doi/10.1145/3372297.3423349 

that can achieve security of full-length MACs with short tags. The sender and the receiver should 

maintain an internal state but they only need to transmit a short tag. 

Regards,

Yaobin

[Roberto Avanzi]

32-bit tags can be useful, depending on the adversarial model. If the Adversary can only attempt to forge one tag and, in case the attempt fails, the system is reset and a new key is used, then it may make sense. For instance, for memory protection, Intel's TDX uses 28-bit tags. And it is a reasonable choice. If a tag verification fails (after ECC correction to reduce the likelihood of tag mismatches due to "acts of god") then the system may even destroy the VM containing the address where the verification has failed.

Perfect? No. Sufficient to deter adversaries? I would say it is.

 Roberto