Software GCM table calculation buggy with gcc -O3 #665

New issue

Closed

opened 2026-01-19 04:05:21 -06:00 by gilles-peskine-arm · 0 comments

gilles-peskine-arm commented

2026-01-19 04:05:21 -06:00

(Migrated from github.com)

Our pure software implementation of GCM is broken when compiled with gcc -O3 in Mbed TLS 3.6.5 and TF-PSA-Crypto 1.0.0. All positive unit tests involving GCM with a non-empty message fail.

(This was also mentioned in https://github.com/Mbed-TLS/mbedtls/issues/9743#issuecomment-2449063776, but the compiler warnings in the original issue are unrelated.)

Reproduction

Steps to reproduce:

Compile with gcc -O3, using GCC 10 through 14.2. I haven't been able to reproduce the bug at -O2, with older/newer GCC (GCC 9, GCC 14.3, GCC 15.1, GCC 15.2), or with Clang. I don't know exactly which (combination of) optimization(s) trigger the bug, but I'm pretty sure that it only happens with sufficient loop unrolling.
Arrange for the buggy code path to be invoked. Only little-endian architectures are buggy. 32-bit vs 64-bit makes no difference. Any of the following triggers the bug:
- A little-endian architecture other than x86 and arm, in the default configuration.
- https://github.com/gilles-peskine-arm/mbedtls/tree/gcm-little-endian-instrument-3.6, with AESNI and AESCE disabled, built with -O3 -DMBEDTLS_ONLY_GENERIC_CODE. This forces the same code path as with non-x86/arm architectures.
```
  mbedtls-prepare-build -p opt -d build-generic-gcc13-opt --config-unset=MBEDTLS_AESCE_C,MBEDTLS_AESNI_C --cc=gcc-13 --cflags='-O3 -DMBEDTLS_ONLY_GENERIC_CODE'
```
- https://github.com/gilles-peskine-arm/mbedtls/tree/gcm-little-endian-instrument-3.6, with AESNI and AESCE disabled, built with -O3 -DGCM_BREAK_PUT. This pinpoints the code change to just the one buggy calculation.
  
  Note that I had to patch two places to use the potentially-buggy PUT code. If I only patch one of them, the calculation is correct. If I patch more, the calculation has the same buggy result.
```
  mbedtls-prepare-build -d build-breakgcm-gcc13-opt -p opt --cc=gcc-13 --cflags='-O3 -DGCM_BREAK_PUT' --config-unset=MBEDTLS_AESNI_C,MBEDTLS_AESCE_C
```

Analysis

I haven't traced back when the bug started, but I think it was between 3.5.0 and 3.6.0: the likely culprit is either https://github.com/Mbed-TLS/mbedtls/pull/8719 or https://github.com/Mbed-TLS/mbedtls/pull/8788.

The bug is specifically in gcm_gen_table(), when the following code path is used:

GCM is done in software (no AESNI or AESCE).
The platform is little-endian.
The optimization path in alignment.h has MBEDTLS_EFFICIENT_UNALIGNED_ACCESS disabled, and UINT_UNALIGNED_STRUCT enabled.

In https://github.com/gilles-peskine-arm/mbedtls/tree/gcm-little-endian-instrument-3.6, I added code to print the resulting table. Here's the correct table for the first test case of test_suite_gcm.aes128_en.run:

0000000000000000 0000000000000000
15febd98009bc186 554551b6d7c95112
2bfd7b300137830c aa8aa36daf92a224
3e03c6a801ac428a ffcff2db785bf336
57faf660026f0619 551546db5f254448
42044bf802f4c79f 0050176d88ec155a
7c078d5003588515 ff9fe5b6f0b7e66c
69f930c803c34493 aadab400277eb77e
aff5ecc004de0c32 aa2a8db6be4a8890
ba0b51580445cdb4 ff6fdc006983d982
840897f005e98f3e 00a02edb11d82ab4
91f62a6805724eb8 55e57f6dc6117ba6
f80f1aa006b10a2b ff3fcb6de16fccd8
edf1a738062acbad aa7a9adb36a69dca
d3f2619007868927 55b568004efd6efc
c60cdc08071d48a1 00f039b699343fee

And here's the table in the buggy case (I got the same bad values for all the buggy cases that I've tried):

0000000000000000 0000000000000000
1500000000000000 554551b6d7c95112
2bfd7b300137830c aa8aa36daf92a224
3efd7b300137830c ffcff2db785bf336
57faf660026f0619 551546db5f254448
42faf660026f0619 0050176d88ec155a
7c078d5003588515 ff9fe5b6f0b7e66c
69078d5003588515 aadab400277eb77e
aff5ecc004de0c32 aa2a8db6be4a8890
baf5ecc004de0c32 ff6fdc006983d982
840897f005e98f3e 00a02edb11d82ab4
910897f005e98f3e 55e57f6dc6117ba6
f80f1aa006b10a2b ff3fcb6de16fccd8
ed0f1aa006b10a2b aa7a9adb36a69dca
d3f2619007868927 55b568004efd6efc
c6f2619007868927 00f039b699343fee

So what happens is that every other row has 9 correct bytes and 7 bytes which duplicate the previous row.

Whose fault is it?

This code isn't standard C, but it says so on the tin: it uses __attribute__((packed)) to cheat with alignment constraints. It's not clear to me where, if anywhere, our code misuses GCC. So it could be a compiler bug. But our code is rather twisty and dodgy, so it doesn't inspire a lot of confidence in me.

The same code breaks on Ubuntu 24.04 with GCC 14.2 but works on Ubuntu 25.10 with GCC 14.3 (x86_64 in both cases). So we might have hit one of the 219 bugs fixed in GCC 14.3.

Goal of this issue

Create an all.sh job that reproduces the problem: build with gcc -O3 using a problematic version of GCC, with AESNI/AESCE disabled, and arranging to trigger the problematic code path in alignment.h. (This may require adding a private config macro.)
Fix the bug in GCM, trying to minimize disruption in alignment.h. (Cleaning up alignment.h is a bigger task that is out of scope here.) We consider the bug to be fixed if the non-regression test passes. Note that in gcm.c, the data is more aligned than the worse case of alignment.h, so we can probably get away with using simpler ways to copy/xor that are as efficient.
We don't have big-endian testing on the CI, so make sure to test locally on a big-endian platform (e.g. PPC).

Our pure software implementation of GCM is broken when compiled with `gcc -O3` in Mbed TLS 3.6.5 and TF-PSA-Crypto 1.0.0. All positive unit tests involving GCM with a non-empty message fail. (This was also mentioned in https://github.com/Mbed-TLS/mbedtls/issues/9743#issuecomment-2449063776, but the compiler warnings in the original issue are unrelated.) ### Reproduction Steps to reproduce: * Compile with **`gcc -O3`**, using GCC 10 through 14.2. I haven't been able to reproduce the bug at `-O2`, with older/newer GCC (GCC 9, GCC 14.3, GCC 15.1, GCC 15.2), or with Clang. I don't know exactly which (combination of) optimization(s) trigger the bug, but I'm pretty sure that it only happens with sufficient loop unrolling. * Arrange for the buggy code path to be invoked. Only **little-endian** architectures are buggy. 32-bit vs 64-bit makes no difference. Any of the following triggers the bug: * A little-endian architecture other than x86 and arm, in the default configuration. * https://github.com/gilles-peskine-arm/mbedtls/tree/gcm-little-endian-instrument-3.6, with AESNI and AESCE disabled, built with `-O3 -DMBEDTLS_ONLY_GENERIC_CODE`. This forces the same code path as with non-x86/arm architectures. mbedtls-prepare-build -p opt -d build-generic-gcc13-opt --config-unset=MBEDTLS_AESCE_C,MBEDTLS_AESNI_C --cc=gcc-13 --cflags='-O3 -DMBEDTLS_ONLY_GENERIC_CODE' * https://github.com/gilles-peskine-arm/mbedtls/tree/gcm-little-endian-instrument-3.6, with AESNI and AESCE disabled, built with `-O3 -DGCM_BREAK_PUT`. This pinpoints the code change to just the one buggy calculation. Note that I had to patch two places to use the potentially-buggy PUT code. If I only patch one of them, the calculation is correct. If I patch more, the calculation has the same buggy result. mbedtls-prepare-build -d build-breakgcm-gcc13-opt -p opt --cc=gcc-13 --cflags='-O3 -DGCM_BREAK_PUT' --config-unset=MBEDTLS_AESNI_C,MBEDTLS_AESCE_C ### Analysis I haven't traced back when the bug started, but I think it was between 3.5.0 and 3.6.0: the likely culprit is either https://github.com/Mbed-TLS/mbedtls/pull/8719 or https://github.com/Mbed-TLS/mbedtls/pull/8788. The bug is specifically in `gcm_gen_table()`, when the following code path is used: * GCM is done in software (no AESNI or AESCE). * The platform is little-endian. * The optimization path in [`alignment.h`](https://github.com/Mbed-TLS/mbedtls/blob/mbedtls-3.6.0/library/alignment.h) has `MBEDTLS_EFFICIENT_UNALIGNED_ACCESS` disabled, and `UINT_UNALIGNED_STRUCT` enabled. In https://github.com/gilles-peskine-arm/mbedtls/tree/gcm-little-endian-instrument-3.6, I added code to print the resulting table. Here's the correct table for the first test case of `test_suite_gcm.aes128_en.run`: ``` 0000000000000000 0000000000000000 15febd98009bc186 554551b6d7c95112 2bfd7b300137830c aa8aa36daf92a224 3e03c6a801ac428a ffcff2db785bf336 57faf660026f0619 551546db5f254448 42044bf802f4c79f 0050176d88ec155a 7c078d5003588515 ff9fe5b6f0b7e66c 69f930c803c34493 aadab400277eb77e aff5ecc004de0c32 aa2a8db6be4a8890 ba0b51580445cdb4 ff6fdc006983d982 840897f005e98f3e 00a02edb11d82ab4 91f62a6805724eb8 55e57f6dc6117ba6 f80f1aa006b10a2b ff3fcb6de16fccd8 edf1a738062acbad aa7a9adb36a69dca d3f2619007868927 55b568004efd6efc c60cdc08071d48a1 00f039b699343fee ``` And here's the table in the buggy case (I got the same bad values for all the buggy cases that I've tried): ``` 0000000000000000 0000000000000000 1500000000000000 554551b6d7c95112 2bfd7b300137830c aa8aa36daf92a224 3efd7b300137830c ffcff2db785bf336 57faf660026f0619 551546db5f254448 42faf660026f0619 0050176d88ec155a 7c078d5003588515 ff9fe5b6f0b7e66c 69078d5003588515 aadab400277eb77e aff5ecc004de0c32 aa2a8db6be4a8890 baf5ecc004de0c32 ff6fdc006983d982 840897f005e98f3e 00a02edb11d82ab4 910897f005e98f3e 55e57f6dc6117ba6 f80f1aa006b10a2b ff3fcb6de16fccd8 ed0f1aa006b10a2b aa7a9adb36a69dca d3f2619007868927 55b568004efd6efc c6f2619007868927 00f039b699343fee ``` So what happens is that every other row has 9 correct bytes and 7 bytes which duplicate the previous row. ### Whose fault is it? This code isn't standard C, but it says so on the tin: it uses `__attribute__((packed))` to cheat with alignment constraints. It's not clear to me where, if anywhere, our code misuses GCC. So it could be a compiler bug. But our code is rather twisty and dodgy, so it doesn't inspire a lot of confidence in me. The same code breaks on Ubuntu 24.04 with GCC 14.2 but works on Ubuntu 25.10 with GCC 14.3 (x86_64 in both cases). So we might have hit one of the [219 bugs fixed in GCC 14.3](https://gcc.gnu.org/bugzilla/buglist.cgi?bug_status=RESOLVED&resolution=FIXED&target_milestone=14.3). ### Goal of this issue * Create an `all.sh` job that reproduces the problem: build with `gcc -O3` using a problematic version of GCC, with AESNI/AESCE disabled, and arranging to trigger the problematic code path in `alignment.h`. (This may require adding a **private** config macro.) * Fix the bug in GCM, trying to minimize disruption in `alignment.h`. (Cleaning up `alignment.h` is a bigger task that is out of scope here.) We consider the bug to be fixed if the non-regression test passes. Note that in `gcm.c`, the data is more aligned than the worse case of `alignment.h`, so we can probably get away with using simpler ways to copy/xor that are as efficient. * We don't have big-endian testing on the CI, so make sure to test locally on a big-endian platform (e.g. PPC).

No milestone

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

gh-Mbed-TLS/TF-PSA-Crypto#665

No description provided.

Rows
Columns