A comprehensive study of multiple deductions-based algebraic trace driven cache attacks on AES

• We propose a model for the key recovery in trace driven cache attacks (TDCAs).
• We describe the technique to combine algebraic attacks with TDCA.
• We construct a mathematical model to estimate the complexity in TDCA on AES.
• We conduct the most efficient TDCA on AES-128 under three scenarios.
• We conduct the first successful TDCA on AES-192/256.

Existing trace driven cache attacks (TDCAs) can only analyze the cache events in the first two rounds or the last round of AES, which limits the efficiency of the attacks. Recently, Zhao et al. proposed the multiple deductions-based algebraic side-channel attack (MDASCA) to cope with the errors in leakage measurements and to exploit new leakage models. Their preliminary results showed that MDASCA can improve TDCAs and attack the AES implemented with a compact lookup table of 256 bytes. This paper performs a comprehensive study of MDASCA-based TDCAs (MDATDCA) on most of the AES implementations that are widely used. First, the key recovery in TDCA is depicted by an abstract model regardless of the specific attack techniques. Then, the previous work of TDCAs on AES is classified into three types and its limitations are analyzed. How to utilize the cache events with MDATDCA is presented and the overhead is also calculated. To evaluate MDATDCA on AES, this paper constructs a mathematical model to estimate the maximal number of leakage rounds that can be utilized and the minimal number of cache traces required for a successful MDATDCA. Extensive experiments are conducted under different implementations, attack scenarios and key lengths of AES. The experimental results are consistent with the theoretical analysis. Many improvements are achieved. For the first time, we show that TDCAs on AES-192 and AES-256 become possible with the MDATDCA technique. Our work attests that combining TDCAs with algebraic techniques is a very efficient way to improve cache attacks.