Planned changes to the SPHINCS+ specification

339 views
Skip to first unread message

David A. Cooper

unread,
May 1, 2023, 4:18:47 PM5/1/23
to pqc-forum

Hello all,

In writing the draft standard based on SPHINCS+, we identified a couple of places in which the specification (https://sphincs.org/data/sphincs+-r3.1-specification.pdf) could be interpreted differently from the reference implementation (https://github.com/sphincs/sphincsplus). (The same issues apply to the specification and reference implementations submitted at the beginning of round 3). After discussion with the SPHINCS+ team, we plan to address these issues as described below.

The first issue is the following pseudocode in spx_sign() and spx_verify():

idx_tree = first h - h/d bits of tmp_idx_tree;
idx_leaf = first h/d bits of tmp_idx_leaf;

In the reference implementation, this is implemented as:

*tree = bytes_to_ull(bufp, SPX_TREE_BYTES);
*tree &= (~(uint64_t)0) >> (64 - SPX_TREE_BITS);
bufp += SPX_TREE_BYTES;

*leaf_idx = (uint32_t)bytes_to_ull(bufp, SPX_LEAF_BYTES);
*leaf_idx &= (~(uint32_t)0) >> (32 - SPX_LEAF_BITS);

For this issue, we plan to write the draft to be consistent with the reference implementation. This is, convert tmp_idx_tree and tmp_idx_leaf to integers and then extract the least significant bits from those integers.

The second issue is with FORS signing and verification. The pseudocode calls for passing "md = first ka bits of tmp_md" to fors_sign() and fors_pkFromSig(). These functions in turn compute a set of k indices, where idx[i] is set to "bits i*log(t) to (i+1)*log(t) - 1" of md. While Section 2.1 of the submission states that "We assume big-endian representation for any data types or structures," the reference implementation (message_to_indices() in fors.c) appears to be consistent with the pseudocode only if bit strings are encoded in little endian. For this issue, we plan to write the draft to be consistent with the pseudocode in the submission, if bit strings are encoded in big endian. In particular, we plan to use the base_w function (generalized to work with values of w other than 4, 16, and 256) to extract indices from tmp_md. The result would (arguably) be consistent with the current specification, but would not be consistent with the reference implementation.

Please let us know if you have any comments or concerns regarding these proposed changes.

David Cooper (on behalf of the NIST PQC team)

Bas Westerbaan

unread,
May 2, 2023, 10:37:14 AM5/2/23
to David A. Cooper, pqc-forum

The result would (arguably) be consistent with the current specification, but would not be consistent with the reference implementation.

To wit, the change to the SPHINCS+ reference implementation would be:


Best,

 Bas

David A. Cooper

unread,
May 2, 2023, 2:14:40 PM5/2/23
to Bas Westerbaan, pqc-forum
Hello Bas,

I do not believe this PR correctly represents what I was proposing. The code in the PR is:

    static void message_to_indices(uint32_t *indices, const unsigned char *m)
    {
        unsigned int i, j;
        unsigned int offset = 0;

        for (i = 0; i < SPX_FORS_TREES; i++) {
            indices[i] = 0;
            for (j = 0; j < SPX_FORS_HEIGHT; j++) {
                indices[i] ^= ((m[offset >> 3] >> (~offset & 0x7)) & 0x1) << j;
                offset++;
            }
        }
    }

As I read this, it takes the most significant bit of m[0] and makes it the least significant bit of indices[0]. The proposal would make the most significant bit of m[0] the most significant bit of indices[0]. The following seems to work:
          indices[i] ^= ((m[offset >> 3] >> (~offset & 0x7)) & 0x1) << (SPX_FORS_HEIGHT - 1 - j);
An equivalent way to do this would be to use a generalized base_w function (as shown below) for both WOTS+ and FORS. For FORS, it would be base_w(indices, tmp_md, 1 << SPX_FORS_HEIGHT, SPX_FORS_TREES). (Obviously, the base_w function could be written more rationally by taking log(w) as input rather than w.)


void base_w(uint16_t *basew, unsigned char *X, uint16_t w, int out_len) {
    int in=0, out, bits=0, logw=0;
    uint32_t tmp, total=0;

    if (w == 0) {
        return;
    }

    /* compute log2(w) */
    tmp = w;
    while ((tmp & 1) != 1) {
        logw+=1;
        tmp = tmp >> 1;
    }

    if (tmp != 1) {
        /* w was not a power of 2 */
        return;
    }

    for (out=0; out <= out_len - 1; out++) {
        while (bits < logw) {
            total = (total << 8) + X[in];
            in+=1;
            bits+=8;
        }
        bits-=logw;
        basew[out] = (total >> bits) & (w - 1);
    }
}


Bas Westerbaan

unread,
May 4, 2023, 7:42:12 AM5/4/23
to David A. Cooper, pqc-forum
Yes, you're right. The PR has been corrected.

Thanks,

 Bas
Reply all
Reply to author
Forward
0 new messages