Faster Leakage Detection and Exploitation

Higher-order side-channel analysis has become very widespread due to the popularity of side channel countermeasures. However, these analysis methods become increasingly expensive in terms of computation time if the attacker has no prior knowledge about when leakage occurs. In many realistic scenarios, the attacker only has a global trigger signal, resulting in long leakage traces. Long traces result in very long analysis time, since the computational complexity of analysis grows in polynomial of the trace length with degree d+1 of the order of the attack. In this paper, we propose a novel, intuitive, yet efficient algorithm that trades the abundance in the number of leakage traces and the signal-to-noise ratio into computational efficiency during processing. The proposed algorithm reaches an exponential improvement of O(log(N)) for the processing time, where N is the number of samples in the trace. The algorithm can be naturally extended to higher-order attacks reducing the complexity from O(N{d+1}) to O(N{d}log(N)).