Add support for SHAKE128 and SHAKE256

[dannote]

Rationale

SHAKE128 and SHAKE256 are part of the SHA-3 hash family (are also based on Keccak-f[1600] permutations), and while they are not as commonly used as SHA3-*, there are notorious projects, such as Tor, which use them as key derivation functions. OpenSSL 1.1.1 supports both.

Purposed changes

As those functions are XOFs (Extendable Output Functions), supporting them might require some tweaks to existing APIs for providing variable output length. I think the cleanest way would be to pass tuples with algorithm name and size of output needed in bits:

crypto:hash({shake256, 32}, Msg)

State = crypto:hash_init({shake128, 256})
State2 = crypto:hash_update(State, Msg)
crypto:hash_final(State2)

[HansN]

We don't plan for this, but it seems as a good medium-level PR project! Volunteers?

[marcellanz]

I had a look into this issue.

Having a POC ready that implements SHAKE128 without the existing API extended yet, beside a new hash-type shake128, I would like to volunteer to implement support for SHAKE128 and SHAKE256.

POC of shake128:

Erlang/OTP 24 [erts-12.1.2] [source-84f2899978] [64-bit] [smp:16:16] [ds:16:16:10] [async-threads:1] [jit]

Eshell V12.1.2  (abort with ^G)
1> crypto:hash(shake128, "Hello Joe").
<<30,193,173,28,104,94,89,86,201,52,207,43,27,229,144,229>>
2> crypto:hash(shake128, "").         
<<127,156,43,164,232,143,130,125,97,96,69,80,118,5,133,62>>
3> 

with the test vector for a zero message matching:

#  CAVS 19.0
#  "SHAKE128 ShortMsg" information for "SHAKE3AllBitsGT"
#  SHAKE128 tests are configured for BIT oriented implementations
#  Length values represented in bits
#  Generated on Thu Jan 28 14:45:08 2016

[Outputlen = 128]

Len = 0
Msg = 00
Output = 7f9c2ba4e88f827d616045507605853e

[marcellanz]

@HansN If there are no objections, I'll work on this further. Already have some more progress and will be able to present some options for the API changes or additions as well.

[HansN]

@marcellanz Please go ahead!

Read Contributing to Erlang/OTP if you haven't done that already. Note specially the need for tests and for documentation. You could base the PR on the maint branch in this case since it will not change the existing API.

God luck!

[marcellanz]

Please go ahead!

@HansN thanks and thanks for the pointers. I'll go forward then and prepare a PR as expected by the guidelines.

God luck!

Thanks :)

[marcellanz]

API change considerations

Beside implementing support for SHAKE I investigate options for the API to use.

The Issue text stated that:

... the cleanest way would be to pass tuples with algorithm name and size of output needed in bits:

crypto:hash({shake256, 32}, Msg)
State = crypto:hash_init({shake128, 256})
State2 = crypto:hash_update(State, Msg)
crypto:hash_final(State2)

I'm not sure about to change the existing API for other hash types too. The FIPS Standard[0] states that:

The SHA-3 family consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384, and SHA3->512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256.

XOF types are not hashes in the common sense

So, to be precise, the XOF SHA3 types are not hash functions in the common sense, but as their name suggests extendable-output functions. While I consulted a few other API of other libraries of other languages that implement XOF types [2],[3],[4],[5],[6], most of them use an explicit API where the output length is chosen at the end of the init/update/final well known digest API call sequences. The output length and therefore the length of the "hash" output with SHAKE128 and SHAKE256 can be chosen after creating the message-digest context right with the usual final call. Other libraries therefore often chose to provide a buffer that is written with the resulting digest, and the length chosen corresponds to the size of the buffer provided. Others just let the user read n-bytes of the resulting digest-stream.

This leads to a property of the SHAKE algorithms and actually all XOFs; the resulting digest can be of arbitrary length. OpenSSL has an open PR and some discussion if they should support that streaming usecase: https://github.com/openssl/openssl/pull/7921 They also discuss if such an API should include the term "final" for this last or continuing step to get consecutive pieces of the digest output stream. OpenSSL so far just suffixed their API with XOF:

int EVP_DigestFinalXOF(EVP_MD_CTX *ctx, unsigned char *md, size_t len)

being the last step to get the output digest written to the output buffer.

Last, there are other types of XOF based functions [1], some are variants of SHAKE: https://en.wikipedia.org/wiki/SHA-3#Additional_instances

cSHAKE128 if cimplemented would have a different API than a "normal" hash

cSHAKE128(X, L, N, S)

with multiple arguments.

With NIST standards body stating:

XOFs have the potential for generating related outputs

a property that is not expected by traditional hashes, XOF based hash functions are not hashes in the common sense and therefore I'm not sure to use the hash API just as it is known so far by the Erlang crypto module.

1st POC for SHAKE128

With my POC for SHAKE128 I've got so far with the following API:

crypto:hash_xof(shake128, Msg, 256)
...
State = crypto:hash_init(shake128),
State2 = crypto:hash_update(State, Msg),
crypto:hash_final_xof(State2, 256).

With even a variation of crypto:hash(shake128, "", 128)

A session with this looks like:

Erlang/OTP 24 [erts-12.1.2] [source-c316df13be] [64-bit] [smp:16:16] [ds:16:16:10] [async-threads:1] [jit]

Eshell V12.1.2  (abort with ^G)
1> binary:encode_hex(crypto:hash_final_xof(crypto:hash_update(crypto:hash_init(shake128), ""), 128)).
<<"7F9C2BA4E88F827D616045507605853E">>
2> binary:encode_hex(crypto:hash_xof(shake128, "", 128)).
<<"7F9C2BA4E88F827D616045507605853E">>
3> binary:encode_hex(crypto:hash(shake128, "", 128)).
<<"7F9C2BA4E88F827D616045507605853E">>
4> 

How to go forward?

With the findings above, I'm inclined to discriminate between hashes and XOF's, and therefore functions.

The NIST Special Publication 800-185[1] states:

Hash Function: 
A function on bit strings in which the length of the output is fixed. The output often serves as a condensed representation of the input.

This does not match with a XOF, that is rather:

eXtendable-Output:
A function on bit strings in which the output can be extended to Function (XOF) any desired length.

To make it not more complicated than needed, we still could prefix these functions with hash_ right? We could use

%% a1)
crypto:hash_xof(shake128, Msg, 256)

or if we choose do be explicit about XOFs:

%% a2)
crypto:xof(shake128, Msg, 256)

If we introduce xof_opts() we could better adapt to the properties of XOFs, like:

%% b1)
crypto:hash_xof(shake128, Msg, [{d, 256}])

or

%% b2)
crypto:xof(shake128, Msg, [{d, 256}])

with the last argument modelled as xor_opts() with the well known identifiers by the XOF functions. For the intermediate funs we could go sticking with the well known init and update functions are they are semantically similar so far, and just the "final" call having hash_final_xof/3with xof_opts as the last argument.

%% c)
State = crypto:hash_init(shake128),
State2 = crypto:hash_update(State, Msg),
crypto:hash_final_xof(State2, [{d, 256}]).

I'm inclined to go with options a2) and b2) and c). Having the option to adapt for future other XOFs supported.

Future support for other XOF

OpenSSL seems not to support other XOF functions other than SHAKE128 and SHAKE256, so we don't have yet to have an API option for that. To support the customized XOFs like cSHAKE and also a streaming API where the "final" hash_final_ can be called might be possible with other options, xof_opts and a message digest state returned with such a function.

@HansN, @dannote wdyt? To go forward I need some other opinions I think. I'm not that experienced (yet) with Erlang API design thinking. I have the impression changing the existing API as stated in the issues text might perhaps not be an option. Also I'd propose as written before, to discriminate the XOF and therefore diverge a bit from the well known API if a traditional hash.

[0] FIPS-202, https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf [1] NIST SP 800-185, https://doi.org/10.6028/NIST.SP.800-185 [2] Python, https://pycryptodome.readthedocs.io/en/latest/src/hash/shake128.html?highlight=shake#Crypto.Hash.SHAKE128.SHAKE128_XOF.read [3] Go, https://pkg.go.dev/golang.org/x/crypto/sha3#ShakeSum128 [4] Java, keccakj, https://github.com/aelstad/keccakj#messagedigests-1 [5] Java, iaik_jce, https://javadoc.iaik.tugraz.at/iaik_jce/current/iaik/security/md/SHAKE128InputStream.html [6] Rust, https://docs.rs/sha3/0.9.1/sha3/struct.Shake128.html