README.md 8.63 KB
Newer Older
Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
1
2
[![forthebadge](https://forthebadge.com/images/badges/uses-badges.svg)](https://forthebadge.com) [![forthebadge](https://forthebadge.com/images/badges/powered-by-electricity.svg)](https://forthebadge.com)
# Streaming Post-Quantum Public Keys and Signatures
3
This repository contains the code accompanying the paper "Verifying Post-Quantum Signatures in 8 kB of RAM".
Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
4
5

All benchmarking results claimed in the paper can be reproduced with this code.
Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
6
It builds on top of [PQM3](https://github.com/mupq/pqm3) and [PQClean](https://github.com/pqclean/pqclean) libraries.
Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
7
8
9
10
11
12

To get started, clone the repository:

```bash
git clone --recursive https://git.fslab.de/pqc/streaming-pq-sigs
```
13
14

**Only the STM NUCLEO-F207ZG** (nucleo-f207zg target of pqm3) is supported.
Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
15
For a general setup of the board, see the [PQM3](https://github.com/mupq/pqm3) documentation.
16

17
18
19
20
21
22
23
24
## Prerequisites
In order to use the code in this repository, a list of software components needs to be installed:

* [An up to date ARM toolchain](https://developer.arm.com/tools-and-software/open-source-software/developer-tools/gnu-toolchain/gnu-rm/downloads)
* Python 3 with `pyserial` and `tabluate` packages installed. This can be done with `pip install -r streaming/requirements.txt`.
* [OpenOCD](http://openocd.org/), which is available as a package in all major Linux distributions
* Make, which is also available as a package in all major Linux distributions

25

Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
26
## Adding a Scheme
27
28
29

To add a scheme, the following functions have to be added to its API:

30
```c
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* Initialize stream with given length of sm.
 * This function has to initialize the context ctx with chunk size etc.
 */
int crypto_sign_open_init_stream(crypto_stream_ctx *ctx, u32 smlen);
/* Consume chunk of public key. */
int crypto_sign_open_consume_pk_chunk(crypto_stream_ctx *ctx, u8 *chunk, size_t pk_pos);
/* Includes the pk chunk into the pk validation hash. 
 * This hash is used to determine if the correct public key was streamed in
 */
int crypto_sign_open_hash_pk_chunk(crypto_stream_ctx *ctx, u8 *chunk, size_t pk_pos);
/* Consume chunk of sm. */
int crypto_sign_open_consume_sm_chunk(crypto_stream_ctx *ctx, u8 *chunk, size_t sm_pos);
/* Return result of verification process and the extracted message.
 * Signature was valid if this function returns 0.
 */
int crypto_sign_open_get_result(crypto_stream_ctx *ctx, u8 *m, u32 *mlen);
```

The included schemes reside in the  [crypto_sign_stream](crypto_sign_stream/) folder.

Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
## Building the Schemes
Every inlcuded scheme can be compiled into 4 targets:

* [test](crypto_sign_streaming/test.c) - Just runs the scheme
* [cycles](crypto_sign_streaming/cycles.c) - Reports cycle counts for all implemented functions
* [stack](crypto_sign_streaming/stack.c) - Reports stack usage
* [hashing](crypto_sign_stream/hashing.c) - Reports cycle counts spend in symmetric primitves

To build all targets, call:

```bash
make PLATFORM=nucleo-f207zg -j8
```

The outputted binaries are now in the `elf` folder.

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
## Test Data
The test data goes in the [streaming/test_data](streaming/test_data) directory.

Each target (elf file that can be build with make) has its own test_data subdirectory.
For example:
```
streaming/test_data/crypto_sign_stream_falcon-512_opt-ct_cycles.elf
``` 
contains test data for this specific target. Since many targets of the same scheme need the same test data, symlinks can be used instead of directories.


Test cases are of the form:

```
sm: $SM_IN HEX
pk: $PK_IN_HEX
```

### Generating Test Cases
Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
86
To generate test cases, the script [generate_testcases.sh](./scripts/generate_testcases.sh) can be used.
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
It uses the PQClean testvectors program.

It can be invoked like this:
```bash
./scripts/generate_testcases.sh $PQCLEAN_SCHEME_NAME $NUM_TEST_CASES $TARGET
```

* `$PQCLEAN_SCHEME_NAME` is the scheme's directory name within PQClean.
* `$NUM_TEST_CASES` is the number of test cases that should be procuced
* `$TARGET` is the target the test cases should be created for

To create 10 falcon-512 test cases for the

* `crypto_sign_stream_falcon-512_opt-ct_cycles.elf` 

target and place them into

* `streaming/test_data/streaming/test_data/crypto_sign_stream_falcon-512_opt-ct_cycles.elf`

, one can use this command:

```bash
109
./scripts/generate_testcases.sh  falcon-512 10 elf/crypto_sign_stream_falcon-512_opt-ct_cycles.elf
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
```


## Tests
All target binaries can be tested, using the [test.py](streaming/test.py) script.

There are three tests included:

* **ValidTest**, checks if signature gets computed correctly
* **PKBitflipTest**, Flips a bit in the pubkey and fails if the signature verification still succeeds
* **SMBitflipTest**, Flips a bit in the sm value and fails if the signature verification still succeeds

### Running Tests on an Implementation
To test the [cycles.c](crypto_sign_stream/cycles.c) implementation with the `falcon-512` scheme do the following steps:

1. Build the binary
2. Flash the binary to the STM NUCLEO-F207ZG
3. Run the tests

Or in shell commands:
```bash
# 1
make PLATFORM=nucleo-f207zg -j8 ./elf/crypto_sign_stream_falcon-512_opt-ct_cycles.elf
# 2
./scripts/flash.sh elf/crypto_sign_stream_falcon-512_opt-ct_cycles.elf
# 3
python3 streaming/test.py elf/crypto_sign_stream_falcon-512_opt-ct_cycles.elf
```

Supplying the `-h` option to `test.py` shows various command line parameters.
To enable DEBUG messages supply `-v 10`.

### Run All Tests
To run the tests on all available targets in the `elf` directory, call the `test_all.sh` script:

```bash
./scripts/test_all.sh
```

## Benchmarks
Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
150
A benchmark sends benchmark results via a benchmark messages (e.g. `STREAM_SPEED_BENCHMARK`).
151
152
153

There are three benchmark implementations included:

Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
154
155
156
* [cycles.c](crypto_sign_stream/cycles.c), measures cpu cycle counts
* [stack.c](crypto_sign_stream/stack.c), measures stack usage
* [hashing.c](crypto_sign_stream/hashing.c), measures how many cpu cycles are spend within symmetric primitives
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

### Runing Benchmarks on an Implementation
To run the `cycles.c` benchmark with the `falcon-512` scheme do the following steps:

1. Build the binary
2. Flash the binary to the STM NUCLEO-F207ZG
3. Run the benchmarks

Or in shell commands:
```bash
# 1
make PLATFORM=nucleo-f207zg -j8 ./elf/crypto_sign_stream_falcon-512_opt-ct_cycles.elf
# 2
./scripts/flash.sh elf/crypto_sign_stream_falcon-512_opt-ct_cycles.elf
# 3
python3 streaming/benchmark.py elf/crypto_sign_stream_falcon-512_opt-ct_cycles.elf > benchmark.csv
```

Supplying the `-h` option to `benchmark.py` lists various command line parameters.
To enable DEBUG messages supply `-v 10`, supplying `-s` additionally measures the sizes of the binary's relevant sections.

### Run All Benchmarks
To run a benchmark on all available targets in the `elf` directory, call the [benchmark_all.sh](benchmark_all.sh) script with the benchmark name, e.g.:

```bash
./scripts/benchmark_all.sh cycles
```

The script will generate `csv` files in the `benchmarks` directory. 
One `csv` file per target is generated.
Every test case (see section *Test Data*) is run once and benchmarked.

Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
189
To run **all** benchmarks on **all** targets, call the [run_all_experiments.sh](scripts/run_all_experiments.sh) script:
190
191
192
193
194
195
196
197
198
199
200
201

```bash
./scripts/run_all_experiments.sh
```

### Print Benchmarks
To print tables with benchmark results, call the [print_benchmarks.py](streaming/print_benchmarks.py) script:

```bash
./streaming/print_benchmarks.py
```

202
This requires the benchmarks to be located in the `benchmarks` folder.
203
204
205
206
207
208
Calling the script with `-h` prints out all supported parameters.

Important parameters:

* `-s` for selecting a specific scheme or multiple schemes
* `-f` specifying the output format (plain, html or latex)
Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
209
* `-p` to output the final tables used in the paper
210
* `-l` supplies a different path (location) to look for benchmarks
211
212
213
214
215
216
217
218
219
220

Example calls:

```bash
# Print table in plain format with two selected schemes
./scripts/print_benchmarks.py -s falcon-512_opt-ct -s dilithium2_m3
# Print table in latex format for all schemes
./scripts/print_benchmarks.py -f latex
```

Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
221
222
223
224
225
226
227
228
229
230
231
232
233
## Communication
A very simple protocol on top of UART is used to stream the signature and public key.
Communication works as follows:
```
[HOST]                 [M3 DEVICE]
        <---[Init]---
       ---[sm length]--->
      <---[req X bytes]---
       ---[send X bytes]-->
       <---[req X bytes]---
       ---[send X bytes]-->
       [...]
```
234

Ruben Anthony Gonzalez's avatar
Ruben Anthony Gonzalez committed
235
236
237
238
The length of `sm` (signed message) is transferred to the device, since it is not known during compile time. The possibility for the device to request chunks individually makes precise timing measurements possible. 
The sending and receiving of UART data is implemented with polling. This makes it possible to disable interrupts for precise timing measurement.

The device can send strings (e.g. for debugging purposes) to the host at any time.