International Association for Cryptologic Research

International Association
for Cryptologic Research


Single-Trace Side-Channel Attacks on the Toom-Cook: The Case Study of Saber

Yanbin Li , Nanjing Agricultural University, Nanjing, China
Jiajie Zhu , Zhejiang Lab, Hangzhou, China
Yuxin Huang , Nanjing Agricultural University, Nanjing, China
Zhe Liu , Zhejiang Lab, Hangzhou, China; Nanjing University of Aeronautics and Astronautics, Nanjing, China
Ming Tang , Wuhan University, Wuhan, China
DOI: 10.46586/tches.v2022.i4.285-310
Search ePrint
Search Google
Presentation: Slides
Abstract: The Toom-Cook method is a well-known strategy for building algorithms to multiply polynomials efficiently. Along with NTT-based polynomial multiplication, Toom-Cook-based or Karatsuba-based polynomial multiplication algorithms still have regained attention since the start of the NIST’s post-quantum standardization procedure. Compared to the comprehensive analysis done for NTT, the leakage characteristics of Toom-Cook have not been discussed. We analyze the vulnerabilities of Toom-Cook in the reference implementation of Saber, a third round finalist of NIST’s post-quantum standardization process. In this work, we present the first single-trace attack based on the soft-analytical side-channel attack (SASCA) targeting the Toom-Cook. The deep learning-based power analysis is combined with SASCA to decrease the number of templates since there are a large number of similar operations in the Toom-Cook. Moreover, we describe the optimized factor graph and improved belief propagation to make the attack more practical. The feasibility of the attack is verified by evaluation experiments. We also discuss the possible countermeasures to prevent the attack.
  title={Single-Trace Side-Channel Attacks on the Toom-Cook: The Case Study of Saber},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 4},
  author={Yanbin Li and Jiajie Zhu and Yuxin Huang and Zhe Liu and Ming Tang},