path: root/lib/crypto/gf128hash.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * GF(2^128) polynomial hashing: GHASH and POLYVAL
 *
 * Copyright 2025 Google LLC
 */

#include <crypto/gf128hash.h>
#include <linux/export.h>
#include <linux/module.h>
#include <linux/string.h>
#include <linux/unaligned.h>

/*
 * GHASH and POLYVAL are almost-XOR-universal hash functions.  They interpret
 * the message as the coefficients of a polynomial in the finite field GF(2^128)
 * and evaluate that polynomial at a secret point.
 *
 * Neither GHASH nor POLYVAL is a cryptographic hash function.  They should be
 * used only by algorithms that are specifically designed to use them.
 *
 * GHASH is the older variant, defined as part of GCM in NIST SP 800-38D
 * (https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf).
 * GHASH is hard to implement directly, due to its backwards mapping between
 * bits and polynomial coefficients.  GHASH implementations typically pre and
 * post-process the inputs and outputs (mainly by byte-swapping) to convert the
 * GHASH computation into an equivalent computation over a different,
 * easier-to-use representation of GF(2^128).
 *
 * POLYVAL is a newer GF(2^128) polynomial hash, originally defined as part of
 * AES-GCM-SIV (https://datatracker.ietf.org/doc/html/rfc8452) and also used by
 * HCTR2 (https://eprint.iacr.org/2021/1441.pdf).  It uses that easier-to-use
 * field representation directly, eliminating the data conversion steps.
 *
 * This file provides library APIs for GHASH and POLYVAL.  These APIs can
 * delegate to either a generic implementation or an architecture-optimized
 * implementation.  Due to the mathematical relationship between GHASH and
 * POLYVAL, in some cases code for one is reused with the other.
 *
 * For the generic implementation, we don't use the traditional table approach
 * to GF(2^128) multiplication.  That approach is not constant-time and requires
 * a lot of memory.  Instead, we use a different approach which emulates
 * carryless multiplication using standard multiplications by spreading the data
 * bits apart using "holes".  This allows the carries to spill harmlessly.  This
 * approach is borrowed from BoringSSL, which in turn credits BearSSL's
 * documentation (https://bearssl.org/constanttime.html#ghash-for-gcm) for the
 * "holes" trick and a presentation by Shay Gueron
 * (https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf) for the
 * 256-bit => 128-bit reduction algorithm.
 */

#ifdef CONFIG_ARCH_SUPPORTS_INT128

/* Do a 64 x 64 => 128 bit carryless multiplication. */
static void clmul64(u64 a, u64 b, u64 *out_lo, u64 *out_hi)
{
	/*
	 * With 64-bit multiplicands and one term every 4 bits, there would be
	 * up to 64 / 4 = 16 one bits per column when each multiplication is
	 * written out as a series of additions in the schoolbook manner.
	 * Unfortunately, that doesn't work since the value 16 is 1 too large to
	 * fit in 4 bits.  Carries would sometimes overflow into the next term.
	 *
	 * Using one term every 5 bits would work.  However, that would cost
	 * 5 x 5 = 25 multiplications instead of 4 x 4 = 16.
	 *
	 * Instead, mask off 4 bits from one multiplicand, giving a max of 15
	 * one bits per column.  Then handle those 4 bits separately.
	 */
	u64 a0 = a & 0x1111111111111110;
	u64 a1 = a & 0x2222222222222220;
	u64 a2 = a & 0x4444444444444440;
	u64 a3 = a & 0x8888888888888880;

	u64 b0 = b & 0x1111111111111111;
	u64 b1 = b & 0x2222222222222222;
	u64 b2 = b & 0x4444444444444444;
	u64 b3 = b & 0x8888888888888888;

	/* Multiply the high 60 bits of @a by @b. */
	u128 c0 = (a0 * (u128)b0) ^ (a1 * (u128)b3) ^
		  (a2 * (u128)b2) ^ (a3 * (u128)b1);
	u128 c1 = (a0 * (u128)b1) ^ (a1 * (u128)b0) ^
		  (a2 * (u128)b3) ^ (a3 * (u128)b2);
	u128 c2 = (a0 * (u128)b2) ^ (a1 * (u128)b1) ^
		  (a2 * (u128)b0) ^ (a3 * (u128)b3);
	u128 c3 = (a0 * (u128)b3) ^ (a1 * (u128)b2) ^
		  (a2 * (u128)b1) ^ (a3 * (u128)b0);

	/* Multiply the low 4 bits of @a by @b. */
	u64 e0 = -(a & 1) & b;
	u64 e1 = -((a >> 1) & 1) & b;
	u64 e2 = -((a >> 2) & 1) & b;
	u64 e3 = -((a >> 3) & 1) & b;
	u64 extra_lo = e0 ^ (e1 << 1) ^ (e2 << 2) ^ (e3 << 3);
	u64 extra_hi = (e1 >> 63) ^ (e2 >> 62) ^ (e3 >> 61);

	/* Add all the intermediate products together. */
	*out_lo = (((u64)c0) & 0x1111111111111111) ^
		  (((u64)c1) & 0x2222222222222222) ^
		  (((u64)c2) & 0x4444444444444444) ^
		  (((u64)c3) & 0x8888888888888888) ^ extra_lo;
	*out_hi = (((u64)(c0 >> 64)) & 0x1111111111111111) ^
		  (((u64)(c1 >> 64)) & 0x2222222222222222) ^
		  (((u64)(c2 >> 64)) & 0x4444444444444444) ^
		  (((u64)(c3 >> 64)) & 0x8888888888888888) ^ extra_hi;
}

#else /* CONFIG_ARCH_SUPPORTS_INT128 */

/* Do a 32 x 32 => 64 bit carryless multiplication. */
static u64 clmul32(u32 a, u32 b)
{
	/*
	 * With 32-bit multiplicands and one term every 4 bits, there are up to
	 * 32 / 4 = 8 one bits per column when each multiplication is written
	 * out as a series of additions in the schoolbook manner.  The value 8
	 * fits in 4 bits, so the carries don't overflow into the next term.
	 */
	u32 a0 = a & 0x11111111;
	u32 a1 = a & 0x22222222;
	u32 a2 = a & 0x44444444;
	u32 a3 = a & 0x88888888;

	u32 b0 = b & 0x11111111;
	u32 b1 = b & 0x22222222;
	u32 b2 = b & 0x44444444;
	u32 b3 = b & 0x88888888;

	u64 c0 = (a0 * (u64)b0) ^ (a1 * (u64)b3) ^
		 (a2 * (u64)b2) ^ (a3 * (u64)b1);
	u64 c1 = (a0 * (u64)b1) ^ (a1 * (u64)b0) ^
		 (a2 * (u64)b3) ^ (a3 * (u64)b2);
	u64 c2 = (a0 * (u64)b2) ^ (a1 * (u64)b1) ^
		 (a2 * (u64)b0) ^ (a3 * (u64)b3);
	u64 c3 = (a0 * (u64)b3) ^ (a1 * (u64)b2) ^
		 (a2 * (u64)b1) ^ (a3 * (u64)b0);

	/* Add all the intermediate products together. */
	return (c0 & 0x1111111111111111) ^
	       (c1 & 0x2222222222222222) ^
	       (c2 & 0x4444444444444444) ^
	       (c3 & 0x8888888888888888);
}

/* Do a 64 x 64 => 128 bit carryless multiplication. */
static void clmul64(u64 a, u64 b, u64 *out_lo, u64 *out_hi)
{
	u32 a_lo = (u32)a;
	u32 a_hi = a >> 32;
	u32 b_lo = (u32)b;
	u32 b_hi = b >> 32;

	/* Karatsuba multiplication */
	u64 lo = clmul32(a_lo, b_lo);
	u64 hi = clmul32(a_hi, b_hi);
	u64 mi = clmul32(a_lo ^ a_hi, b_lo ^ b_hi) ^ lo ^ hi;

	*out_lo = lo ^ (mi << 32);
	*out_hi = hi ^ (mi >> 32);
}
#endif /* !CONFIG_ARCH_SUPPORTS_INT128 */

/* Compute @a = @a * @b * x^-128 in the POLYVAL field. */
static void __maybe_unused
polyval_mul_generic(struct polyval_elem *a, const struct polyval_elem *b)
{
	u64 c0, c1, c2, c3, mi0, mi1;

	/*
	 * Carryless-multiply @a by @b using Karatsuba multiplication.  Store
	 * the 256-bit product in @c0 (low) through @c3 (high).
	 */
	clmul64(le64_to_cpu(a->lo), le64_to_cpu(b->lo), &c0, &c1);
	clmul64(le64_to_cpu(a->hi), le64_to_cpu(b->hi), &c2, &c3);
	clmul64(le64_to_cpu(a->lo ^ a->hi), le64_to_cpu(b->lo ^ b->hi),
		&mi0, &mi1);
	mi0 ^= c0 ^ c2;
	mi1 ^= c1 ^ c3;
	c1 ^= mi0;
	c2 ^= mi1;

	/*
	 * Cancel out the low 128 bits of the product by adding multiples of