Key Recovery Side-Channel Attack on Classic McEliece Implementations
"Learn about a key recovery side-channel attack on Classic McEliece implementations presented at CHES 2022. Explore insights into the secret key parts, side-channel measurements, and results of the attack."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A Key-Recovery Side-Channel Attack on Classic McEliece Implementations Qian Guo1, Andreas Johansson1and Thomas Johansson1 1Dept. of Electrical and Information Technology, Lund University, Sweden CHES 2022 September 21th, 2022
Outline Classic McEliece Secret key parts Idea of side-channel attack Partial and full key-recovery attacks Side-channel measurements Results Conclusion A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
1/20 Classic McEliece Round 4 candidate for PKE in the NIST PQC IND-CCA2 secure key encapsulation mechanism Built from Niederreiter's dual version of McEliece's PKE McEliece Code-based PKE introduced in 1978 Uses binary Goppa codes Hardness of decoding random linear codes A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
2/20 Classic McEliece overview (Niederreiter) ciphertext sent over an insecure channel ? = ????]? Encrypt Decrypt ? ? Plaintext of length ? and weight ? The secret key used during decryption Plaintext multiplied with the public key ? System parameters: ?, ? and ? A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
3/20 Classic McEliece secret key The secret key is a random binary Goppa code defined by a polynomial ? ? ?2?[?] of degree ? a support ? consisting of a list of elements ? = ?1, ,?? ?2? ? System parameters: ?, ? and ? ? ? and ?1, ,?? are used to construct ? Public key A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
4/20 Relations between secret key parts If ? = ?1, ,?? is known, ?(?) can be found by the definition of a Goppa code Not the full set ?1, ,?? is needed to recover ? ? If ?(?) is known, the support splitting algorithm can be used to find ? = ?1, ,?? if ? = 2? if ? = 2? Partial knowledge of ? = ?1, ,?? Full knowledge of ?(?) Full knowledge of ? = ?1, ,?? A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
5/20 Recovering ?(?) Partial knowledge of ? = ?1, ,?? if ? = 2? Full knowledge of ?(?) Full knowledge of ? = ?1, ,?? From the definition of Goppa codes we have that all valid codewords ? = (?1, ,??) ?2 ? ?? ? ?? ?fulfils = 0 mod ?(?) ?=1 Thus, if we form the polynomial ? ? ?2?[?] as ? ?? ? ? = (? ??) ? ?? ?=1 ? (?) we can find ? ? by factoring ?(?) Index set of ? A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
6/20 Recovering ? = (?1, ,??) Partial knowledge of ? = ?1, ,?? if ? = 2? Full knowledge of ?(?) Full knowledge of ? = ?1, ,?? We use ?(?) and an arbitrary permutation of the set ?1, ,?? to construct a Goppa code ?0 From ?0we construct the generator matrix ?0and from the public key ? we construct another generator matrix ? = ?T??] We use the support splitting algorithm to find the index permutation between ?0and ? which gives us the secret support ? = (?1, ,??) Note: This only works when ? = 2? A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
7/20 Attacked implementations Hardware (HW) implementation referenced in Classic McEliece documentation Synthesized for Xilinx Artix7 FPGA with level 1 parameters ? = 12,? = 64, and ,? = 3488 Third-party software (SW) implementation Compiled for STM32 Cortex-M4 microcontroller with level 1 parameters ? = 12,? = 64, and ,? = 3488 A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
8/20 Classic McEliece PKE decryption If ?(??) = 0 then ?[?] = 1 else ?[?] = 0 If ? = (1,1,1,0, ,0) then ?(?) = (? ?1)(? ?2)(? ?3) A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
9/20 Polynomial evaluation Both the HW and SW implementation makes use of an additive-FFT The evaluation of the polynomial is carried out in a deterministic way over the whole field ?2? The only input to the FFT is the error locator ?(?) We can control the value of ?(?) by crafting ciphertexts A fixed ?(?) will give the same intermediate values A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
10/20 Idea of the side-channel attack If we encrypt a plaintext ??where only the ?thbit is set to 1 then the error locator will be ? ? = ? ?? There are 2?possible ?(?) of degree 1, each will give a unique sequence of intermediate values during the FFT If we can distinguish ? ? = ? ??we can predict the value of ?? A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
11/20 Partial key-recovery attack Not the full secret support is needed to recover ?(?) ? ?? ? ? = (? ??) ? ?? ?=1 ? (?) By using a codeword with small Hamming weight the number of required ? s is reduced It is easy to find a codeword of weight ? 2 + 1 where ? = ?? Information set decoding can be used to find a low-weight codeword A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
12/20 Full key-recovery attack When ? = 2? We follow the partial key-recovery procedure to get ?(?) We use the support splitting algorithm ? = (?1, ,??) When ? < 2? We find the matrix ? such that ? = ? ????] This requires that we know ?(?) and the first ?? elements of ? = (?1, ,??) By picking a row of ? = ?T??] as the codeword the number of ? s we need to find is minimized to ? + 1 A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
13/20 Number of ? s for full key recovery Parameter set Kem/mceleice348864 Kem/mceleice360896 Kem/mceliece6688128 Kem/mceleice6960119 Kem/mceliece8192128 ? 12 13 13 13 13 ? ? level ? + 1 769 1249 1665 1548 1665 low-weight ? 64 96 3488 4608 6688 6960 8192 1 3 5 5 5 287 508 693 646 695 128 119 128 Note: One of the level 5 sets requires less ? s than the level 1 set A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
14/20 Profiling phase of side-channel attack Device similar to the one we want to attack Can set the secret key We craft ciphertexts and send them for decryption ? = ????]? ? Decrypt We measure side-channel leakage during decryption We construct a classifier that predicts partial information of the secret key A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
15/20 Attack phase of side-channel attack No knowledge of the secret key We craft ciphertexts and send them for decryption ? Decrypt We measure side-channel leakage during decryption We feed the collected traces to our pre-constructed classifier to predict information of the secret key A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
16/20 Leakage assessment We perform TVLA to evaluate if it seems possible to distinguish the value of ?(?) The first set contains traces of a specific ?specific? = ? ?specificand the second set contains traces of random ? ? of degree 1 HW implementation SW implementation A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
17/20 Collecting traces for classifier We collect traces by Picking a random ? [1, ,?] Constructing ??where only bit ? is set to 1 Using the public key to encrypt the plaintext Measure the power consumption during the additive FFT step of decryption Label the collect trace with ?? A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
18/20 Constructing the classifier We use deep learning to build a classifier that based on a trace predicts the value of ?(?) Since we know ??this will predict the value of ??in the secret support We train a multilayer perceptron model Number of traces: HW 418560, SW 34880 A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
19/20 Results of classifier Attack on HW implementation Experiment on 30 random secret keys For each key we successfully predict the secret support ? = (?1, ,??) A single trace needed for each ??i.e., we got an accuracy of 100% Attack on SW implementation Experiment on 90 random secret keys For each key we successfully predict the secret support ? = (?1, ,??) A single trace needed for each ??i.e., we got an accuracy of 100% A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
20/20 Conclusion First key-recovery side-channel attack on Classic McEliece Kem/mceliece348864 (level 1) Partial key-recovery attack by using 273 traces Full key-recovery attack by using 796 traces Kem/mceliece8192128 (level 5) Partial key-recovery attack by using 679 traces Partial and full key-recovery attacks are equivalent Future research Improving the attack i.e. reducing the number of traces Finding efficient countermeasures A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
Thank you for your time! A Key-Recovery Side-Channel Attack on Classic McEliece Implementations, CHES 2022
