Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond
In this work, we propose generic and novel adaptations to the binary Plaintext-Checking (PC) oracle based side-channel attacks for Kyber KEM. These attacks operate in a chosen-ciphertext setting, and are fairly generic and easy to mount on a given target, as the attacker requires very minimal inform...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/169834 |
| _version_ | 1824453587421364224 |
|---|---|
| author | Rajendran, Gokulnath Ravi, Prasanna D’anvers, Jan-Pieter Bhasin, Shivam Chattopadhyay, Anupam |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Rajendran, Gokulnath Ravi, Prasanna D’anvers, Jan-Pieter Bhasin, Shivam Chattopadhyay, Anupam |
| author_sort | Rajendran, Gokulnath |
| collection | NTU |
| description | In this work, we propose generic and novel adaptations to the binary Plaintext-Checking (PC) oracle based side-channel attacks for Kyber KEM. These attacks operate in a chosen-ciphertext setting, and are fairly generic and easy to mount on a given target, as the attacker requires very minimal information about the target device. However, these attacks have an inherent disadvantage of requiring a few thousand traces to perform full key recovery. This is due to the fact that these attacks typically work by recovering a single bit of information about the secret key per query/trace. In this respect, we propose novel paral lel PC oracle based side-channel attacks, which are capable of recovering a generic P number of bits of information about the secret key in a single query/trace. We propose novel techniques to build chosen-ciphertexts so as to efficiently realize a parallel PC oracle for Kyber KEM. We also build a multi-class classifier, which is capable of realizing a practical side-channel based parallel PC oracle with very high success rate. We experimentally validated the proposed attacks (upto P = 10) on the fastest implementation of unprotected Kyber KEM in the pqm4 library. Our experiments yielded improvements in the range of 2.89× and 7.65× in the number of queries, compared to state-of-the-art binary PC oracle attacks, while arbitrarily higher improvements are possible for a motivated attacker, given the generic nature of the proposed attacks. We further conduct a thorough study on applicability to different scenarios, based on the presence/absence of a clone device, and also partial key recovery. Finally, we also show that the proposed attacks are able to achieve the lowest number of queries for key recovery, even for implementations protected with low-cost countermeasures such as shuffling. Our work therefore, concretely demonstrates the power of PC oracle attacks on Kyber KEM, thereby stressing the need for concrete countermeasures such as masking for Kyber and other lattice-based KEMs. |
| first_indexed | 2025-02-19T03:08:47Z |
| format | Journal Article |
| id | ntu-10356/169834 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:08:47Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1698342023-08-11T15:35:33Z Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond Rajendran, Gokulnath Ravi, Prasanna D’anvers, Jan-Pieter Bhasin, Shivam Chattopadhyay, Anupam School of Computer Science and Engineering Engineering::Computer science and engineering Key Encapsulation Mechanism Plaintext-Checking Oracle In this work, we propose generic and novel adaptations to the binary Plaintext-Checking (PC) oracle based side-channel attacks for Kyber KEM. These attacks operate in a chosen-ciphertext setting, and are fairly generic and easy to mount on a given target, as the attacker requires very minimal information about the target device. However, these attacks have an inherent disadvantage of requiring a few thousand traces to perform full key recovery. This is due to the fact that these attacks typically work by recovering a single bit of information about the secret key per query/trace. In this respect, we propose novel paral lel PC oracle based side-channel attacks, which are capable of recovering a generic P number of bits of information about the secret key in a single query/trace. We propose novel techniques to build chosen-ciphertexts so as to efficiently realize a parallel PC oracle for Kyber KEM. We also build a multi-class classifier, which is capable of realizing a practical side-channel based parallel PC oracle with very high success rate. We experimentally validated the proposed attacks (upto P = 10) on the fastest implementation of unprotected Kyber KEM in the pqm4 library. Our experiments yielded improvements in the range of 2.89× and 7.65× in the number of queries, compared to state-of-the-art binary PC oracle attacks, while arbitrarily higher improvements are possible for a motivated attacker, given the generic nature of the proposed attacks. We further conduct a thorough study on applicability to different scenarios, based on the presence/absence of a clone device, and also partial key recovery. Finally, we also show that the proposed attacks are able to achieve the lowest number of queries for key recovery, even for implementations protected with low-cost countermeasures such as shuffling. Our work therefore, concretely demonstrates the power of PC oracle attacks on Kyber KEM, thereby stressing the need for concrete countermeasures such as masking for Kyber and other lattice-based KEMs. Published version Jan-Pieter D’Anvers is funded by FWO (Research Foundation – Flanders) as juniorpost-doctoral fellow (contract number 133185 / 1238822N LV). 2023-08-07T08:26:56Z 2023-08-07T08:26:56Z 2023 Journal Article Rajendran, G., Ravi, P., D’anvers, J., Bhasin, S. & Chattopadhyay, A. (2023). Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond. IACR Transactions On Cryptographic Hardware and Embedded Systems, 2023(2), 418-446. https://dx.doi.org/10.46586/tches.v2023.i2.418-446 2569-2925 https://hdl.handle.net/10356/169834 10.46586/tches.v2023.i2.418-446 2-s2.0-85150029254 2 2023 418 446 en IACR Transactions on Cryptographic Hardware and Embedded Systems © 2023 Gokulnath Rajendran, Prasanna Ravi, Jan-Pieter D’Anvers, Shivam Bhasin, Anupam Chattopadhyay. This work is licensed under a Creative Commons Attribution 4.0 International License. application/pdf |
| spellingShingle | Engineering::Computer science and engineering Key Encapsulation Mechanism Plaintext-Checking Oracle Rajendran, Gokulnath Ravi, Prasanna D’anvers, Jan-Pieter Bhasin, Shivam Chattopadhyay, Anupam Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond |
| title | Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond |
| title_full | Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond |
| title_fullStr | Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond |
| title_full_unstemmed | Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond |
| title_short | Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond |
| title_sort | pushing the limits of generic side channel attacks on lwe based kems parallel pc oracle attacks on kyber kem and beyond |
| topic | Engineering::Computer science and engineering Key Encapsulation Mechanism Plaintext-Checking Oracle |
| url | https://hdl.handle.net/10356/169834 |
| work_keys_str_mv | AT rajendrangokulnath pushingthelimitsofgenericsidechannelattacksonlwebasedkemsparallelpcoracleattacksonkyberkemandbeyond AT raviprasanna pushingthelimitsofgenericsidechannelattacksonlwebasedkemsparallelpcoracleattacksonkyberkemandbeyond AT danversjanpieter pushingthelimitsofgenericsidechannelattacksonlwebasedkemsparallelpcoracleattacksonkyberkemandbeyond AT bhasinshivam pushingthelimitsofgenericsidechannelattacksonlwebasedkemsparallelpcoracleattacksonkyberkemandbeyond AT chattopadhyayanupam pushingthelimitsofgenericsidechannelattacksonlwebasedkemsparallelpcoracleattacksonkyberkemandbeyond |