Secure implementation of block ciphers against physical attacks

Overview & Synopsis

Since their introduction at the end of the 1990s, side-channel attacks are considered to be a major threat against cryptographic implementations. Higher-order masking is considered to be one the most popular existing protection strategies. It consists in separating each internal variable in the cryptographic computation into several random variables. However, the use of this type of protection entails a considerable efficiency loss, making it unusable for industrial solutions. The goal of this thesis is to reduce the gap between theoretical solutions, proven secure, and efficient implementations that can be deployed on embedded systems. More precisely, I am analysing the protection of block ciphers such as the AES encryption scheme, where the main issue is to protect the s-boxes with minimal overhead in costs. I have tried, first, to find optimal mathematical representations in order to evaluate the s-boxes while minimizing the number of multiplications (a decisive parameter for masking schemes, but also for homomorphic encryption). For this purpose, I have defined a generic method to decompose any function on any finite field with a low multiplicative complexity. These representations can, then, be efficiently evaluated with higher-order masking. The flexibility of the decomposition technique allows also easy adjusting to the developer’s needs. Secondly, I have proposed a formal method for measuring the security of circuits evaluating masking schemes. This technique allows to define with exact precision whether an attack on a protected circuit is feasible or not. Unlike other tools, its response time is not exponential in the circuit size, making it possible to obtain a security proof regardless of the masking order used. Furthermore, this method can strictly reduce the use of costly tools in randomness required for reinforcing the security of masking operations. Finally, we present the implementation results with optimizations both on algorithmic and programming fronts. We particularly employ a bitslice implementation strategy for evaluating the s-boxes in parallel. This strategy leads to speed record for implementations protected at high order. The different codes are developed and optimized under ARM assembly, one of the most popular programming language in embedded systems such as smart cards and mobile phones. These implementations are also available online for public use.