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

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?

-

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.

-
[+1] that is indeed a much better solution to what I proposed. Cheers –  rath Feb 10 at 19:03
I strongly believe that the structure would not make a 'more secure' hash function out of an already available hash function. Think of it as this, by accessing an oracle which finds a preimage for $h(.)$ finding a preimage for $h'(.)$ can be done just using a simple efficient polynomial time algorithm. –  Habib Feb 15 at 14:08
Hm, and how would this algorithm look like? Let's assume you have such an oracle, and it returns a preimage in $\mathbb{N}$. This doesn't help you at all, because $\mathbb{N}$ is pretty large, and you get a preimage and not all of them. The oracle does not provide any information if there is any kind of structure for the preimages in $\mathbb{N}$. Especially if you consider all of $\mathbb{N}$ as possible input to $h(.)$, then the probability that two oracle-answers are the same is 0. –  tylo Feb 17 at 10:17

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.

-
What does OP use for secret? A hash function isn't a PRF. What billpg wants is a construction which takes the fixed-length output of the hash function and stretches it without any secret data (for instance, the variable-length processing Skein uses, which basically runs the Threefish cipher in counter mode using the hash output as a key). One could always use a constant value for secret, but then it's hardly standard. –  Thomas Feb 10 at 13:29
What @Thomas said. :) –  billpg Feb 10 at 16:06

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

-

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.

-