SHA3-SHAKE (KECCAK) implementation

[danielburger1337]

Description

This is a very specific feature request and I don't really expect this to be added any time soon.

Since version 8.1 now supports an options array as an argument to the hash function, PHP could implement native support for the SHAKE128 and SHAKE256 algorithms that are part of KECCAK (SHA3).

Unfortunatly I could not find the original discussions from back when version 7.1 was released (when sha3 support was introduced), nor any other discussions about SHA3 for that matter, to find the reason why they were not implemented. My guess why they weren't implemented is that SHAKE has a variable output length that MUST be specified by the user and that back then there was no way to pass an option by the user to the hash implementation.

I am not too familiar with when and how often SHAKE algorithms are used in the wild, but I can't imagine that many people actually depend on them.

In my use case, we have a custom OAuth2 OpenID Connect implementation and have migrated from RSA to EdDSA token signing because a) EdDSA is faster and b) has a considerably shorter signature length. So that our PHP applications can fully support EdDSA with the curves like "Ed448", OpenID Connect requires SHAKE256 to generate the verification hashes like "s_hash" or "at_hash".

Since the options array is now available, the algorithm could be nicely integrated with the existing hash function:

<?php

print hash('sha3-shake256', 'This is a SHAKE256 test string. ', false, [
  'output_length' => 114 // value from OpenID Connect
]);

// 3477218c282909fa2e1df2e7c3bc

Since this should not break BC, this feature could be implemented with a minor release.

Unfortunatly I have absolutly no experience with PHP internals and much much less knowledge of cryptograhy/hashing in general and therefore am unable to submit a PR myself.

Thank you for reading my feature request and much love and respect to the internals team.

[cmb69]

It seems to me that we already have the underlying implementation:

php-src/ext/hash/sha3/generic64lc/KeccakHash.h

Lines 51 to 57 in 4c37b74

	/** Macro to initialize a SHAKE128 instance as specified in the FIPS 202 standard.
	*/
	#define Keccak_HashInitialize_SHAKE128(hashInstance) Keccak_HashInitialize(hashInstance, 1344, 256, 0, 0x1F)
	/** Macro to initialize a SHAKE256 instance as specified in the FIPS 202 standard.
	*/
	#define Keccak_HashInitialize_SHAKE256(hashInstance) Keccak_HashInitialize(hashInstance, 1088, 512, 0, 0x1F)

We would "only" need to provide that to userland.

[MaxSem]

@danielburger1337 are there any standard output sizes for these algos? Currently, even the Murmur hashes work by default without options specified, and it would be confusing if SHAKE was any different. Therefore, it would make sense to use output size as part of the algo name, e.g. tiger128,3 or sha512/224 currently supported.

[danielburger1337]

@MaxSem As far as I can tell, no.

These algoritms are defined in FIPS 202 Page20 and it only ever refers to the output length as d and only places the requirement that d must but a non-negative integer including 0.

It also doesnt really make sense to me that a default size should exist because these two algorithms are designed to be dynamic and are basically just sha3 with varying lengts.

Requiring the "output_length" option would also help users to not "accidentally" use these algorithms because they would actually have to go to the documentation and read what the output length is supposed to be.

I also found this usefull comment on stackexchange.

[MaxSem]

Yes, but what are the lengths used by its practical applications?😃 I can make a MR/RFC, but need to make sure I understand it enough to design an optimal interface.

[danielburger1337]

The only practical application that I know of, as mentioned in my inital comment, is OpenID connect with the Ed448 curve and EdDSA.

Ed448 uses SHAKE256 in multiple phases, but the important one for me and OpenID is the key generation part, where the private key is hashed with the SHAKE256(x, 114) function to create the public key.

In OpenID there is a concept of "at_hash", "s_hash" and a "c_hash", which are a bit much to explain here, but in short you can embed a hash of the used state, issued access token and issued authorization code in your issued id token.
The hash algorithm used is determined by the algorithm used to sign your id token. If your ID Token is signed with EdDSA Ed448, you have to create your hashes with the SHAKE256(x, 114) function.

The discussion of the OpenID Connect working group can be found here.

Michael Jones
We decided on the 5-Dec-19 working group call to use SHAKE256(x, 114) for Ed448, matching the hash function that EdDSA uses.

[MaxSem]

Okay, I've dug through the code and it needs a lot of refactoring around how it's using the options parameter in order for this to happen, especially if SHAKE is needed in HMAC. Meanwhile, I've discovered a segfault in #12186 :P