5 ms·

This reads as if a poisoned CPU cache can indeed leak secrets and has been known for many years now? Am I reading that right?

by esaym 9y ago

nickpsecurity 9y ago
The folks that invented high-assurance security (TCSEC A1-class) were eliminating storage and timing channels best they could. An early reference was in VAX Security Kernel that tried to assess and mitigate timing channels. http://ix.cs.uoregon.edu/~butler/teaching/10F/cis607/papers/karger1991.pdf http://ix.cs.uoregon.edu/~butler/teaching/10F/cis607/papers/... http://ieeexplore.ieee.org/document/213271/ http://ieeexplore.ieee.org/document/213271/ Mainstream security professionals have always ignored such work dismissing it as red tape with no value or too costly. The early work preempted most problems, though, back in the 1980's-1990's by focusing on root causes. The same crowd that ignores them keep rediscovering the lessons in new forms while continuing to ignore them. (There are exceptions who pay attention.) Far as covert channels, the first technique I saw to systematically examine was Kemmerer's in 1983. It was one that made it into the first criteria for security certification. As in, it was mandatory to look for covert/side channels the best you could. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.462.316&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.462... https://fas.org/irp/nsa/rainbow/tg030.htm https://fas.org/irp/nsa/rainbow/tg030.htm So, the basic concepts have been known for decades under covert, channel analysis. The analysis technique established long ago was to identify every shared resource between two things in the system. If they could read/write to it, it was a potential, storage channel. It was a timing channel if they can manipulate its activity with a way to time that. Those are basic ones. So, you can just list everything, categorize them, and do the analysis by brute force. They'd have found the caching stuff quickly. Here's an example that should've happened a long time ago: https://eprint.iacr.org/2016/613.pdf https://eprint.iacr.org/2016/613.pdf
KirinDave 9y ago
Even longer. What's really wild is that they even got the rough proportion of security cost for losing it down to 5% of the numbers were seeing with today's security patches. I submitted this because I think their technique is preferred for lots of stuff distributed systems developers do with crypto primitives (as opposed to retpoline). There are lots of well-known things no one seems to know outside of Academia, like how generalized sorting is O(n) and compilers that can prove the correctness of real world code when it's written a specific way
- dgoldstein0 9y ago
  what's interesting to me about this paper is how many different things they had to worry about. Disable scheduling, pin to a single core, page coloring, no huge pages, disable hyperthreading, disabling frequency scaling, and lastly the lazy cleanup (I think that's all?). it's a pretty long list of kernel modifications and configuration, and I doubt these will ever be defaults.
- wallacoloo 9y ago
  Could you share some more information about generalized sorting in O(n)? Are you talking about algorithms like radix sort?
  - KirinDave 9y ago
    I replied above: https://news.ycombinator.com/item?id=16084178 https://news.ycombinator.com/item?id=16084178
- tyilo 9y ago
  > generalized sorting is O(n) What do you mean by generalized sorting and how isn't this affected by the comparison sorting lower bound? Do you have a source?
  - cryptonector 9y ago
    They probably mean the "postman sort", or whatever catchy name it goes by (radix sort, IIRC). That doesn't involve any comparisons between elements to be sorted. Think of how a postman sorts mail into P.O. boxes... you just algorithmically map a number to a row and column (bin), and deliver. This truly is O(N), but there's a catch: it doesn't work when you don't have bins to sort into, or when you don't know even how many bins you'll need. If you try to generalize this it becomes O(N log N).
    - KirinDave 9y ago
      Well... Actually. No. First of all, radix sort uses structural features to arrive at linear time, it doesn't incomplrtely sort the input. Secondly, I've tried to get the white paper exposed here and it generally goes over like a lead balloon but: http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... Is the technique. It's an imposing 80 page paper even dedicated educators like Edward Kmett has trouble explaining trivially, but there is a talk here by the author to help sum it up: https://www.youtube.com/watch?v=sz9ZlZIRDAg https://www.youtube.com/watch?v=sz9ZlZIRDAg We've had some of Henglein's associates here to talk about it, too. There is a Haskell implementation and it can really speed up certain types of operations. It's tricky to get the constants low in Haskell, but Kmett seems to have done a pretty good job.
tptacek 9y ago
Practical secret extraction from caches --- practical as in "papers documented C programs the authors wrote to verify their claims" --- go back to at least 2005. Here's a very well-known paper: https://www.cs.tau.ac.il/~tromer/papers/cache.pdf https://www.cs.tau.ac.il/~tromer/papers/cache.pdf It's the speculative execution side channel that's new. What we didn't fully grok was the idea that code that never really runs could leave predictable cache footprints.
- dgoldstein0 9y ago
  and that you can poison prediction state (branch predictor / branch target buffer etc) and cache state to force longer periods of processor speculation, leaving more room for unintended side effects.
- cryptonector 9y ago
  It's so obvious now, in retrospect :(
pas 9y ago
Cache as a channel: SSH over cache: https://www.youtube.com/watch?v=a9sGk7FtnYk https://www.youtube.com/watch?v=a9sGk7FtnYk

This reads as if a poisoned CPU cache can indeed leak secrets and has been known for many years now? Am I reading that right?

by esaym 9y ago

This reads as if a poisoned CPU cache can indeed leak secrets and has been known for many years now? Am I reading that right?

nickpsecurity 9y ago

The folks that invented high-assurance security (TCSEC A1-class) were eliminating storage and timing channels best they could. An early reference was in VAX Security Kernel that tried to assess and mitigate timing channels. http://ix.cs.uoregon.edu/~butler/teaching/10F/cis607/papers/karger1991.pdf http://ix.cs.uoregon.edu/~butler/teaching/10F/cis607/papers/... http://ieeexplore.ieee.org/document/213271/ http://ieeexplore.ieee.org/document/213271/ Mainstream security professionals have always ignored such work dismissing it as red tape with no value or too costly. The early work preempted most problems, though, back in the 1980's-1990's by focusing on root causes. The same crowd that ignores them keep rediscovering the lessons in new forms while continuing to ignore them. (There are exceptions who pay attention.) Far as covert channels, the first technique I saw to systematically examine was Kemmerer's in 1983. It was one that made it into the first criteria for security certification. As in, it was mandatory to look for covert/side channels the best you could. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.462.316&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.462... https://fas.org/irp/nsa/rainbow/tg030.htm https://fas.org/irp/nsa/rainbow/tg030.htm So, the basic concepts have been known for decades under covert, channel analysis. The analysis technique established long ago was to identify every shared resource between two things in the system. If they could read/write to it, it was a potential, storage channel. It was a timing channel if they can manipulate its activity with a way to time that. Those are basic ones. So, you can just list everything, categorize them, and do the analysis by brute force. They'd have found the caching stuff quickly. Here's an example that should've happened a long time ago: https://eprint.iacr.org/2016/613.pdf https://eprint.iacr.org/2016/613.pdf

KirinDave 9y ago

Even longer. What's really wild is that they even got the rough proportion of security cost for losing it down to 5% of the numbers were seeing with today's security patches. I submitted this because I think their technique is preferred for lots of stuff distributed systems developers do with crypto primitives (as opposed to retpoline). There are lots of well-known things no one seems to know outside of Academia, like how generalized sorting is O(n) and compilers that can prove the correctness of real world code when it's written a specific way

dgoldstein0 9y ago
what's interesting to me about this paper is how many different things they had to worry about. Disable scheduling, pin to a single core, page coloring, no huge pages, disable hyperthreading, disabling frequency scaling, and lastly the lazy cleanup (I think that's all?). it's a pretty long list of kernel modifications and configuration, and I doubt these will ever be defaults.
wallacoloo 9y ago
Could you share some more information about generalized sorting in O(n)? Are you talking about algorithms like radix sort?
- KirinDave 9y ago
  I replied above: https://news.ycombinator.com/item?id=16084178 https://news.ycombinator.com/item?id=16084178
tyilo 9y ago
> generalized sorting is O(n) What do you mean by generalized sorting and how isn't this affected by the comparison sorting lower bound? Do you have a source?
- cryptonector 9y ago
  They probably mean the "postman sort", or whatever catchy name it goes by (radix sort, IIRC). That doesn't involve any comparisons between elements to be sorted. Think of how a postman sorts mail into P.O. boxes... you just algorithmically map a number to a row and column (bin), and deliver. This truly is O(N), but there's a catch: it doesn't work when you don't have bins to sort into, or when you don't know even how many bins you'll need. If you try to generalize this it becomes O(N log N).
  - KirinDave 9y ago
    Well... Actually. No. First of all, radix sort uses structural features to arrive at linear time, it doesn't incomplrtely sort the input. Secondly, I've tried to get the white paper exposed here and it generally goes over like a lead balloon but: http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... Is the technique. It's an imposing 80 page paper even dedicated educators like Edward Kmett has trouble explaining trivially, but there is a talk here by the author to help sum it up: https://www.youtube.com/watch?v=sz9ZlZIRDAg https://www.youtube.com/watch?v=sz9ZlZIRDAg We've had some of Henglein's associates here to talk about it, too. There is a Haskell implementation and it can really speed up certain types of operations. It's tricky to get the constants low in Haskell, but Kmett seems to have done a pretty good job.

tptacek 9y ago

Practical secret extraction from caches --- practical as in "papers documented C programs the authors wrote to verify their claims" --- go back to at least 2005. Here's a very well-known paper: https://www.cs.tau.ac.il/~tromer/papers/cache.pdf https://www.cs.tau.ac.il/~tromer/papers/cache.pdf It's the speculative execution side channel that's new. What we didn't fully grok was the idea that code that never really runs could leave predictable cache footprints.

dgoldstein0 9y ago
and that you can poison prediction state (branch predictor / branch target buffer etc) and cache state to force longer periods of processor speculation, leaving more room for unintended side effects.
cryptonector 9y ago
It's so obvious now, in retrospect :(

pas 9y ago

Cache as a channel: SSH over cache: https://www.youtube.com/watch?v=a9sGk7FtnYk https://www.youtube.com/watch?v=a9sGk7FtnYk