Subject: [COSE] SHAKE hashing discuss

From: Jim Schaad <[email-masked]>
Date: Sat, 27 Jun 2020 11:33:49 -0700

During the IESG review of the hash algorithms draft, Ben pointed out that I
had a big hole in my understanding of how SHAKE worked.  Even worse, I
should have known this but it went against how I had thought SHAKE was
designed so when I read that I was wrong I just did not review it.

SHAKE128 does not have the property that prefixes are going to be unique
depending on the length requested.  In order to fix this there are four
different paths that I see:

1.  Just make the lengths of the outputs fixed.  Thus SHAKE-128 => 128-bits
and SHAKE-256 => 256-bits.

2.  Switch from using SHAKE to using KMAC with a zero-length key.  KMAC does
have the property that it is does not generate prefixes.  The output is
changed by specifying the length of the output.

3.  Make the lengths fixed, but define some additional algorithms with
different lengths.  This is the approach used with SHA-2.

4.  Do a combination of either 1 and 2 or 1 and 3.  In this case the second
half would be deferred to the more-algs draft.

If I have not seen any sort of consensus on the list by July 3, I will just
do option one and punt on anything else.

Jim

---

From: Quynh Dang <[email-masked]>
Date: Sat, 27 Jun 2020 15:43:54 -0400

Hi Jim,

You should not hash (process) the same message X twice to produce 2
different outputs (2 different-length outputs). It is the same situation as
SHA-512 with output lengths being 512 and 256 (a truncated output of
SHA-512).

In that situation, you should do SHAKE256 (domain_seperation_i || X,
output_length_i) for each different output_i.

With SHA3s such as SHA-3/256, if you want a 512-bit output from input X,
you will run SHA-3/256 twice such as SHA-3/256 (X) || SHA-3/256 (1|| X).

With SHAKE256, you just run SHAKE256 (X, 512).

So, the former option destroys the benefit of the sponge construction and
it is practically 2 times more expensive than the latter.

Regards,
Quynh.

On Sat, Jun 27, 2020 at 2:34 PM Jim Schaad <[email-masked]> wrote:

> _______________________________________________
> COSE mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cose
>

---

From: Benjamin Kaduk <[email-masked]>
Date: Sun, 28 Jun 2020 11:48:22 -0700

> do option one and punt on anything else.

FWIW, my expectation was (IIUC) similar to what Quynh described, just
prepending an encoding of the requested output length to the digest input,
to provide domain separation.

-Ben

---

From: Jim Schaad <[email-masked]>
Date: Sun, 28 Jun 2020 20:58:18 -0700

> -----Original Message-----
> From: Benjamin Kaduk <[email-masked]>
> Sent: Sunday, June 28, 2020 11:48 AM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [COSE] SHAKE hashing discuss
> 
> > During the IESG review of the hash algorithms draft, Ben pointed out
> > that I had a big hole in my understanding of how SHAKE worked.  Even
> > worse, I should have known this but it went against how I had thought
> > SHAKE was designed so when I read that I was wrong I just did not review
it.
> >
> > SHAKE128 does not have the property that prefixes are going to be
> > unique depending on the length requested.  In order to fix this there
> > are four different paths that I see:
> >
> > 1.  Just make the lengths of the outputs fixed.  Thus SHAKE-128 =>
> > 128-bits and SHAKE-256 => 256-bits.
> >
> > 2.  Switch from using SHAKE to using KMAC with a zero-length key.
> > KMAC does have the property that it is does not generate prefixes.
> > The output is changed by specifying the length of the output.
> >
> > 4.  Do a combination of either 1 and 2 or 1 and 3.  In this case the
> > second half would be deferred to the more-algs draft.
> >
> > If I have not seen any sort of consensus on the list by July 3, I will
> > just do option one and punt on anything else.
> 
to
> provide domain separation.

I don't know that I would really want to add a step to just this one hash
function.  Using KMAC appends the requested output length and has the domain
separator.  The only issue would be that it is not the same function call.

Jim