ellswift: constant-time tests don't cover `auxrnd32` in `secp256k1_ellswift_create` #1962

The header of secp256k1_ellswift_create says (include/secp256k1_ellswift.h:139):

Constant time in seckey and auxrnd32, but not in the resulting public key.

The code is constant time in seckey32, but not in auxrnd32. ctime_tests does not catch it because it marks only the key secret: its two calls pass NULL and the public ellswift buffer as auxrnd32 (src/ctime_tests.c:314,319).

In src/modules/ellswift/main_impl.h, seckey32 and 32 zero bytes fill the 64-byte block after the tagged-hash midstate, so that block is compressed into hash.s (455-456; src/hash_impl.h:43-48, :220-225). Line 458 then declassifies hash.s only:

/* Declassify only hash state. seckey32 has been hashed, but copy remains in the hash buffer */

auxrnd32 is written after that, into hash.buf (459), and is compressed only inside secp256k1_ellswift_prng (310-325). The branch pool (349) and each u (356) are PRNG outputs. secp256k1_ellswift_xswiftec_inv_var branches on them (198, 256), and the loop stops at the first accepted candidate (365).

I added a call that marks auxrnd32 secret too (b72730b, CI run). 70 jobs fail on their ctime_tests run: 66 run it under Valgrind and exit 42, 4 under MSan and exit 1. All 70 have the ellswift module on, and make check passes in each (# FAIL: 0). The 4 jobs that run ctime_tests with ellswift off pass. From one MSan job, addresses trimmed:

WARNING: MemorySanitizer: use-of-uninitialized-value
    [#0](/bitcoin-core-secp256k1/0/) in secp256k1_ellswift_xswiftec_inv_var src/modules/ellswift/main_impl.h:198:9
    [#1](/bitcoin-core-secp256k1/1/) in secp256k1_ellswift_xelligatorswift_var src/modules/ellswift/main_impl.h:365:13

On timing I can argue only from the code. The output holds only the accepted u and t, and the rejected candidates are other SHA256 outputs of the same inputs. I don't see how they would reveal seckey32 or auxrnd32 without inverting SHA256, but I have not proven it.

I see two options:

1. Weaken the header for auxrnd32.
2. Keep the header. Declassify each PRNG output in secp256k1_ellswift_xelligatorswift_var, as line 458 declassifies a hash of seckey32, and mark auxrnd32 secret in ctime_tests.c. I have not tried this. Declassifying hash.s again after writing auxrnd32 would not be enough, since auxrnd32 is still in hash.buf.

Which do you prefer? I can open a PR for either.

Assisted-by: my usual tools (LLM, Internet, computer). Mistakes are mine.

On timing I can argue only from the code. The output holds only the accepted u and t, and the rejected candidates are other SHA256 outputs of the same inputs. I don't see how they would reveal seckey32 or auxrnd32 without inverting SHA256, but I have not proven it.

Indeed, this is not a security issue. The code is strictly speaking not constant-time time in auxrnd32, but branches happen on the resulting hash. The same is true for seckey32. The docs don't mention that seckey32 and auxrnd32 stay secret only against a computationally bounded timing attacker but this is fine.

So the issue is that the ctime tests don't cover auxrnd32 (and adding it is not trivial because we need a precise declassification). I've edited the title to make this clear.

So how do we resolve this?

1. Dropping the constant-time guarantee would be okay but dropping a guarantee doesn't sound like the ideal option (even though I can't see how anyone would rely on this guarantee in a meaningful way)
2. Declassifying PRNG outputs sounds good though it adds complexity to the already complex declassification here.
3. We could change the PRNG: We could create a seed = seckey32 XOR SHA256(auxrnd32) first (like in BIP340, maybe with a tagged hash), declassify seed and pass that one around to other functions instead of a hasher. (Or open a new hasher, write seed into it, and pass that one around.) This makes the declassification stuff simpler and doesn't even add a compression. Changing the PRNG is fine according to the header, though I'm not sure if it's worth doing it.

cc @sipa

also cc @furszy author of #1863