1
$\begingroup$

Assuming there is a web service that returns the following to an unauthenticated user:

SHA-1(known_prefix + user_input + backend_secret)

where + is string concatenation, known_prefix is known to the attacker, user_input can be specified almost arbitrarily (maybe only printable ascii characters, but arbitrary length), and the backend_secret is something that the attacker should not know.

Is there an intelligent way, by specifying different user_input strings and analyzing the returned SHA-1 hash, how an attacker could extract the backend_secret? Something better than bruteforcing it.

$\endgroup$

1 Answer 1

4
$\begingroup$

Is there an intelligent way, by specifying different user_input strings and analyzing the returned SHA-1 hash, how an attacker could extract the backend_secret?

There is a possible way to get some information on backend_secret (at least, the value of the first several bytes); this might speed up the follow-up brute force search.

This is based on finding a SHA-1 collision, where $SHA1(A) = SHA1(B)$ (and, in particular, the internal SHA-1 state immediately after processing $A$ and $B$ is the same), and has these further properties:

  • $A, B$ both start with known_prefix

  • The last byte of $A, B$ are the same

  • If we replace the last byte of $A, B$ with a different value, they are not a collision.

I believe that it is feasible to find such a collision.

The probe is obvious, we query for both known_prefix + user_input = A (less the last byte), and known_prefix + user_input = B (less the last byte). If the first byte of backend_secret was the common last byte of A, B, then the results of the two queries are the same (and hence we have learned the first byte of backend_secret). If they are different, we have learned what the first byte of backend_secret was not (and we can try again with a different collision with a different final last byte).

We can then proceed with the same attack to recover the second (and then third, etc) bytes. The requirements on the collision become stricter; it is likely that the known $O(2^{60})$ collision attacks will no longer yield applicable collisions, however a straight-forward $O(2^{80})$ birthday attack will, and so this would yield a $O(2^{88})$ effort per byte (which may or may not be considered feasible, depending on whether we're looking at this as a cryptodesigner or an adversary).

$\endgroup$
3
  • 1
    $\begingroup$ Yes! Addition: we need $A$, $B$, known_prefix + user_input + probed_start_of_backend_secret to be of the same size multiple of 512 bits (32 bytes). $\endgroup$
    – fgrieu
    Sep 16, 2023 at 12:32
  • $\begingroup$ Alright nice, so this works because of the Merkle–Damgård construction. I'm wondering if there is some even more efficient way that works directly with the compression function... $\endgroup$
    – dan-ros
    Sep 16, 2023 at 15:06
  • 3
    $\begingroup$ @dan-ros: doesn't look extremely likely. The known issues with the SHA-1 compression function are the collision attacks (which I exploited) and the fact that finding 'fixed points' (that is, given a message block, what initial state is mapped to itself) is easy (and that second observation doesn't appear to be exploitable) $\endgroup$
    – poncho
    Sep 16, 2023 at 15:59

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.