Find $ secret in $ a == md5 ($ b. $ Secret)

Question

Function:

$a == md5($b . $secret); 

• You can choose $ a and $ b
• You don't know $ secret
• You get the function value for $ a and $ b, which you select as true or false.

Is there a better attack than brute force to find the secret as a whole? Is there a more effective attack than brute force to find $ secret using the PHP md5 function ?

From what I found on the Internet, I think not, although md5 is deprecated for some other use cases. Therefore, to be sure ...

Yours faithfully

Answer 1

If MD5 behaves like a random oracle (this is a big “if”, see below), then an exhaustive search on $secret is the best possible attack - and, more importantly, each “guess” on the value of $secret MUST use a function request ( since you are using PHP, I assume that the function is implemented on a web server, and each "request" requires communication with this server). The latter is explained by the lack of information sent to the attacker: the attacker receives nothing but one bit (the result is " True " or " False "). In particular, he himself does not get the MD5 output. An attacker will receive a long stream of uninformative " False " results, unless he chooses the correct MD5 result, either from a pure chance (probability 2 ^-128 that Darn Small really is), or because he guessed in advance about the value of $secret . It is worth noting that this prevents the attacker from using many cost-sharing methods, including pre-computed tables, in particular, over-inflated rainbow tables .

A random oracle is a mythical object that can be thought of as a deterministic black box: you don't know anything about the output you get from a given input, except that the field will always return the same result for the given input. The model is this: the field contains a gnome, some bones and a large book. A dwarf uses bones to randomly select a result. He also uses the book to track responses that he has already submitted to be consistent, i.e. If the input is identical to the previously presented input, gnome will return the same result as before, instead of throwing the dice.

MD5, however, is not a random oracle. For example, we can build collisions for MD5 much faster than theoretical resistance 2 ⁶⁴ for a function with 128-bit output. Also, note that a good hash function (collision resistant, etc.) does not require absolutely “random oracle”. For example, SHA-256 is considered a safe hash function, while it still suffers from the so-called “extension extension attack” (given SHA256($a) , SHA256($a . $b) can be calculated without knowing $a , for almost arbitrary values ​​of $b ). Thus, the guarantees of an accidental oracle are not related to MD5 (or, for that matter, SHA-256). This does not mean that faster attacks are known! Just that you yourself are here.

You can also indicate that md5($b . $secret) is a kind of "key hash", i.e. MAC (message authentication code). Creating a MAC from a hash function is not easy, precisely because of things like a length extension attack ( md5($secret . $b) , for example, will be a very weak MAC). A robust way has been developed to build a MAC from a hash function; it is called HMAC and includes two calls to the underlying hash function (but one of them is on a short input, so it is nonetheless efficient). HMAC security, more precisely, how HMAC can be considered a random oracle, can be "proved", that is, reduced to some internal properties of the hash function, which are considered true in the case of SHA-256 (see New evidence for NMAC and HMAC: security without Mihir Bellar collision resistance for details). Using HMAC / SHA-256 on top of $b , with the $secret key, you will benefit from these security results and your design will be more convincingly reliable. Again, I am not saying that there is a well-known attack on md5($b . $secret) , only that using MD5 and the home MAC design raises red flags that reduce the level of trust that can be transferred to such a system.

Answer 2

This is an interesting question, because in typical scenarios in IT-Security you cannot select $a and $b as an attacker. For example, if you can get a hashed password, $a and $b already defined, and you need to work with it. In this case, you can use only brute force or a rainbow table if there is salt $b .

In your example, on the other hand, you can select both values. You can take an arbitrary secret, for example. test and accordingly select values ​​for $a and $b . I select $ b for an empty string and compute $a with $a = md5($secret) , which leads to 098f6bcd4621d373cade4e832627b4f6 .

I select $a = "098f6bcd4621d373cade4e832627b4f6" and $b= "" and ask if there is $secret == "test" . You are telling the truth, and I am saying that the problem is solved.

This finally leads us to a real answer. Two conditions specified

• You can choose $ a and $ b
• You don't know $ secret

don't work together. In my example, I myself defined $secret . I violated the second condition. On the other hand, I cannot select $a and $b arbitrarily without calling them from $secret , because they may not have a solution.

Assuming that there is at least one solution for all possible pairs of $a and $b (maybe there is evidence for this, I don’t know), and you choose them in such a way that you really don’t know $secret , I would always like to define $b = "" to make the attack as simple as possible. Rainbow tables are your friends in this case.

Answer 3

download a rainbow table / hash password with a known password! :)