Transactions on Cryptographic Hardware and Embedded Systems, Volume 2025
Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation
README
Description
This repository comes with the article entitled "Single-Trace Key-Recovery Template Attack on Classic McEliece Decapsulation"
Installation
The following Python packages are required:
- coloredlogs
- galois
- msgpack
- numpy
- tqdm
- natsort
- scikit-learn
- scipy
They can be installed with:
$ python3 -m pip install -r requirements.txt
The ChipWhisperer Python library can be installed using the following instructions
(extracted from https://chipwhisperer.readthedocs.io/en/latest/linux-install.html#quick-installation):
sudo apt update && sudo apt upgrade
# python prereqs
sudo apt-get install build-essential gdb lcov pkg-config \
libbz2-dev libffi-dev libgdbm-dev libgdbm-compat-dev liblzma-dev \
libncurses5-dev libreadline6-dev libsqlite3-dev libssl-dev \
lzma lzma-dev tk-dev uuid-dev zlib1g-dev curl
sudo apt install libusb-dev make git avr-libc gcc-avr \
gcc-arm-none-eabi libusb-1.0-0-dev usbutils
# install pyenv - skip if already done
curl https://pyenv.run | bash
echo 'export PATH="~/.pyenv/bin:$PATH"' >> ~/.bashrc
echo 'export PATH="~/.pyenv/shims:$PATH"' >> ~/.bashrc
echo 'eval "$(pyenv init -)"' >> ~/.bashrc
echo 'eval "$(pyenv virtualenv-init -)"' >> ~/.bashrc
source ~/.bashrc
pyenv install 3.9.5
pyenv virtualenv 3.9.5 cw
pyenv activate cw
cd ~/
git clone https://github.com/newaetech/chipwhisperer
cd chipwhisperer
git checkout b69bf3db66f0e806f738cb95b65c6a68d939d35a
sudo cp 50-newae.rules /etc/udev/rules.d/50-newae.rules
sudo udevadm control --reload-rules
sudo groupadd -f chipwhisperer
sudo usermod -aG chipwhisperer $USER
sudo usermod -aG plugdev $USER
python -m pip install -e .
Unzipping precomputed hash tables
You may download precomputed hash tables directly from the GitHub repository.
As far as we can tell, pulling them does not work since they are stored with LFS.
The precomputed hash tables can be unzipped with:
$ gunzip -k F2\^9_n_pow_22.msgpack.gz
$ gunzip -k F2\^12_n_pow_22.msgpack.gz
$ gunzip -k F2\^13_n_pow_22.msgpack.gz
Usage
Usage on ChipWhisperer traces
Due to limitation in the number of samples acquired by the Chipwhisperer, the attack works for toyeliece51220 only.
Compute profiling phase and matching phase
python3 side-channel_attack.py
Compute profiling phase only
python3 side-channel_attack.py p
Compute matching phase only
python3 side-channel_attack.py m
Example
$ python3 side-channel_attack.py
[XX:01:33] Profiling phase starts
[XX:01:33] Secret parameters generation starts
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 200/200 [00:21<00:00, 9.22it/s]
[XX:01:56] Secret parameters generation done
[XX:01:56] Traces acquisiton starts
Detected known STMF32: STM32F302xB(C)/303xB(C)
Extended erase (0x44), this can take ten seconds or more
Attempting to program 5547 bytes at 0x8000000
STM32F Programming flash...
STM32F Reading flash...
Verified flash OK, 5547 bytes
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 200/200 [13:55<00:00, 4.18s/it]
[XX:22:54] Traces acquisiton done
[XX:22:54] Traces preprocessing starts
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 200/200 [00:02<00:00, 72.35it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 200/200 [02:25<00:00, 1.38it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 200/200 [04:23<00:00, 1.32s/it]
[XX:36:59] Traces preprocessing done
[XX:36:59] Lda starts
[XX:38:54] Lda done
[XX:38:54] Templates creation starts
[XX:38:58] Templates creation done
[XX:38:58] Profiling phase done
[XX:38:58] Matching phase starts
[XX:38:58] Secret parameters generation starts
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:02<00:00, 2.03s/it]
[XX:39:01] Secret parameters generation done
[XX:39:01] Traces acquisiton starts
Detected known STMF32: STM32F302xB(C)/303xB(C)
Extended erase (0x44), this can take ten seconds or more
Attempting to program 5547 bytes at 0x8000000
STM32F Programming flash...
STM32F Reading flash...
Verified flash OK, 5547 bytes
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:04<00:00, 4.19s/it]
[XX:39:10] Traces acquisiton done
[XX:39:10] Traces preprocessing starts
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:00<00:00, 71.82it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:00<00:00, 1.49it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:01<00:00, 1.30s/it]
[XX:39:15] Traces preprocessing done
[XX:39:15] Lda starts
[XX:39:15] Lda done
[XX:39:15] Hamming weights recovery starts
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:03<00:00, 3.48s/it]
[XX:39:18] Hamming weights recovery done
[XX:39:18] Matching phase done
[XX:39:18] Loading precomputed hash table for F2^9 and n_powers=22
[XX:39:18] Loading done
[XX:39:18] Actual attack starts !
[XX:39:19] HW sequences matching completed successfully after 224 iterations, still 288 left
[XX:39:19] [Alg.1 l.2] Recovered mt+δ pairs (ɑ, g(ɑ))
[XX:39:19] [Alg.1 l.3] Polynomial g recovered with interpolation
[XX:39:19] Searching for an invertible submatrix in Hpub
[XX:39:19] Invertible submatrix found in Hpub
[XX:39:19] [Alg.1 l.4] Vandermonde matrix V constructed with g and the mt+δ (ɑ, g⁻²(ɑ)) pairs
[XX:39:19] [Alg.1 l.5] Computed the change-of-basis S using V and H_pub
[XX:39:19] [Alg.1 l.6] H_priv = S⁻¹H_pub recovered
0.002185, 0.50512, 0.016697, 0.051792, 0.010277, 0.00019,
[XX:39:19] [Alg.1 l.7] Full permuted support L recovered
[XX:39:19] Attack successful ! Done in 0:00:00.587649
Usage on simulated side-channel traces
python3 attack.py n t m --accuracy=a
Perfect accuracy
$ python3 attack.py 512 20 9
[XX:XX:02] Keygen starts
[XX:XX:04] Keygen done
[XX:XX:04] Done simulating side-channel trace of shape (n, 2t) = (512, 40)
[XX:XX:04] Loading precomputed hash table for F2^9 and n_powers=22
[XX:XX:04] Loading done
[XX:XX:04] Actual attack starts !
[XX:XX:04] HW lists matching completed after 190 iterations (190 minimum), still 322 left
[XX:XX:04] [Alg.1 l.2] Recovered mt+δ pairs (ɑ, g(ɑ))
[XX:XX:05] [Alg.1 l.3] Polynomial g recovered with interpolation
[XX:XX:05] Searching for an invertible submatrix in Hpub
[XX:XX:05] Invertible submatrix found in Hpub
[XX:XX:05] [Alg.1 l.4] Vandermonde matrix V constructed with g and the mt+δ (ɑ, g⁻²(ɑ)) pairs
[XX:XX:05] [Alg.1 l.5] Computed the change-of-basis S using V and H_pub
[XX:XX:05] [Alg.1 l.6] H_priv = S⁻¹H_pub recovered
0.000746, 0.405126, 0.052468, 0.050393, 0.010012, 0.000143,
[XX:XX:05] [Alg.1 l.7] Full permuted support L recovered
[XX:XX:05] Attack successful ! Done in 0:00:00.520167
Custom accuracy
$ python3 attack.py 512 20 9 --accuracy=0.97
[XX:XX:12] Keygen starts
[XX:XX:15] Keygen done
[XX:XX:15] Done simulating side-channel trace of shape (n, 2t) = (512, 40)
[XX:XX:15] Loading precomputed hash table for F2^9 and n_powers=22
[XX:XX:15] Loading done
[XX:XX:15] Actual attack starts !
[XX:XX:15] HW lists matching completed after 349 iterations (190 minimum), still 163 left
[XX:XX:15] [Alg.1 l.2] Recovered mt+δ pairs (ɑ, g(ɑ))
[XX:XX:15] [Alg.1 l.3] Polynomial g recovered with interpolation
[XX:XX:15] Searching for an invertible submatrix in Hpub
[XX:XX:15] Invertible submatrix found in Hpub
[XX:XX:15] [Alg.1 l.4] Vandermonde matrix V constructed with g and the mt+δ (ɑ, g⁻²(ɑ)) pairs
[XX:XX:15] [Alg.1 l.5] Computed the change-of-basis S using V and H_pub
[XX:XX:15] [Alg.1 l.6] H_priv = S⁻¹H_pub recovered
0.004836, 0.4443, 0.028606, 0.054372, 0.010048, 0.000141,
[XX:XX:15] [Alg.1 l.7] Full permuted support L recovered
[XX:XX:15] Attack successful ! Done in 0:00:00.543559
$ python3 attack.py 512 20 9 --accuracy=0.9
[XX:XX:17] Keygen starts
[XX:XX:20] Keygen done
[XX:XX:20] Done simulating side-channel trace of shape (n, 2t) = (512, 40)
[XX:XX:20] Loading precomputed hash table for F2^9 and n_powers=22
[XX:XX:20] Loading done
[XX:XX:20] Actual attack starts !
[XX:XX:20] Could not match enough HW lists, only 56/190. Possible fixes are:
[XX:XX:20] - decrease delta (currently 10),
[XX:XX:20] - get a more accurate side-channel distinguisher.
Reproducibility
Execution time
Execution times for the 6 lines of Algorithm 1 (Table 7) are measured with:
$ ./measure_timings.sh
Success rate
The attack success rate (Figure 3) is computed with:
$ python3.8 compute_success_rate.py