8
$\begingroup$

Consider the following code snippet:

<?php
session_start();
if (md5($_POST['password']) === '550b1f8802ca3d7a987fc46a2af408c3') {
         $_SESSION['loggedIn'] = true;
}
header("Location: /");
exit;

If an attacker doesn't know the hash, they should still be able to leak bits of the hash via timing information (and by knowing the hashing strategy employed).

If you send thousands of requests and study the MD5 hash you transmit (as well as the timing information) of various passwords, you should be able to deduce the first N hexits of the hash. Then, using a client-side brute force search against this known information, optimize your online guessing by discarding a large number of guesses.

Even deducing the first 4 bytes can cut your guess time down by a factor of a billion.

That said, has anyone published any research in this area? Specifically, exploiting a partial leak via timing information and using it to guess passwords against unknown hashes faster.

Would this be worth researching at all?

$\endgroup$
  • $\begingroup$ It's a known vulnerability. What's more to be said? The solution is to use a password hash (PBKDF) instead and verify it using a timing attack resistant approach, e.g. password_verify which has the following description: "Verify a password against a hash using a timing attack resistant approach" $\endgroup$ – Maarten Bodewes May 12 '15 at 19:55
  • $\begingroup$ Of course. I know the right answer, I'm just interested in PoCing the wrong ones (if for no other reason than to motivate people to stop adopting them). $\endgroup$ – Scott Arciszewski May 12 '15 at 20:02
  • $\begingroup$ There's no timing attack on MD5 as used here because there is no secret to extract. You have provided the password parameter, you know exactly what the internal state of the hash will be through the entire invocation. If you were trying to extract a salt, then maybe you could contemplate a timing attack. @fgrieu is correct about the comparison being vulnerable. $\endgroup$ – bmm6o May 15 '15 at 15:26
  • $\begingroup$ I worded the title incorrectly; the timing attack is on the MD5 comparison not the hash function. $\endgroup$ – Scott Arciszewski May 15 '15 at 15:27
  • $\begingroup$ @MaartenBodewes The Php Link you provided has changed the text into This function is safe against timing attacks. You have the power of update :). $\endgroup$ – kelalaka May 9 at 8:27
14
$\begingroup$

There is no timing attack possible on MD5 as practically implemented on most platforms. That's because MD5 uses only 32-bit addition, 32-bit bitwise boolean operators, and constant rotations/shifts, which exhibit no data-dependent timing for any reasonable implementation, even written without consideration for resistance to timing attacks.

There is however a conceivable timing attack, unrelated to MD5, on the code shown (which is PHP, but that holds in many other languages, with minor variants), aiming at finding the first few characters of the hash value if that's unknown (the equivalent of the constant 550b1f8802ca3d7a987fc46a2af408c3 in the code sample). Assuming the string comparison of === is performed from left to right, character by character, and stopping on the first non-matching character, there can be a timing attack on the string comparison: if on average the password test1 (hashing to 5a1…) is rejected significantly slower than test0 (hashing to f6f…) and test2 (hashing to ad0…), then the true hash of the password can safely be assumed to starts in 5. We can then find and time the rejection of other test passwords which hash starts in 5 (like test8 hashing to 5e4…) to try find the second character of the hash; and so on. In this way we need to perform (significant) timing measurements for at most 32×16 well-chosen test passwords in order to find the whole hash.

That's fine in theory. In practice the attacker trying this will face at least two hurdles:

  • The difference in timing is very small, and a variety of things will conspire to mask it: network delays, other tasks and how they left the various CPU caches, numerous clocks on the hardware..; in order to make any progress, the attacker will need an awful lot of measurements, a direct network connection, a low-load server, and a sound strategy (like considering the average of observed times for a given test password after some setup-dependent filtering, perhaps keeping the few lowest measurements if all the accidental masking factors are additive).
  • Finding the leftmost $n$ characters of the hash requires about $2^{4n}$ evaluations of MD5 in order to find the test passwords to be timed; with $2^{60}$ evaluations (which is already requiring serious effort), the attacker only gets 12 characters (60 bits) out of 32 (128 bits).

If the first of these two hurdles can be overcome, the method has a benefit: the attacker can explore test passwords according to a synthesized list of candidate passwords approximately by decreasing likelihood, so that a low-entropy password will be found with (hopefully) fewer online queries to the server than without the timing attack; and no more offline hashes than required for a brute force attack with the hash known, even though the attack is performed without the hash.

I would be slightly surprised if that was a real threat for any server accessed through a few network hops; and I'm unsure this is worth academic publication in a first-tier conference or journal.

$\endgroup$
  • 1
    $\begingroup$ I'm no academic, I was thinking more Phrack / PoC||GTFO (because it would be just for fun) than, say, IEEE. $\endgroup$ – Scott Arciszewski May 15 '15 at 10:22
1
$\begingroup$

So first we'll assume the end-game is to perform a dictionary attack on the not-yet-known hash. In that case you also have a dictionary.

First, store the dictionary it's md5 hashes in a database, with a sort index on the md5 hashes.

Now, for each character of the hash:

  1. Select an md5 hash starting with what you know so far plus 1 extra character for each possible next-character (16 max)
  2. Use timing signal to figure out which extra hash character matches
    • If no signal, you don't have the hash in your dictionary
    • You may also have guessed correctly, in which case you win!
  3. GOTO 1
$\endgroup$
1
$\begingroup$

Your questions are 1) is there any research in this area? and 2) is this worth researching? which are still mostly unanswered. Even though there is an accepted answer, i'll take a shot at answering your questions.

1) Yes, there is a lot of research in this area. Here are the talks I'd recommend:

I'm sure you can find plenty of others via Google or YouTube.

2) String comparison timing attacks are well known but poorly explored, so there is plenty of room for more research in my opinion. There are probably countless vectors to take this to make it amazing research. As an example, here are some topics off of the top of my head that could be explored to make very interesting research:

  • Timing attacks in embedded devices.
  • Timing attacks in IoT devices
  • Timing attacks in routers.
  • Timing attacks against wifi encryption (not sure if there is a vector for this).
  • Timing attacks against systems on the LAN.
  • Exploiting timing attacks remotely by using using SSRF locally (not sure if there is a vector to make this possible).

A talk was just accepted yesterday at BlackHat USA 2015 on timing attacks, so it's interesting to hear that a first-tier conference would not be interested in research on timing attacks.

$\endgroup$
  • $\begingroup$ Depends on the focus of the conference. If the intent is to protect against such an attack, it isn't very interesting. It's a timing attack, methods of doing them are known, ways of mitigating them are known and easy to do (and sometimes faster than a naive approach), so it isn't a very interesting theoretical problem. $\endgroup$ – Steve Peltz May 30 '15 at 23:25
  • $\begingroup$ Well. I was more thinking, "Can I write a compelling PoC for several projects that use MD5 for password auth?" and then it morphed into, "Should I instead try to write a paper about it?" That's why I asked. I don't think there's anything novel, new, or revolutionary here. Most crypto people seem to accept this as a fact and encourage the simple mitigations. It's convincing project authors that it's a real risk that's the challenge. $\endgroup$ – Scott Arciszewski May 30 '15 at 23:28
  • $\begingroup$ The real risk is in doing crypto in a scripting language that returns a hash as a hex character string. If you cared about security, you'd do word comparisons, and probably by doing an OR of the XOR of n 32-bit or 64-bit words. Producing a PoC isn't going to convince anyone who hasn't already been convinced. $\endgroup$ – Steve Peltz May 31 '15 at 8:48

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.