Bitslice software implementation of KeeLoq as a side-channel countermeasure

Abstract

Bitslice is a non-conventional way to implement algorithms using a scalar processor as a {SIMD}. It involves breaking down the algorithm into logical bit operations so that N parallel <operations are possible on a single N-bit microprocessor. It is applied to encryption algorithms, processing N consecutive blocks simultaneously, to achieve high throughput. Security applications using the {KeeLoq} algorithm are not suitable to traditional bitslice implementations because usually there are no N blocks to be processed. We propose a {KeeLoq} bitslice implementation, derived from its Algebraic Normal Form, for a single input block as a countermeasure against side-channel attacks. Our experimental results show there is no timing information leaked with an improvement factor of 3.01 in executed cycles. However, the implementation is still vulnerable to differential side-channel analysis, so we propose a secured variation that increases the resistance against differential power analysis without timing leakage, with a lower improvement factor of 1.21 in executed cycles.