Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Mon, 1 Oct 2018 13:11:46 +0000

Hi Natanael,

To expand a bit on Quynh's comment, your point is valid and we needed to touch on it a bit more on the draft. Jim S. had also brought it in his review. To make it clearer to an implementer, we expanded the paragraph in the security considerations section to say

The SHAKEs are deterministic functions. Like any other deterministic functions, executing each function with the same input multiple times will produce the same output. Therefore, users should not expect unrelated outputs (with the same or different output lengths) from excuting a SHAKE function with the same input multiple times. The shorter one of any 2 outputs produced from a SHAKE with the same input is a prefix of the longer one. It is a similar situation as truncating a 512-bit output of SHA-512 by taking its 256 left-most bits. These 256 left-most bits are a prefix of the 512-bit output.

Rgs,
Panos

From: Cfrg <[email-masked]> On Behalf Of Dang, Quynh (Fed)
Sent: Sunday, September 30, 2018 6:43 AM
To: Natanael <[email-masked]>; Russ Housley <[email-masked]>
Cc: IRTF CFRG <[email-masked]>
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Hi Natanael,

Thank you for reviewing the document and for giving a nice security discussion.

We described that property of the SHAKEs or any other stream ciphers similarly in FIPS 202.

In this specification, output lengths of the SHAKEs are all fixed-lengths. When they are used to generate message digests, their outputs are 256 or 512 bits.

In RSA-PSS, with any given length of a RSA modulus, all outputs of a SHAKE are in fixed lengths and all inputs are different from each other. So, the uses of a SHAKE in RSA-PSS are good.

Regards,

Quynh.

________________________________
From: Cfrg <[email-masked]<mailto:[email-masked]>> on behalf of Natanael <[email-masked]<mailto:[email-masked]>>
Sent: Saturday, September 29, 2018 7:48:27 PM
To: Russ Housley
Cc: IRTF CFRG
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

(note that the following is my layman's opinion (perhaps in more words then necessary))

---

I think that the security considerations in these documents currently aren't phrased strongly enough regarding one point - to "not expect unrelated outputs" from a XOF for the same input doesn't properly explain the risk. The relevant section is this;

> The SHAKEs are deterministic functions. Like any other deterministic functions, executing each function with the same input multiple times will produce the same output. Therefore, users should not expect unrelated outputs (with the same or different output lengths) from excuting a SHAKE function with the same input multiple times.

Explained another way, SHAKE as a XOF (extensible output function) takes an input and derives a fixed pseudorandom bit sequence of arbitary length as an output (similar to a stream cipher), where the requested length only determines how much of that sequence to use. In pseudocode: SHAKE128(message, length) == truncate(SHAKE128(message, length+N), length). To be clear, changing the requested length doesn't influence the output sequence, the output bits remain the same.

As a consequence, any XOF output can be truncated to any shorter length and still remain valid, for as long as the recipient will accept that shorter output. This is *very* different from just "not unrelated"!

In short, the risk here is that a poorly implemented client could be convinced to accept shorter XOF lengths than intended, perhaps even dangerously short hashes! For example, a SHAKE output that initially was 2048 bits long would still be equally valid even if reduced to 80 bits or less, or alternatively a client might accept a 128 bit XOF in place of a 256 bit one (perhaps enabling a birthday collision attack).

Verifying the intended output length of the SHAKE function is absolutely necessary in order to ensure that the intended security level is preserved, and too short output lengths needs to be prohibited entirely. Every protocol or algorithm using a XOF needs to be very clear with what lengths are accepted. They also need to take extra care when multiple lengths are allowed, to not mix them up / allow unintended reuse or cross-protocol exploits, etc.

Note: in algorithms / protocols where multiple lengths are allowed it is possible to encode the chosen output length as a part of the message, and to also require validation of that encoded length by the client. This would be a fairly simple way to ensure correctly behaving clients will not be fooled by truncated hashes. This effectively works as a form of domain separation between different messages with different requested XOF output lengths.

So far I have only looked briefly at a few of the documents where SHAKE is being recommended, so I can't say if there currently are any such risks here. I have seen some documents specify fixed output lengths which is a very good sign, but more review might still be a good idea. Especially whenever multiple XOF lengths are allowed.

Also, some uses of XOF:s might also not be at risk of this at all, such as when the XOF output is authenticated (signed or MAC tagged, etc), where truncating it breaks the authentication. But once again, it's a good idea to review it first.

Den mån 17 sep. 2018 22:57Russ Housley <[email-masked]<mailto:[email-masked]>> skrev:
Dear CFRG:

The IETF LAMPS WG is specifying the use of SHAKE with RSA-PSS for use with certificates and CMS signed objects.  The current drafts are:

        draft-ietf-lamps-cms-shakes-01.txt
        draft-ietf-lamps-pkix-shake-02.txt

In discussion of these drafts, it was suggested that instead of replacing SHA-1 in the RSA-PSS default mask generation function (MGF), one could replace the entire MGF with SHAKE.  While it does look like a simple substitution, I do not think the IETF LAMPS WG is the right group to make the assessment.  CFRG may have people with the right skills, so I would greatly appreciate you thoughts on this idea.

Russ

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&data=02%7C01%7Cquynh.dang%40nist.gov%7C8905e4261449422112b808d626663950%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636738617850955007&sdata=VX7Mc1ZeeC%2FR%2BIZM8R%2BfoiEyrzzlcJrdnU7Lg5B2Crg%3D&reserved=0>