HQC implementation out of date/vulnerable

[ambiso]

The current HQC implementation still contains the timing side-channel vulnerable rejection sampling, whose running time is dependent on the seed that is derived from the secret message.

PQClean/crypto_kem/hqc-rmrs-128/avx2/vector.c

Lines 49 to 54 in f1ef566

	while (i < weight) {
	do {
	if (j == random_bytes_size) {
	seedexpander(ctx, rand_bytes, random_bytes_size);
	j = 0;
	}

See here for details.

There's a new round 4 submission that uses Sendrier's countermeasure (see vector.c).

Unfortunately with gcc the modulo reductions in the loop compile to divide instructions, which might not be constant-time.

clang successfully compiles the modulo reductions down to (I believe) Barrett reductions (which don't use div instructions).

I don't know how practical it is however to exploit any leakage from this on x86, however the clean version which might be used to target microprocessors where division might be very leaky.

One could manually inline the assembly to ensure that the timing behavior of the implementation doesn't depend on whether the compiler is having a good day or not 🙂

[thomwiggers]

One could manually inline the assembly to ensure that the timing behavior of the implementation doesn't depend on whether the compiler is having a good day or not 🙂

This, of course, is not a solution for PQClean's clean implementation because then the code would not be portable. Updating the HQC implementation is "on the list", but not a very high priority issue right now I'm afraid. Naturally I would be very happy if someone submits a patch.

See also some concurrent discussion at open-quantum-safe/liboqs#1319.

[thomwiggers]

There are more problems apparently: open-quantum-safe/liboqs#995