When efficient code fails: Timing Attacks

Efficient code is normally what professional software engineers strive for, but sometimes it could make us vulnerable to timing attacks.

So you might be wondering, that's a very bold statement to make Tariq. After all, we learnt all of this computer science theory in order to make the machine bend to our will while using the least amount of CPU cycles, stack and heap usage.

And you would be very correct, however in some scenarios, particularly in the context of authentication, we have to ensure that we aren't making some of our branching logic faster than others.

Warming up your intuition

Remember when you were a kid or maybe you still are, who cares... and you were playing a game where you have to guess something your friend told you. They would only give you a clue whether your guess is warmer or colder and finally with enough time, you were able to narrow in on what they had in mind.

Keep this in the back of your mind as you keep on reading.

Huh, what does that even mean. Why would the timing of different branches even be relevant? And a Guessing game...

To a reasonably sophisticated hacker, the differences in how long something takes relative to an alternative path reveals very valuable information. This is the essence of a Timing attack.

Here's a very simple but practical example in which I will use for explaining timing attacks. I'll write it in Typescript since I assume most developers are exposed to the C-family of languages and Javascript powers the web (TypeScript is basically just a superset of Javascript with types)

Say for instance we were implementing a trivial function to do byte pair comparison of the hashes of a user submitted password, to an existing hash stored in our database representing the users password.


const isTheUserPasswordValid = (
    userSubmittedHash: Uint8Array, hashInDB: Uint8Array
    ): boolean => {
    if (userSubmittedHash.length !== hashInDB.length) {
        return false;
    }
    for (let i = 0; i < userSubmittedHash.length; i++) {
        if (userSubmittedHash[i] !== hashInDB[i]) {
            return false;
        }
    }
    return true;
};

This is efficient, as we are doing byte by byte comparison, we would early return as soon as we encounter a byte that doesn't match. In fact, this was exactly how java.security.MessageDigest in Java 6.0 update 15 as pointed out Coda Hale (see link in sources) did it.

/**
  * Compares two digests for equality. Does a simple byte compare.
  *
  * @param digesta one of the digests to compare.
  *
  * @param digestb the other digest to compare.
  *
  * @return true if the digests are equal, false otherwise.
  */
public static boolean isEqual(byte digesta[], byte digestb[]) {
    if (digesta.length != digestb.length)
        return false;

    for (int i = 0; i < digesta.length; i++) {
        if (digesta[i] != digestb[i]) {
            return false;
        }
    }
    return true;
}

The problem lies in the information that a adversary gets in the case of an early return. Say each iteration of the for loop takes 1s on your machine (it doesn't, but humor me for the sake of easy arithmetic) then for every byte that the hacker got closer to the original hash, it would take 1s longer. Now you see what I'm getting at... as the adversary keeps generating bytes whether randomly or with the help of a rainbow table, they gain valuable feedback on whether their guess is getting hotter.

(I felt pretty good coming up with this parallel describing a kid's guessing game and what a sophisticated hacker would do. If you like this sort of parallelism, let me know and I will rack my brain to come up with some whenever I write future articles)

Anyways back to our hacker, you might be thinking, well 1s isn't how long it takes...it is an order of at least 10000 times faster. Combined with the fluctuations over a network... how can anyone possibly determine any useful information?

Oh but they can thanks to taking thousands of measurements and using statistics. From Crosby et al.:

"even though the Internet induces significant timing jitter, we can reliably distinguish remote timing differences as low as 20µs. A LAN environment has lower timing jitter, allowing us to reliably distinguish remote timing differences as small as 100ns (possibly even smaller). These precise timing differences can be distinguished with only hundreds or possibly thousands of measurements."

So what can we do to prevent this? Crosby et al.'s paper shines again:

"We also observed, generally, that the round trip time or network hop count did not significantly contribute to the network jitter, and thus network distance may not confer immunity to remote timing attacks. We found that the choice CPU or networking card may introduce more jitter than a local area network. Prospective attackers can work around this by benchmarking their measurement machines, in advance. If an attacker can accurately perform timing measurements, then a number of cryptographic or algorithmic weaknesses in a server might leak critical information to the attacker. As a consequence, we recommend that the algorithms used inside web and other Internet servers that process important secrets be carefully audited and, where necessary, be modified to limit observable differences in execution times to at most a few microseconds."

Essentially using the example I came up with above, we could simply do this to make a timing attack even harder:


const saferIsTheUserPasswordValid = (
  userSubmittedHash: Uint8Array,
  hashInDB: Uint8Array
): boolean => {
  // 0 means unknown, -1 means invalid, 1 means valid.
  // I use a number instead of a boolean to hold 3 states
  let validityInNumericForm = 0;
  for (let i = 0; i < hashInDB.length; i++) {
    // note in javascript the return type
    // of accessing an out of bounds array is undefined
    // this works great in this example as it will always
    // loop through the length of hashInDB
    // regardless of the user's input.
    if (hashInDB[i] !== userSubmittedHash[i]) {
      validityInNumericForm = -1;
    }
  }
  if (validityInNumericForm < 1) {
    return false;
  } else {
    return true;
  }
};

However for actual production use I'd recommend using Node's crypto.timingSafeEqual docs for a thoroughly tested way.

BTW for curious readers, you can find the testcases that Node uses for crypto.timingSafeEqual right here to give you an idea of how to test your implementation

Also the underlying implementation is written in C++ and can be found here There's a lot of code for error handling however the meat of what does the comparison is this:


return CRYPTO_memcmp(buf1.data(), buf2.data(), buf1.size()) == 0;

which just calls an OpenSSL function which you can find further information here

I highly encourage you to check out the sources below for more in depth coverage of how they measured this (Crosby et al. paper, only 29pages) and for a slightly different perspective and for actually discovering the java bug, check out Coda's article.

Sources:

Disclaimer: None of this post was written by AI.

I blog for a couple reasons:

Because it's a great way to learn as part of the Feynman technique (Named after a physicist that I admire)
It helps me refine my thinking as the thoughts in my head are less concrete. Writing imposes form upon them.
While I think AI is pretty darn cool and will be writing articles about it, especially the math and architectures behind it, I want to improve my writing skills. I don't think I am a terrible writer, but I do think that there's room for mastery.