Is there a standard way to extend the output of a hash?

Question

Say I have a hash function, a state-of-the-art hash function that we would all approve of that produces a fixed number of bits (n) as output. (I'll call it HASH.)

Is there are a standard way to produce a different number of bits from this building block? (I'd prefer it if HASH is treated as a black-box component that can't be modified internally.)

If I wanted less than n, I could just use as many bits from the output I want, ignoring the rest. (I think SHA-224 does this internally.) But what if I want more than n?

Or to put it another way, can I call (say) SHA256 sixteen times and produce something that's just as good (other than for speed) as a hypothetical SHA4096 would be?

Answer 1

If you assume the hash function as block box with no known preimage attack, then you can do the following to get a "more secure" hash:

• You have a message $m$ and a hash function $h(\cdot)$, and you want to extend the hash length by factor $k$.
• Assuming the hash function as block box, you don't change anything if you add a fixed prefix or suffix to the input string.
• However, if the prefix or suffix is different, you will get a random different output.
• Therefore if you have e.g. $h_0=h(m|0)$ and $h_1=(m|1)$, it should be even harder to find a common preimage $m$ than for a single hash function. But I have no idea how much harder it actually gets. But if you assume a random oracle for the hash function, and find a preimage for $h(m)$ after testing $x$ values in average, the common preimage should be found after testing $x^2$ values.

This leaves us with this formula (the suffix number inside the hash functions should be fixed size bitstrings):
$h'(m):=h(m|1)\,|\,h(m|2)\,|\,...\,|\,h(m|k)$

Finding a preimage or a collision then is not reduced to finding a match for a single input to the hash function but to several.

Answer 2

What you want is a PRF. For example, the one described in the TLS 1.2 RFC, which is defined as follows:

P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
                             HMAC_hash(secret, A(2) + seed) +
                             HMAC_hash(secret, A(3) + seed) + ...

where + indicates concatenation.

A() is defined as:

    A(0) = seed
    A(i) = HMAC_hash(secret, A(i-1))

P_hash can be iterated as many times as necessary to produce the
required quantity of data.  For example, if P_SHA256 is being used to
create 80 bytes of data, it will have to be iterated three times
(through A(3)), creating 96 bytes of output data; the last 16 bytes
of the final iteration will then be discarded, leaving 80 bytes of
output data.

This is built on HMAC, which can be used with any hash function of your choice. As described above, the result of the procedure is truncated after a sufficient amount of data has been generated, leaving the desired number of bytes as output.

Answer 3

If you believe it's ready for prime time, you could use Keccak, which provides as much output as you care to have.

Answer 4

If you just want long identifiers you could do $s = h(m) | h(h(m)) | \ldots$ and that's pretty fast for most uses (probably barring some embedded applications) but of course it's not as good as the hypothetical SHA4096 because each appended block is an "echo" of the previous one. In this case for $s=s_1 | s_2 | \ldots$ finding $s_a$ gives you $s_{a+1}, \ldots, s_n$

I think the best way to do this is by combining multiple hash functions (you'll notice that question has no accepted answer) or by using a hardcore predicate to extend your output by 1 bit at a time:

$$s=H(m, n) : h(m) | b(m_1), \ldots, b(m_n)$$

For a quick-and-dirty solution (this may be wrong - see below) let's consider a family of functions $h_1, h_2, ... \in h$, assuming the differences between them isn't just the point of truncation (as is the case with SHA256 and SHA512), and that all of them are as secure as the most secure function, output

$$s = h_1(m) | h_2(m) | \ldots$$

If $m$ is long enough you could split it up in parts and use $m_n$ for each $h_n$, but this also affects brute-force time, because the adversary now can use recovered pieces as "hints" to aid him in finding the others.

tl;dr: If we were to treat hash functions as black-boxes, for any fixed-length hash function I think your question boils down to combining a number of them.