Comment by klabb3 | Hacker News Reader

Comment by klabb3 | Hacker News Reader

Parent Full thread

> […] and I get why they are important if you don't know what software is running on your computer.

Side channel attacks are not limited to attackers on the same device. Timing attacks can be remote for instance, and with RSA some operations are slow enough to be noticeable over networks.

> Wouldn't a fuzz tester (comparing your implementation to a known good one) be well adapted to making sure you didn't do it wrong?

Not really. Cryptography is inherently not very conducive to tests, because they can only prove the outcome of specific inputs. You need to be a lot more defensive than that, and use reason, proofs etc to prove properties like “an adversary cannot gain any knowledge about X or Y given that they control Z”.

Of course reimplementing a vetted spec like RSA is better than rolling your own primitives which is beyond doomed. OTOH an opportunistic attacker will probably not bother with a custom crypto - it’s still a lot of work to find the flaws. But once found, game over..

> Timing attacks can be remote for instance, and with RSA some operations are slow enough to be noticeable over networks.

Huh, I'd be pretty curious about that.

> Not really. Cryptography is inherently not very conducive to tests, because they can only prove the outcome of specific inputs

I'm pretty confused by this. It's a completely deterministic operation on a series of bytes. If you have identical results to 2 billion randomized inputs how can that not be pretty high confidence that the underlying algorithm is sound?

Obviously it's good to do the math and reasoning as well, but... I just don't get it. It's not magic, it's math and bit munging.

You are right that it increases the confidence. If you’re following a known algorithm conformance- and edge case tests can be a blessing. Of course in the case of RSA you need arbitrary precision bigint math which is another issue with adversarial inputs.

(What I meant is that you can’t test whether the algorithm is secure, because you can’t enumerate the weaknesses that a cryptanalyst would attempt.)

Ah, you can test the implementation but not the algorithm itself. Got it. I see now I said "roll your own crypto" and I should have said something like "reimplement a crypto"

To prevent side channel, can't you do something as stupid as add a randomized [0-0.1) second sleep to your crytpographic operations? That would make any difference in your algorithms performance negligible.

Bottom line: Yes and no. Yes, you can do that. No, it won't really do what you want.

The best way I've found to imagine a timing attack is as a set of graphs produced from thousands to millions of data points, each of which is a time measurement. Any given high-level input takes a certain amount of time to process (example: trying a login). Curves - and thus timing side channels - are distinguishable from one another when the curves have different peaks. The width of the (probably bell-shaped) curves are going to be determined by the amount of variance.

What happens if you add a little predictable random variance to each operation that's the same in each operation? Each curve probably gets a little wider, but you don't move their peaks relative to one another. At most, it might mean the person carrying out a timing attack needs to gather more data. Timing attacks already work with network noise implicitly doing what you've suggested doing explicitly.

You can simulate this yourself. Graph a thousand points of [0-1] and another thousand points of [0-1]+0.1. Superimpose the curves on one another. You may have to use some bucketing to make the curves visible.

That makes sense. So instead you could just require that your crypto stuff takes an absurd amount of time, say 0.5 seconds / MiB? Then every operation will take that long and no information can be gleaned.

I'm not saying this is a good solution, just trying to understand the problem space.

That works if you're willing to have your system be DoS'd. If every request takes half a second, that just means the attacker needs more systems sending requests in parallel to get the required number of samples quickly. In today's world, you'd probably just scale up a bit to ensure you could still serve requests. If you let your system go down under load, you can severely restrict how much data attackers can get at the cost of being useless to whoever your intended users are.

The attacker would also likely need more patience, but timing attacks are not for those looking for quick wins.

The preferred way to handle this is to make sure your operations are constant-time. This eliminates the timing side channel. This is harder, and often slower, but solves the problem entirely.

> So instead you could just require that your crypto stuff takes an absurd amount of time, say 0.5 seconds / MiB?

To add to the other (correct) answer: it’s not a terrible idea, because constant time does not leak. However:

- You need to make sure the time is only a function of input data, otherwise you might leak info about internal code paths.

- If the operation cannot complete in time you may be leaking information, even if you only return a generic error.

These are not massive attack surfaces, but they do exist. As with regular programming, you want to reduce the risk of things that can go wrong by reducing the number of code paths. Only now, the cost of an error is much higher, and can go undetected. But no, other than the various and highly subtle side channels there’s no magic to rolling your own crypto, only a long track record of people who overestimated their abilities (or underestimated their adversaries). Oftentimes it’s due to optimizations in the CPU, memory, disks, language runtimes etc that are the culprits. These subsystems often cache, share, or soft-delete data that the programmer thought was exclusive or lifetime-bounded in a way that it wasn’t.

That’s why I like ECC or AES much more than say RSA or other bigint math heavy things. Bit operations are very predictable, and if they run in a loop of constant iterations even better. All else equal, I’d pick an ECC implementation (and not just because it’s faster and smaller). Almost all vulnerabilities have been implementation or parameter choices, not the foundational math. That said, say OpenSSL RSA has been battletested heavily and for a long time.

Reply on news.ycombinator.com