SHA1 padding on length extension attack

Question

I was recently trying to replicate a length extension attack on SHA1. I implemented the registers state and also the new padding implementation (with the whole of the message that I want to extend). And it works, I know the length of the key, so I'm able to get the total length of the message and forge a hash. However, when I try to brute force the length of the key (as it should be unknown), I always end up getting the same hashes for groups of 64 lengths, and not different ones for each. This makes sense for me, as I am padding the (original message + key) and so the length of the padded message should be the same for a certain number of key sizes, right? Does this imply that it is impossible to retrieve the key length? I think there is something wrong in my reasoning... Here is the code that I'm using:

for i in range(0, 200):

        specificLength = len(padSHA1(i * "a" + originalMsg) + "extension")

        forged = sha1ExtensionAttack("extension", registers, specificLength)

        print i, forged, payloadSHA, specificLength

        if forged == payloadSHA:
            print i, len(key)
            assert len(key) == i

            print "[*] Length of key is {}".format(i)
            break

When I run it with a key length of 49 I end up getting a success with a length of 43, which doesn't make much sense. Then, I get the same hash for lengths 43 to 107...

I'll be very grateful if anyone explains to me what's wrong with this approach, thank you!

Answer 1

Yes, the length extension is identical for key sizes that are a multiple of 64 as SHA-1 has an input block size of 512 bits. So you would have to generate the exact same padding for the same message in that case. However, commonly this includes the encoding of the length of the input message of the hash in bits.

The output of a number of blocks of SHA-1 cannot be distinguished from random if the input is sufficiently randomized. This is definitely true if a fully randomized key is used at the start of the hash. So you cannot get any information out of it. This is also true for any MD5, SHA-2 or any other Merkle-Damgård hash without any pre/post-processing to avoid it.

The fact that you can test your attack successfully while the sizes are unknown in advance must therefore mean that you have some kind of oracle to test against. And this oracle simply returns success if you guessed the total message input size correctly, which is the addition of the key size and message size of the keyed hash.

For most protocols you'd know the key size, or consider it known due to the Kerckhoff principle. This is just a configuration parameter after all, it is not part of the security delivered by the key. However, that doesn't mean that you can calculate it from just the output of the hash function.