Known non-constant time behaviour in HQC

[jschanck]

Our constant time test raises three issues with the "clean" implementation of the HQC code. I've reviewed these and I am of the opinion that they are true instances of non-constant time behaviour.

I've copied a description of each issue and a link to the issue file below.

---

hqc_gf_mul

Secret-dependent indexing into the "gf_exp" array in line 20 of gf.c:

liboqs/src/kem/hqc/pqclean_hqc-rmrs-128_clean/gf.c

Lines 16 to 21 in 8981b7f

	uint16_t PQCLEAN_HQCRMRS128_CLEAN_gf_mul(uint16_t a, uint16_t b) {
	uint16_t mask;
	mask = (uint16_t) (-((int32_t) a) >> 31); // a != 0
	mask &= (uint16_t) (-((int32_t) b) >> 31); // b != 0
	return mask & gf_exp[PQCLEAN_HQCRMRS128_CLEAN_gf_mod(gf_log[a] + gf_log[b])];
	}

---

hqc_vect_set_random_fixed_weight

Line 90 of vector.c reveals partial information about the location of non-zero bits in a secret fixed weight vector

liboqs/src/kem/hqc/pqclean_hqc-rmrs-128_clean/vector.c

Lines 82 to 92 in 8981b7f

	void PQCLEAN_HQCRMRS128_CLEAN_vect_set_random_fixed_weight(AES_XOF_struct *ctx, uint64_t *v, uint16_t weight) {
	uint32_t tmp[PARAM_OMEGA_R] = {0};
	PQCLEAN_HQCRMRS128_CLEAN_vect_set_random_fixed_weight_by_coordinates(ctx, tmp, weight);
	for (size_t i = 0; i < weight; ++i) {
	int32_t index = tmp[i] / 64;
	int32_t pos = tmp[i] % 64;
	v[index] |= ((uint64_t) 1) << pos;
	}
	}

---

hqc_fast_convolution_mult

The "fast_convolution_mult" routine makes secret dependent accesses to an array. It obfuscates the pattern of memory accesses by applying some permutations, but I'm not convinced that this is an adequate countermeasure.

liboqs/src/kem/hqc/pqclean_hqc-rmrs-128_clean/gf2x.c

Line 70 in 8981b7f

static void fast_convolution_mult(uint8_t *o, const uint32_t *a1, const uint64_t *a2, uint16_t weight, AES_XOF_struct *ctx) {

[dstebila]

Have you raised this with PQClean and/or the HQC team?

[jschanck]

I have not. Philippe Gaborit (of the HQC team) posted to pqc-forum on Nov. 3 2020:

the reference version is not secure (and is not supposed to be), for instance it is not constant time.

So I assume they are aware of the issues.

In the same email, Philippe says that the team will fix a number of other problems that were identified by PQClean. We're still waiting on an updated code package.

[baentsch]

Quick "sanity" question: We are holding the release of 0.7.2 on constant-time issues in Picnic -- but not on this, apparently same, issue in HQC: Intentional or omission?