Decrypt email address hashed using specified hashi

问题:

So I am trying to solve this problem. I am supposed to obtain the email address hashed by the hash function.

The secret email address is hashed below:

092b41aa59dacb2124f5a04464bcd13297f6a09d69e6eabf1be7bef3ef86402d1b023677b38763b3cfae5c3ba71ba6cfe38526cf77e267373be8be893b1939af897c87302750d35f175f9664896ff78d9969ce2a72c3f1b5c439b7a952c557c2097332ecc01f50b12593826ba0872d24cd3c21dca4e1859a97ca4394b2544ef53df1f35cbb68b6a1e526df4e669920ba18c5c845aaee2f9d5b0b2c72b15d2296f0a42e4e37042713855c4cb84ca738bcbc151c84fe6448fca60efb64393c8b974d6ae3ab53c0cecdb11fc8a0e0e8864218ba49cb972bd76759290caf3a1851ca30cfbc46ff3137b342a28a159d9a483576e1ed3840f2d287b8cf74fafe2269cf7716d553f11eccce6fcd1b9e411789d989d97a2d95b4ac0aa6e92b512b923fa13e85ce24a5ee8527656b43a4f9b3817c9f67aa18966d70bc10e07ca19dd0cf6af5ca15876ee1d21d3afc8ba1524c6239a77184c0a84557c672230a38f41c8a1166425785a37cc2ac841d32c5558b38cd5c38c53551c5002815c71a4c4c4420fb945dc02cbb80e1c99b6b73c3d03318af914a26f7b760c299e3748f930febb97d7f8333ba0c29732ebdbe7ef9a181d7747986a7b6040a6b1165084a477f14643b

First, we generated a series of string prefixes with lengths increasing by 2. For example, if our secret email address was [e-mail], we would generate:
he
hell
hellow
hellowor
... [e-mail]

Then, for every prefix s, we computed the following hash J: md5(md5(e) + s + md5(s)) [where + is the string concatenation operator and e is your email address]. Finally, we concatenated all hash strings J to form the long hash above!

For example, for [e-mail], we would compute:

md5(md5('[e-mail]') + 'he' + md5('he')) +
md5(md5('[e-mail]') + 'hell' + md5('hell')) +
md5(md5('[e-mail]') + 'hellow' + md5('hellow')) +
...

For the sake of simplicity, you can assume that our email address only contains alphanumeric characters and these 4 characters: _.@+

I am not familiar with this kind of problem. If you could give me a rough idea of what I am supposed to do (a game plan), that would be of great help. It is safe to assume that I do not know much about hashing (or the related data structures). This problem would be a great opportunity for me to learn these things.

回答1:

as long as e is known, you can quite easily forge a collision, that is likely to be the original ...

md5 has a 128 bit output ... so devide your long string there into seperate md5 hex strings

now if e is known, all you need to guess for the first hash are 2 characters ... exhaustive search will be a total of [a-z0-9_.@+]^2 = 40^2 = 1600 possible candidates ...

once you have a collision, you "know" the first 2 chars of the secret ...

for the next hash, all you have to guess are the next 2 chars of s since the first two are already known from step 1 ...

repeat for all hashes in order of appearance in your large string J ... since you only have to guess 2 chars per hash and can reuse information from the found collision of the previous hash, this is fairly easy ...

in terms of complexity, the md5 hash of e needs to be calculated only once, and you have 2 concatinations and 2 md5 calculations per guess ... per hash you have an exaustive search candidate pool of 1600 so as and average you can say that you will need 800 guesses per hash in J

keep in mind that this is no decrytion ... it is still a search for a collision ... but most likely it will be the original data, since md5 will most likely (one could almost be tempted to say certainly) be collision free for the possible inputs ...