A beginner's guide to constant-time cryptography
6 points by runxiyu
6 points by runxiyu
Sometimes I wonder what really prevents people from making compilers that have, for example, a pragma that says “don’t optimize this function in any way”. Perhaps LTO or something?
As the article alludes to its not just the compiler. Ie the compiler is not optimizing something like string comparison or memcpy - the code is written as early exit, most os’s now provide constant time comparison functions that are in principle guaranteed to not leak information about when the failure occurs. In general code that is not constant time with optimizations enabled is also unlikely to be constant time without optimizations.
But as the post said, even if you have attempted to write constant time code, that’s only constant time according to the isa, not the hardware implementation.
Historically people were only concerned about branch predictors, but recent years have led to ever more focus on load predictors and cache behaviour which leaks information the is secret dependent.
To start mitigating this many isas have started adding modes (either instruction flags or mode switches) that can be used to disable caches and predictors for timing/load/access sensitive regions, but over time researchers find parts of the hardware that aren’t sufficiently limited by those modes.
For symmetric encryption (aes) almost all cpus provide direct support that is guaranteed to be constant time and free of other side channels. The problem with AES is that it was designed to be efficiently implementable in hardware via table lookups, but when implemented in software those lookups leak information.
A more robust solution in many cases is blinding - basically perform an invertible operation so you can completely disassociate the behaviour of the operations from actual secret. It’s still not perfect as you can leak information through the blinding operations themselves.
Imagine a cipher where you are just multiply the secret by a key in mod N (there is no such cipher let’s just assume for this example). To blind this what you would do is
In theory step 3 is exposes no information because one value is completely random, the operation 4 involves the key, but because blinded is functionally random that masks the key values, and the finally step 5 is the multiplication of two values that are randomly diverged from the message and the key that also leaks no info.
This general blinding approach is used as part of the defenses in a number of rsa implementations at least due to the many many ways rsa leaks timing information - it does have the effect of making rsa - an already slow operation - even slower, and it’s only part of the defense as it possible to attack parts of the blinding process for rsa (iirc), but I never really studied how attacks on blinding work.