Non deterministic caches: a simple and effective defense against side channel attacks

Side channel cryptanalysis has received significant attention lately, because it provides a low-cost and facile way to reveal the secret information held on a secure computing system. One particular type of side channel attacks, called cache-based side channel attacks, aims to deduce information about the state of a cryptographic algorithm or its key by observing the data-dependent behavior of a microprocessor's cache memory. These attacks have been proven successful and very hard to protect against. In this paper, we introduce the use of the Cache Decay approach as an aid to guard against cache-based side channel attacks. Cache Decay controls the lifetime (called decay interval) of the cache items and was initially proposed for cache power leakage savings. By randomly selecting the decay interval of the cache, we actually create caches with non-deterministic behavior in regard to their statistics. Thus, as we demonstrate, multiple runs of the same algorithm (performing on the same input) will result in different cache statistics, defending against the attacker and reinforcing the protection offered by the system. In our work, we use a cycle-based processor simulator, enhanced with the required modifications, in order to evaluate our proposal and show that our technique can be used effectively to protect against cache-based side channel attacks.