Are there other major reasons not to roll your own crypto besides "you might do it wrong"? 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?
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..
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.
(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.)
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.
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.
I'm not saying this is a good solution, just trying to understand the problem space.
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.
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.