1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What is the max length of element3? $\endgroup$
    – kelalaka
    Mar 1 '20 at 17:33
  • $\begingroup$ well actually ...it could be anything (I suppose 8 characters)..does that make any difference? ...are you thinking about a brute-force attack? $\endgroup$
    – terence
    Mar 1 '20 at 17:40
  • $\begingroup$ On 1: the rainbow table would have to have been prepared with knowledge of element1 and element2; any other one is useless. $\endgroup$
    – fgrieu
    Jul 5 at 7:00
2
$\begingroup$

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;

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.

  1. 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.

$\endgroup$
1
  • 1
    $\begingroup$ thanks @kelalaka ..as I expected it's quite hard ... $\endgroup$
    – terence
    Mar 1 '20 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.