TY - JOUR AU - Li, Yanbin AU - Zhu, Jiajie AU - Huang, Yuxin AU - Liu, Zhe AU - Tang, Ming PY - 2022/08/31 Y2 - 2024/03/28 TI - Single-Trace Side-Channel Attacks on the Toom-Cook: The Case Study of Saber JF - IACR Transactions on Cryptographic Hardware and Embedded Systems JA - TCHES VL - 2022 IS - 4 SE - Articles DO - 10.46586/tches.v2022.i4.285-310 UR - https://tches.iacr.org/index.php/TCHES/article/view/9821 SP - 285-310 AB - <p>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.</p> ER -