Recovering Rainbow's Secret Key with a First-Order Fault Attack

Thomas Aulbach; Tobias Kovats; Juliane Krämer; Soundes Marzougui

Paper 2022/632

Recovering Rainbow's Secret Key with a First-Order Fault Attack

Thomas Aulbach, Tobias Kovats, Juliane Krämer, and Soundes Marzougui

Abstract

Rainbow, a multivariate digital signature scheme and third round finalist in NIST's PQC standardization process, is a layered version of the unbalanced oil and vinegar (UOV) scheme. We introduce two fault attacks, each focusing on one of the secret linear transformations $T$ and $S$ used to hide the structure of the central map in Rainbow. The first fault attack reveals a part of $T$ and we prove that this is enough to achieve a full key recovery with negligible computational effort for all parameter sets of Rainbow. The second one unveils $S$ , which can be extended to a full key recovery by the Kipnis-Shamir attack. Our work exposes the secret transformations used in multivariate signature schemes as an important attack vector for physical attacks, which need further protection. Our attacks target the optimized Cortex-M4 implementation and require only first-order instruction skips and a moderate amount of faulted signatures.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. 13th International Conference on Cryptology, AfricaCrypt 2022
Keywords: Rainbow Fault injection attacks Multivariate schemes Post-quantum cryptography Cortex M4 implementation
Contact author(s): thomas aulbach @ ur de
History: 2022-05-23: received
Short URL: https://ia.cr/2022/632
License: CC BY

BibTeX

@misc{cryptoeprint:2022/632,
      author = {Thomas Aulbach and Tobias Kovats and Juliane Krämer and Soundes Marzougui},
      title = {Recovering Rainbow's Secret Key with a First-Order Fault Attack},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/632},
      year = {2022},
      url = {https://eprint.iacr.org/2022/632}
}