Planned changes to the SPHINCS+ specification

[David A. Cooper]

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]

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:

https://github.com/sphincs/sphincsplus/pull/51

Best,

 Bas

[David A. Cooper]

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]

Yes, you're right. The PR has been corrected.

Thanks,

 Bas

[Jade Philipoom]

Are there any other backwards-incompatible changes like this one expected for SPHINCS+ before the final standard? I haven't heard of any being discussed, but it would be helpful to know for planning purposes.

[David A. Cooper]

NIST plans to talk about the upcoming standards at the Fifth PQC Standardization Conference next month. This will include a discussion about some of the comments received and how NIST plans to address them.

For FIPS 205 in particular, there have been discussions about whether and how to include a pre-hash option (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/qsmP_5ZZx0g) and whether any of the parameter sets should be omitted from the final standard (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Rhikcg_YuJM).