Checking that functions are constant time with Valgrind

http://www.imperialviolet.org/2010/04/01/ctgrind.html

by l0stman • 16 years ago

42 8 16 years ago

carbocation2• 16 years ago

Did he just disclose a potential OpenSSL vulnerability?

NateLawson2• 16 years ago

No, he identified that all RSA software implementations are potentially vulnerable to side channel attacks and you have to understand the microarchitectural details of your system to be more certain you aren't actually vulnerable.

carbocation2• 16 years ago

Thank you for your answer, which makes it clear that his point is actually more generally important than I had realized. Perhaps this is well known to people with an interest in security, but it was news to me. Fascinating.

jbert• 16 years ago

That's inspired.

I guess the insight it that valgrind is basically retrofitting a type system over the raw memory accesses.

I wonder if a similar approach could be used to check that certain classes of program input are all processed in a certain way? (e.g. untrusted data being escaped before display in an web app (XSS prevention), e.g. charset conversions being performed)?

It would require more work (valgrind would need a different set of things to warn on, and a way of realising when some memory has been made safe).

All very reminiscent of perl's taint mode (scalar values are flagged with a contagious 'taint bit', which prevents their use in output, calls to 'system()' etc.)

abecedarius• 16 years ago

Oblivious algorithms have uses besides avoiding side channels (example: http://www.cs.dartmouth.edu/~thc/papers/slabpose.pdf) -- though I can't see as sore a need for an automated check of obliviousness in their case.

growt• 16 years ago

I hate April 1. - now I can't tell if this is just a joke (that I don't get) or something serious.

NateLawson2• 16 years ago

Although he doesn't say it, I assume he has suppressed warnings about plain uninitialized memory reads since his system will generate spurious warnings even for safe, constant-time comparisons.

The thing the author probably doesn't realize is that his approach only helps with the simplest of operations like his target compare loop. With an RSA implementation, all versions would be tagged as vulnerable.

This shows up at the end of his post where he flags BN_mod_exp_mont_consttime() as vulnerable. The reason this code is safer (not safe) against side-channel attacks is that it takes advantage of cache layout of x86 processors to ensure that indexed accesses do not reveal private information. His approach also won't be able to model more complex countermeasures such as blinding. It will always flag them as vulnerable.

I don't understand why this needs valgrind (dynamic analysis). You can do a fully static analysis by storing the address of your safe_compare() routine, then disassembling starting at that function until it returns. If you hit a branch instruction before, flag an error. This could be one of your pre-commit checks for the repo.

In other words, this is not useful for finding timing attacks, it's useful for detecting regression.

ralph• 16 years ago

Is it only branch instructions that matter in the disassembly? Might some instructions not take a varying amount of cycles depending on the data/ALU flags?

Checking that functions are constant time with Valgrind

Related Stories