Monday 11 June 2012

MySql Authentication Bypass Explained

Yesterday a severe vulnerability in MySql was published (CVE-2012-2122). It allows an attacker to login under any username simply by trying to login around 300 times. No special tricks required. The line below shows how you can test for this vulnerability:
for i in `seq 1 1000`; do mysql -u root --password=bad -h <remote host> ; done
Where <remote host> should be replaced by the server you want to test. If it's vulnerable there's a high probability you will successfully connect to the MySql instance.

The flaw was located in sql/password.c in the function check_scramble:

Can you see what's wrong with it? To give a hint, the vulnerability is in the last line of the function, where the call to memcmp is made.

Before explaining the bug, first some background. When a user connects to MariaDB/MySQL database, a token (SHA1 hash over the given password and a random scramble string) is calculated and compared with the expected value [source]. So in essence the above code checks if the supplied password is correct. The comparison of the two hash values is done in the last line using a call to memcmp.

Reading the manual page of memcmp we see that it returns zero when both hashes are equal. More precisely
The memcmp(s1, s2, n) function returns an integer less than, equal to, or greater than zero if the first n bytes of s1 is found, respectively, to be less than, to match, or be greater than the first n bytes of s2.
The problem is that memcmp can return any integer (depending on the input value). Although most implementations of memcmp only return -1, 0, or 1 this is not required in the specification of memcmp. Now what happens when our implementation of memcmp returns a different number? Let's find out by assuming that it returned the number 0x200. Since this value is not equal to zero the two hashes are not equal, hence the passwords were also not equal.

Unfortunately the integer 0x200 is being cast to a my_bool type, which in turn is typedef'ed as a char. Because a char is smaller than an integer the number has to be truncated. In practice only the last byte of 0x200 (the return value of memcmp) will survive. And this last byte is 0x00, so simply zero.

We now get that even though memcmp returned a value different than zero (say 0x200) the function check_scramble does return zero! As we can see in the description of the function it should only return zero when the password is correct... which here is clearly not the case, hence the security vulnerability.

Apparent "randomness" in return values of memcmp

The question is now when, and why, memcmp would return a number different than -1, 0 or 1. The answer lies in how memcmp compares the input buffers. To compare if two bytes are equal it subtracts them. Only when the result is zero are the two bytes equal. If not zero, one could simply return the result of the subtraction, as this would match the behaviour specified in the manual page. The range of values memcmp would then return lies between -128 and 127. But this doesn't include our example number 0x200!

To speed up the comparison memcmp will subtract multiple bytes at once (when possible). Let's assume it will subtract 4 bytes at once. Then the result of memcmp will be within the range -0x80000000 and 0x7FFFFFFF. This range does include our example value of 0x200.

The apparent randomness comes from the fact that the protocol uses random strings. So each time a random input is given to the memcmp function. The security vulnerability only occurs when the last byte of the integer returned by memcmp is zero. Hence the probability of the vulnerability occurring is 1/256.

The Fix

The vulnerability was fixed by defining the macro
#define test(a) ((a) ? 1 : 0)
 and putting it around the memcmp call.