Information leaks via timing side channels can be deadly. You can steal RSA keys from other processes on the same host, extract the kernel's dm_crypt keys and steal AES keys over the network.
In order for a function to be constant time, the branches taken and memory addresses accessed must be independent of any secret inputs. (That's assuming that the fundamental processor instructions are constant time, but that's true for all sane CPUs.)
However, it's tough to write constant time functions. You can see the source to a few simple ones that I wrote Go. Sometimes the design of the function is fundamentally flawed (like AES), but even when the function can be efficiently implemented in a constant time fashion, it's easy to slip up. Careful code review is currently the best practice but it's error prone as the amount of code increases and fragile in the face of change.
A type system could probably help here, but that's not the path I'm taking today. Since cryptographic functions result in abnormally straight line code, it's common for a typical input to exercise every instruction. So a tool like Valgrind could check all the branches and memory accesses to make sure that they haven't been tainted with secret data.
This would mean keeping track of every bit in memory to know if it's secret or not, likewise for all the CPU registers. Preferably at the bit level. The tool would also have to know that adding secret and non-secret data results in secret data etc. That suggests that it would be quite a complex tool.
But memcheck already does this! In order to keep track of uninitialised data it shadows every bit of memory and will warn you if you use uninitialised data in a branch or to index a memory access. So if we could tell memcheck to treat our secret data as uninitialised, everything should just work.
I've a Valgrind patch does just that (against SVN r11097). It will intercept any calls to ct_poison and ct_unpoison in libctgrind.so* .
Let's look at a bad way to test a 128-bit MAC against a calculated value:
char check16_bad(unsigned char *a, unsigned char *b) { unsigned i; for (i = 0; i < 16; i++) { if (a[i] != b[i]) return 0; } return 1; }
int main() { unsigned char a[16], b[16]; memset(a, 42, sizeof(a)); memset(b, 42, sizeof(b)); ct_poison(a, sizeof(a)); printf("check16_bad
... continue reading