1
$\begingroup$

I was thinking the below attack scenario on hash function. Let's assume that three binary numbers A(1000 bits), B(16 bits) and C(283 bits) are concatenated together and H(A||B||C) is generated using SHA256 or SHA512. Here, the attacker knows C. Knowing C, is it possible for an attacker to find A or B or (A||B) from the output H(A||B||C)? If yes, what are the attacks and how to prevent them?

Thank You.

Improve this question
$\endgroup$
2
  • $\begingroup$ What did you try? $\endgroup$
    – kelalaka
    Commented Apr 22, 2021 at 18:51
  • $\begingroup$ What actually I wanted to do is that, 1st entity wants to send H(A||B||C) to 2nd entity for integrity check. Both entity know A, B and C. but C is public so attacker also know that. So is it safe to send this H(A||B||C) where the attacker can not know about A, B or A||B? $\endgroup$
    – Sami
    Commented Apr 22, 2021 at 19:05

1 Answer 1

Reset to default
1
$\begingroup$

Let consider $h = H(A\mathbin\|B\mathbin\|C)$ for SHA-256 or SHA-512 where both are MD-based cryptographic hash functions of NIST with

  • $A$ is 1000 bits
  • $B$ 16 bits, and
  • $C$ 283 bits

and we further assume that the attacker knows $h$ and $C$

Brute-force search

Definitely, the attacker cannot test the 1016-bit of unknown data to match the $h$. Bitcoin miners, the biggest known collective entity, can reach around $\approx 2^{93}$ This road is closed.

Prime-image attack

To find a pre-image normally we look for the first $a2^n$ input to find an input $x$ such that $h=H(x)$. For your case a little different.

  • Try random $a2^n$ values in the range $[2^{1299},2^{1300}]$. This has two problems;

    1. It is infeasible
    2. Even if the attackers have found one, the probability of result is equal to your data is $$\frac{2^{1299}}{2^{256}} = \frac{1}{2^{1043}}$$ for SHA-256, and $$\frac{2^{1299}}{2^{512}} = \frac{1}{2^{787}}$$ for SHA=512. Impractical, this road is closed, too.

And, we know that SHA-256 and SHA-512 are pre-image resistant, this road is also closed, too.

A simple counter-argument

  • If there is an attack on your case, that is one can extract $A$ and $B$ from $H(A\mathbin\|B\mathbin\|C)$ with the knowledge of $C$, Then we can use the length extension attacks on SHA-256 and SHA-512 to execute a pre-image. Simple, for a given $h'$ with $h' = SHA-256(x)$, execute a length extension $h'' = \operatorname{SHA-256}(x\mathbin\|C')$, then extract $X$ form $h''$ with the knowledge of $C'$. We don't have such any method.

    In other words, extend the hash then find a pre-image. End of the path.

If you are looking for a secure way to hash with a key, the obvious method is the HMAC or you can use KMAC of SHA3.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't understand how length extension attacks come into play. We know a length extension attack on SHA-256: If you know $H(A||B||C)$ then there is one specific $D$ for which you also know $H(A||B||C||D)$. So what? How does that matter towards finding $A||B$? $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Apr 22, 2021 at 21:53
  • 1
    $\begingroup$ @Gilles'SO-stopbeingevil' By considering that knowing C is a subset length extension. Then, if one can extract the information from $H(A||B||C)$ by knowing only the $C$, then take any $H(X)$ and extend it, since we know the extended part, we can extract the $X$. Not a great argument, I know. $\endgroup$
    – kelalaka
    Commented Apr 22, 2021 at 22:04
  • $\begingroup$ I have a very naive question. For length extension attacks, the format is H(secret || message). But I change the format, is it still vulnerable? for example: A and B are secrets and C is the message. Then, I concatenate (A || C || B) and generate the hash H(A || C || B), will it still be vulnerable to length extension attack? If so, how? $\endgroup$
    – Sami
    Commented Apr 23, 2021 at 17:47
  • 1
    $\begingroup$ @Sami the precious moment of the LEA is that the attacker can execute a signature without learning the key. The easiest mitigation is use SHA3, which naturally has resistance, use Blake2 which uses the HAIFA. Your modification is secret suffix is secure. Why don't you use HMAC or KMAC? $\endgroup$
    – kelalaka
    Commented Apr 23, 2021 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.