As far as I understand it, Spectre is caused by speculative execution not completely undoing all side effects of an incorrect branch prediction (specifically, not undoing a CPU cache write). Doesn't that mean that it would be relatively simple to fix in future hardware, simply by ensuring that any cache entries that appeared due to speculative execution are purged in the event of an incorrect prediction? I read on an LWN article that there might be a problem with cache eviction behavior too; if so, what would that be?
Any side-effect of speculative execution that is visible can be used. There are some (perhaps many) side-effects that don't involve the cache at all.
From the Spectre whitepaper:
... In this section we explore potential combinations and conclude that virtually any observable effect of speculatively executed code can potentially lead to leaks of sensitive information
Spectre vulnerabilities do not necessarily need to involve caches. Instructions whose timing depends on the values of the operands may leak information on the operands. In the following example, the multiplier is occupied by the speculative execution of
multiply R1, R2. The timing of when the multiplier becomes available for
multiply R3, R4(either for out-of-order execution or after the misprediction is recognized) could be affected by the timing of the first multiplication, revealing information about
if (false but mispredicts as true) multiply R1, R2 multiply R3, R4