sphincs / sphincsplus Goto Github PK

Thank you for this repo! But I'm getting a bit lost amongst the benchmarks and plethora of parameterizations.

Can you provide some examples of using the API provide here for a few common digital signature tasks, using the parameters that may be most likely to be standardized?

For extra credit, run thru the examples in a style similar to what Prof Bill Buchanan does at https://medium.com/asecuritysite-when-bob-met-alice/meet-the-standard-of-the-future-sphincs-ee2b9e4c7b5e. Or just show how to do his example if he's already using likely parameters.

Using linux perf to profile I currently measure sha256_update8x to take about 9-10% (9.76% specifically) of the total time. Looking at the generated assembly it seems that memcpy is the bottleneck in this function.
Interestingly, changing memcpy to memmove (which is expected to be slower) reduces sha256_update8x to take about 1-2% (1.37% specifically) of the total time. Looking at that assembly shows that it calls glibc rather than doing it inline.

I observe this behavior on the following platforms (all set to a single core with a fixed frequency):

• Intel i5-8250u using Arch Linux
• Intel i5-4460 using Debian
• AMD r5 1600 using Ubuntu

Initially I expected perf to not measure the calls to glibc but the built-in benchmark (which uses the cycle counter) shows that there is indeed an improvement matching what perf reported.

Output with memcpy:

Parameters: n = 32, h = 64, d = 8, b = 14, k = 22, w = 16
Running 10 iterations.
Generating keypair.. avg.   247850.48 us (0.25 sec); median    446,894,147 cycles,      1x:    446,894,147 cycles
  - WOTS pk gen..    avg.      903.39 us (0.00 sec); median      1,621,072 cycles,    256x:    414,994,432 cycles
Signing..            avg.  2886344.25 us (2.89 sec); median  5,352,747,435 cycles,      1x:  5,352,747,435 cycles
  - FORS signing..   avg.   894149.36 us (0.89 sec); median  1,612,681,974 cycles,      1x:  1,612,681,974 cycles
  - WOTS signing..   avg.       87.48 us (0.00 sec); median        156,892 cycles,      8x:      1,255,136 cycles
  - WOTS pk gen..    avg.      907.55 us (0.00 sec); median      1,651,092 cycles,   2048x:  3,381,436,416 cycles
Verifying..          avg.    11163.45 us (0.01 sec); median     40,992,378 cycles,      1x:     40,992,378 cycles
Signature size: 29792 (29.09 KiB)
Public key size: 64 (0.06 KiB)
Secret key size: 128 (0.12 KiB)

Output with memmove:

Parameters: n = 32, h = 64, d = 8, b = 14, k = 22, w = 16
Running 10 iterations.
Generating keypair.. avg.   232337.44 us (0.23 sec); median    419,017,549 cycles,      1x:    419,017,549 cycles
  - WOTS pk gen..    avg.      838.53 us (0.00 sec); median      1,509,783 cycles,    256x:    386,504,448 cycles
Signing..            avg.  2705637.84 us (2.71 sec); median  5,021,943,488 cycles,      1x:  5,021,943,488 cycles
  - FORS signing..   avg.   837526.53 us (0.84 sec); median  1,511,390,594 cycles,      1x:  1,511,390,594 cycles
  - WOTS signing..   avg.       87.87 us (0.00 sec); median        157,444 cycles,      8x:      1,259,552 cycles
  - WOTS pk gen..    avg.      837.10 us (0.00 sec); median      1,506,140 cycles,   2048x:  3,084,574,720 cycles
Verifying..          avg.    11371.54 us (0.01 sec); median     20,489,610 cycles,      1x:     20,489,610 cycles
Signature size: 29792 (29.09 KiB)
Public key size: 64 (0.06 KiB)
Secret key size: 128 (0.12 KiB)

I'm not quite sure what is causing inline memcpy to be so much slower but it seems worth looking into.

As per NIST publication, following changes are proposed to SPHINCS+ in SLH-DSA

Would be nice if these changes can be incorporated. Thanks in advance!

https://csrc.nist.gov/pubs/fips/205/ipd

• Two new address types were defned, WOTS_PRF and FORS_PRF, which are used for WOTS+
and FORS secret key value generation.
• PK.seed was added as an input to PRF in order to mitigate multi-key attacks.
• For the category 3 and 5 parameter sets that use SHA-2, SHA-256 was replaced with
SHA-512 in Hmsg, PRFmsg, H, and Tl based on weaknesses that were discovered when
using SHA-256 to obtain category 5 security [6, 7, 8].
• R and PK.seed were added as inputs to MGF1 when computing Hmsg for the SHA-2
parameter sets in order to mitigate against multi-target long-message second preimage
attacks.

Overview

Address operations are done at the byte level, yet represented by uint32_t arrays.

This results in a lot of casting in the functions, eg:

void set_keypair_addr(uint32_t addr[8], uint32_t keypair)
{
#if SPX_FULL_HEIGHT/SPX_D > 8
        /* We have > 256 OTS at the bottom of the Merkle tree; to specify */
        /* which one, we'd need to express it in two bytes */
    ((unsigned char *)addr)[SPX_OFFSET_KP_ADDR2] = (unsigned char)(keypair >> 8);
#endif
    ((unsigned char *)addr)[SPX_OFFSET_KP_ADDR1] = (unsigned char)keypair;
}

Alternative

Addresses are well suited as union types, this would result in cleaner code, improved readability and less casting.

Implementation

union address {
    uint32_t u32[8];
    unsigned char bytes[32];
};

void set_keypair_addr(union address addr, uint32_t keypair) {
#if SPX_FULL_HEIGHT/SPX_D > 8
    addr.bytes[SPX_OFFSET_KP_ADDR2] = (unsigned char)(keypair >> 8);
#endif
    addr.bytes[SPX_OFFSET_KP_ADDR1] = (unsigned char)keypair;
}

I run the benckmark.py as @thomwiggers said in mail with gcc 12.2.0 and Clang 14.0.6 in linux, there still are warnings and errors as before.
Is there something wrong with configuration of gcc and Clang?
Thanks.

The Readme for this project states

This repository contains the software that accompanies the SPHINCS+ submission to NIST's Post-Quantum Cryptography project.

The FIPS 205 IPD references v.3 and v.3.1 SPHINCS+ submissions. Does the master branch of this project represent the v.3.1 submission?

Thanks!

In liboqs we've gotten some feedback (open-quantum-safe/liboqs#1437) that the CC0 license is a barrier to adoption by some distributions. Would SPHINCS+ be willing to consider dual licensing to add another license? See also open-quantum-safe/liboqs#1388 (comment) for comments from the Fedora team.

The reference code as included in pqclean contains various small fixes that should still be upstreamed back to this repository. It's nothing major, but for the time being it may be nice to take that as a starting point instead.

There is no cycles.h file in the repository while it is included from several other files.

There is an issue with the existing reference implementation when experimenting with the new reduced-signature size SPHINCS+ parameter sets due to the fact that some of the new parameter sets utilize large subtree sizes (i.e., > 16) that result in the address.c::set_keypair_addr() function not setting all of the necessary bits as it only copies over the first two bytes.

In general, you may want to modify all ADDR-handling functions to ensure they copy over, or set, all of the bytes of each of the ADDR fields to ensure this doesn't happen.

Hi,

I have generated a sphincs+-sha256-256s-simple keypair and looked at their contents. I think the format in the comment section might be incorrect:
https://github.com/sphincs/sphincsplus/blob/06f42f47491085ac879a72b486ca8edb10891963/ref/api.h#LL44C1-L49C63

According to the comment, the order of "root" and "PUB_SEED" should be switched in SK and PK. But looking at the bytes, the PK is appended to the SK as is, without switching any order of components.

Either my implementation is wrong, or the comment should contain something like this:

/*
 * Generates a SPHINCS+ key pair given a seed.
 * Format sk: [SK_SEED || SK_PRF || root || PUB_SEED]
 * Format pk: [root || PUB_SEED]
 */

or

/*
 * Generates a SPHINCS+ key pair given a seed.
 * Format sk: [SK_SEED || SK_PRF || PUB_SEED || root]
 * Format pk: [PUB_SEED || root]
 */

...depending on what is actually first in PK, root or PUB_SEED (I'm not sure, didn't have chance to study SPHINCS that much yet).

In above file, in consistent-basew branch, in sha3_512_inc_finalize function, should the value in the for loop need to be 64? In similar code in https://github.com/PQClean/PQClean/blob/master/common/fips202.c it is 64 bytes (512)

`void sha3_512_inc_finalize(uint8_t *output, uint64_t *s_inc) {
uint8_t t[SHA3_512_RATE];
keccak_inc_finalize(s_inc, SHA3_512_RATE, 0x06);

keccak_squeezeblocks(t, 1, s_inc, SHA3_512_RATE);

for (size_t i = 0; i < 32; i++) { <--------------------- needs to be 64?
    output[i] = t[i];
}

}`

We should get rid of the global variables so that it's thread safe.

In the category "Microsoft compilers suck", such as previously seen in #14, the use of variable-length arrays is not supported by Microsoft compilers. This means even the ref implementation doesn't work on Windows.

The implementation uses a lot of unsigned long long for sizes of buffers and assumes that it's the same size as the size_t data type: it's passed to e.g. memmove and memcpy a lot. But on 32-bit x86 at least, sizeof(size_t) < sizeof(unsigned long long). This can lead to a lot of compiler warnings.

It would probably clean up the source code a lot to switch over to stdint.h types and use stddef.h for size_t whenever relevant. I'm not preparing a PR for this right now, as there are some large PRs open, but I am posting this as an issue for future reference.