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
RainbowFault injection attacksMultivariate schemesPost-quantum cryptographyCortex M4 implementation
Contact author(s)
thomas aulbach @ ur de
History
2022-05-23: received
Short URL
https://ia.cr/2022/632
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2022/632}},
      url = {https://eprint.iacr.org/2022/632}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.