The security of bilinear pairings against implementation attacks such as side channel and fault attacks is largely an uncharted area of research. Apart from one publication on the topic, coverage of this area is non-existent. Armed with the fact that the number of applications based on bilinear pairings is ever-increasing, the bilinear pairing algorithms themselves are constantly being enhanced and optimised such that they are commercially viable, and the fact that the current research on elliptic curve primitives is not applicable to bilinear pairings, makes this a vital topic for further investigation and analysis.
This research aims to begin to fill this void. Along with addressing some of the more subtle aspects of implementation attacks, this research presents an investigation into the security of bilinear pairings against implementation attacks. Specifically, the process of performing the data analysis phase of a Side Channel Attack (SCA) is analysed. A theoretical fault attack on the Digital Signature Algorithm (DSA) is examined and implemented in practice. A number of candidate bilinear pairing algorithms are assessed for vulnerability to the SCA, first-order power analysis, which passively monitors the power consumption of a device. Furthermore, a number of candidate bilinear pairing algorithms are assessed for vulnerability to fault analysis, which seeks to actively disrupt the normal execution of an algorithm.
Our principal results can be summarised as follows: We suggest computational improvements to the Differential Power Analysis (DPA) data analysis process, which can reduce the number of operations by up to 97%. We demonstrate how a theoretical attack on the DSA using lattice reduction can be executed in practice with the aid of a glitch attack. We propose a novel SCA technique to attack various finite field operations. This attack involves analysing the structural evolution of finite field operations and is based on Correlation Power Analysis (CPA), which is a form of first-order power analysis. We examine the Tate, Ate and nT pairing for vulnerability to first-order power analysis and discover that given certain parameter choice, the Tate and Ate pairing can provide options for minimising an attack, whereas the nT pairing provides no such options and can be attacked from all parameter positions. We investigate the existence of opportunistic faults on the Weil, Tate and nT pairing and discover two types of fault attacks that can be successfully applied to the Weil and n pairing to reveal the secret key. This weakness is attributed to the absence or simplicity of the final exponentiation employed, highlighting the fact that the final exponentiation is a vital operation in bilinear pairing computation and in particular adds a layer of protection to pairings. This fact is further compounded in the proof that the Tate pairing is immune to such fault attacks. Finally, we provide recommendations based on our findings for secure bilinear pairing implementation in terms of power and fault analysis.