International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Separating Oil and Vinegar with a Single Trace: Side-Channel Assisted Kipnis-Shamir Attack on UOV

Authors:
Thomas Aulbach , University of Regensburg, Regensburg, Germany
Fabio Campos , RheinMain University of Applied Sciences, Wiesbaden, Germany; Radboud University, Nijmegen, Netherlands
Juliane Krämer , University of Regensburg, Regensburg, Germany
Simona Samardjiska , Radboud University, Nijmegen, Netherlands
Marc Stöttinger , RheinMain University of Applied Sciences, Wiesbaden, Germany
Download:
DOI: 10.46586/tches.v2023.i3.221-245
URL: https://tches.iacr.org/index.php/TCHES/article/view/10962
Search ePrint
Search Google
Abstract: Due to recent cryptanalytical breakthroughs, the multivariate signature schemes that seemed to be most promising in the past years are no longer in the focus of the research community. Hence, the cryptographically mature UOV scheme is of great interest again. Since it has not been part of the NIST process for standardizing post-quantum cryptography so far, it has not been studied intensively for its physical security.In this work, we present a side-channel attack on the latest implementation of UOV. In the first part of the attack, a single side-channel trace of the signing process is used to learn all vinegar variables used in the computation. Then, we employ a combination of the Kipnis-Shamir attack and the reconciliation attack to reveal the complete secret key. Our attack, unlike previous work, targets the inversion of the central map and not the subsequent linear transformation. It further does not require the attacker to control the message to be signed.We have verified the practicality of our attack on a ChipWhisperer-Lite board with a 32-bit STM32F3 ARM Cortex-M4 target mounted on a CW308 UFO board. We publicly provide the code and both reference and target traces. Additionally, we discuss several countermeasures that can at least make our attack less efficient.
BibTeX
@article{tches-2023-33288,
  title={Separating Oil and Vinegar with a Single Trace: Side-Channel Assisted Kipnis-Shamir Attack on UOV},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 3},
  pages={221-245},
  url={https://tches.iacr.org/index.php/TCHES/article/view/10962},
  doi={10.46586/tches.v2023.i3.221-245},
  author={Thomas Aulbach and Fabio Campos and Juliane Krämer and Simona Samardjiska and Marc Stöttinger},
  year=2023
}