Restrictions in Keccak parametrization affect KMAC

[falko-strenzke]

While implementing KMAC256, I found that the current Keccak implementation has the following restriction regarding output lengths:

   if(output_bits != 224 && output_bits != 256 &&
      output_bits != 384 && output_bits != 512)
      throw Invalid_Argument("Keccak_1600: Invalid output length " +
                             std::to_string(output_bits));

Is there a specific reason for this? This restriction means that Keccak[c](N, d) defined in the Keccak specification is not supported for general parameters. My suggestion would be to lift at least the restriction for the output lengths and allow arbitrary output lengths. Would this have any known implications?

[randombit]

1. You do not want Keccak at all here; Keccak is the old pre-final version from the SHA-3 competition which has slightly different padding rules.
2. IIUC SHA-3 is in fact only defined for the specified output sizes, with SHAKE handling "arbitrary length" outputs, so I would not want to allow eg SHA-3 with 192 bit output length if this is not going to be implemented by other versions.
3. I think you do not want to define this in terms of the HashFunction at all, but build it out of the public static functions SHA_3::absorb, SHA_3::finish, SHA_3::expand and SHA_3::permute which are exposed to allow this sort of thing; for example the various SHAKE implementations are defined in terms of these functions.

[falko-strenzke]

I am a bit confused now.

You do not want Keccak at all here; Keccak is the old pre-final version from the SHA-3 competition which has slightly different padding rules.

What is imlemented in Botan as Keccak is not Keccak[capacity](input string, output_length) according according to https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf#page=28 ? And it is meant to stay like this?

IIUC SHA-3 is in fact only defined for the specified output sizes, with SHAKE handling "arbitrary length" outputs, so I would not want to allow eg SHA-3 with 192 bit output length if this is not going to be implemented by other versions.

SHA-3 is for sure the wrong primitive to build on. KMAC is defined in terms of Keccak.

I think you do not want to define this in terms of the HashFunction at all, but build it out of the public static functions SHA_3::absorb, SHA_3::finish, SHA_3::expand and SHA_3::permute which are exposed to allow this sort of thing; for example the various SHAKE implementations are defined in terms of these functions.

Why would I not want define it in terms of the hash function? That is the most natural approach in my understanding and avoids unnecessary code duplication. My approach would be to implement Keccak and then KMAC on top of it. But if a hash named Keccak already exists and it is not the standardized version of Keccak, then I think we need a second version of Keccak and need to agree on the naming.

[randombit]

What is imlemented in Botan as Keccak is not Keccak[capacity](input string, output_length) according according to https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf#page=28 ? And it is meant to stay like this?

It seems like these may be the same? But if so this is largely an accident. What is implemented as Keccak is the hash function proposal that was submitted to NIST which eventually became SHA-3. It is used for example in Ethereum. The only real reason it is implemented is because I implemented this hash function in anticipation of it being a likely SHA-3 finalist (was originally added in 2010), and then they changed the padding rules late in the process, which is why there is SHA-3 and Keccak.

If it happens that this Keccak is in fact identical to what NIST standardized, then fine to generalize this. The restriction was matching what was in the original Keccak proposal. Note that if you want large output lengths you would need to modify Keccak::finish to handle this.

[falko-strenzke]

OK, I think now I basically understand the source of the confusion. NIST themselfes seem to use the name "Keccak" to refer to two different things:

• by the name Keccak without any further parameters they refer to a concrete algorithm, probably the final submission (?) during the contest
• in the FIPS 202 'Keccak[c]' is defined to a "Keccak" instance with width 1600 and capacity c.

I didn't try to find out where both version deviate technically, but in any case they differ in scope as the Keccak[c] allows for various capacities where Keccak must have one specific capacity.

So most likely both variants are useful. I will propose a PR with Keccak_FIPS[256] etc. added. All Keccak[c]-based algorithms, namely SHA-3, SHAKE and KMAC will be based on it, simplifying the code-base to some extend.

[randombit]

All Keccak[c]-based algorithms, namely SHA-3, SHAKE and KMAC will be based on it, simplifying the code-base to some extend.

I am unconvinced that this is the best approach.

While it may be the easiest implementation of these subsidiary algorithms, it exposes a HashFunction instance that - AFIACT - nobody would actually want to use directly in practice.

Also I am unconvinced this is a simplification overall. The implementations of SHAKE_128, SHAKE_256 and Keccak are currently implemented in terms of the functions SHA_3::{absorb,finish,expand,permute} which are intentionally exposed for this purpose, and the implementations of these algorithms are already very short.

[falko-strenzke]

While it may be the easiest implementation of these subsidiary algorithms, it exposes a HashFunction instance that - AFIACT - nobody would actually want to use directly in practice.

No problem, then the Keccak-FIPS algorithm needs not to be part of the public API.

Also I am unconvinced this is a simplification overall. The implementations of SHAKE_128, SHAKE_256 and Keccak are currently implemented in terms of the functions SHA_3::{absorb,finish,expand,permute} which are intentionally exposed for this purpose, and the implementations of these algorithms are already very short.

I disagree. They can be much shorter. With the changes I propose SHA3 based on Keccak[c] – which is simply the order of derivation the specs give us – there is only the need to override the ctor of SHA3. The current code reproduces the whole set of member functions, while in the specs these algorithms differ only in a few parameters.

With the present code-base I had a pretty hard time figuring out how to realize KMAC. This is due to

• SHA-3 being used as a the underlying primitive instead of Keccak[c] as the specs do
• an intricate interfacing to the final padding that requires to delve into internals of the implementation and the internals of Keccak[c]:
  • Mixing the Keccak[c] final padding with the custom padding of the derived algorithm
  • Making the custom final padding obscure as it is mixed with the inital "1" bit of the Keccak[c] final padding

In my proposal I resolve all these problems. The complete pull request isn't ready, but I'll if want to take a look here: https://github.com/falko-strenzke/botan, branch kmac

@randombit From tomorrow I am on vacation for 3 weeks. Afterwards I'll be happy to pick up the discussion again.

[FAlbertDev]

The BSI asked us to move the integration of KMAC forward because they need it for one of their projects. You, @falko-strenzke, already created a branch for this integration. Is there still work to be done with KMAC, or can we expect a pull request in the following weeks? Otherwise, we want to offer our support, or, if you currently do not have time, offer to continue/finish your work.

[falko-strenzke]

Work on KMAC is mostly done from my side, but since I accidentally based the implementation on the dilithium branch, I still have some rebasing work to do. But I plan to finish it in the next weeks.

[FAlbertDev]

Very nice!

[reneme]

With the parallel introduction of the XOF interface (#3671), this whole integration process became a mess. Sorry for that! Nevertheless, I think, we're converging nicely now. Here's what I think needs to be done to integrate this:

1. Squash: (@falko-strenzke)
   • Refactoring SHA3: based on new permutation keccak-fips #3673 and
   • Refactor: Keccak Permutation #3675
2. Review/Merge the squashed version of the Keccak_Permutation refactoring (@FAlbertDev, @randombit)
3. Rebase and adapt: (@falko-strenzke, @reneme, @FAlbertDev)
   • KMAC, 2nd: added keccak-fips as standalone; added KMAC-256 #3570
   • Feature: KMAC-128/256, NIST SP.800-185 #3689
   • eXtendable Output Functions as first-class citizen #3671
   • Use XOF interface in Kyber and Dilithium #3672
4. Review/Merge

[reneme]

This was quite a journey to get KMAC upstream. Though, I think the improvements in Keccak and the XOF interface were very much worth it. I'm happy with the final shape of this implementation. Thanks a lot @falko-strenzke for all the work you put in and also your patience. @randombit thanks for bearing with us discussing the nitty gritty Keccak architecture. :)