SHAKE, cSHAKE and some more bit ordering
posted April 2017
cSHAKE is something to make your own SHAKE! It's defined in this NIST's doc SP 800-185 along other awesome Keccak structures like KMAC (a message authentication code a la
hash(key + data) with no length-extension attacks!) and TuppleHash (a hash function to hash structures without ambiguity (fingerprints!)).
So I thought it would be a good opportunity for me to talk more about SHAKE, cSHAKE and remind you how the bit ordering works!
What is SHAKE?
SHAKE (Secure Hash Algorithm and KECCAK), defined in FIPS 202, is an Extendable-Output Function (or XOF). It's like SHA-3 but with an infinite output. For whatever length you need. You can use that as a KDF, a PRNG, a stream cipher, etc ...
It's based on The Keccak permutation function, and it works pretty much like SHA-3 does. The two differences are that a different domain separator is used (
1111 is appended to the input instead of
01 for SHA-3) and you can continue to squeeze the sponge as much as you like (whereas SHA-3 defines how much you should squeeze).
Of course the squeezing will affect the security of your output, if used as a hash you can expect to have 128-bit security against all attacks (including collision resistance) when using an output of 256-bit. If you truncate that down to 128-bit, you will get rid of the collision resistance property but still have (at least) 128-bit security against pre-image attacks. More information is available in the FIPS 202 document where you will find this table in Appendix A:
SHA-3 and SHAKE were great constructions, but Keccak has so much to offer that the NIST had to release another document: SP 800-185 (for "special publication"). It covers some other constructions (as I said previously), but this is still not the extent of what is possible with Keccak. If you're interested, check KangarooTwelve (which is to SHA-3 what Blake2 is to Blake, a less secure but more efficient hash function), the duplex construction (use the sponge continuously!), Ketje and Keyak (two authenticated encryption modes), ...
SP 800-185 defines cSHAKE as a customable version SHAKE. It works the same except that you have one new input to play with: a customization string. If you've used HKDF before you will quickly get its purpose: avoid collisions between different usages of the Shake function. Here are two examples given by the NIST special publication:
cSHAKE128(input: public_key, output: 256 bits, "key fingerprint"), where "key fingerprint" is the customization string.
cSHAKE128(input: email_contents, output: 256 bits, "email signature")
how it works
As with SHAKE, you can choose an output length, here is how the input and the customization string gets fed to the cSHAKE function:
- Use an empty
Nstring (this is for NIST use only)
- Choose a customization string
encode_string()on the empty string
Nand on your customization string
- apply the
bytepadfunction to both with the rate of the permutation in bytes (
168in the case of cSHAKE128).
- prepend this to your input
- append the bits
00to your input (domain separator)
KECCAK(bytepad(encode_string(N) || encode_string(S), 168) || input || 00)
What are these functions?
left_encode(len(input)) || input.
left_encode: a way to encode a length. It encodes the length of the length, then the length :) all of that in an LSB bit numbering.
left_encode(block_size) | input | 0000...0000 with enough 0s for the resulting output to be a byte array multiple of the rate.
The above function can be rewritten:
KECCAK(left_encode(block_size) || left_encode(0) || "" || left_encode(len(S)) || S || 0000...0000 || input || 00)
(This input will then get padded inside of Keccak.)
These functions are defined in the special publication NIST document, but they are quite different in the reference implementation).
So here is another explanation on this bit re-ordering trick. Imagine that we have this input to the
0001 0000 | 0011 0001 | 0111 1110
As an hex table it would look like this:
0x10 | 0x31 | 0x7e
left_encode specification tells us to completely reverse this value, then add a reversed length on the left (here 3). It would look like this:
0111 1110 | 1000 1100 | 0000 1000 1100 0000 | 0111 1110 | 1000 1100 | 0000 1000
This is quite annoying to code. Fortunately, the reference implementation has a trick: it takes the bytes as-is but re-position them following the little endian ordering convention, then add the padding in a natural MSB first bit numbering:
0111 1110 | 0011 0001 | 0001 0000 0000 0011 | 0111 1110 | 0011 0001 | 0001 0000
The Sponge code then re-interprets this in little endian convention:
0001 0000 | 0011 0001 | 0111 1110 | 0000 0011
Which is exactly what was expected, except in reversed order :) which is OK because if you remember correctly from my previous blogpost every operation of the spec is implemented in reversed in the reference implementations.
How to use cSHAKE?
The official Keccak Code Package contains all the keccak functions in C. I've written a Golang version of cShake here that you can put in your
golang.org/x/crypto/sha3/ directory, as it hasn't been reviewed by anyone yet I would take this with chopsticks.