Open this publication in new window or tab >>2023 (English)In: Applied Cryptography and Network Security Workshops - ACNS 2023 Satellite Workshops, ADSC, AIBlock, AIHWS, AIoTS, CIMSS, Cloud S and P, SCI, SecMT, SiMLA, Proceedings, Springer Nature , 2023, p. 159-177Conference paper, Published paper (Refereed)
Abstract [en]
Shuffling is a well-known countermeasure against side-channel attacks. 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 attacks more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the long-term secret key was reported. In this paper, we present an attack that can recover the long-term 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 decryption 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 of length l, where k is the module rank, 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.
Place, publisher, year, edition, pages
Springer Nature, 2023
Keywords
CRYSTALS-Kyber, Post-quantum cryptography, Power analysis, Public-key cryptography, Saber, Side-channel attack
National Category
Signal Processing
Identifiers
urn:nbn:se:kth:diva-339267 (URN)10.1007/978-3-031-41181-6_9 (DOI)2-s2.0-85174450161 (Scopus ID)
Conference
21st International Conference on Applied Cryptography and Network Security, ACNS 2023, Kyoto, Japan, Jun 19 2023 - Jun 22 2023
Note
Part of ISBN 9783031411809
QC 20231106
2023-11-062023-11-062023-11-06Bibliographically approved