Hash extension(padding) attack

Question

I recently came across this website talking about sha1 padding attack.

https://web.archive.org/web/20140729003849/http://www.vnsecurity.net/2010/03/codegate_challenge15_sha1_padding_attack/

After reading here are some of my doubts:

1. How do the server side checks the signature? Even after successful padding, the sha1 hash is still different from the validate signature isn't it?

For example:
secretkey = key1
username = shaun
role = 1
sha1 hash : b7de8c16d9f42394b51e0c1c86c36a4b9bca8d49

secretkey = key1
username = shaun
role = 0
sha1 hash : 4e86a40776a282816ee0654cb2ec8a3fb2bd25e5

Can someone please explain to me which part do I get it wrongly? Thanks a lot :)

Answer 1

In this example, the server code looks like this:

Incoming value is "X|Y" -> split between "X" and "Y"
Compute id = Un-Base64(X)
Compute h = SHA-1(secret_key + id)
If the hexadecimal value of h is not equal to Y, then deny access
id is "user|role" with "role" being either 0 or 1; so, if id ends with "|0",
grant administrator access.

secret_key, of course, is unknown to the attacker. But the attacker can try to guess the length of that key, if only by trying different lengths; in that example, secret_key has length 25 bytes.

SHA-1 suffers from the length extension attack (like all Merkle–Damgård hash functions). See this answer for detailed explanations; bottom-line is that by knowing the length of secret_key, the attacker can compute a special "id" string like this:

id2 = aaaa|1somebytes|0

where somebytes include the SHA-1 standard padding, and then the attacker can compute the appropriate hash value for that "id", starting with the known SHA-1 value (the one for aaaa|1) and without knowing secret_key (that's the point of the "length extension attack": computing h(m') where m' starts with an unknown m, but with h(m) known).

The server will believe the provided "id" string to be genuine, and grant administrator rights to a user named "aaaa|1somebytes".