# $\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? Commented Nov 30, 2020 at 13:55
• A few hundred characters worth of dictionary words. Commented Dec 1, 2020 at 1:36
• Please don't cross post math.stackexchange.com/q/3928486/338051 delete the other copy. Commented Dec 1, 2020 at 20:50
• Done, sorry about that Commented Dec 2, 2020 at 3:12

## 2 Answers

The answer depends on your definition of a hash function.

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, Commented Dec 1, 2020 at 1:45
• This is an answer, not a comment. Please do not ask additional questions within the comment section below any answer. Commented Dec 30, 2020 at 12:06

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$$.

• Ok, thank you for your reply, it was helpful. You're saying that knowing C and D etc. will help me know that A is the correct A and not another A that happens to resolve to the same value. It seems your also saying that a hash function could be made to take advantage of knowing C and D etc. But standard hash functions likely do not have that property. Am I getting that right? Commented Dec 1, 2020 at 1:41
• @Xhiggy: yes! Basically, for a good hash, the best strategy is to search for the value of A using the shortest B, C, D... available, because that minimizes the duration; then check.
– fgrieu
Commented Dec 1, 2020 at 6:30