Undefined behavior in the FrodoKEM reference implementation

[protz]

As it stands, the FrodoKEM source code contains several instances of undefined behavior. This makes it hard to reason about what the code may do, since the compiler can potentially do anything -- it may also turn into security issues.

The two chief issues are:

• lack of alignment of some stack variables, which are then cast as as pointers of type uint32_t*. The C standard mandates that such pointers be aligned on a sizeof(uint32) == 4 byte boundary, but right now, these pointers are only aligned on a two-bytes boundary because they originate from a stack allocation of uint16_ts.
• potentially violating strict aliasing by having two live pointers that are aliases, yet have different types, none of which is char*

See https://blog.regehr.org/archives/1520 for some background context about UB and why it undermines properties of programs (including security and correctness).

The first issue could potentially be fixed as follows:

diff --git a/FrodoKEM/src/frodo_macrify.c b/FrodoKEM/src/frodo_macrify.c
index 0acc623..3c1b08d 100644
--- a/FrodoKEM/src/frodo_macrify.c
+++ b/FrodoKEM/src/frodo_macrify.c
@@ -344,7 +344,7 @@ void frodo_key_encode(uint16_t *out, const uint16_t *in)
     for (i = 0; i < nwords; i++) {
         temp = 0;
         for(j = 0; j < PARAMS_EXTRACTED_BITS; j++)
-            temp |= ((uint64_t)((uint8_t*)in)[i*PARAMS_EXTRACTED_BITS + j]) << (8*j);
+            temp |= ((uint64_t)((const uint8_t*)in)[i*PARAMS_EXTRACTED_BITS + j]) << (8*j);
         for (j = 0; j < npieces_word; j++) {
             *pos = (uint16_t)((temp & mask) << (PARAMS_LOGQ - PARAMS_EXTRACTED_BITS));
             temp >>= PARAMS_EXTRACTED_BITS;
diff --git a/FrodoKEM/src/kem.c b/FrodoKEM/src/kem.c
index c3152a9..fb3b7af 100644
--- a/FrodoKEM/src/kem.c
+++ b/FrodoKEM/src/kem.c
@@ -23,8 +23,8 @@ int crypto_kem_keypair(unsigned char* pk, unsigned char* sk)
     uint8_t *sk_pk = &sk[CRYPTO_BYTES];
     uint8_t *sk_S = &sk[CRYPTO_BYTES + CRYPTO_PUBLICKEYBYTES];
     uint8_t *sk_pkh = &sk[CRYPTO_BYTES + CRYPTO_PUBLICKEYBYTES + 2*PARAMS_N*PARAMS_NBAR];
-    uint16_t B[PARAMS_N*PARAMS_NBAR] = {0};
-    uint16_t S[2*PARAMS_N*PARAMS_NBAR] = {0};                          // contains secret data
+    ALIGN_HEADER(32) uint16_t B[PARAMS_N*PARAMS_NBAR] ALIGN_FOOTER(32) = {0};
+    ALIGN_HEADER(32) uint16_t S[2*PARAMS_N*PARAMS_NBAR] ALIGN_FOOTER(32) = {0};                          // contains secret data
     uint16_t *E = (uint16_t *)&S[PARAMS_N*PARAMS_NBAR];                // contains secret data
     uint8_t randomness[CRYPTO_BYTES + BYTES_SEED_SE + BYTES_SEED_A];   // contains secret data via randomness_s and randomness_seedSE
     uint8_t *randomness_s = &randomness[0];                            // contains secret data
@@ -93,7 +93,7 @@ int crypto_kem_enc(unsigned char *ct, unsigned char *ss, const unsigned char *pk
     ALIGN_HEADER(32) uint16_t Sp[(2*PARAMS_N+PARAMS_NBAR)*PARAMS_NBAR] ALIGN_FOOTER(32) = {0};  // contains secret data
     uint16_t *Ep = (uint16_t *)&Sp[PARAMS_N*PARAMS_NBAR];              // contains secret data
     uint16_t *Epp = (uint16_t *)&Sp[2*PARAMS_N*PARAMS_NBAR];           // contains secret data
-    uint8_t G2in[BYTES_PKHASH + BYTES_MU + BYTES_SALT];                // contains secret data via mu
+    ALIGN_HEADER(32) uint8_t G2in[BYTES_PKHASH + BYTES_MU + BYTES_SALT] ALIGN_FOOTER(32);                // contains secret data via mu
     uint8_t *pkh = &G2in[0];
     uint8_t *mu = &G2in[BYTES_PKHASH];                                 // contains secret data
     uint8_t *salt = &G2in[BYTES_PKHASH + BYTES_MU];
@@ -184,7 +184,7 @@ int crypto_kem_dec(unsigned char *ss, const unsigned char *ct, const unsigned ch
     const uint8_t *sk_pkh = &sk[CRYPTO_BYTES + CRYPTO_PUBLICKEYBYTES + 2*PARAMS_N*PARAMS_NBAR];
     const uint8_t *pk_seedA = &sk_pk[0];
     const uint8_t *pk_b = &sk_pk[BYTES_SEED_A];
-    uint8_t G2in[BYTES_PKHASH + BYTES_MU + BYTES_SALT];                // contains secret data via muprime
+    ALIGN_HEADER(32) uint8_t G2in[BYTES_PKHASH + BYTES_MU + BYTES_SALT] ALIGN_FOOTER(32);                // contains secret data via muprime
     uint8_t *pkh = &G2in[0];
     uint8_t *muprime = &G2in[BYTES_PKHASH];                            // contains secret data
     uint8_t *G2in_salt = &G2in[BYTES_PKHASH + BYTES_MU];

However, this does not resolve the issue with strict aliasing.

The second issue can be fixed as follows:

diff --git a/FrodoKEM/src/frodo_macrify.c b/FrodoKEM/src/frodo_macrify.c
index 0acc623..3c1b08d 100644
--- a/FrodoKEM/src/frodo_macrify.c
+++ b/FrodoKEM/src/frodo_macrify.c
@@ -30,7 +30,7 @@ int frodo_mul_add_as_plus_e(uint16_t *out, const uint16_t *s, const uint16_t *e,
     ALIGN_HEADER(32) int16_t a_row[4*PARAMS_N] ALIGN_FOOTER(32) = {0};

     for (i = 0; i < (PARAMS_N*PARAMS_NBAR); i += 2) {
-        *((uint32_t*)&out[i]) = *((uint32_t*)&e[i]);
+        memcpy(&out[i], &e[i], 4);
     }

This also fixes the first issue as a side-effect. However, I wonder why the loop is necessary here -- could this simply be replaced by a memcpy?

[protz]

Note that I was slightly surprised to see those stack variables aligned on a 32-byte boundary. Is this intentional?

[dstebila]

Thanks for the report.

In terms of these being undefined behaviour, should we expect clang's UBSan to catch these? I turned it on in my local build but it didn't raise any warnings.

For the second issue, perhaps this would be even simpler, just memcpy the whole of e into out:

memcpy(out, e, sizeof(uint16_t) * PARAMS_N * PARAMS_NBAR);

[msprotz]

I think UBSan won't detect the alignment issues if the particular stack layout on your ABI happens to have the correct alignment (i.e. if clang made a decision that aligns the array on a 4-byte boundary).

I agree that a complete memcpy would avoid all the issues. I would still align the stack arrays for performance reasons, because then you'll get a fast SSE-based memcpy (since the pointers will be aligned).

[dstebila]

I agree that a complete memcpy would avoid all the issues. I would still align the stack arrays for performance reasons, because then you'll get a fast SSE-based memcpy (since the pointers will be aligned).

I don't fully understand this suggestion. Are you suggesting that we also align out and e to improve performance? But out and e are parameters to the function, so can we even impose alignment conditions on them?

[msprotz]

My suggestion is to i) use memcpy (avoids UB) and ii) align B, S, and G2in on the stack, so that at run-time, when that memcpy is called, the effective arguments to memcpy are already aligned and go directly to the SIMD fast-path (my mental model is that actual implementation of memcpy have to do extra work if the pointers are not already aligned, see e.g. https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/multiarch/memset-vec-unaligned-erms.S)

[msprotz]

(Because B, S and G2in eventually end up as the out and e arguments to that memcpy)