2
$\begingroup$

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?

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

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

$\endgroup$
2
  • $\begingroup$ 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, $\endgroup$
    – Xhiggy
    Dec 1 '20 at 1:45
  • $\begingroup$ This is an answer, not a comment. Please do not ask additional questions within the comment section below any answer. $\endgroup$
    – Maarten Bodewes
    Dec 30 '20 at 12:06
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Xhiggy
    Dec 1 '20 at 1:41
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Dec 1 '20 at 6:30

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.