crypto: Add AES-GCM implementation to lib/crypto

Provide a generic library implementation of AES-GCM which can be used really early during boot, e.g., to communicate with the security coprocessor on SEV-SNP virtual machines to bring up secondary cores. This is needed because the crypto API is not available yet this early.

We cannot rely on special instructions for AES or polynomial multiplication, which are arch specific and rely on in-kernel SIMD infrastructure. Instead, add a generic C implementation that combines the existing C implementations of AES and multiplication in GF(2^128).

To reduce the risk of forgery attacks, replace data dependent table lookups and conditional branches in the used gf128mul routine with constant-time equivalents. The AES library has already been robustified to some extent to prevent known-plaintext timing attacks on the key, but we call it with interrupts disabled to make it a bit more robust. (Note that in SEV-SNP context, the VMM is untrusted, and is able to inject interrupts arbitrarily, and potentially maliciously.)

Changes since v4:
- Rename CONFIG_CRYPTO_GF128MUL to CONFIG_CRYPTO_LIB_GF128MUL
- Use bool return value for decrypt routine to align with other AEAD library code
- Return -ENODEV on selftest failure to align with other algos
- Use pr_err() not WARN() on selftest failure for the same reason
- Mention in a code comment that the counter cannot roll over or result in a carry due to the width of the type representing the size of the input

Changes since v3:
- rename GCM-AES to AES-GCM

Changes since v2:
- move gf128mul to lib/crypto
- add patch #2 to make gf128mul_lle constant time
- fix kerneldoc headers and drop them from the .h file

Changes since v1:
- rename gcm to gcmaes to reflect that GCM is also used in combination with other symmetric ciphers (Jason)
- add Nikunj's Tested-by

Ard Biesheuvel (3):
crypto: move gf128mul library into lib/crypto
crypto: gf128mul - make gf128mul_lle time invariant
crypto: aesgcm - Provide minimal library implementation

 arch/arm/crypto/Kconfig           |   2 +-
 arch/arm64/crypto/Kconfig         |   2 +-
 crypto/Kconfig                    |   9 +-
 crypto/Makefile                   |   1 -
 drivers/crypto/chelsio/Kconfig    |   2 +-
 include/crypto/gcm.h              |  22 +
 lib/crypto/Kconfig                |   9 +
 lib/crypto/Makefile               |   5 +
 lib/crypto/aesgcm.c               | 727 ++++++++++++++++++++
 {crypto => lib/crypto}/gf128mul.c |  58 +-
 10 files changed, 808 insertions(+), 29 deletions(-)
 create mode 100644 lib/crypto/aesgcm.c
 rename {crypto => lib/crypto}/gf128mul.c (87%)

2.35.1

The gf128mul library does not depend on the crypto API at all, so it can be moved into lib/crypto. This will allow us to use it in other library code in a subsequent patch without having to depend on CONFIG_CRYPTO.

While at it, change the Kconfig symbol name to align with other crypto library implementations. However, the source file name is retained, as it is reflected in the module .ko filename, and changing this might break things for users.

---
 arch/arm/crypto/Kconfig           | 2 +-
 arch/arm64/crypto/Kconfig         | 2 +-
 crypto/Kconfig                    | 9 +++------
 crypto/Makefile                   | 1 -
 drivers/crypto/chelsio/Kconfig    | 2 +-
 lib/crypto/Kconfig                | 3 +++
 lib/crypto/Makefile               | 2 ++
 {crypto => lib/crypto}/gf128mul.c | 0
 8 files changed, 11 insertions(+), 10 deletions(-)

index 3858c4d4cb98854d..7b2b7d043d9be9e6 100644
@@ -18,7 +18,7 @@ config CRYPTO_GHASH_ARM_CE
 	depends on KERNEL_MODE_NEON
 	select CRYPTO_HASH
 	select CRYPTO_CRYPTD
-	select CRYPTO_GF128MUL
+	select CRYPTO_LIB_GF128MUL
 	help
 	  GCM GHASH function (NIST SP800-38D)
 

index 8bd80508a710d112..8542edaf592dc491 100644
@@ -6,8 +6,8 @@ config CRYPTO_GHASH_ARM64_CE
 	tristate "Hash functions: GHASH (ARMv8 Crypto Extensions)"
 	depends on KERNEL_MODE_NEON
 	select CRYPTO_HASH
-	select CRYPTO_GF128MUL
 	select CRYPTO_LIB_AES
+	select CRYPTO_LIB_GF128MUL
 	select CRYPTO_AEAD
 	help
 	  GCM GHASH function (NIST SP800-38D)

index d779667671b23f03..9c86f704515761c4 100644
@@ -175,9 +175,6 @@ config CRYPTO_MANAGER_EXTRA_TESTS
 	  This is intended for developer use only, as these tests take much
 	  longer to run than the normal self tests.
 
-config CRYPTO_GF128MUL
-	tristate
-
 config CRYPTO_NULL
 	tristate "Null algorithms"
 	select CRYPTO_NULL2

@@ -714,9 +711,9 @@ config CRYPTO_KEYWRAP
 
 config CRYPTO_LRW
 	tristate "LRW (Liskov Rivest Wagner)"
+	select CRYPTO_LIB_GF128MUL
 	select CRYPTO_SKCIPHER
 	select CRYPTO_MANAGER
-	select CRYPTO_GF128MUL
 	select CRYPTO_ECB
 	help
 	  LRW (Liskov Rivest Wagner) mode

@@ -926,8 +923,8 @@ config CRYPTO_CMAC
 
 config CRYPTO_GHASH
 	tristate "GHASH"
-	select CRYPTO_GF128MUL
 	select CRYPTO_HASH
+	select CRYPTO_LIB_GF128MUL
 	help
 	  GCM GHASH function (NIST SP800-38D)
 

@@ -967,8 +964,8 @@ config CRYPTO_MICHAEL_MIC
 
 config CRYPTO_POLYVAL
 	tristate
-	select CRYPTO_GF128MUL
 	select CRYPTO_HASH
+	select CRYPTO_LIB_GF128MUL
 	help
 	  POLYVAL hash function for HCTR2
 

index 303b21c43df05a5e..d0126c915834b2f0 100644
@@ -85,7 +85,6 @@ obj-$(CONFIG_CRYPTO_WP512) += wp512.o
 CFLAGS_wp512.o := $(call cc-option,-fno-schedule-insns)  # https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79149
 obj-$(CONFIG_CRYPTO_BLAKE2B) += blake2b_generic.o
 CFLAGS_blake2b_generic.o := -Wframe-larger-than=4096 #  https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105930
-obj-$(CONFIG_CRYPTO_GF128MUL) += gf128mul.o
 obj-$(CONFIG_CRYPTO_ECB) += ecb.o
 obj-$(CONFIG_CRYPTO_CBC) += cbc.o
 obj-$(CONFIG_CRYPTO_CFB) += cfb.o

index f886401af13e7b27..5dd3f6a4781a2c96 100644
@@ -3,11 +3,11 @@ config CRYPTO_DEV_CHELSIO
 	tristate "Chelsio Crypto Co-processor Driver"
 	depends on CHELSIO_T4
 	select CRYPTO_LIB_AES
+	select CRYPTO_LIB_GF128MUL
 	select CRYPTO_SHA1
 	select CRYPTO_SHA256
 	select CRYPTO_SHA512
 	select CRYPTO_AUTHENC
-	select CRYPTO_GF128MUL
 	help
 	  The Chelsio Crypto Co-processor driver for T6 adapters.
 

index 7e9683e9f5c63645..6767d86959de8f9c 100644
@@ -11,6 +11,9 @@ config CRYPTO_LIB_AES
 config CRYPTO_LIB_ARC4
 	tristate
 
+config CRYPTO_LIB_GF128MUL
+	tristate
+
 config CRYPTO_ARCH_HAVE_LIB_BLAKE2S
 	bool
 	help

index c852f067ab06019e..7000eeb72286e253 100644
@@ -13,6 +13,8 @@ libaes-y					:= aes.o
 obj-$(CONFIG_CRYPTO_LIB_ARC4)			+= libarc4.o
 libarc4-y					:= arc4.o
 
+obj-$(CONFIG_CRYPTO_LIB_GF128MUL)		+= gf128mul.o
+
 # blake2s is used by the /dev/random driver which is always builtin
 obj-y						+= libblake2s.o
 libblake2s-y					:= blake2s.o

similarity index 100%
rename from crypto/gf128mul.c
rename to lib/crypto/gf128mul.c

2.35.1

The gf128mul library has different variants with different memory/performance tradeoffs, where the faster ones use 4k or 64k lookup tables precomputed at runtime, which are based on one of the multiplication factors, which is commonly the key for keyed hash algorithms such as GHASH.

The slowest variant is gf128_mul_lle() [and its bbe/ble counterparts], which does not use precomputed lookup tables, but it still relies on a single u16[256] lookup table which is input independent. The use of such a table may cause the execution time of gf128_mul_lle() to correlate with the value of the inputs, which is generally something that must be avoided for cryptographic algorithms. On top of that, the function uses a sequence of if () statements that conditionally invoke be128_xor() based on which bits are set in the second argument of the function, which is usually a pointer to the multiplication factor that represents the key.

In order to remove the correlation between the execution time of gf128_mul_lle() and the value of its inputs, let's address the identified shortcomings:
- add a time invariant version of gf128mul_x8_lle() that replaces the table lookup with the expression that is used at compile time to populate the lookup table;
- make the invocations of be128_xor() unconditional, but pass a zero vector as the third argument if the associated bit in the key is cleared.

The resulting code is likely to be significantly slower. However, given that this is the slowest version already, making it even slower in order to make it more secure is assumed to be justified.

The bbe and ble counterparts could receive the same treatment, but the former is never used anywhere in the kernel, and the latter is only used in the driver for a asynchronous crypto h/w accelerator (Chelsio), where timing variances are unlikely to matter.

---
 lib/crypto/gf128mul.c | 58 +++++++++++++-------
 1 file changed, 39 insertions(+), 19 deletions(-)

index a69ae3e6c16cbbb3..8f8c45e0cdcf283a 100644
@@ -146,6 +146,17 @@ static void gf128mul_x8_lle(be128 *x)
 	x->a = cpu_to_be64((a >> 8) ^ (_tt << 48));
 }
 
+/* time invariant version of gf128mul_x8_lle */
+static void gf128mul_x8_lle_ti(be128 *x)
+{
+	u64 a = be64_to_cpu(x->a);
+	u64 b = be64_to_cpu(x->b);
+	u64 _tt = xda_le(b & 0xff); /* avoid table lookup */
+
+	x->b = cpu_to_be64((b >> 8) | (a << 56));
+	x->a = cpu_to_be64((a >> 8) ^ (_tt << 48));
+}
+
 static void gf128mul_x8_bbe(be128 *x)
 {
 	u64 a = be64_to_cpu(x->a);

@@ -169,38 +180,47 @@ EXPORT_SYMBOL(gf128mul_x8_ble);
 
 void gf128mul_lle(be128 *r, const be128 *b)
 {
-	be128 p[8];
+	/*
+	 * The p array should be aligned to twice the size of its element type,
+	 * so that every even/odd pair is guaranteed to share a cacheline
+	 * (assuming a cacheline size of 32 bytes or more, which is by far the
+	 * most common). This ensures that each be128_xor() call in the loop
+	 * takes the same amount of time regardless of the value of 'ch', which
+	 * is derived from function parameter 'b', which is commonly used as a
+	 * key, e.g., for GHASH. The odd array elements are all set to zero,
+	 * making each be128_xor() a NOP if its associated bit in 'ch' is not
+	 * set, and this is equivalent to calling be128_xor() conditionally.
+	 * This approach aims to avoid leaking information about such keys
+	 * through execution time variances.
+	 *
+	 * Unfortunately, __aligned(16) or higher does not work on x86 for
+	 * variables on the stack so we need to perform the alignment by hand.
+	 */
+	be128 array[16 + 3] = {};
+	be128 *p = PTR_ALIGN(&array[0], 2 * sizeof(be128));
 	int i;
 
 	p[0] = *r;
 	for (i = 0; i < 7; ++i)
-		gf128mul_x_lle(&p[i + 1], &p[i]);
+		gf128mul_x_lle(&p[2 * i + 2], &p[2 * i]);
 
 	memset(r, 0, sizeof(*r));
 	for (i = 0;;) {
 		u8 ch = ((u8 *)b)[15 - i];
 
-		if (ch & 0x80)
-			be128_xor(r, r, &p[0]);
-		if (ch & 0x40)
-			be128_xor(r, r, &p[1]);
-		if (ch & 0x20)
-			be128_xor(r, r, &p[2]);
-		if (ch & 0x10)
-			be128_xor(r, r, &p[3]);
-		if (ch & 0x08)
-			be128_xor(r, r, &p[4]);
-		if (ch & 0x04)
-			be128_xor(r, r, &p[5]);
-		if (ch & 0x02)
-			be128_xor(r, r, &p[6]);
-		if (ch & 0x01)
-			be128_xor(r, r, &p[7]);
+		be128_xor(r, r, &p[ 0 + !(ch & 0x80)]);
+		be128_xor(r, r, &p[ 2 + !(ch & 0x40)]);
+		be128_xor(r, r, &p[ 4 + !(ch & 0x20)]);
+		be128_xor(r, r, &p[ 6 + !(ch & 0x10)]);
+		be128_xor(r, r, &p[ 8 + !(ch & 0x08)]);
+		be128_xor(r, r, &p[10 + !(ch & 0x04)]);
+		be128_xor(r, r, &p[12 + !(ch & 0x02)]);
+		be128_xor(r, r, &p[14 + !(ch & 0x01)]);
 
 		if (++i >= 16)
 			break;
 
-		gf128mul_x8_lle(r);
+		gf128mul_x8_lle_ti(r); /* use the time invariant version */
 	}
 }
 EXPORT_SYMBOL(gf128mul_lle);

2.35.1

Implement a minimal library version of AES-GCM based on the existing library implementations of AES and multiplication in GF(2^128). Using these primitives, GCM can be implemented in a straight-forward manner.

GCM has a couple of sharp edges, i.e., the amount of input data processed with the same initialization vector (IV) should be capped to protect the counter from 32-bit rollover (or carry), and the size of the authentication tag should be fixed for a given key. [0]

The former concern is addressed trivially, given that the function call API uses 32-bit signed types for the input lengths. It is still up to the caller to avoid IV reuse in general, but this is not something we can police at the implementation level.

As for the latter concern, let's make the authentication tag size part of the key schedule, and only permit it to be configured as part of the key expansion routine.

Note that table based AES implementations are susceptible to known plaintext timing attacks on the encryption key. The AES library already attempts to mitigate this to some extent, but given that the counter mode encryption used by GCM operates exclusively on known plaintext by construction (the IV and therefore the initial counter value are known to an attacker), let's take some extra care to mitigate this, by calling the AES library with interrupts disabled.

[0] https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf

---
 include/crypto/gcm.h |  22 +
 lib/crypto/Kconfig   |   6 +
 lib/crypto/Makefile  |   3 +
 lib/crypto/aesgcm.c  | 727 ++++++++++++++++++++
 4 files changed, 758 insertions(+)

index 9d7eff04f22441e0..fd9df607a8364f72 100644
@@ -3,6 +3,9 @@
 
 #include <linux/errno.h>
 
+#include <crypto/aes.h>
+#include <crypto/gf128mul.h>
+
 #define GCM_AES_IV_SIZE 12
 #define GCM_RFC4106_IV_SIZE 8
 #define GCM_RFC4543_IV_SIZE 8

@@ -60,4 +63,23 @@ static inline int crypto_ipsec_check_assoclen(unsigned int assoclen)
 
 	return 0;
 }
+
+struct aesgcm_ctx {
+	be128			ghash_key;
+	struct crypto_aes_ctx	aes_ctx;
+	unsigned int		authsize;
+};
+
+int aesgcm_expandkey(struct aesgcm_ctx *ctx, const u8 *key,
+		     unsigned int keysize, unsigned int authsize);
+
+void aesgcm_encrypt(const struct aesgcm_ctx *ctx, u8 *dst, const u8 *src,
+		    int crypt_len, const u8 *assoc, int assoc_len,
+		    const u8 iv[GCM_AES_IV_SIZE], u8 *authtag);
+
+bool __must_check aesgcm_decrypt(const struct aesgcm_ctx *ctx, u8 *dst,
+				 const u8 *src, int crypt_len, const u8 *assoc,
+				 int assoc_len, const u8 iv[GCM_AES_IV_SIZE],
+				 const u8 *authtag);
+
 #endif

index 6767d86959de8f9c..45436bfc6dffe1db 100644
@@ -8,6 +8,12 @@ config CRYPTO_LIB_UTILS
 config CRYPTO_LIB_AES
 	tristate
 
+config CRYPTO_LIB_AESGCM
+	tristate
+	select CRYPTO_LIB_AES
+	select CRYPTO_LIB_GF128MUL
+	select CRYPTO_LIB_UTILS
+
 config CRYPTO_LIB_ARC4
 	tristate
 

index 7000eeb72286e253..6ec2d4543d9cad48 100644
@@ -10,6 +10,9 @@ obj-$(CONFIG_CRYPTO_LIB_CHACHA_GENERIC)		+= libchacha.o
 obj-$(CONFIG_CRYPTO_LIB_AES)			+= libaes.o
 libaes-y					:= aes.o
 
+obj-$(CONFIG_CRYPTO_LIB_AESGCM)			+= libaesgcm.o
+libaesgcm-y					:= aesgcm.o
+
 obj-$(CONFIG_CRYPTO_LIB_ARC4)			+= libarc4.o
 libarc4-y					:= arc4.o
 

2.35.1

Given include/crypto/aes.h:

struct crypto_aes_ctx {
        u32 key_enc[AES_MAX_KEYLENGTH_U32];
        u32 key_dec[AES_MAX_KEYLENGTH_U32];
        u32 key_length;
};

plus:
...
+struct aesgcm_ctx {
+ be128 ghash_key;
+ struct crypto_aes_ctx aes_ctx;
+ unsigned int authsize;
+};
...

...

...

No. But this applies to all uses of AES in CTR, XCTR, CMAC, CCM modes, not just to the AES library.

I'm not sure what problem we would be solving here tbh. AES key expansion is unlikely to occur on a hot path, and the 240 byte overhead doesn't seem that big of a deal either.

Note that only full table based C implementations of AES have a need for the decryption key schedule, the AES library version could be tweaked to use the encryption key schedule for decryption as well (see below). But the instruction based versions are constructed in a way that also requires the modified schedule for decryption.

So I agree that there appears to be /some/ room for improvement here, but I'm not sure it's worth anyone's time tbh. We could explore splitting off the expandkey routine that is exposed to other AES implementations, and use a reduced schedule inside the library itself.

Beyond that, I don't see the need to clutter up the API and force all AES code in the tree to choose between an encryption-only or a full key schedule.

-------------8<-----------------

@@ -310,3 +310,3 @@
 {
-       const u32 *rkp = ctx->key_dec + 4;
+       const u32 *rkp = ctx->key_enc + ctx->key_length + 16;
        int rounds = 6 + ctx->key_length / 4;

@@ -315,6 +315,6 @@
 
-       st0[0] = ctx->key_dec[0] ^ get_unaligned_le32(in);
-       st0[1] = ctx->key_dec[1] ^ get_unaligned_le32(in + 4);
-       st0[2] = ctx->key_dec[2] ^ get_unaligned_le32(in + 8);
-       st0[3] = ctx->key_dec[3] ^ get_unaligned_le32(in + 12);
+       st0[0] = rkp[ 8] ^ get_unaligned_le32(in);
+       st0[1] = rkp[ 9] ^ get_unaligned_le32(in + 4);
+       st0[2] = rkp[10] ^ get_unaligned_le32(in + 8);
+       st0[3] = rkp[11] ^ get_unaligned_le32(in + 12);
 

@@ -331,7 +331,7 @@
 
-       for (round = 0;; round += 2, rkp += 8) {
-               st1[0] = inv_mix_columns(inv_subshift(st0, 0)) ^ rkp[0];
-               st1[1] = inv_mix_columns(inv_subshift(st0, 1)) ^ rkp[1];
-               st1[2] = inv_mix_columns(inv_subshift(st0, 2)) ^ rkp[2];
-               st1[3] = inv_mix_columns(inv_subshift(st0, 3)) ^ rkp[3];
+       for (round = 0;; round += 2, rkp -= 8) {
+               st1[0] = inv_mix_columns(inv_subshift(st0, 0) ^ rkp[4]);
+               st1[1] = inv_mix_columns(inv_subshift(st0, 1) ^ rkp[5]);
+               st1[2] = inv_mix_columns(inv_subshift(st0, 2) ^ rkp[6]);
+               st1[3] = inv_mix_columns(inv_subshift(st0, 3) ^ rkp[7]);
 

@@ -340,12 +340,12 @@
 
-               st0[0] = inv_mix_columns(inv_subshift(st1, 0)) ^ rkp[4];
-               st0[1] = inv_mix_columns(inv_subshift(st1, 1)) ^ rkp[5];
-               st0[2] = inv_mix_columns(inv_subshift(st1, 2)) ^ rkp[6];
-               st0[3] = inv_mix_columns(inv_subshift(st1, 3)) ^ rkp[7];
+               st0[0] = inv_mix_columns(inv_subshift(st1, 0) ^ rkp[0]);
+               st0[1] = inv_mix_columns(inv_subshift(st1, 1) ^ rkp[1]);
+               st0[2] = inv_mix_columns(inv_subshift(st1, 2) ^ rkp[2]);
+               st0[3] = inv_mix_columns(inv_subshift(st1, 3) ^ rkp[3]);
        }
 
-       put_unaligned_le32(inv_subshift(st1, 0) ^ rkp[4], out);
-       put_unaligned_le32(inv_subshift(st1, 1) ^ rkp[5], out + 4);
-       put_unaligned_le32(inv_subshift(st1, 2) ^ rkp[6], out + 8);
-       put_unaligned_le32(inv_subshift(st1, 3) ^ rkp[7], out + 12);
+       put_unaligned_le32(inv_subshift(st1, 0) ^ rkp[0], out);
+       put_unaligned_le32(inv_subshift(st1, 1) ^ rkp[1], out + 4);
+       put_unaligned_le32(inv_subshift(st1, 2) ^ rkp[2], out + 8);
+       put_unaligned_le32(inv_subshift(st1, 3) ^ rkp[3], out + 12);

All applied. Thanks.

Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt