guest - flak

notes on timingsafe_memcmp

A short while ago, I converted some memcmp calls in libssl to CRYPTO_memcmp. As noted at the time, it’s easier to assume something is secret and sensitive to timing attacks than to prove it’s not. However, one must be a little cautious because CRYPTO_memcmp, unlike its libc namesake memcmp, is actually an equality function (zero or not-zero) and not a comparison function (negative, zero, positive for less than, equal, greater than). (Don’t confuse it with OPENSSL_memcmp, which does have memcmp semantics, but is vulnerable to timing attacks because it’s not constant time.)

This observation sparked a little side discussion about the timingsafe family of functions. timingsafe_bcmp, the current actual libc function backing CRYPTO_memcmp, is obviously named after bcmp. bcmp has always been an equality function, so the fact that the constant time variant is too is unremarkable. The danger comes when a comparison memcmp call is blithely replaced by a call to (apparent best fit) timingsafe_bcmp. (Related: Reminder that memcmp and bcmp are not the same.) We need a true comparison function. Using a constant time function to sort or order secrets is most likely counterproductive, as the ordering itself leaks information, but nevertheless parallel functions should have parallel semantics. (The original internal implementation of CRYPTO_memcmp was very similar to timingsafe_bcmp; we were careful not to change the behavior in making that change.)

A few days ago, matthew added timingsafe_memcmp.c to complement timingsafe_bcmp. It can be used anywhere the standard memcmp can be used.

related

NetBSD had an internal __consttime_bcmp function, but decided they didn’t like the bcmp name and renamed it to consttime_memequal, wisely avoiding the memcmp name for a function which is not memcmp. Unfortunately, as clear as the memequal name is, one must remember to reverse the sense of the test, converting memcmp() == 0 to consttime_memequal() != 0 which is easy to overlook.

An older post from Root Labs surveys a few systems and notes that optimized memcmp leaks useful timing differences. While a multibyte comparison function could make exploitation of timing attacks more difficult, it requires cooperation from the compiler to not inline memcmp. More recently, Red Hat also did some work to defeat memory comparison timing oracles. The two downsides are that, again, it requires compiling with a special flag to keep the compiler in line, and also it only benefits Red Hat users. That doesn’t make it a bad change, but portable crypto libraries cannot rely on the system memcmp to provide such safety guarantees. Much easier to bundle a short C file that works everywhere. (BSD memcmp is documented to return single byte differences. Hopefully no software relies on that behavior, but changing existing documented behavior is always hard.)

Hysterically, multibyte memcmp implementations were the partial cause of the MySQL password bypass vuln in 2012, because large multiples of 256 clamped down to one byte turn into 0. A winner is your password, whatever it is.

rationale

The reason drop in compatibility is so important is to encourage adoption by making transitioning as painless as possible. It should be possible to trivially convert code using memcmp to timingsafe_memcmp, even to the point of compiling with -Dmemcmp=timingsafe_memcmp. Whenever “you should do this” advice is blunted with “but only when you need to”, it loses momentum.

Hypothetically, if we successfully pushed a “just use timingsafe_bcmp” meme, inevitably somebody would convert a memcmp used for sorting to timingsafe_bcmp, introducing a bug, to be quickly followed by blog posts about “timingsafe_bcmp considered harmful”, and then everything comes crashing down. Maybe this would never happen, but the only way to know would be to run the experiment and see it happen, and then what do we do?

Another way to phrase this is that it’s not about a function for simultaneously doing both ordered and constant time comparisons, it’s about one function that can do either. Choice is bad (™).

Nate disagrees and thinks that API parity is bad in this case. I obviously weigh the pros and cons a little differently, but timingsafe_bcmp hasn’t disappeared nor have its uses been replaced yet.

Posted 2014-06-17 03:06:37 by tedu Updated: 2014-12-26 04:41:46
Tagged: c programming security