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

From: Russ Housley <[email-masked]>
Date: Mon, 17 Sep 2018 16:57:10 -0400

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

---

From: "Saqib A. Kakvi" <[email-masked]>
Date: Wed, 19 Sep 2018 17:58:14 +0200

Hello Russ,

Replacing MGF1 with SHAKE should not present any problems that I can 
see. The Mask Generation Function was used to overcome the fact that 
hash functions have fixed length outputs. The fact that SHAKE is an 
eXtensible Output Function (XOF) means that one no longer needs to use 
an MGF.

On the other hand, since we do have an XOFs, I'm not sure that RSA-PSS 
should still be the algorithm of choice, but rather one might consider 
switching to the simpler RSA-Full Domain Hash or PKCS#1 v1.5 signature 
schemes.
Tibor Jager, Alexander May and myself have recently found a security 
proof for PKCS#1 v1.5 signatures, with the caveats that one must double 
their modulus length and use an XOF/MGF. I will be presenting this 
result will at CCS 18 next month, and would be glad to discuss it with 
anybody there. Additionally version should be appear in the IACR ePrint 
archive in the near future. I am also happy to send a copy of the paper 
to anybody who would like to have one.

Best
Saqib

>
> *From: *Russ Housley <[email-masked] <mailto:[email-masked]>>
> *Subject: **[Cfrg] A new MGF for RSA-PSS based on SHAKE*
> *Date: *17 September 2018 at 22:57:10 CEST
> *To: *IRTF CFRG <[email-masked] <mailto:[email-masked]>>
>
> 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:
>
> 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

---

From: Jim Schaad <[email-masked]>
Date: Wed, 19 Sep 2018 10:53:20 -0700

I have to admit that I was thinking about using a Full Domain Hash for the
signature, esp. because you could probably XOR in the ASN.1 hash algorithm
identifier and get back the hash substitution attack.   However when I look
at http://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf I see that they claim
that PSS is more secure that Full Domain.  I have not done any sort of
search to see if things are tighter now than they were back in '96.

Jim

From: Cfrg <[email-masked]> On Behalf Of Saqib A. Kakvi
Sent: Wednesday, September 19, 2018 8:58 AM
To: [email-masked]
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Hello Russ,

Replacing MGF1 with SHAKE should not present any problems that I can see.
The Mask Generation Function was used to overcome the fact that hash
functions have fixed length outputs. The fact that SHAKE is an eXtensible
Output Function (XOF) means that one no longer needs to use an MGF.

On the other hand, since we do have an XOFs, I'm not sure that RSA-PSS
should still be the algorithm of choice, but rather one might consider
switching to the simpler RSA-Full Domain Hash or PKCS#1 v1.5 signature
schemes.
Tibor Jager, Alexander May and myself have recently found a security proof
for PKCS#1 v1.5 signatures, with the caveats that one must double their
modulus length and use an XOF/MGF. I will be presenting this result will at
CCS 18 next month, and would be glad to discuss it with anybody there.
Additionally version should be appear in the IACR ePrint archive in the near
future. I am also happy to send a copy of the paper to anybody who would
like to have one.

Best
Saqib

From: Russ Housley <[email-masked] <mailto:[email-masked]> >

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

Date: 17 September 2018 at 22:57:10 CEST

To: IRTF CFRG <[email-masked] <mailto:[email-masked]> >

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:

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

---

From: "Saqib A. Kakvi" <[email-masked]>
Date: Wed, 19 Sep 2018 20:31:20 +0200

Hello Jim,

PSS was more secure than FDH in 1996, but that has since changed. 
Jean-Sebastian Coron showed an optimal proof (with proof of optimality) 
in 2001 (ia.cr/2001/062<https://ia.cr/2001/062>) and in 2012, Eike Kiltz 
and myself showed that one can get a better proof for FDH for small 
exponents. 
(http://www5.rz.rub.de:8032/mam/foc/content/publ/rsa-fdh_fullversion.pdf). 
In this case FDH is as secure as PSS.

Best,
Saqib

On 19/09/2018 19:53, Jim Schaad wrote:
>
> I have to admit that I was thinking about using a Full Domain Hash for 
> the signature, esp. because you could probably XOR in the ASN.1 hash 
> algorithm identifier and get back the hash substitution attack.   
> However when I look at 
> http://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf 
> <http://web.cs.ucdavis.edu/%7Erogaway/papers/exact.pdf> I see that 
> they claim that PSS is more secure that Full Domain.  I have not done 
> any sort of search to see if things are tighter now than they were 
> back in ’96.
>
> Jim
>
> *From:*Cfrg <[email-masked]> *On Behalf Of *Saqib A. Kakvi
> *Sent:* Wednesday, September 19, 2018 8:58 AM
> *To:* [email-masked]
> *Subject:* Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE
>
> Hello Russ,
>
> proof for PKCS#1 v1.5 signatures, with the caveats that one must 
> double their modulus length and use an XOF/MGF. I will be presenting 
> this result will at CCS 18 next month, and would be glad to discuss it 
> with anybody there. Additionally version should be appear in the IACR 
> ePrint archive in the near future. I am also happy to send a copy of 
> the paper to anybody who would like to have one.
>
> Best
> Saqib
>
>
>
>     *Subject: [Cfrg] A new MGF for RSA-PSS based on SHAKE*
>
>     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:
>
>     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
>

---

From: John Mattsson <[email-masked]>
Date: Wed, 26 Sep 2018 06:41:08 +0000

Hi,

I think an important aspect here is what we actually believe people will implement. Given that there is an ongoing (but slow) move to ECDSA/EdDSA and people are expecting to start implementing the outcome of the NIST PQC standardization in 5 years, I do not know how interested people are to implement something new based on RSA.

If FDH gives better security it should be discussed, but based on your comments it is only as secure as PSS. I feel like making small and easy to implement changes to RSA-PSS is the way to go.

Is the use of SHA-1 in RSA-PSS causing any known security problems, or is the idea to remove SHA-1 anyway (which makes sense)?

Cheers,
John

From: Cfrg <[email-masked]> on behalf of "Saqib A. Kakvi" <[email-masked]>
Date: Wednesday, 19 September 2018 at 20:32
To: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Hello Jim,

PSS was more secure than FDH in 1996, but that has since changed. Jean-Sebastian Coron showed an optimal proof (with proof of optimality) in 2001 (ia.cr/2001/062) and in 2012, Eike Kiltz and myself showed that one can get a better proof for FDH for small exponents. (http://www5.rz.rub.de:8032/mam/foc/content/publ/rsa-fdh_fullversion.pdf). In this case FDH is as secure as PSS.

Best,
Saqib

On 19/09/2018 19:53, Jim Schaad wrote:
I have to admit that I was thinking about using a Full Domain Hash for the signature, esp. because you could probably XOR in the ASN.1 hash algorithm identifier and get back the hash substitution attack.   However when I look at http://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf<http://web.cs.ucdavis.edu/%7Erogaway/papers/exact.pdf> I see that they claim that PSS is more secure that Full Domain.  I have not done any sort of search to see if things are tighter now than they were back in ’96.

Jim

From: Cfrg <[email-masked]><mailto:[email-masked]> On Behalf Of Saqib A. Kakvi
Sent: Wednesday, September 19, 2018 8:58 AM
To: [email-masked]<mailto:[email-masked]>
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Hello Russ,

Replacing MGF1 with SHAKE should not present any problems that I can see. The Mask Generation Function was used to overcome the fact that hash functions have fixed length outputs. The fact that SHAKE is an eXtensible Output Function (XOF) means that one no longer needs to use an MGF.

On the other hand, since we do have an XOFs, I'm not sure that RSA-PSS should still be the algorithm of choice, but rather one might consider switching to the simpler RSA-Full Domain Hash or PKCS#1 v1.5 signature schemes.
Tibor Jager, Alexander May and myself have recently found a security proof for PKCS#1 v1.5 signatures, with the caveats that one must double their modulus length and use an XOF/MGF. I will be presenting this result will at CCS 18 next month, and would be glad to discuss it with anybody there. Additionally version should be appear in the IACR ePrint archive in the near future. I am also happy to send a copy of the paper to anybody who would like to have one.

Best
Saqib

From: Russ Housley <[email-masked]<mailto:[email-masked]>>
Subject: [Cfrg] A new MGF for RSA-PSS based on SHAKE
Date: 17 September 2018 at 22:57:10 CEST
To: IRTF CFRG <[email-masked]<mailto:[email-masked]>>

Dear CFRG:

Russ

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Jim Schaad <[email-masked]>
Date: Wed, 26 Sep 2018 07:54:18 -0700

The current proposal in the draft is to replace SHA-1 in MGF1 with SHAKE where the SHAKE output size is essentially infinite so that there is never a need to iterate on the counter.  This means that you compute

      SHAKE(  mfgSeed || I2OSP(counter = 0, 4) , maskLen)

What I suggested was that we just switch to a new MGF function where we computed

        SHAKE ( mfgSeed, maskLen)

Jim

From: Cfrg <[email-masked]> On Behalf Of John Mattsson
Sent: Tuesday, September 25, 2018 11:41 PM
To: Saqib A. Kakvi <[email-masked]>; [email-masked]
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Hi,

Cheers,

John

From: Cfrg <[email-masked] <mailto:[email-masked]> > on behalf of "Saqib A. Kakvi" <[email-masked] <mailto:[email-masked]> >
Date: Wednesday, 19 September 2018 at 20:32
To: "[email-masked] <mailto:[email-masked]> " <[email-masked] <mailto:[email-masked]> >
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Hello Jim,

Best,
Saqib

I have to admit that I was thinking about using a Full Domain Hash for the signature, esp. because you could probably XOR in the ASN.1 hash algorithm identifier and get back the hash substitution attack.   However when I look at http://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf <http://web.cs.ucdavis.edu/%7Erogaway/papers/exact.pdf>  I see that they claim that PSS is more secure that Full Domain.  I have not done any sort of search to see if things are tighter now than they were back in ’96.

Jim

From: Cfrg  <mailto:[email-masked]> <[email-masked]> On Behalf Of Saqib A. Kakvi
Sent: Wednesday, September 19, 2018 8:58 AM
To: [email-masked] <mailto:[email-masked]> 
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Hello Russ,

Best
Saqib

Dear CFRG:

Russ

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 26 Sep 2018 19:14:02 +0000

​John Mattsson <[email-masked]> writes:

>If FDH gives better security it should be discussed, but based on your
>comments it is only as secure as PSS. 

Also, given recent results, neither are more secure than good old v1.5:

https://eprint.iacr.org/2018/855

Given that PSS and FDH are much, much more complex to implement than v1.5
(i.e. more things to go wrong), and require a source of random numbers that
v1.5 doesn't, is there any advantage to using PSS or FDH over just staying
with v1.5?

Peter.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 26 Sep 2018 19:47:48 +0000

However, there are two practical issues with what the paper actually proves:

- It proves that PKCS v1.5 signature with a 2n bit modulus is (at least as) hard to break as n bit RSA.  Hence, to get (say) 128  bit security, we would need (say) RSA-6144, rather than the conventional wisdom of RSA-3072.

- Even that that, the proof doesn't apply to v1.5 as used in practice, as it requires quite long hash outputs

To quote the paper:

Concretely, for signatures instantiated with an 2048-bit RSA modulus N, we can prove security under the 1024-bit RSA assumption, with 1024-bit padding and 1024-bit hash function....  Thus, ... our proofs do not immediately apply to PKCS#1 v1.5 when instantiated with standard hash functions, such as SHA-512...

Yes, v1.5 is nicer in practice, and it's good to have a proof of something, but lets not oversell what we have. 

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Peter Gutmann
> Sent: Wednesday, September 26, 2018 3:14 PM
> To: John Mattsson <[email-masked]>; Saqib A. Kakvi
> <[email-masked]>; [email-masked]
> Given that PSS and FDH are much, much more complex to implement than
> v1.5 (i.e. more things to go wrong), and require a source of random numbers
> that
> [email-masked]

---

From: Jim Schaad <[email-masked]>
Date: Wed, 26 Sep 2018 16:38:38 -0700

I may be wrong, but I was under the impression that FDH did not require a source of randomness, just a hash function that would deliver a full n-byte hash.  This is highly doable with SHAKE functions.

Jim

> Sent: Wednesday, September 26, 2018 12:14 PM
> v1.5 doesn't, is there any advantage to using PSS or FDH over just staying with
> v1.5?
> 
> Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 26 Sep 2018 23:56:49 +0000

Jim Schaad <[email-masked]> writes:

>I may be wrong, but I was under the impression that FDH did not require a
>source of randomness, just a hash function that would deliver a full n-byte
>hash.  This is highly doable with SHAKE functions.

Yep, sorry, for the randomness I meant only PSS, it's the complexity issue
that affects both of them.

Peter.

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 26 Sep 2018 17:13:02 -0700

> On Sep 26, 2018, at 4:56 PM, Peter Gutmann <[email-masked]> wrote:
> 

FDH seems quite simple, and has the nice property that, unlike v1.5 signatures, would be hard to verify improperly.

I wonder how much bias in the hash the security proof can tolerate. For example, suppose the modulus n is b bits. If H is a b-bit hash, would (H(m) if H(m)<n else H(m)-n) be good enough? That construction is fast and admits a fairly straightforward constant time implementation.

---

From: John Mattsson <[email-masked]>
Date: Thu, 27 Sep 2018 06:36:53 +0000

>        SHAKE ( mfgSeed, maskLen)

That looks like a good idea.

From: Jim Schaad <[email-masked]>
Date: Wednesday, 26 September 2018 at 16:55
To: John Mattsson <[email-masked]>, "'Saqib A. Kakvi'" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: RE: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Jim

Hi,

Cheers,
John

From: Cfrg <[email-masked]<mailto:[email-masked]>> on behalf of "Saqib A. Kakvi" <[email-masked]<mailto:[email-masked]>>
Date: Wednesday, 19 September 2018 at 20:32
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] A new MGF for RSA-PSS based on SHAKE

Hello Jim,

Best,
Saqib

Jim

Hello Russ,

Best
Saqib

Dear CFRG:

Russ

---

From: John Mattsson <[email-masked]>
Date: Thu, 27 Sep 2018 06:44:31 +0000

Thanks for summarizing the paper Scott. Going to RSA-6144 or RSA-8096 is not attractive at all. It creates much larger signatures and increases processing. Also, there are implementations that do not support anything more than RSA-3072.

/John

On 2018-09-26, 21:48, "Scott Fluhrer (sfluhrer)" <[email-masked]> wrote:

To quote the paper:

---

From: "A. Huelsing" <[email-masked]>
Date: Thu, 27 Sep 2018 09:52:01 +0200

Say n is ~1.5 * 2^(b-1), i.e. in the center of the interval [2^(b-1), 2^b]. Then
we know that the encoded message m' = H(m) mod n is in [0, 2^(b-2)] with
probability 1/2 and in [2^(b-2), 3*2^(b-2)] also with probability 1/2 but the
interval has twice the size. So there is a recognizable shift. This does not
necessarily allow for an attack but ....

You will be better off using the following:
Generate a hash value of length 2^(2b) and reduce it mod n. In this case the
shift in the distribution / the statistical distance is negligibly small.

---

From: Tibor Jager <[email-masked]>
Date: Thu, 27 Sep 2018 10:57:45 +0200

> On 26 Sep 2018, at 21:47, Scott Fluhrer (sfluhrer) <[email-masked]> wrote:
> 

The security proof from our paper has the following property: If we instantiate PKCS#1 v1.5 sigs with a hash function with h bit output length, then we get the same "provable security" as "h-bit RSA". In particular, the RSA modulus N need not have twice the size of the hash function, this was just one example in the paper.

To consider more examples, let |N| be the size of the modulus and |H| be the output length of the hash function. The padding then has length |pad| = |N| - |H|.

- In order to achieve security equivalent to "1024-bit RSA", one has to use |H| = 1024 and then of course |N| >= 1024. For instance, |N| = 2048 would work.
- In order to achieve the same security as "2048-bit RSA", one could use |N| = 3072, |H| = 2048.

Note that for |N| = |H| RSS-PKCS#1 v1.5 is basically the same scheme as RSA Full-Domain Hash.  Also, having |N| > |H| seems pointless from a formal provable security point of view. It may be useful for settings where PKCS#1 v1.5-like signatures cannot be avoided and it is still possible to use a hash function with long enough output. I am not sure if there are concrete examples of such settings.

> - Even that that, the proof doesn't apply to v1.5 as used in practice, as it requires quite long hash outputs

This is true. The proof guarantees no meaningful security for, say, SHA-256, or any other hash function with short output.

I would not recommend to prefer RSS-PKCS#1 v1.5  over RSA-FDH. When given a choice between different RSA signature schemes, RSA-FDH would be my preferred choice for practical use, for many different reasons:

- Very simple scheme. Note that "provable security" in the sense of theoretical cryptography means: secure, if implemented correctly. Hence, it may be useful to prefer as simple as possible algorithms.
- Very simple and clear security proof.
- The scheme is subversion-resilient in the sense of Ateniese et al. (ACM CCS 2015), when used with sufficiently-large public exponent.

Arguably, all these properties are not achieved by RSA-PSS.
RSA-PKCS#1 v1.5 signatures with |N| < |H| achieve the same properties, but the proof is much weaker, in the sense that we get only the security of "|H|-bit RSA". If |H| is too small (e.g., any choice from the current standard), we get no meaningful security. If we maximise |H|, then we are back at RSA-FDH.

All three signature schemes share that they have "tight" security proofs. The statement from RFC 8017, §8.1, on the non-tightness of RSA-FDH is incorrect. The tight proof is given in a paper by Kakvi-Kiltz (EUROCRYPT 2012).

> On 27 Sep 2018, at 02:13, Andy Lutomirski <[email-masked]> wrote:
> 

I think the known RSA-FDH proofs (both the "tight" and the "non-tight" ones) would carry over quite easily to a setting where |H| = |N| - 8 (or some other small value instead of 8 - note that |H| and |N| are measured in bits here, not in bytes).

For instance, one could use |N| = 2048 and |H| = 2040 without significant security loss.

Maybe this would allow for an even simpler, straightforward and constant-time implementation?

Cheers,
Tibor

---

From: Natanael <[email-masked]>
Date: Sun, 30 Sep 2018 01:48:27 +0200

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

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Sun, 30 Sep 2018 10:42:38 +0000

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]> on behalf of Natanael <[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:

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>