ML-KEM doesn't perform encapsulation key check

[ueno]

Describe the bug
When encapsulating, FIPS 203 7.1 suggests checking input key so any integers in the encoded public key are in the range [0, q - 1]. However, the current liboqs code seems to omit this check.

To Reproduce
Steps to reproduce the behavior:

1. Compile the attached test-kem.c with: gcc -o test-kem test-kem.c $(pkg-config liboqs --cflags --libs)
2. Run test-kem
3. You will see: test-kem: test-kem.c:48: main: Assertion 'rc != OQS_SUCCESS' failed.

Expected behavior
The program should exit normally.

Environment (please complete the following information):

• OS: Fedora Linux 40
• OpenSSL version 3.2.2
• Compiler version used gcc 14.2.1
• Build variables used -DBUILD_SHARED_LIBS=ON -DOQS_USE_AES_OPENSSL=ON -DOQS_USE_AES_INSTRUCTIONS=OFF -DOQS_DIST_BUILD=ON -DOQS_ALGS_ENABLED=STD_IANA -DOQS_USE_SHA3_OPENSSL=ON -DOQS_DLOPEN_OPENSSL=ON -DCMAKE_BUILD_TYPE=Debug -LAH
• liboqs version 0.11.0

Additional context
This was found when running a tlsfuzzer test script currently in development, against gnutls-serv (in MR).

[SWilson4]

Thanks for the report, @ueno. We pull our ML-KEM implementation from the pq-crystals/kyber repo. It seems to me that it would be better to add the optional checks upstream and then integrate the updated code into liboqs. Would you agree with that assessment?

As an aside, I don't believe we support the STD_IANA value for the OQS_ALGS_ENABLED variable—I assume this is something from a fork?

[SWilson4]

Also tagging @bhess as he is the one most familiar with the CRYSTALS algorithms.

[bhess]

Thanks for the report, input validation still needs to be added upstream, see pq-crystals/kyber#87 (comment)

[nidhidamodaran]

Can you please help me understand whether this patch to liboqs will be able to identify bad keys

+int poly_frombytes(poly *r, const uint8_t a[KYBER_POLYBYTES])
 {
   unsigned int i;
   for(i=0;i<KYBER_N/2;i++) {
     r->coeffs[2*i]   = ((a[3*i+0] >> 0) | ((uint16_t)a[3*i+1] << 8)) & 0xFFF;
     r->coeffs[2*i+1] = ((a[3*i+1] >> 4) | ((uint16_t)a[3*i+2] << 4)) & 0xFFF;
+    if((r->coeffs[2*i] >= KYBER_Q) || (r->coeffs[2*i+1]  >= KYBER_Q))
+       return -1;
   }
+  return 0;
 }

[tomato42]

@nidhidamodaran on first look, yes, it does look like the thing that's missing

[SWilson4]

Can you please help me understand whether this patch to liboqs will be able to identify bad keys

+int poly_frombytes(poly *r, const uint8_t a[KYBER_POLYBYTES])
 {
   unsigned int i;
   for(i=0;i<KYBER_N/2;i++) {
     r->coeffs[2*i]   = ((a[3*i+0] >> 0) | ((uint16_t)a[3*i+1] << 8)) & 0xFFF;
     r->coeffs[2*i+1] = ((a[3*i+1] >> 4) | ((uint16_t)a[3*i+2] << 4)) & 0xFFF;
+    if((r->coeffs[2*i] >= KYBER_Q) || (r->coeffs[2*i+1]  >= KYBER_Q))
+       return -1;
   }
+  return 0;
 }

This patch is not a good idea for a couple of reasons.

1. Most importantly, the >= operation is not constant time and may leak information about whatever data it operates on. The poly_frombytes function is used to process the secret key, so this is a problem.
2. This patch only works for the ref, non-optimized code. There's a good chance you're not running this code at all.

[tomato42]

Most importantly, the >= operation is not constant time and may leak information about whatever data it operates on. The poly_frombytes function is used to process the secret key, so this is a problem.

when would it be operating on a secret values though?

either it's used for checking input for decapsulation: that's public
or it's used for sanity checking output of encapsulation: that will be public...

[SWilson4]

Most importantly, the >= operation is not constant time and may leak information about whatever data it operates on. The poly_frombytes function is used to process the secret key, so this is a problem.

when would it be operating on a secret values though?

either it's used for checking input for decapsulation: that's public or it's used for sanity checking output of encapsulation: that will be public...

The poly_frombytes function is used throughout the Kyber / ML-KEM reference code. In particular, it's used (via the calls pack_sk <- polyvec_frombytes <- poly_frombytes) here to process the secret key at generation time.

[nidhidamodaran]

Right, for my use case i have defined a different API available only in ref implementation,

[SWilson4]

The poly_frombytes function is used throughout the Kyber / ML-KEM reference code. In particular, it's used (via the calls pack_sk <- polyvec_frombytes <- poly_frombytes) here to process the secret key at generation time.

Sorry, this trace isn't what I meant to send. Give me a second...

EDIT: Here is the correct trace. I mixed up tobytes and frombytes. It is used to process the secret key at decapsulation time.