MD5 hash: retrieve an element of a source string

Question

Suppose you have a string, precisely an MD5 hash string, which basically it is computed in the following way:

"element1:element2:element3"

So, in order to get the hash (MD5 hash) you can issue the command:

echo -en "element1:element2:element3" | md5sum

MD5_hash_output

Given that MD5 is a one-way function (it is now considered broken, no more secure...etc), think that you want to retrieve element3 and you know:

• element1
• element2
• MD5_hash_output

Is my reasoning correct if I say:

1. you can get element3 if there's a rainbow table which includes MD5_hash_output

2. you can get element3 if it is guessable (easy to guess: a default device password ...for instance)

It may sound a trivial question...the answer is, of course, that MD5 is a one-way cryptographic function..but I just wanted to have some other different opinions

Answer 1

TL;DR; The success depends on the size of the element3.

---

The MD5 pre-image resistance theoretically is broken bu not practically. Instead of the generic preimage attack with $\mathcal{O}(2^{128})$ complexity, there is an attack by;

• Sasaki and Aoki: Finding Preimages in Full MD5 Faster Than Exhaustive Search, EUROCRYPT 2009.

This attack requires $2^{123.4}$-time complexity and requires $2^{45}\times 11$-words of memory. If we combine them the direct brute force is still faster. Even if we only consider the time complexity of the attack, MD5 is not practically broken. You cannot reach the 123-bit search space in a meaningful time. Consider the collective power of BitCoin miners; in 2020/1/17 they reached 126.1314 Exahashes per second, that makes

• $2^{67}$ SHA256 double hashes in a second, and
• $2^{92}$ SHA256 double hashes in a year. So you need $2^{21}$ years with that power.

Apart from the above; we don't expect special data would make the pre-image attacks easier.

---

The below is totally depending on the size of the element3

1. you can get element3 if there's a rainbow table which includes MD5_hash_output

Actually, using only once, a rainbow table is not necessary. You can build one with a special reduction functions; like $$R(md5(previous)) := \texttt{element1:element2:} \mathbin\| md5(previous)|_{target\;length}$$

The size of the table depends on your target length. It may not be possible to build one after $2^{63}$ (not an exact number) due to the memory requirements to process.

Instead of building the Rainbow Table, if it is only used once, just search the all possible space. As seen above, there is a limit on the search space that one can achieve in a meaningful time. If you somehow agree with all the Bitcoin Miners (though some of the use of special hardware that cannot be changed), you can search the 8-byte space less than a second. If not, maybe one can use the Summit Supercomputer to reach $\approx 2^{63}$ in a day and $\approx 2^{73}$ in a year (those are calculated on SHA-1 capabilities). Therefore 12-byte is far far away.

2. you can get element3 if it is guessable (easy to guess: a default device password ...for instance)

If you have the collection like the commons password, knowledge about the target, etc. you can easily check them with some script.