whibox/whibox-contest-2021_supplementary-materials

Supplementary materials for the WhibOx Contest Editon 3 (CHES 2021 Challenge)

Supplementary Materials for the WhibOx Contest Edition 3

This repository provides the supplementary materials for the WhibOx Contest Edition 3. Specifically, it has the following three main contents:

1. A CMD tool for generate a key pair given a seed.
2. CMD tools for generating / verifying EC-Schnorr signature.
3. The reference implementation in C using the GNU GMP library.

Prerequisites

In order to use this repository, one has to install

• GNU Make (tested with version 3.81)
• GCC version 10.2
• Python 3.9 (tested with version 3.9.4)
• Click 7.x (test with version 7.1.2)
• GNU GMP version 6.2.1 (configure prefix /usr/local/)

Usage

Generate EC key pairs from seed

$ ./keygen.py CHES2021
private key: d = 9C29EDDAEF2C2B4452052B668B83BE6365004278068884FA1AC3F6D0622875C3
public key:  Q = (x = 78E0E9DACCC47DE94D674DF3B35624A2F08E600B26B3444077022AD575AF4DB7, y = 3084B4B8657EEA12396FDE260432BA7BDB3E092D61A42F830150D6CC8D798F9F)
encoded public key:  78E0E9DACCC47DE94D674DF3B35624A2F08E600B26B3444077022AD575AF4DB73084B4B8657EEA12396FDE260432BA7BDB3E092D61A42F830150D6CC8D798F9F

Generate and verify EC-Schnorr signature

Notice the signature here is not deterministic.

$ ./ec_schnorr_sign.py 9C29EDDAEF2C2B4452052B668B83BE6365004278068884FA1AC3F6D0622875C3
Signature: 50163A72D46876355608D738FA2CB4BDF3AFFBF9AC3DC9E29C5EE276CD7599F7E38529FC98F653E4513B3D19A8435B38348972DBA482A407CBD9CDB043DB0E46

$ ./ec_schnorr_verify.py 78E0E9DACCC47DE94D674DF3B35624A2F08E600B26B3444077022AD575AF4DB73084B4B8657EEA12396FDE260432BA7BDB3E092D61A42F830150D6CC8D798F9F 50163A72D46876355608D738FA2CB4BDF3AFFBF9AC3DC9E29C5EE276CD7599F7E38529FC98F653E4513B3D19A8435B38348972DBA482A407CBD9CDB043DB0E46
Good signature :)

The reference implementation

The source code of the reference implementation can be found in dECDSA.c. Try make && ./dECDSA to test it.

$ xxd -ps -c 64 -u test_hash
F7FD41E28DFCCA32C1CEEF637C202CA6E99E57F18AFEF957DF0866B4CDD60F5C

$ ./dECDSA <test_hash | xxd -ps -c 128 -u
8007ABC1CD96650531BD8039893E8CF549A52D26E2A8A0E4700087523A7156A42794DE699028D0768259367AD4676BFE2DACCA139263A684D0A7434EA3842BC4

$ ./ecdsa_verify.py 78E0E9DACCC47DE94D674DF3B35624A2F08E600B26B3444077022AD575AF4DB73084B4B8657EEA12396FDE260432BA7BDB3E092D61A42F830150D6CC8D798F9F F7FD41E28DFCCA32C1CEEF637C202CA6E99E57F18AFEF957DF0866B4CDD60F5C 8007ABC1CD96650531BD8039893E8CF549A52D26E2A8A0E4700087523A7156A42794DE699028D0768259367AD4676BFE2DACCA139263A684D0A7434EA3842BC4
Good signature :)

whibox-contest-2021_supplementary-materials's Issues

Incorrect r check in dECDSA.cpp

We see in the source code on lines 222-224 (https://github.com/whibox/whibox-contest-2021_supplementary-materials/blob/main/dECDSA.c):

    /* calculate r = Q[x] mod n, if r = 0, restart. */
    mpz_mod(r, Q->x, n);
    if (mpz_cmp_ui(Q->x, 0) == 0) {

Suggest:
if (mpz_cmp_ui(r, 0) == 0) {
which agrees with the comment and algorithm description here: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Despite the astronomically low chance of this occurring. Specifically if Q->x==n expressed in gmp then r==0 but the condition is not met. Rather than a modulo, comparison and subtraction given the bit size might be more appropriate e.g. r = Q->x >= n ? Q->x - n : Q->x; again assuming it is expressed in gmp.

Memory leaks in dECDSA.c

There is a memory leak of G in the main signature routine which should have a point_clear(G); before returning after the loop.
Also in point addition when an inverse occurs, point_init_infinity(R) always leaks memory and should call point_clear(R) before reinitializing mpz_t big integers.