From 4b3865cbdbb5ceeb7e284e622550855071c2b8d6 Mon Sep 17 00:00:00 2001 From: antirez Date: Thu, 21 Jun 2012 11:50:01 +0200 Subject: [PATCH] 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. --- src/config.c | 5 +++++ src/redis.c | 44 +++++++++++++++++++++++++++++++++++++++++++- src/redis.h | 1 + 3 files changed, 49 insertions(+), 1 deletion(-) diff --git a/src/config.c b/src/config.c index c2ea5b76..6b513940 100644 --- a/src/config.c +++ b/src/config.c @@ -264,6 +264,10 @@ void loadServerConfigFromString(char *config) { { server.aof_rewrite_min_size = memtoll(argv[1],NULL); } else if (!strcasecmp(argv[0],"requirepass") && argc == 2) { + if (strlen(argv[1]) > REDIS_AUTHPASS_MAX_LEN) { + err = "Password is longer than REDIS_AUTHPASS_MAX_LEN"; + goto loaderr; + } server.requirepass = zstrdup(argv[1]); } else if (!strcasecmp(argv[0],"pidfile") && argc == 2) { zfree(server.pidfile); @@ -411,6 +415,7 @@ void configSetCommand(redisClient *c) { zfree(server.rdb_filename); server.rdb_filename = zstrdup(o->ptr); } else if (!strcasecmp(c->argv[2]->ptr,"requirepass")) { + if (sdslen(o->ptr) > REDIS_AUTHPASS_MAX_LEN) goto badfmt; zfree(server.requirepass); server.requirepass = ((char*)o->ptr)[0] ? zstrdup(o->ptr) : NULL; } else if (!strcasecmp(c->argv[2]->ptr,"masterauth")) { diff --git a/src/redis.c b/src/redis.c index 46915c13..ec313fbf 100644 --- a/src/redis.c +++ b/src/redis.c @@ -1698,10 +1698,52 @@ int prepareForShutdown(int flags) { /*================================== Commands =============================== */ +/* 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[REDIS_AUTHPASS_MAX_LEN], bufb[REDIS_AUTHPASS_MAX_LEN]; + /* 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. */ +} + 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 { diff --git a/src/redis.h b/src/redis.h index 7cde4eb7..a194bed4 100644 --- a/src/redis.h +++ b/src/redis.h @@ -56,6 +56,7 @@ #define REDIS_SLOWLOG_LOG_SLOWER_THAN 10000 #define REDIS_SLOWLOG_MAX_LEN 128 #define REDIS_MAX_CLIENTS 10000 +#define REDIS_AUTHPASS_MAX_LEN 512 #define REDIS_REPL_TIMEOUT 60 #define REDIS_REPL_PING_SLAVE_PERIOD 10 -- 2.45.2