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.
Comments
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.
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.