December 5, 2017 –
Title: Practicality and Application of the Algebraic Side-Channel Attack
Student: Chujiao Ma
Major Advisor: Dr. John Chandy
Associate Advisors: Dr. Laurent Michel, Dr. Bing Wang
Location: ITEB 401
Side-channel attacks break cryptographic algorithms by performing statistical analysis on information correlated with the secret key during encryption, such as timing, power consumption or electromagnetic waves. While it is popular due to its passive and non-invasive nature, it is vulnerable to noise in the system and measuring equipment. To reduce the limitations of the attack, it is often combined with other methods such as algebraic analysis. This proposal focuses on the practicality and application of algebraic side-channel attack (ASCA) to retrieve cryptography keys.
ASCA models the cryptographic algorithm as well as the side-channel information as a set of equations that are put through a solver to solve for the secret key. The proposal first considers the application of ASCA to different algorithms. ASCA was performed with side-channel information from faults injected in the system and proven to be successful on simple algorithms such as LED as well as GOST. ASCA was also performed on TwoFish and AES with side-channel information collected from power consumptions, which are more difficult to detect.
ASCA allows the attack to succeed in unknown plaintext/ciphertext scenarios and has low data complexity. While the attack can succeed for algorithms of various complexity, it is susceptible to error from the side-channel information. We attempt to mitigate the effect of error by exploiting the incomplete diffusion feature in one AES round using incomplete diffusion analytical side-channel analysis (IDASCA). In addition to different ways to exploit the data, we also explored using different solvers. While ASCA has traditionally been solved with SAT solvers, we introduce the use of a Constraint-Programming (CP) solver which allows us to have a simpler model with better error tolerance.
Since ASCA is feasible against a variety of algorithms and is error-tolerant, we then examined how the structure of the algorithm (confusion, diffusion, non-linearity, complexity of operations) affects the attack, which will not only give us ideas on how to improve the attack but also on different ways countermeasures can be designed.