Indeed, having no speculative execution, or just having caches separated by trust domains, would make Spectre impossible. This would make the whole promise of 'securely virtualized hardware' largely disappear, though. For guaranteed isolation, you'd have to have a physical core (or set of cores) per trust domain.
With trust domains sliced pretty thinly, e.g. a domain per JS-executing web page, it's hard. AFAICT, reseting the caches when switching processes (that is, trust domains) sort of mitigates this attack at a relative low cost, a performance hit instead of having to replace the CPU.
Wrong.
Even if you separate different privilege levels onto different physical computers, and they only exchange information by message passing, then they are likely to leak information merely from the message timing.
The message timing may indicate what has been cached or pre-computed on the privileged machine. So it's a matter of sending messages from the malicious machine such that they manipulate what is cached/pre-computed on the privileged machine based on the contents of privileged information.
Manipulating what is cached/pre-computed is generally not too hard for an attacker; the real trick is doing so based on the contents of privileged information. But it's conceivable that you could extract some information from a database by determining which pages of a btree got cached when you try (and fail) to look at something you're not supposed to. It might be hard to extract the 1000th byte of a big text field that way, but you might be able to find out whether "joe" or "sally" is the person you're looking for.
Sounds a bit difficult in practice, but computing (perhaps more than any other field) tends to quickly eliminate the difference between theory and practice when the motivation is strong enough.
The more you trust the code you run alongside other code, the less precautions like that you have to take. Delimiting security domains right is hard, though.
On a related topic, I know someone who worked on CPU/FPGA hybrid architectures. The idea was to move processes between CPUs and FPGAs. Awesome stuff, realtime processes offloaded to the FPGA get to run completely off the CPU, with ridiculously low latencies. The issue is that you really have to design your code for it.
How about 16 big core and 4096 small cores that don't have speculative execution?
https://content.riscv.org/wp-content/uploads/2017/12/Tue1136...
Perhaps one day we'll talk about how many cores are allocated to a program rather than the other way around. OTOH even their chip will have shared caches. Spectre is achieved via speculation but communicates via side channel of the cache, so it's not clear this is a whole lot better.
What nobody wants to say is that the real problem is running untrusted code. They don't want to say it because Apps and JS are so many peoples bread an butter these days.
Course, in the context of the larger thread, I can't help but wonder how much more attack surface this would tend to create.
We could consider something like Tilera chips working together with privileged "general compute" chips, the same way as current machines work with separate GPUs as privilege "vector compute" chips.
Ok, fine, in some abstract sense. But they are fundamental to realizations of computing that involve shared resources, as the rest of your comment is getting at.
We want to share resources for efficiency, which is going to be the constant pressure that keeps leaks coming.
Reality is always about compromises and tradeoffs. Now we see how the balance point is being pushed back closer to the pole of "security". A new equilibrium will eventually appear.
(You can see the very same process in e.g. encryption algorithms: tradeoffs between performance and security, and phasing out of solutions that yielded either to finding of logical flaws or increases in available computing power.)
As far as sharing cache goes, there can be 4096 PCIDs/ASIDs AFAICT, maybe there should be more. Tying speculative execution to PCIDs/ASIDs might not be too bad of an idea.. if it isn't done already. Better CPU security models that reason about cache and speculative execution should be enough to solve this problem.
Disable TSC access, lower clock_gettime precision, make clock_gettime return fuzzy (randomized) time. Randomize CPU frequency to make usage of spinning threads for time measurement hard. Insert randomized delays into untrusted binaries, kinda like DTrace inserts probes (i.e. imagine a JavaScript JIT that inserts no-ops all over the compiled code, and randomly changes these to random sleeps). etc.
A practical vision of computing without these things is challenging, though!
At least on the server side, that's realistic. Big companies like Google already run their own trusted code on their own hardware. For everyone else, it's not impossible to move from VPS hosting to "bare metal cloud" like Scaleway offers.
(Vision for the Future™: instead of their tied-to-Linux "someone else's Raspberry Pi" experience, it would be a bunch of tiny single core processors, each connected to their own tiny DRAM chip. You upload unikernel images or CloudABI binaries (that would be then wrapped into unikernels) into the Cloud™, where the load balancer boots up your images on-demand on as many of these tiny computers as needed. RAM is zeroed before boot.)
The other big environment with tons of untrusted code is of course the web browser. This is significantly more ridiculous, but: why not embed a ton of tiny simple in-order ARM cores without any shared cache into desktop processors, and run JS/WASM on them? (One core used per origin per site) :D
I definitely chuckled. :) On a more serious note- I'd bet at least a couple bucks it would be possible (albeit super weird and difficult) to channel information through hardware-acceleration mechanisms. Lots of rendering happens on the GPU these days.
rr does just this! I think it uses the "instructions retired" performance counter as its "fake time"; that turns out to be deterministic enough for its purposes. Whether it's deterministic enough in a security context, I don't know for sure.
But this approach, though it can run threaded software, will not let untrusted software (which should really mean all software!) use more than one real core or hardware thread.
Only if you define 'deterministically' to mean 'determined only by the program's own legitimately accessible context'. These timing side-channel attacks work precisely because the processor performs in a deterministic and detectable manner, but does so based on information which the attacking program should not be able to access.
The program is equivalent to a pure function from (state, events) to (state, actions) and the computing device that evaluates this function can't leak any information to the function without evaluating it incorrectly. It can still leak information in how long it takes to evaluate the function, but there is no direct way to get this information back into the function.
You could ask the user what time it is, or how long something took, but that starts to look suspicious fast!
You just need to refine statistics. The underlying program can‘t be solved in a physical universe.
If the randomizations have such an effect that data sniffing is still possible but its speed is 1 bit per week, trying to sniff something interesting becomes impractical. (Or not; depends on your threat model.)
Given that "silicon is cheap" why don't we work around these problems by ensuring that processes within different security domains run on separate cores with their own cache and branch prediction cache? At context-switch, flush all that.
This is similar to eval(). The operating system always needs a way to load new code, but you don't need it in the language, or least not in a sandboxed language.
It's also more consistent with the abstract programming model that we typically use. A new version of a function is normally considered compatible with the previous one based on the values it returns, not the details of its timing (within reason).
We often depend on this correctness vs. performance separation to be able to make performance improvements easily. It's very convenient to be able to swap in faster code without worrying that you'll break any callers. It's also convenient not to have to write constant-time functions (to avoid information leaks) most of the time.
Industry reality is that we are still fighting stack overflow bugs 40 years after safe languages were invented.
Timing attacks are going to be around a long time.
As devices become more powerful and more connected, thus increasing the attack surface and the potential losses form them being cracked, the cost-based analysis will start to prioritize security more.
The tools for writing dramatically less brittle code are there, but there's the cost of switching. It needs to become lower than the potential losses. And with the current state of the industry, the losses and lawsuits are surely coming. Remember what it took to make an average e-commerce website become reasonably secure.
Getting people to use heavy static analysis is an uphill battle. Getting people to use prepared statements to prevent SQL injection is an uphill battle! But nobody should take then lesson that we are woefully unprepared to deal with timing leaks via program analysis and that we've entered some new unfamiliar territory.
For example, here's Z in C++14, used to compute 5 factorial: https://godbolt.org/g/se5B8u
I think proving that no recursion exists should be relatively simple, just keep following the call graph and keep a set of the nodes (functions) called; you either reach the terminal node(s), or reach an already-visited node again, which means a recursion exists.
[0] https://en.wikipedia.org/wiki/Total_functional_programming
But sometimes it is hard, and I'm afraid it's equivalent to the halting problem in general case.
Without recursion, though, finding the maximal depth of the call graph is definitely solvable, and likely not even very hard.
Side note: an interesting case is the Stable Marriage Problem. It's easy to write the O(n) algorithm and prove its bound, but it's hard to translate into a bounded recursive algorithm that does the same thing.
(At least as far as I understand -- I searched it on Stack Overflow and that's what it said, and I've tried the problem itself. A Coq fanatic insisted that "if you can prove the run time is bounded it's easy to write the bounded recursive equivalent" but somehow that never translated into an actual insight on how to do it.)
There are still cases where you can prove that a recursion is bounded (I suppose something like dependent types could help here). There are definitely cases where you can prove that a loop is bounded, because the semantics of the language requires them to: a loop with a counter (not otherwise mutated), iteration over a known finite structure, etc.
Well, both C++ and Haskell allow you to use compiler features that are undecidable in general case, but usually work well in practical cases. Also, if e.g. your recursion / loop analysis is taking too long, you can just stop the analyzer. If the code can't be reasonably proved right, it should be considered wrong (with a chance of a false negative).
Timing leaks are an absolutely fundamental flaw of computers. It may be the case that this specific instance of speculation-based attacks that leak information via timing channels can be fixed by stopping speculation or by complete rollback of speculated state including caches. "It's the chip's fault" is true for Spectre and Meltdown, yes, and it will take some time for Intel and other manufacturers to design new chips that stop leaking information due to speculation.
However, timing attacks are probably everywhere. They are covert channels that subvert language safety. The question isn't whether information leaks, but what and how fast. How are we going to deal with them comprehensively at the language level? I don't know.