That seems like it would be a useful primitive. Using it in place of a block cipher in the Merkle–Damgård construction would give a variable-length hash, maybe without the tricky business with related keys? Using it to hash a key+nonce+position would give you a stream cipher. Though maybe the collision resistance we need from hashes is wasteful for a cipher?

Relatedly, why is it that block ciphers seem to be the low-level building block of choice for hashes and stream ciphers? Especially when the decryption operation doesn't seem to get used very often.

  • 5
    $\begingroup$ You are pretty much describing the core of the Salsa and ChaCha stream ciphers, as well as the Blake hash functions $\endgroup$ – Richie Frame Dec 30 '15 at 9:21
  • 3
    $\begingroup$ Technically, any standard hash function can be made into one that takes a fixed-size input, simply by restricting its inputs to a specific size. $\endgroup$ – Ilmari Karonen Dec 30 '15 at 9:40
  • 2
    $\begingroup$ @Richie Frame: the Salsa(20) core is not collision-resistant, and Bernstein insists it, or the ChaCha core, are not intended to be fixed-size hash functions. See this question. $\endgroup$ – fgrieu Dec 30 '15 at 10:57
  • 1
    $\begingroup$ SHAKE128 and SHAKE256 (part of SHA-3 / Keccak) are "hash functions" with configurable output, if you're after that. The official name for this kind of function is a XOF. $\endgroup$ – Maarten Bodewes Jan 1 '16 at 15:32

Such a category of functions is not generally used as is, but compression functions, which are close to what you describe, are (as you describe) used to build (variable length) hash functions. For example, Merkle–Damgård hashes like SHA-2 have a compression function that takes an IV (or previous block output) and a fixed size data block to generate a smaller fixed-size output.

If you want to use a compression function as a cipher you can. If you use the key as the data block input, you get a block cipher that in the case of SHA-1 and SHA-256 is called SHACAL-1 and SHACAL-2. You can then construct a stream cipher from these using CTR mode.

However, Merkle Damgård does not require a block cipher, and Damgård suggested several number theoretical problems for the compression function in A Design Principle for Hash Functions.

Relatedly, why is it that block ciphers seem to be the low-level building block of choice for hashes and stream ciphers?

Many hashes and stream ciphers are built from something else, like Salsa20 or SHA-3.

However, it is true that block ciphers have been used a lot. Partially because everyone was looking for ways to use DES (and later AES) which was standardized by NIST. Partially because the design of block ciphers is well understood.


Hash functions generally (always ?) take a variable size input that's why they are also called compression functions. The hash functions are also generally collision resistant, or they are designed in such aim for cryptographic applications. What you are describing is a particular category of one way function (OWF). There is also a subcategory : random permutation where the input and output sets have the same size (necessary but not sufficient: the sufficient condition is one to one mapping).

In this function category the collision resistance is not always necessary, for instance in the Lamport signature scheme a one way function with second preimage only is required.

For a "post quantum" design it seems that the ideal primitive would be a 256 bits -> 256 bits function. Does anyone know such primitive?

  • 5
    $\begingroup$ At least in cryptographic terms a compression function is not quite the same thing as a hash function. Compression functions are used inside some hash function constructions (like the Merkle-Damgård used in SHA-1 and -2) and in fact do take a fixed-sized input. $\endgroup$ – otus Dec 30 '15 at 17:58
  • $\begingroup$ This is correct, I should have used the term "function which performs data compression". That being said one interesting question would be : do a cryptographic hash function necessarly uses a compression function with fixed size input ? Are there cryptographic hash functions which don't apply this paradigm, like Merkle Damgard ? $\endgroup$ – Fraktal Dec 30 '15 at 20:13
  • $\begingroup$ SHA-3 uses the sponge construction where the iterated sponge function has the same size input as output. (However, you could still recast it in terms of a compression function of sorts by defining the input XOR as part of the function.) $\endgroup$ – otus Jan 1 '16 at 9:49
  • $\begingroup$ Does anyone know such primitive? – is that a question? ;) $\endgroup$ – e-sushi Jan 29 '16 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.