"One in 256 times *any* password might get you in" - MySQL authentication disaster

Filed Under: Featured, Vulnerability

We've reported on a number of hacks lately in which password hashes have been stolen.

A hashed password is useless on its own, of course, but checking a list of really obvious passwords against a hash can quickly reveal low-hanging fruit.

That's why we keep advising you to choose non-obvious passwords - so they're harder for hackers to guess.

But what if the authentication system itself is at fault?

You could have the hardest-to-guess password, salted and hashed thousands of times, and still be at risk.

That happened about a year ago at Dropbox, for instance, when the file-sharing site inadvertently removed its authentication validation altogether for a few hours. Anyone could use any password.

It's happened again, this time with a more corporate angle.

Open source database giant MySQL (and its post-Oracle fork, MariaDB) contained a bug which meant that your password might be checked correctly only 255 out of every 256 times. One in 256 times, anything might get you in.

The good news is that this bug doesn't show itself on all systems, and was fixed well over a month ago in both MariaDB and MySQL. To summarise:

All MariaDB and MySQL versions up to 5.1.61, 5.2.11, 5.3.5, 5.5.22 are vulnerable. MariaDB versions from 5.1.62, 5.2.12, 5.3.6, 5.5.23 are not. MySQL versions from 5.1.63, 5.5.24, 5.6.6 are not.

The bad news is that the popular exploitation automation tool Metasploit now has a plug-in that tries to retrieve the password hashes from a vulnerable system. That's so you can use this exploit whilst it lasts, and then recover weak passwords off-line to use later when the system is patched.

The vulnerability is a weird one.

When you compare two memory buffers in C - as you might when checking if a supplied password's hash matches the one from your database - you usually use the memcmp() function.

If the two memory blocks are the same, memcmp() returns zero. (Although zero generally means FALSE in C, many library functions return zero on success, leaving a choice of non-zero values to denote various error conditions.)

If the memory blocks differ, memcmp() returns a number which indicates the sort order of the two memory buffers. A negative number means that the first block would sort before the second; positive means it would sort after it.

But what do "a negative number" and "a positive number" mean? According to my Linux man page:

And according to my OS X man page:

Since a byte can hold a value from zero to 255, my conclusions are therefore that:

* The value returned by memcmp() on OS X is theoretically limited to the range from -255 (zero minus 255) up to +255 (255 minus zero).

* The value returned by Linux isn't obviously limited other than by the range of the int that the function returns.

* It would be unwise to assume any artificial limits on the return value of memcmp().

Apparently, in the MySQL code, the password hash validation bug happened if memcmp() returned a value outside the range from -128 up to +127 (the ambit of a signed char).

Then, with a one-in-256 chance, the code would recognise two cryptographic hashes as equal regardless of reality. In short, with repeated attempts to log in with any password, you'd eventually get in just by chance.

With most paths through the Linux memcmp() library code, the function just happens to stick to a return value which fits into a signed char, so the bug never shows itself.

But in some cases - if an SSE-accelerated implementation of memcmp() is used, for example - the bug may be triggered:

Whether a particular build of MySQL or MariaDB is vulnerable, depends on how and where it was built. A prerequisite is a memcmp() that can return an arbitrary integer (outside of -128..127 range). To my knowledge gcc builtin memcmp is safe, BSD libc memcmp is safe. Linux glibc sse-optimized memcmp is not safe, but gcc usually uses the inlined builtin version.

Ouch. Four security morals from this story:

1. Never make assumptions when coding. If a function returns an int, accept that any value which fits in an int might be returned, regardless of what the developer, the manual and received wisdom tell you.

2. Patch your MySQL or MariaDB installations if you haven't already.

3. Don't expose database servers to external connectivity unless you really mean to. Even inside your corporate network, be very restrictive about who can reach database servers at all, let alone log in to them.

4. Watch out for speed optimisations. Invoke them only if you genuinely need extra speed - they may represent a less-travelled code path and thus expose your users to obscure bugs.


-

NB. Thanks to Naked Security reader Bill for his email about this intriguing bug.

, , , , , , , , , , ,

You might like

7 Responses to "One in 256 times *any* password might get you in" - MySQL authentication disaster

  1. Toby · 839 days ago

    I'm a bit confused here.
    From what I understand about the memcmp() function is deterministic, i.e. if I compare two blocks A and B I will always get the same result, however often I do the comparison. Thus then, to exploit the bug, one would need to basically need to do a bruteforce attack, trying different passwords, until you find one that appears to be equal under SSE-accelerated memcmp(). Which would be slightly less dramatic because depending on the password it might be hard to find such a "collision" that mis-matches.
    However, you seem to suggest ("...repeated attempts to log in with any password...") that by repeated attempts with the same password, you can trigger the bug. Which would be even worse.

    So how bad is it? Though I suppose either way is really well bad enough.

    • Paul Ducklin · 838 days ago

      According to the bug reporters, the probability of an accidental mismatch is 1/256.

      Also, AFAIR, the hash-compute-and-check function includes some randomness so that the actual values compared are different each time you try to log in. So you don't even need to supply a different faux-password each time - you can just keep knocking on the door with the same password, and the randomness added to the hash-and-check routine does the rest - ironically reducing security slightly rather than increasing it.

      • njorl · 838 days ago

        I've previously noticed that the md5crypt function (the GRUB4DOS implementation thereof) does not return a constant result for a fixed input. I presume that this feature has been employed to increase the size of pre-built hash table necessary for a particular level of success in a "rainbow table attack". (It's less effective than a per-user salt for protecting passwords from that mode of attack, of course.)

        Note, however, that when I use my password, to attempt to gain the protected access, I enter it just the once. I would conclude, therefore, that the verification process must begin generating and checking all possible results of hashing the entered password, at least until it finds one result that equals the one it has recorded for my account.

        The number of possible hashes, for a single password, must be limited because of the increase to the time required to validate the log-in and, possibly, an increase in coincidental matches. (Let me call the number "n".)

        However, if such a mechanism were employed in MySQL, with this data-size bug present, a single, trial, password would have the same n chances of getting through the loophole, each time we input it. Thus, the trial password would consistently either work (with a probability which we are unable to calculate from the available information) or fail. So, an attacker should try a different password each time.

  2. Bill C. · 839 days ago

    Another great read, very detailed description of the bug.

    Thank you for taking the time to read my e-mail.

  3. njorl · 838 days ago

    I am deeply doubtful that a result "outside the range from -128 up to +127" is sufficient.

    For example, -129 is 0xFFFF...FF7F or 11111111...1111111101111111 (binary) and it's very difficult to imagine a program mistaking it for zero. (I state, explicitly, that I've adopted the signed-number convention used by nearly all modern processors. Other representations are possible, as are non-binary processors.)

    Let's look, first, at the Linux case.

    For completeness, I introduce p as the probability that the trial password would be accepted by a sound implementation (either because the attacker has guessed correctly, or because he has hit upon a hash collision).

    So, there is a probability (1 - p) that memcmp will signal "wrong password", which it does by returning a non-zero, signed, integer (we are told).

    The bug, most likely, is that MySQL considers only the least (/less) significant byte of the result, i.e. the lower eight bits. (Doing so is consistent with expecting a return "value which fits into a signed char".)

    MySQL would, thus, reach the wrong conclusion when both every one of the bottom eight bits is 0 and at least one of the higher bits is 1. (When all bits are zero, memcmp is signalling a password match, of course.)

    If we assume the integer data type is n bytes (or 8n bits), there are (256^n) - 1 memcmp results that could be used to signal "wrong password", of which (256^(n - 1)) - 1 have the hoped-for zero as their bottom byte. (To see this, we note that after discarding the bottom byte, we have n -1 bytes left, and, hence, the number of non-zero values they can convey is (256^(n - 1)) -1.)

    Hence, MySQL would reach the false-positive match (256^(n - 1)) -1 times out of (256^n) - 1 (under the assumption of even distribution).

    If we assume n = 2 (i.e. a two-byte integer, which is the case for a lot of implementations), the result is one in 257. For n >= 3, it tends rapidly to one in 256.

    Incorporating the possibility (probability p) that the bug-free implementation would have accepted the trial password, the probability that the buggy MySQL accepts our log-in is p + (1 - p)((256^(n - 1)) -1)/((256^n) - 1).

    Looking at the OSX case, there seems not to be a problem. There is no integral, value, between -255 and -1 {0xFFFF...FF01, 0xFFFF...FF02, ... 0xFFFF...FFFE, 0xFFFF...FFFF} or between +1 and +255 {0x01, 0x02, ... 0xFE, 0xFF}, that has zero as its bottom byte.

  4. Mark Sitkowski · 784 days ago

    Very interesting, and thanks for the detailed analysis. Personally, I've always used bcmp(), which only returns 0 or 1 (also, because I didn't understand what 'lexicographically' meant... :-)

    • Paul Ducklin · 784 days ago

      According to "man bcmp" on OS X, bcmp() returns "zero if the byte strings are identical, non-zero otherwise." No suggestion that it returns only zero or one...

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

About the author

Paul Ducklin is a passionate security proselytiser. (That's like an evangelist, but more so!) He lives and breathes computer security, and would be happy for you to do so, too. Paul won the inaugural AusCERT Director's Award for Individual Excellence in Computer Security in 2009. Follow him on Twitter: @duckblog