Paper 2022/1692

Secret Key Recovery Attacks on Masked and Shuffled Implementations of CRYSTALS-Kyber and Saber

Linus Backlund, Royal Institute of Technology
Kalle Ngo, Royal Institute of Technology
Joel Gärtner, Royal Institute of Technology
Elena Dubrova, Royal Institute of Technology
Abstract

Shuffling is a well-known countermeasure against side-channel analysis. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel analysis more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the secret key was reported. In this paper, we present an attack that can recover the secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack. We capture a power trace during the execution of the decapsulation algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted. By recovering messages contained in k ∗ l chosen ciphertexts constructed using a new method based on error-correcting codes with length l, where k is the security level, we recover the long term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Public-key cryptography post-quantum cryptography CRYSTALS-Kyber Saber side-channel attack power analysis
Contact author(s)
lbackl @ kth se
kngo @ kth se
jgartner @ kth se
dubrova @ kth se
History
2022-12-06: approved
2022-12-06: received
See all versions
Short URL
https://ia.cr/2022/1692
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1692,
      author = {Linus Backlund and Kalle Ngo and Joel Gärtner and Elena Dubrova},
      title = {Secret Key Recovery Attacks on Masked and Shuffled Implementations of CRYSTALS-Kyber and Saber},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1692},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1692}},
      url = {https://eprint.iacr.org/2022/1692}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.