49
$\begingroup$

How would timing attack occur on a particular code but not in another code (because of good coding practice)? Could anyone give an example? I am having trouble figuring out how timing attacks would occur based on the way the code is written.

$\endgroup$
  • $\begingroup$ I wrote an answer relating to this question here: crypto.stackexchange.com/a/40285/12962, though Biv's is somewhat more thorough than mine. $\endgroup$ – ymbirtt Nov 22 '16 at 9:52
  • $\begingroup$ If you are worried you can always stick a call to sleep(rand()) :) $\endgroup$ – mcfedr Nov 22 '16 at 15:14
  • 3
    $\begingroup$ @mcfedr that won't really help - statistical analysis can eliminate the variance from there given a large enough sample size, since random numbers are distributed relatively evenly. If your libc has an uneven distribution of random numbers, then a potential attacker could actively test against it with specifically chosen data to identify the distribution of your "random numbers" and then take that into account when executing their timing attack. TL;DR: DON'T EVEN THINK FOR A MOMENT THAT THAT WILL HELP YOU MAKE TIMING VULNERABLE CRYPTO OKAY! $\endgroup$ – haneefmubarak Nov 22 '16 at 18:13
76
$\begingroup$

TL;DR at the bottom.

The general ideas of timing attacks are the following:

  • Secret data has influence on timing of software
  • Attacker measures timing
  • Attacker computes influence$^{-1}$ to obtain secret data

A Basic weakness: if( secret )

The base of an exploitable code sensitive to a timing attack looks like this:

if(secret)
{
  do_A();
}
else
{
  do_B();
}

The idea is that the time to compute A is different to the time to compute B. Thus knowing this difference, you can compute back the secret.

Let us have a look at the following code which is closer to a real world code. This is the core operation in RSA decryption: $a^d \bmod n$ with secret key $d$:

typedef unsigned long long uint64;
typedef uint32_t uint32;

/* This really wants to be done with long integers */
uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      if((exp[i] >> j) & 1)
        r = ((uint64)a*r) % mod;
    }
  }
  return r;
}

In this code you can see that you have a if section which depend on the secret (exp[i] >> j) & 1. If the value of the secret is 1 then you will execute r = ((uint64)a*r) % mod. If the value of the secret is 0 you will execute nothing. Thus you have a difference in the time of the execution depending on the secret.

Let us improve this code a bit:

typedef unsigned long long uint64;
typedef uint32_t uint32;

/* This really wants to be done with long integers */
uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1, t;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      if((exp[i] >> j) & 1)
        r = ((uint64)a*r) % mod;
      else
        t = ((uint64)a*r) % mod;
    }
  }
  return r;
}

In this code you can think that because we do the same thing on both branch of the if statement that depend on the secret (exp[i] >> j) & 1:

  • 1 assignment.
  • 1 multiplication
  • 1 modulo operation

The time to execute either branch will be the same, Right ?






Well... No. Because... t is a dead variable and the compiler will certainly notice it and will optimize the code. "This variable is useless, get rid of it!". The compiled code will therefore be the same as the one from before where you had your timing vulnerability.

But even if we force the compiler to not optimize the code, it is still not constant time :

  • modern CPUs have branch prediction.
  • and instruction cache.

Therefore we need to get rid of this branching weakness.

Removing the branches

How do we remove the branching of something like this:

if (s)
  r = do_A()
else
  r = do_B()

We replace it by something like this:

r = s * do_A() + (1 - s) * do_B()

Because we want fast code, we can expand s to all-one/all-zero mask and use XOR instead of addition, AND instead of multiplication.

So moving back to our Square-and-multiply:

uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1,t;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      t = ((uint64)a*r) % mod;
      cmov(&r, &t, (exp[i] >> j) & 1);
    }
  }
  return r;
}

where cmov (as conditionnal move) is an assembler instruction of same name (which doesn't use any prediction) or is defined as the following:

/* decision bit b has to be either 0 or 1 */
void cmov(uint32 *r, const uint32 *a, uint32 b)
{
  uint32 t;
  b = -b; /* Now b is either 0 or 0xffffffff */
  t = (*r ^ *a) & b;
  *r ^= t;
}

Another weakness: table[secret]

The idea is the following, the cache of your processor contains your table. And because everything in the cache is accessible within the same timeframe your secret is safe.

address  | content
------------------
0x0001   |    8
0x0002   |    7
0x0003   |    6
0x0004   |    5
0x0005   |    4
0x0006   |    3
0x0007   |    2
0x0008   |    1

That is true... if you only have this code running. However you always have other code running at the same time on your CPU, therefore some parts of your table will be as following:

address  | content
------------------
0x0001   |    8
0x0002   |   XXX
0x0003   |   XXX
0x0004   |    5
0x0005   |   XXX
0x0006   |    3
0x0007   |    2
0x0008   |    1

And we assume that the attacker has control over which part of the cache is corrupted. Therefore if secret is 0x0001 then you will have an immediate response from the cache. However, if the secret is 0x0002, the cache is invalid. Therefore the CPU will have to reload the value from the stack / memory. This takes a longer time, because we have a timing difference... We have a possible timing attack.

The counter measures are quite complex and I won't elaborate on them.

References

A big part of this answer is from this slides: Timing Attacks and Countermeasures by Peter Schwabe at the Crypto Summer School 2016 - Croatia.

Some interesting readings:

Osvik, Shamir, Tromer, 2006: Cache Attacks and Countermeasures: the Case of AES. http://eprint.iacr.org/2005/271/

AlFardan, Paterson, 2013: Lucky Thirteen: Breaking the TLS and DTLS Record Protocols. http://www.isg.rhul.ac.uk/tls/Lucky13.html

Yarom, Falkner, 2014: FLUSH + RELOAD: a High Resolution, Low Noise, L3 Cache Side-Channel Attack. http://eprint.iacr.org/2013/448/

Benger, van de Pol, Smart, Yarom, 2014: “Ooh Aah... Just a Little Bit”: A small amount of side channel can go a long way. http://eprint.iacr.org/2014/161/

Bernstein, 2005: Cache-timing attacks on AES. http://cr.yp.to/papers.html#cachetiming

Brickell, 2011: Technologies to Improve Platform Security. http://www.chesworkshop.org/ches2011/presentations/Invited%201/CHES2011_Invited_1.pdf

Bernstein, Schwabe, 2013: A word of warning. https://cryptojedi.org/peter/data/chesrump-20130822.pdf https://cryptojedi.org/peter/data/cacheline.tar.bz2

Yarom, Genkin, Heninger, 2016: CacheBleed: A Timing Attack on OpenSSL Constant Time RSA https://ssrg.nicta.com.au/projects/TS/cachebleed/

Hamburg, 2009: Accelerating AES with Vector Permute Instructions. http://mikehamburg.com/papers/vector_aes/vector_aes.pdf

Biham, 1997: “A Fast New DES Implementation in Software.” http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1997/CS/CS0891

TL;DR

If you read this and skipped the whole answer, then it means that you definitively don't want to write crypto code.

If you did read the whole answer, then you probably understood why it is a bad idea to write crypto code by yourself given how many ways you can screw up.

$\endgroup$
  • 25
    $\begingroup$ dat cheeky little tl;dr plot twist at the end tho! $\endgroup$ – Tasos Papastylianou Nov 21 '16 at 14:31
  • 3
    $\begingroup$ Every time you have a branch (and people tend to not realize just how often you have branches), there's a jump, and it's almost always conditional. Jumps are bad enough, but conditional branches are deadly. With CPUs of ye olde days, they would merely cause a pipeline flush; with modern CPUs, they might, if the CPU mispredicts whether the branch will fall through or not. Either way, literally any branch leaks information, even if everything else is constant-time right down to the assembly. And don't be fooled by absence of if, for, while and friends; yes, ?: is potentially a branch! $\endgroup$ – a CVn Nov 21 '16 at 17:25
14
$\begingroup$

The following example is difficult to exploit in real life, and impossible over a network, but it is simple enough to understand and extrapolate from.

Consider a piece of code on a server that checks a MAC for correctness.

int compare_mac(unsigned char *mac1, unsigned char *mac2, size_t n)
{
    for (; n--; mac1++, mac2++) {
        if (*mac1 != *mac2) {
            return *mac1 - *mac2;
    }
    return 0;
}

If the MACs do not match, the function exits early. In other words, two MACs differing at the first byte will return almost immediately, while MACs differing only at one of the last bytes will need more time to compare.

Now suppose a malicious user tries to send a message without knowing the secret key. Suppose he can also time very accurately, enough to distinguish between a couple of instructions. He can simply send random MACs and time the response, and figure out each byte of the MAC with maximally 256 guesses per byte. He guesses the first byte first, then the second, etc.

In other words, he will need maximally $256n$ calls to the server to forge a MAC.

If the above coding did not have an early return, and was constant time for all inputs of length $n$, then the attacker will need $256^n$ calls to the server to forge the MAC.

Obviously, this is a huge difference.

In practice, you probably won't be able to distinguish between a few instructions, especially over a network. However, other timing leaks may be much larger, and you can get very far with the application of some basic statistical analysis.

$\endgroup$
  • 4
    $\begingroup$ IIRC there was a bug in Windows 95's SMB file sharing support that allowed a variation on this attack against share passwords, but based on password length instead of timing. It was something like, if you sent a $n$ character password, then only the first $n$ characters of the share password were checked, regardless of the length of the share password, and a success/failure result was returned to the client based on the correctness of those $n$ characters. Oops. :-) $\endgroup$ – a CVn Nov 21 '16 at 17:31
  • $\begingroup$ FWIW, I am not able to reproduce this attack when the MAC checking is done in PHP with a simple string equation (if ("something" == $_POST["field"])). Even doing 5000 attempts and taking the fastest one (and how often this fastest time was hit), or the fastest 10%, or the fastest 30% minus the fastest 10%... none give me a reliable answer when trying in blocks of two or three characters, e.g. submitting aa vs. bb when the secret is aaaa. Sometimes aa (the correct one) is faster, sometimes bb is faster. $\endgroup$ – Luc Feb 24 '17 at 19:19
  • $\begingroup$ @Luc That's not surprising, it was more of a theoretical example. Distinguishing between the timing of aa and bb is essentially trying to time a handful of instructions, which will execute in the order of a few nanoseconds. Also, maybe the PHP string comparison function checks for length equality first? $\endgroup$ – bkjvbx Feb 25 '17 at 14:37
  • $\begingroup$ @bkjvbx Maybe, I don't know. It was quicker to cook up a POC than to dig through the source code I thought. The reason I'm looking into this is because I always try to do constant-time comparison when checking passwords in PHP, but I was wondering how vulnerable it really is and whether it's robust enough to would work over the internet (given jitter in the connection). Well, either it's not vulnerable at all (length check) or even on localhost there is too much jitter. $\endgroup$ – Luc Feb 25 '17 at 15:33
  • $\begingroup$ This attack should never apply to passwords, since passwords should be hashed by a strong and slow password hashing function server side. This means that even if the attacker is aware of the hash of the password, he would need to perform a preimage attack to find a password that matches. Either you are doing something horribly wrong in your password verification, or you've (hopefully) misunderstood the way that this attack works :) $\endgroup$ – bkjvbx Feb 25 '17 at 17:01

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.