  Cache randomization has recently been revived as a promising defense against
conflict-based cache side-channel attacks. As two of the latest
implementations, CEASER-S and ScatterCache both claim to thwart conflict-based
cache side-channel attacks using randomized skewed caches. Unfortunately, our
experiments show that an attacker can easily find a usable eviction set within
the chosen remap period of CEASER-S and increasing the number of partitions
without dynamic remapping, such as ScatterCache, cannot eliminate the threat.
By quantitatively analyzing the access patterns left by various attacks in the
LLC, we have newly discovered several problems with the hypotheses and
implementations of randomized caches, which are also overlooked by the research
on conflict-based cache side-channel attack.
  However, cache randomization is not a false hope and it is an effective
defense that should be widely adopted in future processors. The newly
discovered problems are corresponding to flaws associated with the existing
implementation of cache randomization and are fixable. Several new defense
techniques are proposed in this paper. our experiments show that all the newly
discovered vulnerabilities of existing randomized caches are fixed within the
current performance budget. We also argue that randomized set-associative
caches can be sufficiently strengthened and possess a better chance to be
actually adopted in commercial processors than their skewed counterparts as
they introduce less overhaul to the existing cache structure.
