Algorithmic Countermeasures Against Passive and Active Physical Attacks

Symmetric key cryptography has been the corner stone in defending applications against cyber attacks. Ever since the proposal of the Data Encryption Standard (DES), people were able to protect their information technology using top of the line cryptography. Nevertheless, even the top of line symmetric cryptography is endangered when placed in an embedded device.

In 1999, an attack called differential power analysis was made public to the world. The attack abuses the relation between the power consumption of a device and the data it is processing. Using statistical methods, the authors showed it was possible to break DES using only a thousand calls to the primitive. Since the attack was so potent, it became obvious immediate countermeasures were needed. The attack also started a new field named side-channel analysis.

One countermeasure withstood the test of time and became a centre piece in the protection of hardware applications. This was masking. Masking is essentially an algorithmic countermeasure splitting the symmetric primitive in multiple parts. Each part seemingly operates on pure random data. However, when the parts are combined, the regular computation of the primitive can be seen again. The essential idea of masking is based on noise amplification. Observing multiple parts of the computation at the same time exponentially increases the noise, which was present due to measuring errors or noise inherent to the device. This allows industry to create countermeasures where attackers would need several millions if not billions of samples in order to break the device. Numbers which are not possible to obtain in practice.

Nevertheless, while masking provides practical protection. It comes with additional hardware costs such as latency and area which is often inhibiting for industry. Also the academic world is still invested to improve their understanding of masking. While there are some security models available to verify the masking, these security models are still crude. Often the models are too strong assuming the adversary has unlimited resources or queries to the primitive. The models are also often too weak as they don't include all the physical effects which occur in practice. In short, those security models do not properly reflect reality and this comes at the cost of potentially insecure maskings or a significant overhead in cost.

In this thesis, we question the perfect security of maskings and instead propose a model where the adversary only has some limited queries to the primitive. We propose an analysis method which allows us to verify the masking of a primitive in its entirety as opposed to methods which verify the security modularly. The analysis method is interesting on two accounts. The first is that it combines the field of side-channel analysis with symmetric key cryptanalysis. This shows a connection between the masking of a primitive and the primitive proper. The second relates to threshold implementations and the possibility to reduce the randomness cost of maskings. This cost has often been under-reported and under-investigated. Instead, with the new security model, we find that we can create higher-order threshold implementations, the security of which has been a long-standing open problem. This results in maskings which do not rely on any fresh randomness to secure its operation. We investigate such masking methods further to remove this randomness cost without shifting the cost somewhere else. 

The second research direction of the thesis concerns fault analysis. In 1997 Biham and Shamir showed that using a well-placed fault, it becomes possible to attack symmetric ciphers and retrieve their secret key. The authors showcased their attack on DES using only a few faulty ciphertexts. Fault attacks and their countermeasures have been largely under-studied. In this thesis, we propose a simple active adversary and study security models in order to verify the security of countermeasures. More specifically, we propose composable security models such that it becomes possible to secure any primitive. We also extend the analysis to combined attacks where adversaries can use both side-channel analysis and fault attacks. We then investigate extensions to the adversary in order to better capture realistic fault attacks and observe whether the composable security model still works with the new adversary. The result is a first step towards provable secure countermeasures against active and combined attacks.