# $\mathrm{Hash}(A\|B)$ where $B$ is known, $A$ is unknown. Would knowing $\mathrm{Hash}(A\|C)$ as well as $C$, speed up a brute force search for $A$

Let's say $$\mathrm{Hash}(A\|B)$$ is a hash of two concatenated strings, $$A$$ and $$B$$.

Suppose I am trying to figure out $$A$$ from $$\mathrm{Hash}(A\|B)$$, I know $$B$$ but not $$A$$, I want to brute force to find $$A$$. Let's ignore practical reality for a moment.

If I also know $$\mathrm{Hash}(A\|C)$$, $$\mathrm{Hash}(A\|D)$$ etc, as well as $$C$$ and $$D$$ etc. can I use this info to reduce the time required in the brute force search?

• What are the size of all? Nov 30 '20 at 13:55
• A few hundred characters worth of dictionary words. Dec 1 '20 at 1:36
• Please don't cross post math.stackexchange.com/q/3928486/338051 delete the other copy. Dec 1 '20 at 20:50
• Done, sorry about that Dec 2 '20 at 3:12

In general hash functions don't guarantee, that they hide their input. A general hash function gives you three properties:

• preimage resistance (given $$y = H(x)$$ it is hard to find $$x^*$$ such that $$H(x^*) = H(x)$$)
• second preimage resistance (given $$y = H(x)$$ it is hard to find $$x^*$$ such that $$H(x^*) = H(x)$$ and $$x^* \neq x$$)
• collision resistance (it is hard to find $$x_1$$ and $$x_2$$ such that $$x_1 \neq x_2$$ and $$H(x_1) = H(x_2)$$)

None of these properties guarantee that the hash function doesn't reveal part of the input - i.e. there are hash functions that reveal $$A$$.

However, in practice you typically model hash functions as random oracles - for any input, the function yields a randomly chosen output.

In this case it is easy to show that it is hard to find $$A$$.

You might also want to take a look at length extension attacks, which are a way many hash functions deviate from a random oracle. However, these won't help you in finding $$A$$, they will however help you in finding (roughly) $$H(A \| B \| C)$$, given $$H(A \| B)$$ (without knowing $$A$$ or $$B$$).

• Thank you for your comment, I'll look into how length extension attacks can make my problem more feasible. In general I'm using the hash function more as a checksum. If I find there has been changes, how can I recreate the data knowing the hashes described in the question. Have you encountered any similar problems? It could save me a bunch of time to be pointed to the right source of information, Dec 1 '20 at 1:45
First the obvious: for most common hashes, if $$B$$ is large (several blocks), and $$C$$ is empty or small, and $$A$$ is amenable to brute force search, it makes a difference if $$\hat C=\text{Hash}(A\mathbin\|C)$$ is known, because testing if a value $$A'$$ matches $$\text{Hash}(A'\mathbin\|C)=\hat C$$ requires hashing less material than testing if $$\text{Hash}(A'\mathbin\|B)=\hat B$$, where $$\hat B=\text{Hash}(A\mathbin\|B)$$.
It's possible to construct a function $$F$$ where additional knowledge of $$\hat C=F(A\mathbin\|C)$$ with $$C\ne B$$ and $$|B|=|C|$$ would considerably help finding $$A$$ given $$\hat B=F(A\mathbin\|B)$$. But we do not know that's the case for standard hashes like those of the SHA-2 family. And if their security goal is met, that's not the case for more modern hashes like those of the SHA-3 family.
Independently, knowing $$\text{Hash}(A\mathbin\|C)$$ with $$C\ne B$$ gives an additional criteria to confirm that $$A'$$ found by brute force with $$\text{Hash}(A'\mathbin\|B)=\text{Hash}(A\mathbin\|B)$$ is indeed $$A$$.