339 views

Skip to first unread message

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)

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

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++;

}

}

}

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);

}

}

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

Search

Clear search

Close search

Google apps

Main menu