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?