Skip to content
This repository

Timing Attack Vulnerability #560

Open
K4lium opened this Issue June 19, 2012 · 27 comments

5 participants

Jeremy Wagner-Kaiser Salvatore Sanfilippo Jon Frisby Josiah Carlson Dmitry Chestnykh
Jeremy Wagner-Kaiser
K4lium commented June 19, 2012
void authCommand(redisClient *c) {
    if (!server.requirepass) {
        addReplyError(c,"Client sent AUTH, but no password is set");
    } else if (!strcmp(c->argv[1]->ptr, server.requirepass)) {
      c->authenticated = 1;
      addReply(c,shared.ok);
    } else {
      c->authenticated = 0;
      addReplyError(c,"invalid password");
    }
}

This authentication is vulnerable to a timing attack through strcmp.

The correct behavior here would be a constant-time comparison between the stored password and the user-supplied password or is strictly proportional to the length of the input string.

Salvatore Sanfilippo
Owner

Thanks for reporting this. Probably not exploitable as with a modern server we are in the orders of a few nanoseconds that's too little even with a LAN to distinguish from noise (at least this is what I found reported in existing literature, using 1000 samples, but it's not clear how the attack can be improved with multiple samples). But still worth fixing.

I tried an attack using Redis pipelining without results as well, in local host, without success. This is probably one of the best attacks possible and I did it using 1 million samples, but without using any special filtering, just means.
Probably plotting distribution of time taken is more interesting and may spot some difference in the curve that is not noticeable with just the mean.

This will be fixed before 2.6 final, probably also back ported into Redis 2.4.

Jon Frisby
MrJoy commented June 20, 2012

We're planning on filing a report on the Full Disclosure list, but would prefer to do so after you've got a patch in place. Can you provide an ETA on that? Our preferred timeframe for disclosure would be about 1 week from now.

Josiah Carlson

Have you actually been able to exploit this in the wild, mrjoy?

Jon Frisby
MrJoy commented June 20, 2012

No, but the relevant research (circa 2008, IIRC) shows an ability to isolate timing differences of 100ns over incredibly noisy environments (network). I.E. it's highly probably that with proper statistical techniques that this is exploitable.

For our use-case, we don't treat Redis as trustworthy (I.E. we don't trust what goes in or what comes out), so it's somewhat less of a direct concern for us, but we (K4lium and I) feel an ethical duty to ensure that people have the relevant information they need to defend themselves against possible attacks, even without a known live exploit. That includes having an accurate picture of the security model involved, so they can make more informed decisions about how they handle accessibility of Redis.

Josiah Carlson

My point of asking was that execution speed of the password comparison within the context of Redis is dominated context switch times in transferring network data between the network card and Redis, not by actual memory comparison operations.

While this kind of attack is possible in Python, Ruby, PHP, Lua, etc., (whose execution engines typically run in the <10 million instructions/second range with JITs, or in the 100ns-1us per instruction), and could even be attacked; strcmp() executes on the order of 5ns or better per character on Core2 or better processors (basically everything manufactured in the last 6-7 years). Trying to measure differences of 5ns or less, when your precision is 100ns (but only over 1k measurements) doesn't work. It is like measuring a medium grain of sand with a ruler whose markings were irregularly spaced somewhere between .5 and 1.5 cm apart and not being able to distinguish the difference. In fact, even if you were to slow down the machine to force high processing times on a per-character basis, network jitter times would increase linearly with the comparison times, so your precision would get worse with the comparison times!

So the attack is not even theoretical at this point; it is demonstrably impractical in the face of Redis.

And as such, your attempt at claiming "ethical duty" for responsible disclosure so that people can "defend themselves" is unnecessary. You can tell people now. Redis won't be exploited by this flaw.

Instead, what is roughly 1 million times more likely is that if someone has access to attempt one of the LAN-based attacks (with the aforementioned 100ns precision), they would instead put their network card in promiscuous mode and capture traffic. Why? All of the Redis protocol is in cleartext, including passwords. That's an actual attack vector. And that is by design.

Jon Frisby
MrJoy commented June 20, 2012

Actually, all that means is that instead of identifying one character at a time, I need to identify several characters at a time -- which does increase the effort involved, but does not render it impractical. And network jitter times increasing is irrelevant -- proper statistical modeling will smooth those away no matter how large they get.

As for the issue of the Redis protocol being unencrypted, and thus promiscuous mode being a viable option for sniffing -- that's an issue we hadn't considered but we do appreciate you pointing it out.

Josiah Carlson

You missed the point of my post entirely.

Timing attacks on Redis won't work because the precision of the measurements used to attack it in that fashion are not sufficiently precise. How many characters would you need to match? Well, if the precision of your measurements is 100ns, then you'd need to simultaneously match X characters some 1000+ times (according to the paper). That X is not 2, it's not even 3 or 4. That X is closer to 8+ with a modern processor in practice.

Even with just lowercase alpha characters, there are over 200 billion combinations of 8 alpha characters, which you then need to try 1000 times each. Assuming that you can sustain some 100k requests/second against Redis (you may be able to get 2-4x with work, but you will be pushing Redis to its limit, and you will be noticed), That will take you 4 years to run (on average) just to find a match for the first 8 characters (or really to determine that some sizable portion of those 8 characters are likely a match). Again, not practical.

I didn't tell you about the password thing so that you could submit an advisory; actual users of Redis already know about the plain text part of the protocol. Again, that's a design decision.

If you want to play the security researcher, find a buffer overflow or a situation where Redis isn't checking a password; that has the potential to actually affect people using Redis. This "we might be able to time the difference in a strcmp() call from a remote client" isn't security research, it's a distraction.

Josiah Carlson

This "you can measure time differences of character comparisons remotely with strcmp()" is the same kind of thing that lead people to say "why are you using iterated sha hashing (aka PKBDF2), just use bcrypt!"

Salvatore Sanfilippo
Owner

@MrJoy please go ahead with the full disclosure, I believe in full disclosure and I think this will have zero practical impact because of the environments where Redis is ran, and because I tested even guessing 6 chars at once without obtaining statistically differences over loopback interface. This does not mean it is not a good idea to fix the bug of course, but simply that being an strcmp() call in the context of Redis in an average computer around in the 6 nanoseconds figure (to compare the whole password) even guessing multiple characters at time the attack is so far at the limits of the exploitability with the current state of art techniques.

We'll get this fixed in short time anyway :)

Thanks for reporting the issue, security auditing is very appreciated.

Salvatore Sanfilippo
Owner

@josiahcarlson it was shown in the mast multiple times that actually this sort of attacks under certain conditions are practically exploitable, even when the difference between the network latency and the time to compare the password is significant, for instance Redis pipelining can help to multiply the time used to strcmp() the password, and various filtering techniques can use to almost filter away the errors due to the fact that there is a network between you and the server. Attackers always get better never worse, so maybe this is not practically exploitable right now with a direct attack, but working on it may reveal it is exploitable, or that it is exploitable in a slow computer compared to the i7 that I used to perform a few tests, or maybe with a libc where strcmp() is not optimized, and so forth.

So I understand this looks suspicious but it's more practical than it seems in my opinion.

Salvatore Sanfilippo
Owner

p.s. just an example, at some point when I was conceiving the Idle Scan attack I posted a related attack that is just part of the full attack, that is network traffic activity discovery checking the increment of the IP ID. On Bugtraq I got replies that this was harmless in many ways, then a few weeks later I improved the attack turning it into the idle scan. This is not an isolated case, always happens :)

Salvatore Sanfilippo
Owner

This is the solution I propose, comments welcomed:

+/* Return 0 if strings are the same, 1 if they are not.
+ * The comparison is performed in a way that prevents an attacker to obtain
+ * informations about the nature of the strings just monitoring the execution
+ * time of the function.
+ *
+ * Note that in theory the following line may leak information related to
+ * the length of the strings due to branch prediction / misprediction:
+ *
+ * int minlen = (alen < blen) ? alen : blen;
+ *
+ * In the context of Redis this is believed to be impossible to measure
+ * from an external attack.
+ */
+int time_independent_strcmp(char *a, char *b) {
+    int alen = strlen(a);
+    int blen = strlen(b);
+    int minlen = (alen < blen) ? alen : blen;
+    int j;
+    int diff = 0;
+
+    for (j = 0; j < minlen; j++) {
+        diff |= (a[j] ^ b[j]);
+    }
+    diff |= alen ^ blen;
+    return diff;
+}
+
 void authCommand(redisClient *c) {
     if (!server.requirepass) {
         addReplyError(c,"Client sent AUTH, but no password is set");
-    } else if (!strcmp(c->argv[1]->ptr, server.requirepass)) {
+    } else if (!time_independent_strcmp(c->argv[1]->ptr, server.requirepass)) {
       c->authenticated = 1;
       addReply(c,shared.ok);
     } else {
Salvatore Sanfilippo
Owner

@MrJoy I already did exactly this, also preventing any branch prediction timing leak, posting in a second.

p.s. padding is also bad as it is time dependent, I used the approach of pre-alloc + copy.

Jon Frisby
MrJoy commented June 21, 2012

... and I just realized your comments outlined my exact concern, thus the retraction of my (sleep-deprived) comment. :)

Salvatore Sanfilippo
Owner

Hopefully final solution ;)

/* Return 0 if strings are the same, 1 if they are not.
 * The comparison is performed in a way that prevents an attacker to obtain
 * information about the nature of the strings just monitoring the execution
 * time of the function.
 *
 * Note that limiting the comparison length to strings up to 512 bytes we
 * can avoid leaking any information about the password length and any
 * possible branch misprediction related leak.
 */
int time_independent_strcmp(char *a, char *b) {
    char bufa[512], bufb[512];
    /* The above two strlen perform len(a) + len(b) operations where either
     * a or b are fixed (our password) length, and the difference is only
     * relative to the length of the user provided string, so no information
     * leak is possible in the following two lines of code. */
    int alen = strlen(a);
    int blen = strlen(b);
    int j;
    int diff = 0;

    /* We can't compare strings longer than our static buffers.
     * Note that this will never pass the first test in practical circumstances
     * so there is no info leak. */
    if (alen >= sizeof(bufa) || blen >= sizeof(bufb)) return 1;

    memset(bufa,0,sizeof(bufa));        /* Constant time. */
    memset(bufb,0,sizeof(bufb));        /* Constant time. */
    /* Again the time of the following two copies is proportional to
     * len(a) + len(b) so no info is leaked. */
    memcpy(bufa,a,alen);
    memcpy(bufb,b,blen);

    /* ALways compare all the chars in the two buffers without
     * conditional expressions. */
    for (j = 0; j < sizeof(bufa); j++) {
        diff |= (bufa[j] ^ bufb[j]);
    }
    /* Length must be equal as well. */
    diff |= alen ^ blen;
    return diff; /* If zero strings are the same. */
}
Dmitry Chestnykh
dchest commented June 21, 2012

"proportional to len(a) + len(b)"

If an attacker knows len(a), then she can learn len(b) from this sum, no?

Jeremy Wagner-Kaiser
K4lium commented June 21, 2012
    /* The above two strlen perform len(a) + len(b) operations where either
     * a or b are fixed (our password) length, and the difference is only
     * relative to the length of the user provided string, so no information
     * leak is possible in the following two lines of code. */
    int alen = strlen(a);
    int blen = strlen(b);

...

+    memcpy(bufa,a,alen);
+    memcpy(bufb,b,blen);

Hm, this is still a leak, as the attacker does know the length of the password they supplied and I think strlen() has linear runtime.

Maybe use two special-purpose buffers: one for the server password allocated at server startup and the other allocated at user connection time. Copy the server password into its buffer during redis startup and the user-supplied password whenever they supply it (do length-checks, obviously). Then you can compare these buffers to check the passwords against each other. Result: run-time of password checking strictly proportional to input password and everything related to server password is done ahead of time.

Also, I would think this would require updating the config parser to reject any password over 512 bytes in length.

Salvatore Sanfilippo
Owner

@dchest not in practical terms, because for instance:

  • a is the length of the password set inside the server.
  • b is the length of the user provided password.

The attacker can only change 'b' and will see a time difference proportional to the change it does to 'b'. This can't work as an oracle to understand size of 'a'.

Your reasoning appear to be in the line "But I know the total time so I can estimate how much work the server is doing", but actually timing attacks are ran in a different way changing the input to see how the time change to guess information, so we are safe. There is no real-world way AFAIK for the attacker to be able to tell given the absolute time what is the length of the string.

Salvatore Sanfilippo
Owner

@K4lium the reply I wrote for @dchest also applies to your message I think.

Jeremy Wagner-Kaiser
K4lium commented June 21, 2012

@antirez It does, thank you.

Actually, I think I can see how to use this to attack. Measure the time proportional for b values of differing lengths. Use 1 and 512 as a basis to reason from, and I think you could get pretty close to deducing len(a) + len(b). Once the difference between runtime(b=512) and runtime(b=1) is roughly known, then that difference can be divided by 511 to yield a unit of difference per character of a and b combined.

I'm not convinced this is practical, but I think it's there in theory. Knowing the absolute times and the variation in timing due to user input would seem to create an oracle for the uknowns.

Dmitry Chestnykh
dchest commented June 21, 2012

@antirez You seem to be right :) However, can't the attacker still estimate the length of the stored password by measuring how long it takes for the server to respond to her one-byte queries? Not that it's important or practical.

Salvatore Sanfilippo
Owner

@K4lium I understand your reasoning but once we start considering timing attacks that use the absolute time we really open a can of worms :) If we would be concerned about those kind of stuff probably the most practical thing to do is to add a random delay, but probably this would be an overkill right now, especially considering that:

  • If the password is long enough, we are safe even if the attacker can guess it.
  • If the password is short enough, we are unsafe anyway because an external attacker using pipelining can probably test 1 million passwords per second... and find it by brute force :)

So the current approach is probably paranoid enough not exposing the password length by a trivial "differential attack" but protecting the password content in a far better way with a constant time loop.

Btw I'll make sure to document all this findings in the commit log. I'm also altering config.c so that it enforces the 512 bytes password limit at startup time, and returns an error when using CONFIG SET REQUIREPASS.

Jon Frisby
MrJoy commented June 21, 2012

@dchest If the comparison operation is strictly proportional to the length of either the user-supplied password, or the max-allowed-password-length, then no, you shouldn't be able to estimate the length...

Salvatore Sanfilippo
Owner

Yes, I think the only concern would be with what @K4lium proposed, that is:

  • The attacker changes size of 'b' to guess the time the memcpy() uses per byte.
  • The attacker considers the whole operation, and try to estimate, from the per-byte speed, what is the time taken by the whole process, and to understand what is the length of 'a' from this, but this is an incredibly hard thing to do. I think impossible because:
  • We are now dealing with absolute times.
  • The password memcpy() time is a tiny percentage of the total running time of the computation. What makes timing attacks practical is that we deal with a difference triggered by the input. Once it starts to be absolute it is an entirely different business.

As you can see the attacker here needs to understand, from the time needed to copy one character, what is the proportionality with all the other operations performed by the command, as there is no way to just isolate the time needed to copy just the password from the rest, as changing 'b' anyway you see:

+----------------------------------------------------------------+-----------------------------------+
| the whole time taken to execute the command    | time used for memcpy(b)  |
+----------------------------------------------------------------+-----------------------------------+

p.s. github sucks as ASCII art environment.

Salvatore Sanfilippo antirez referenced this issue from a commit June 21, 2012
Salvatore Sanfilippo Fixed a timing attack on AUTH (Issue #560).
The way we compared the authentication password using strcmp() allowed
an attacker to gain information about the password using a well known
class of attacks called "timing attacks".

The bug appears to be practically not exploitable in most modern systems
running Redis since even using multiple bytes of differences in the
input at a time instead of one the difference in running time in in the
order of 10 nanoseconds, making it hard to exploit even on LAN. However
attacks always get better so we are providing a fix ASAP.

The new implementation uses two fixed length buffers and a constant time
comparison function, with the goal of:

1) Completely avoid leaking information about the content of the
password, since the comparison is always performed between 512
characters and without conditionals.
2) Partially avoid leaking information about the length of the
password.

About "2" we still have a stage in the code where the real password and
the user provided password are copied in the static buffers, we also run
two strlen() operations against the two inputs, so the running time
of the comparison is a fixed amount plus a time proportional to
LENGTH(A)+LENGTH(B). This means that the absolute time of the operation
performed is still related to the length of the password in some way,
but there is no way to change the input in order to get a difference in
the execution time in the comparison that is not just proportional to
the string provided by the user (because the password length is fixed).

Thus in practical terms the user should try to discover LENGTH(PASSWORD)
looking at the whole execution time of the AUTH command and trying to
guess a proportionality between the whole execution time and the
password length: this appears to be mostly unfeasible in the real world.

Also protecting from this attack is not very useful in the case of Redis
as a brute force attack is anyway feasible if the password is too short,
while with a long password makes it not an issue that the attacker knows
the length.
31a1439
Salvatore Sanfilippo
Owner

Fixed into unstable, cherry-picking into 2.6.

Salvatore Sanfilippo antirez referenced this issue from a commit June 21, 2012
Salvatore Sanfilippo Fixed a timing attack on AUTH (Issue #560).
The way we compared the authentication password using strcmp() allowed
an attacker to gain information about the password using a well known
class of attacks called "timing attacks".

The bug appears to be practically not exploitable in most modern systems
running Redis since even using multiple bytes of differences in the
input at a time instead of one the difference in running time in in the
order of 10 nanoseconds, making it hard to exploit even on LAN. However
attacks always get better so we are providing a fix ASAP.

The new implementation uses two fixed length buffers and a constant time
comparison function, with the goal of:

1) Completely avoid leaking information about the content of the
password, since the comparison is always performed between 512
characters and without conditionals.
2) Partially avoid leaking information about the length of the
password.

About "2" we still have a stage in the code where the real password and
the user provided password are copied in the static buffers, we also run
two strlen() operations against the two inputs, so the running time
of the comparison is a fixed amount plus a time proportional to
LENGTH(A)+LENGTH(B). This means that the absolute time of the operation
performed is still related to the length of the password in some way,
but there is no way to change the input in order to get a difference in
the execution time in the comparison that is not just proportional to
the string provided by the user (because the password length is fixed).

Thus in practical terms the user should try to discover LENGTH(PASSWORD)
looking at the whole execution time of the AUTH command and trying to
guess a proportionality between the whole execution time and the
password length: this appears to be mostly unfeasible in the real world.

Also protecting from this attack is not very useful in the case of Redis
as a brute force attack is anyway feasible if the password is too short,
while with a long password makes it not an issue that the attacker knows
the length.
4b3865c
Emmanuel Roullit eroullit referenced this issue from a commit June 21, 2012
Emmanuel Roullit Swap memset()+memcpy() for strncpy() (Issue #560).
strncpy() does in one call what memset()+memcpy() does:
	- Copying the source string to the destination buffer
	- Pads the remainder of destination buffer with null bytes

It means that the write operation occurs on the whole length buffer
everytime. It mitigates the string length timing attack.

Null termination is irrellevant as string buffers are compared
byte-to-byte over their whole length in all cases.
7b08ec8
Emmanuel Roullit eroullit referenced this issue from a commit June 21, 2012
Emmanuel Roullit Changed types in time_independent_strcmp() (Issue #560).
'int' variables are replaced with 'size_t' variables as:
	- strlen() returns a 'size_t'
	- sizeof() is a 'size_t'
	- comparing signed integers with unsigned ones is not recommanded
67940e1
Jeremy Wagner-Kaiser
K4lium commented July 02, 2012

Is this going to be in the next RC? Any indication of when that will be released?

Steffen Müller tsee referenced this issue from a commit in tsee/redis June 21, 2012
Salvatore Sanfilippo Fixed a timing attack on AUTH (Issue #560).
The way we compared the authentication password using strcmp() allowed
an attacker to gain information about the password using a well known
class of attacks called "timing attacks".

The bug appears to be practically not exploitable in most modern systems
running Redis since even using multiple bytes of differences in the
input at a time instead of one the difference in running time in in the
order of 10 nanoseconds, making it hard to exploit even on LAN. However
attacks always get better so we are providing a fix ASAP.

The new implementation uses two fixed length buffers and a constant time
comparison function, with the goal of:

1) Completely avoid leaking information about the content of the
password, since the comparison is always performed between 512
characters and without conditionals.
2) Partially avoid leaking information about the length of the
password.

About "2" we still have a stage in the code where the real password and
the user provided password are copied in the static buffers, we also run
two strlen() operations against the two inputs, so the running time
of the comparison is a fixed amount plus a time proportional to
LENGTH(A)+LENGTH(B). This means that the absolute time of the operation
performed is still related to the length of the password in some way,
but there is no way to change the input in order to get a difference in
the execution time in the comparison that is not just proportional to
the string provided by the user (because the password length is fixed).

Thus in practical terms the user should try to discover LENGTH(PASSWORD)
looking at the whole execution time of the AUTH command and trying to
guess a proportionality between the whole execution time and the
password length: this appears to be mostly unfeasible in the real world.

Also protecting from this attack is not very useful in the case of Redis
as a brute force attack is anyway feasible if the password is too short,
while with a long password makes it not an issue that the attacker knows
the length.
172916f
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.