Provably Secure Countermeasures against Side-channel Attacks

Side-channel attacks exploit the fact that the implementations of cryptographic algorithms leak information about the secret key. In power analysis attacks, the observable leakage is the power consumption of the device, which is dependent on the processed data and the performed operations.\ignore{While Simple Power Analysis (SPA) attacks try to recover the
secret value by directly interpreting the power measurements with the
corresponding operations, Differential Power Analysis (DPA) attacks are more
sophisticated and aim to recover the secret value by applying statistical
techniques on multiple measurements from the same operation.} Masking is a
widely used countermeasure to thwart the powerful Differential Power Analysis (DPA) attacks. It uses random
variables called masks to reduce the correlation between the secret key and
the obtained leakage. The advantage with masking countermeasure is that one can formally prove its security under reasonable assumptions on the device leakage model. This thesis proposes several new masking schemes along with the analysis and improvement of few existing masking schemes.

The first part of the thesis addresses the problem of converting between Boolean and arithmetic masking. To protect a cryptographic algorithm which contains a mixture of Boolean and arithmetic operations, one uses both Boolean and arithmetic masking. Consequently, these masks need to be converted between the two forms based on the sequence of operations. The existing conversion schemes are secure against first-order DPA attacks only. This thesis proposes first solution to switch between Boolean and arithmetic masking that is secure against attacks of any order. Secondly, new solutions are proposed for first-order secure conversion with logarithmic complexity (${\cal O}(\log k)$ for $k$-bit operands) compared to the existing solutions with linear complexity (${\cal O}(k)$). It is shown that this new technique also improves the complexity of the higher-order conversion algorithms from ${\cal O}(n^2 k)$ to ${\cal O}(n^2 \log k)$ secure against attacks of order $d$, where $n = 2d+1$. Thirdly, for the special case of second-order masking, the running times of the algorithms are further improved by employing lookup tables.

The second part of the thesis analyzes the security of two existing Boolean masking schemes. Firstly, it is shown that a higher-order masking scheme claimed to be secure against attacks of order $d$ can be broken with an attack of order $d/2+1$. An improved scheme is proposed to fix the flaw. Secondly, a new issue concerning the problem of converting the security proofs from one leakage model to another is examined. It is shown that a second-order masking scheme secure in the Hamming weight model can be broken with a first-order attack on a device leaking in the Hamming distance model. This result underlines the importance of re-evaluating the security proofs for devices leaking in different models.