You cannot hide behind the mask: Power analysis on a provably secure s-box implementation

Power analysis has shown to be successful in breaking symmetric cryptographic algorithms implemented on low resource devices. Prompted by the breaking of many protected implementations in practice, researchers saw the need of validating security of implementations with formal methods. Three generic S-box implementation methods have been proposed by Prouff el al., together with formal proofs of their security against 1st or 2nd-order side-channel analysis. These methods use a similar combination of masking and hiding countermeasures. In this paper, we show that although proven resistant to standard power analysis, these implementation methods are vulnerable to a more sophisticated form of power analysis that combines Differential Power Analysis (DPA) and pattern matching techniques. This new form of power analysis is possible under the same assumptions about power leakage as standard DPA attacks and the added complexity is limited: our experiments show that 900 traces are sufficient to break these algorithms on a device where 150 traces are typically needed for standard DPA. We conclude that the defense strategies-hiding by repeating operations for each possible value, and masking and hiding using the same random number-can create new vulnerabilities.