Side Channel

[smuellerDD]

After integrating SPHINCS+ into [1] and adding instrumentation to detect side channels based on sensitive data, I had to add the following changes to the AVX2 implementation to ensure that the analyzer did not complain: [2] and [3]. In addition, I added similar changes to the ARMv8 implementation. These changes replace the branch with a constant-time operation to copy the data into the destination depending on the condition.

The associated poisoning of the sensitive data is shown in [4] and [5].

[1] /~https://github.com/smuellerDD/leancrypto

[2] smuellerDD/leancrypto@fa9c9d8#diff-866a5e68a28003004aca7b017921a4fc686df41a92a4fadf08446bc3f6419829R130

[3] smuellerDD/leancrypto@fa9c9d8#diff-9bdf5946a941ed242ded66d4bd4b67d7dccf106c2c9ad2d29cab87dfc817f746R253

[4] smuellerDD/leancrypto@fa9c9d8#diff-69f9b989ca20bfba561bb05e6dcc55479d30209c96d14c19dfc26425d29ed0bbR231

[5] smuellerDD/leancrypto@fa9c9d8#diff-69f9b989ca20bfba561bb05e6dcc55479d30209c96d14c19dfc26425d29ed0bbR252

[MrPugh]

To sign with SPHINCS+, we sign the data with FORS and the FORS root with WOTS+/Merkle and then for several iterations one Merkle root with another WOTS+/Merkle layer. Hence, you need to 'unpoison' each of those intermediate roots. This should look something like this in your code (not tested):

diff --git a/slh-dsa/src/sphincs_sign.c b/slh-dsa/src/sphincs_sign.c
index c23ecf2..133f389 100644
--- a/slh-dsa/src/sphincs_sign.c
+++ b/slh-dsa/src/sphincs_sign.c
@@ -262,6 +262,8 @@ LC_INTERFACE_FUNCTION(int, lc_sphincs_sign_ctx, struct lc_sphincs_sig *sig,
        CKINT(f_ctx->fors_sign(sig->sigfors, ws->root, ws->mhash, &ctx_int,
                               ws->wots_addr));
 
+       unpoison(ws->root, sizeof(*(ws->root)));
+
        for (i = 0; i < LC_SPX_D; i++) {
                set_layer_addr(ws->tree_addr, i);
                set_tree_addr(ws->tree_addr, ws->tree);
@@ -274,6 +276,8 @@ LC_INTERFACE_FUNCTION(int, lc_sphincs_sign_ctx, struct lc_sphincs_sig *sig,
                                         ws->idx_leaf));
                wots_sig += LC_SPX_WOTS_BYTES + LC_SPX_TREE_HEIGHT * LC_SPX_N;
 
+               unpoison(ws->root, sizeof(*(ws->root)));
+
                /* Update the indices for the next layer. */
                ws->idx_leaf = (ws->tree & ((1 << LC_SPX_TREE_HEIGHT) - 1));
                ws->tree = ws->tree >> LC_SPX_TREE_HEIGHT

[smuellerDD]

Am Montag, 14. Oktober 2024, 08:39:46 MESZ schrieb MrPugh: Hi MrPugh,

To sign with SPHINCS+, we sign the data with FORS and the FORS root with WOTS+/Merkle and then for several iterations one Merkle root with another WOTS+/Merkle layer. Hence, you need to 'unpoison' each of those intermediate roots. This should look something like this in your code (not tested): ``` diff --git a/slh-dsa/src/sphincs_sign.c b/slh-dsa/src/sphincs_sign.c index c23ecf2..133f389 100644 --- a/slh-dsa/src/sphincs_sign.c +++ b/slh-dsa/src/sphincs_sign.c @@ -262,6 +262,8 @@ LC_INTERFACE_FUNCTION(int, lc_sphincs_sign_ctx, struct lc_sphincs_sig *sig, CKINT(f_ctx->fors_sign(sig->sigfors, ws->root, ws->mhash, &ctx_int, ws->wots_addr)); + unpoison(ws->root, sizeof(*(ws->root))); + for (i = 0; i < LC_SPX_D; i++) { set_layer_addr(ws->tree_addr, i); set_tree_addr(ws->tree_addr, ws->tree); @@ -274,6 +276,8 @@ LC_INTERFACE_FUNCTION(int, lc_sphincs_sign_ctx, struct lc_sphincs_sig *sig, ws->idx_leaf)); wots_sig += LC_SPX_WOTS_BYTES + LC_SPX_TREE_HEIGHT * LC_SPX_N; + unpoison(ws->root, sizeof(*(ws->root))); + /* Update the indices for the next layer. */ ws->idx_leaf = (ws->tree & ((1 << LC_SPX_TREE_HEIGHT) - 1)); ws->tree = ws->tree >> LC_SPX_TREE_HEIGHT ```

Thank you very much for the hint. The code compiles flawless with your changes. However, when I undo the changes I made to wots_gen_leafx1 and treehashx1 such that the code complies with the upstream version, valgrind still complains. Only with the changes (i.e. the use of the cmov() function which has a constant time conditional copy operation), valgrind stops complaining. PS: I have not tested the ARMv8 / AVX2 branches, but I suspect the same result. Ciao Stephan

[MrPugh]

I can only trace back the two issues in wots_gen_leafx1 and treehashx1 to idx_leaf, which is set by hash_message in the sign function, based on sig->r, on which you already do call 'unpoison'. Can you check if ws->idx_leaf in the sign function indeed is the culprit - and if that is already the case right after the call to hash_message?

[smuellerDD]

Apologies for the long delay, some other leancrypto developments took my time.

Now I came back to the issue and I was debugging it a bit more: When I unpoison the ws->root variable before the merkle_sign invocation, the valgrind complaint with the upstream branching code goes away.

The ws->root is generated by the fors_sign function. There, the origin of the side channel is ctx_int.sk_seed. I.e. when unpoison'ing this variable, all valgrind complaints go away.

[MrPugh]

I currently don't fully understand what issue remains after unpoisning ws->root. You could try to unpoison both ws->root and sig->sigfors after the call to fors_sign. Does that make a difference?

[smuellerDD]

Am Montag, 3. März 2025, 11:06:21 CET schrieb MrPugh: Hi MrPugh,

MrPugh left a comment (sphincs/sphincsplus#63) I currently don't fully understand what issue remains after unpoisning `ws->root`. You could try to unpoison both `ws->root` and `sig->sigfors` after the call to `fors_sign`. Does that make a difference?

Unpoisoning ws->root after the fors_sign alleviates the issue with the current upstream code. But my concern now is: is the root truly a non-sensitive parameter? Ciao Stephan

[MrPugh]

Yes, both the FORS and the WOTS+ root nodes are public information. They are in fact re-computed during verification (that is, if neither message, signature, nor public key are altered, in which case verification is expected to fail).

You can check this yourself by printing and comparing the respective data during (successful) singing and verification.