Practicality and Application of the Algebraic Side-Channel Attack

Algebraic Side-Channel Attack (ASCA) is a side-channel attack that models the cryptographic algorithm and side-channel leakage from a system as a set of equations, then solves for the secret key. Unlike pure side-channel attacks, ASCA has low data complexity and can succeed in unknown plaintext/ciphertext scenarios. However, past research on ASCA has been done on either 8-bit microcontroller data or simulated data. In this dissertation, we explore the application and feasibility of error tolerant ASCA on a field-programmable gate array (FPGA). FPGAs run faster and are more difficult for the encryption power trace to be isolated, so it presents more of a challenge for the attacker. Our work is the first to show that FPGAs are as susceptible to ASCA as 8-bit micro-controllers. As a result, the attack could have widespread implications since it may be applicable to other hardware platforms as well. While algebraic side-channel attack (ASCA) has been successful in breaking simple cryptographic algorithms, it has never been done on larger or more complex algorithms such as Twofish. Compared to other algorithms that ASCA has been used on, Twofish is more difficult to attack due to the key-dependent S-boxes as well as the complex key scheduling. In this dissertation, we demonstrate the first algebraic side-channel attack on Twofish, and examine the importance of side-channel information in getting past the key-dependent S-boxes and the complex key scheduling. While ASCA is feasible on a variety of platforms, it is susceptible to error and the complexity of the model may drastically increase the runtime as well as the memory consumption. In this dissertation, we explore the attack by examining the importance of various Hamming weights in terms of success of the attack, which also allows us to gain insights into possible areas of focus for countermeasures, as well as successfully launch ASCA on AES with a larger error tolerance.