Classic McEliece implementation for ARM-Cortex M4

Code for experiments of outsourcing key-generation of Classic McEliece.

Goal: minimizing stack usage of key-generation by outsourcing some computation to un-trusted remote pcs.

Authors

Ming-Shing Chen (IIS, Academia Sinica) and Tung Chou (CITI, Academia Sinica)

Licence

All implementations are in the public domain.

APIs

These functions are called by the device for out-sourcing key-generation.

// pksrv_nXXXX_tXXX.h
uint32_t pksrv_init( parameters );  // return a (communication) token, for generating a new key
uint32_t pksrv_retrive_pk( const uint8_t* pkhash );  // return a token, for retriving generated pk with its hash value

unsigned pksrv_store_prepk( uint32_t token , const uint8_t* prepk_chunk , unsigned idx_prepk );
unsigned pksrv_compute_pk( uint32_t token );
unsigned pksrv_get_pk(uint32_t token, uint8_t * pk_chunk , unsigned idx_pk );

host-side/: A (python) pk server executed in the PC side.
u32_nXXXX_tXXXX: Classic McEliece cdoe with various parameters for performing the out-sourcing experiments in a M4 device.
pqm4-projects: Projects for PQM4(https://github.com/mupq/pqm4).
[Note] The implementation generates the same KATs as the R3 submisions in https://classic.mceliece.org/ .

Running PQM4 tests and benchmarks with the mps2-an386 simulator

Follow the setup of PQM4 first.

Then obtain the pqm4 library and the submodules:

git clone --recursive https://github.com/mupq/pqm4.git

Copy files to the PQM4 directory:

cp -r u32_nxxxx_txxx/src  /pqm4/crypto_kem/u32_nxxxx_txxx

Set up a pk server(see /host-side):

Build a serial port channel for simulating communication channel:

socat -d -d pty,rawer pty,rawer

ex:/dev/pts/2 and /dev/pts/3

Open a new terminal and go to /host-side
Build a C library for computing inverse matrix:

make

Run the Classic McEliece PK storage server for communication with a simulated /dev/pts/2 serial port:

python3 ./host-mc348864keysrv.py /dev/pts/2

Go to /pqm4.

Build projects for mps2-an386 platform:

make -j4 PLATFORM=mps2-an386 IMPLEMENTATION_PATH=crypto_kem/u32_nxxxx_txxx/

Finally, run tests or benchmarks:

qemu-system-arm -M mps2-an386 -nographic -semihosting -serial /dev/pts/3 -kernel elf/crypto_kem_u32_nxxxx_txxx__xxxxx.elf

Running PQM4 tests and benchmarks with the stm32f4-discovery board

Set up a pk server(see /host-side):

Go to /host-side
Build a C library for computing inverse matrix:

make

Run the Classic McEliece PK storage server for communication between an M4 and /dev/ttyUSB0 port:

python3 ./host-mc348864keysrv.py /dev/ttyUSB0 38400

[Note] The file /dev/ttyUSB0 must have rwx permissions.

Go to the /pqm4.

Build projects for mps2-an386 platform:

make -j4 PLATFORM=stm32f4discovery IMPLEMENTATION_PATH=crypto_kem/u32_nxxxx_txxx/

Write the binary to the board and run the test:

st-flash write bin/crypto_kem_u32_nxxxx_txxx__stack.bin 0x8000000

[Note] There is a instruction for connecting the board in https://github.com/mupq/pqm4#connecting-the-stm32f4-discovery-board-to-the-host.

Finally, press the reset button on the board for running tests or benchmarks.

Experiments and Results:

Experiments:

Set up a pk server in the PC side(see host-side/host-mc348864keysrv.py), listening to a particular tty device (e.g., /dev/ttyUSB0)
The M4 device (STM32F4-discovery) performs key-generation. The steps:
1. The M4 device sends some public pre-pk chunks to pk server in the PC side.
2. The M4 device will query if the pk server successfully generates the pk. The server side performs a Gaussian elimination and returns its results.
3. If successfully generating a pk, the M4 device requests PK chunks from the server side.
4. While receiving pk chunks, the M4 device tests its integrity with its sk. If the pk is correct, the device calcuates its hash and stores hashes instead of a real pk.
  (Note: the M4 can always generate its pk from its sk. It choices to store the pk in the key server to save its local storage space.)
The M4 device performs encapsulation with pkhsahes:
1. With the stored pk hashes, the M4 device ask the server if the server stored its pk.
2. If yes, the device requests the pk chunks.
3. While receiving pk chunks, the M4 device check its integrity with the stored hashes of the pk chunks.
4. The device performs encapsulation chunk by chunk.
We hope the encapsulation experiment can show the scenario:
We assumed that the key server (host-side/) stored MANY public keysfrom many devices it served. Supposing device A wants to generate a shared secret with device B and device A has only the HASH of public key of B (PKb), then device A can request PKb from the key server by the HASH of PKb. The server sends PKb to device A chunk by chunk, and device A performs the encapsulation while checking the integrity of PKb via its own HASH of PKb.
In the experiment, it might be misleading since the M4 performs encapsulation with its own pk. The point here is that the M4 device can request any pk from the server as long as the M4 device has the hashes of requested pks.
Decapsulation: The M4 device decaps the previous encap results for a shared key.

Benchmarks:

We report experiment results on a STM32F4-discovery(168MHz) and a pk sever on a x86 PC.
The connection between M4 and PC is M4 USART port (baud rate 38400 bits/sec) <-> USB dongle <-> PC.

The API for KEM and execution evniroment and the same with the PQM4.
(PQM4 version: 2691b4915 Nov/29/2021 and arm-none-eabi-gcc (15:9-2019-q4-0ubuntu2) 9.2.1).

Execution time:

Turnaroud time (successfully generating pk with only one attempt):

Parameter	keypair	encaps	decaps
mceliece348864	180.843(sec)	70.082(sec)	0.0160(sec)
mceliece460896	404.980(sec)	140.186(sec)	0.0388(sec)
mceliece6688128	799.080(sec)	279.089(sec)	0.0439(sec)
mceliece6960119	782.217(sec)	281.028(sec)	0.0425(sec)
mceliece8192128	996.62(sec)	364.21(sec)	0.0442(sec)

Communication and other costs

Commnunication baud rate: 38400 bits/second
Key-generation

Parameter	Turnaround time	Measured Communication time	Expected Communication time
mceliece348864	180.843(sec)	161.914(sec)	127.066(sec)
mceliece460896	404.980(sec)	333.427(sec)	262.8(sec)
mceliece6688128	799.080(sec)	650.619(sec)	513.093(sec)
mceliece6960119	782.217(sec)	642.082(sec)	506.009(sec)
mceliece8192128	996.62(sec)		644.693(sec)

Parameter	pre-pk chunks(SYS) -> server	pre-pk chunks(PK) -> server	pk chunks <- server
mceliece348864	16.000000(sec)	56.666667(sec)	54.400000(sec)
mceliece460896	41.600000(sec)	112.000000(sec)	109.200000(sec)
mceliece6688128	73.493333(sec)	221.893333(sec)	217.706667(sec)
mceliece6960119	64.475833(sec)	222.375833(sec)	219.158333(sec)
mceliece8192128	73.493333(sec)	288.320000(sec)	282.880000(sec)

Parameter	chunk size (pre-pk,m4->server)	chunk size (pk,m4<-server)	pre-pk chunks(SYS+PK) -> server	pk chunks <- server
mceliece348864	3200 x (24+85)	3072 x 85	76800+272000(byte)	261120(byte)
mceliece460896	5120 x (39+105)	4992 x 105	199680+537600(byte)	524160(byte)
mceliece6688128	6784 x (52+157)	6656 x 157	352768+1065088(byte)	1044992(byte)
mceliece6960119	6316 x (49+169)	6188 x 170	309484+1067404(byte)	1051960(byte)
mceliece8192128	6784 x (52+204)	6656 x 204	352768+1383936(byte)	1357824(byte)

Encapsulation

Parameter	Turnaround time	Measured Communication time	Expected Communication time
mceliece348864	70.082(sec)	69.918(sec)	54.400000(sec)
mceliece460896	140.186(sec)	139.860(sec)	109.200000(sec)
mceliece6688128	279.089(sec)	278.443(sec)	217.706667(sec)
mceliece6960119	281.028(sec)	280.374(sec)	219.158333(sec)
mceliece8192128	364.21(sec)		282.880000(sec)

Stack usage:

[Note] Cover /pqm4/mupq/crypto_kem/stack.c by our stack.c .

Benchamrked on STM32F4-discovery.

Parameter	keypair	encaps	decaps
mceliece348864	52620	7204	18492
mceliece460896	96640	11416	34964
mceliece6688128	100928	15104	35708
mceliece6960119	96972	14888	35756
mceliece8192128	100928	15296	36092

Benchamrked on mps2-an386.

Parameter	keypair	encaps	decaps
mceliece348864	52620	7204	18492
mceliece460896	96572	11308	34964
mceliece6688128	100920	14996	35708
mceliece6960119	96972	14780	35756
mceliece8192128	100816	15188	36092

These numbers are the measurements of stack usage of related functions. It does not contain the key pair storage provided by the caller functions.

Name		Name	Last commit message	Last commit date
Latest commit History 7 Commits
host-side		host-side
u32_n3488_t64		u32_n3488_t64
u32_n4608_t96		u32_n4608_t96
u32_n6688_t128		u32_n6688_t128
u32_n6960_t119		u32_n6960_t119
u32_n8192_t128		u32_n8192_t128
README.md		README.md
stack.c		stack.c

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

Classic McEliece implementation for ARM-Cortex M4

Authors

Licence

APIs

Contents

Running PQM4 tests and benchmarks with the mps2-an386 simulator

Running PQM4 tests and benchmarks with the stm32f4-discovery board

Experiments and Results:

Experiments:

Benchmarks:

Execution time:

Communication and other costs

Stack usage:

About

Releases

Packages

Contributors 2

Languages

devillegna/McOutsourcing

Folders and files

Latest commit

History

Repository files navigation

Classic McEliece implementation for ARM-Cortex M4

Authors

Licence

APIs

Contents

Running PQM4 tests and benchmarks with the mps2-an386 simulator

Running PQM4 tests and benchmarks with the stm32f4-discovery board

Experiments and Results:

Experiments:

Benchmarks:

Execution time:

Communication and other costs

Stack usage:

About

Resources

Stars

Watchers

Forks

Releases

Packages 0

Contributors 2

Languages

Packages