5 ms·

What can an attacker do by knowing how many much queued crypto work there is?

by rictic 4y ago

ChrisLomont 4y ago
There's lots of attacks currently on existing systems exploiting this. Leaking any information about other processes or supposedly hidden state of the system means you are leaking - and attacks always get better, not worse. The point is once you have shared, scheduled resources, others are going to get knowledge that they should not have. The rough idea is, say some other process is repeatedly running some known code with an unknown key, and you want to get that key. By fiddling with how you schedule your requests, you can interrupt or interject his work and your work, and the timing issues due to scheduling have been shown to leak things. Say one process is dealing with web requests, signing things fairly often. An attacker on the same machine can craft web requests, learn how the shared system is responding, and glean information about the web server via timing. This type of poking has been used to leak AES keys by exploiting things thought safe until they were on shared resources.
- loup-vaillant 4y ago
  You're making a general hand wavy argument here, but this is a rather specific issue. "Constant time" in cryptography means that there is no information flow from secrets to timings. Keys are secret. Plaintexts are secret. Ciphertexts, and most importantly their size, is public. You're basically saying that leaking public information is dangerous. This is the same as saying it should be private. In some specific cases you'd be right (I'm thinking of variable length audio encoding, where you could recover part of the conversations or voice prints from network analysis alone), and in these cases you mist hide sizes as well (basically use constant length audio encodings). But in the general case, message sizes are much less important that you make it sound.
  - ChrisLomont 4y ago
    > Constant time" in cryptography means that there is no information flow from secrets to timings If "constant time" cryptography were achievable don't you think we'd have it and there'd be no more timing attacks breaking encryption schemes? "Constant time" cryptography is a mathematical abstraction, a goal, like "unbreakable cipher" and "unbreakable hash" and "frictionless surface." They don't occur in practice. This article breaks itself breaks a "constant time" cryptography with a timing attack. The problem is, as this paper demonstrates (along with many others) coding up a constant time crypto and especially making it portable over time and architectures, is nearly impossible. Caches, chip nuances, power draw mixed with power scaling, and other chip architecture complexity, contribute to attacks. Compiler changes, architecture changes (some even unpublished), architecture variety, user settings, even flaws in any part of the chain, all contribute to making holes in crypto in the real world. This paper [1], for example, is one of many that shows the "constant time" goal is likely not possible, and is certainly not possible in portable code. Here's [2] a paper tying to make simple AES "timing-attack resistant" - and you note they did not claim they could make it "constant time" because they realize that is not possible. "Timing-attack resistant" is at least professionally defensible. Here's [3] a paper referencing [2], trying to make systems more resistant to cross process leaks using Intel SGX to hide things that leaking. And here [4] is the attack on Intel SGX that shows there are still exploitable leaks. This type of chain is not unique. If you want to read literally thousands of papers on such things use google scholar or surf the cryptology eprint archive. Both make searching on such topics pretty easy. We could go on and on. The literature of crypto is littered with such threads - "constant time" crypto is the goal, but so is "unbreakable encryption" - both are mathematical fantasies that do not play out in practice. [1] https://arxiv.org/pdf/1711.08002.pdf https://arxiv.org/pdf/1711.08002.pdf [2] https://link.springer.com/chapter/10.1007/978-3-642-04138-9_1 https://link.springer.com/chapter/10.1007/978-3-642-04138-9_... [3] https://arxiv.org/pdf/1702.08719.pdf https://arxiv.org/pdf/1702.08719.pdf [4] https://arstechnica.com/information-technology/2020/03/hackers-can-steal-secret-data-stored-in-intels-sgx-secure-enclave/ https://arstechnica.com/information-technology/2020/03/hacke...
    - loup-vaillant 4y ago
      If you're going that route, everything is influenced by anything, and with a sufficiently advanced sensor array you could detect a butterfly flapping its wing across the globe. If instead we get serious for a minute, we can notice that cryptography is not magic, and neither is the way data flows from secrets to timings. Quite obviously, whether a program's timings depends on its inputs or not is a function of the hardware it runs on more than anything else. As long as energy consumption does not meaningfully influenced timings, we're actually in very good shape. Most CPUs have constant time arithmetic (multiplication may be more problematic), and the only way data flows from secrets to timings are branches and the cache. All we have to do is avoid secret dependent branches and secret dependent indices. When energy does influence timings (frequency scaling, listening at an audio feed…), we're basically screwed, because no CPU instruction is constant energy. No way we can fix this without help from the hardware. > coding up a constant time crypto and especially making it portable over time and architectures, is nearly impossible. Sure. I'll settle for constant time now with my hardware. And I'll ask hardware vendors to pretty please sell me hardware that makes it possible. --- In the mean time, I'll see what this new finding actually leads. I don't anticipate major disruption to be honest. The attack demonstrated here required 36 hours, in the lab. This is a far cry from AES cache timing attacks which took 65 milliseconds. I'll wait and see what actually breaks in realistic threat models.
hinkley 4y ago
This stuff is complicated. You can still get some timing data by trying to schedule additional cryptographic work on the same core where some sensitive operation is going on, and looking at the delays you get.

What can an attacker do by knowing how many much queued crypto work there is?

by rictic 4y ago

What can an attacker do by knowing how many much queued crypto work there is?

There's lots of attacks currently on existing systems exploiting this. Leaking any information about other processes or supposedly hidden state of the system means you are leaking - and attacks always get better, not worse. The point is once you have shared, scheduled resources, others are going to get knowledge that they should not have. The rough idea is, say some other process is repeatedly running some known code with an unknown key, and you want to get that key. By fiddling with how you schedule your requests, you can interrupt or interject his work and your work, and the timing issues due to scheduling have been shown to leak things. Say one process is dealing with web requests, signing things fairly often. An attacker on the same machine can craft web requests, learn how the shared system is responding, and glean information about the web server via timing. This type of poking has been used to leak AES keys by exploiting things thought safe until they were on shared resources.

loup-vaillant 4y ago
You're making a general hand wavy argument here, but this is a rather specific issue. "Constant time" in cryptography means that there is no information flow from secrets to timings. Keys are secret. Plaintexts are secret. Ciphertexts, and most importantly their size, is public. You're basically saying that leaking public information is dangerous. This is the same as saying it should be private. In some specific cases you'd be right (I'm thinking of variable length audio encoding, where you could recover part of the conversations or voice prints from network analysis alone), and in these cases you mist hide sizes as well (basically use constant length audio encodings). But in the general case, message sizes are much less important that you make it sound.
- ChrisLomont 4y ago
  > Constant time" in cryptography means that there is no information flow from secrets to timings If "constant time" cryptography were achievable don't you think we'd have it and there'd be no more timing attacks breaking encryption schemes? "Constant time" cryptography is a mathematical abstraction, a goal, like "unbreakable cipher" and "unbreakable hash" and "frictionless surface." They don't occur in practice. This article breaks itself breaks a "constant time" cryptography with a timing attack. The problem is, as this paper demonstrates (along with many others) coding up a constant time crypto and especially making it portable over time and architectures, is nearly impossible. Caches, chip nuances, power draw mixed with power scaling, and other chip architecture complexity, contribute to attacks. Compiler changes, architecture changes (some even unpublished), architecture variety, user settings, even flaws in any part of the chain, all contribute to making holes in crypto in the real world. This paper [1], for example, is one of many that shows the "constant time" goal is likely not possible, and is certainly not possible in portable code. Here's [2] a paper tying to make simple AES "timing-attack resistant" - and you note they did not claim they could make it "constant time" because they realize that is not possible. "Timing-attack resistant" is at least professionally defensible. Here's [3] a paper referencing [2], trying to make systems more resistant to cross process leaks using Intel SGX to hide things that leaking. And here [4] is the attack on Intel SGX that shows there are still exploitable leaks. This type of chain is not unique. If you want to read literally thousands of papers on such things use google scholar or surf the cryptology eprint archive. Both make searching on such topics pretty easy. We could go on and on. The literature of crypto is littered with such threads - "constant time" crypto is the goal, but so is "unbreakable encryption" - both are mathematical fantasies that do not play out in practice. [1] https://arxiv.org/pdf/1711.08002.pdf https://arxiv.org/pdf/1711.08002.pdf [2] https://link.springer.com/chapter/10.1007/978-3-642-04138-9_1 https://link.springer.com/chapter/10.1007/978-3-642-04138-9_... [3] https://arxiv.org/pdf/1702.08719.pdf https://arxiv.org/pdf/1702.08719.pdf [4] https://arstechnica.com/information-technology/2020/03/hackers-can-steal-secret-data-stored-in-intels-sgx-secure-enclave/ https://arstechnica.com/information-technology/2020/03/hacke...
  - loup-vaillant 4y ago
    If you're going that route, everything is influenced by anything, and with a sufficiently advanced sensor array you could detect a butterfly flapping its wing across the globe. If instead we get serious for a minute, we can notice that cryptography is not magic, and neither is the way data flows from secrets to timings. Quite obviously, whether a program's timings depends on its inputs or not is a function of the hardware it runs on more than anything else. As long as energy consumption does not meaningfully influenced timings, we're actually in very good shape. Most CPUs have constant time arithmetic (multiplication may be more problematic), and the only way data flows from secrets to timings are branches and the cache. All we have to do is avoid secret dependent branches and secret dependent indices. When energy does influence timings (frequency scaling, listening at an audio feed…), we're basically screwed, because no CPU instruction is constant energy. No way we can fix this without help from the hardware. > coding up a constant time crypto and especially making it portable over time and architectures, is nearly impossible. Sure. I'll settle for constant time now with my hardware. And I'll ask hardware vendors to pretty please sell me hardware that makes it possible. --- In the mean time, I'll see what this new finding actually leads. I don't anticipate major disruption to be honest. The attack demonstrated here required 36 hours, in the lab. This is a far cry from AES cache timing attacks which took 65 milliseconds. I'll wait and see what actually breaks in realistic threat models.

hinkley 4y ago

This stuff is complicated. You can still get some timing data by trying to schedule additional cryptographic work on the same core where some sensitive operation is going on, and looking at the delays you get.