src/crypto/gcm.c

/*
 * Copyright (C) 2022 Michael Brown <mbrown@fensystems.co.uk>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 *
 * You can also choose to distribute this program under the terms of
 * the Unmodified Binary Distribution Licence (as given in the file
 * COPYING.UBDL), provided that you have satisfied its requirements.
 */

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );

/** @file
 *
 * Galois/Counter Mode (GCM)
 *
 * The GCM algorithm is specified in
 *
 * https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf
 * https://csrc.nist.rip/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf
 *
 */

#include <stdint.h>
#include <string.h>
#include <byteswap.h>
#include <ipxe/crypto.h>
#include <ipxe/gcm.h>

/**
 * Perform encryption
 *
 * This value is chosen to allow for ANDing with a fragment length.
 */
#define GCM_FL_ENCRYPT 0x00ff

/**
 * Calculate hash over an initialisation vector value
 *
 * The hash calculation for a non 96-bit initialisation vector is
 * identical to the calculation used for additional data, except that
 * the non-additional data length counter is used.
 */
#define GCM_FL_IV 0x0100

/**
 * GCM field polynomial
 *
 * GCM treats 128-bit blocks as polynomials in GF(2^128) with the
 * field polynomial f(x) = 1 + x + x^2 + x^7 + x^128.
 *
 * In a somewhat bloody-minded interpretation of "big-endian", the
 * constant term (with degree zero) is arbitrarily placed in the
 * leftmost bit of the big-endian binary representation (i.e. the most
 * significant bit of byte 0), thereby failing to correspond to the
 * bit ordering in any CPU architecture in existence.  This
 * necessitates some wholly gratuitous byte reversals when
 * constructing the multiplication tables, since all CPUs will treat
 * bit 0 as being the least significant bit within a byte.
 *
 * The field polynomial maps to the 128-bit constant
 * 0xe1000000000000000000000000000000 (with the x^128 term outside the
 * 128-bit range), and can therefore be treated as a single-byte
 * value.
 */
#define GCM_POLY 0xe1

/**
 * Hash key for which multiplication tables are cached
 *
 * GCM operates much more efficiently with a cached multiplication
 * table, which costs 4kB per hash key.  Since this exceeds the
 * available stack space, we place a single 4kB cache in .bss and
 * recalculate the cached values as required.  In the common case of a
 * single HTTPS connection being used to download a (relatively) large
 * file, the same key will be used repeatedly for almost all GCM
 * operations, and so the overhead of recalculation is negligible.
 */
static const union gcm_block *gcm_cached_key;

/**
 * Cached multiplication table (M0) for Shoup's method
 *
 * Each entry within this table represents the result of multiplying
 * the cached hash key by an arbitrary 8-bit polynomial.
 */
static union gcm_block gcm_cached_mult[256];

/**
 * Cached reduction table (R) for Shoup's method
 *
 * Each entry within this table represents the result of multiplying
 * the fixed polynomial x^128 by an arbitrary 8-bit polynomial.  Only
 * the leftmost 16 bits are stored, since all other bits within the
 * result will always be zero.
 */
static uint16_t gcm_cached_reduce[256];

/** Offset of a field within GCM context */
#define gcm_offset( field ) offsetof ( struct gcm_context, field )

/**
 * Reverse bits in a byte
 *
 * @v byte		Byte
 * @ret etyb		Bit-reversed byte
 */
static inline __attribute__ (( always_inline )) uint8_t
gcm_reverse ( const uint8_t byte ) {
	uint8_t etyb = etyb;
	uint8_t mask;

	for ( mask = 1 ; mask ; mask <<= 1 ) {
		etyb <<= 1;
		if ( byte & mask )
			etyb |= 1;
	}
	return etyb;
}

/**
 * Update GCM counter
 *
 * @v ctr		Counter
 * @v delta		Amount to add to counter
 */
static inline __attribute__ (( always_inline )) void
gcm_count ( union gcm_block *ctr, uint32_t delta ) {
	uint32_t *value = &ctr->ctr.value;

	/* Update counter modulo 2^32 */
	*value = cpu_to_be32 ( be32_to_cpu ( *value ) + delta );
}

/**
 * XOR partial data block
 *
 * @v src1		Source buffer 1
 * @v src2		Source buffer 2
 * @v dst		Destination buffer
 * @v len		Length
 */
static inline void gcm_xor ( const void *src1, const void *src2, void *dst,
			     size_t len ) {
	uint8_t *dst_bytes = dst;
	const uint8_t *src1_bytes = src1;
	const uint8_t *src2_bytes = src2;

	/* XOR one byte at a time */
	while ( len-- )
		*(dst_bytes++) = ( *(src1_bytes++) ^ *(src2_bytes++) );
}

/**
 * XOR whole data block in situ
 *
 * @v src		Source block
 * @v dst		Destination block
 */
static inline void gcm_xor_block ( const union gcm_block *src,
				   union gcm_block *dst ) {

	/* XOR whole dwords */
	dst->dword[0] ^= src->dword[0];
	dst->dword[1] ^= src->dword[1];
	dst->dword[2] ^= src->dword[2];
	dst->dword[3] ^= src->dword[3];
}

/**
 * Multiply polynomial by (x)
 *
 * @v mult		Multiplicand
 * @v res		Result
 */
static void gcm_multiply_x ( const union gcm_block *mult,
			     union gcm_block *res ) {
	unsigned int i;
	uint8_t byte;
	uint8_t carry;

	/* Multiply by (x) by shifting all bits rightward */
	for ( i = 0, carry = 0 ; i < sizeof ( res->byte ) ; i++ ) {
		byte = mult->byte[i];
		res->byte[i] = ( ( carry << 7 ) | ( byte >> 1 ) );
		carry = ( byte & 0x01 );
	}

	/* If result overflows, reduce modulo the field polynomial */
	if ( carry )
		res->byte[0] ^= GCM_POLY;
}

/**
 * Construct cached tables
 *
 * @v key		Hash key
 * @v context		Context
 */
static void gcm_cache ( const union gcm_block *key ) {
	union gcm_block *mult;
	uint16_t reduce;
	unsigned int this;
	unsigned int other;
	unsigned int i;

	/* Calculate M0[1..255] and R[1..255]
	 *
	 * The R[] values are independent of the key, but the overhead
	 * of recalculating them here is negligible and saves on
	 * overall code size since the calculations are related.
	 */
	for ( i = 1 ; i < 256 ; i++ ) {

		/* Reverse bit order to compensate for poor life choices */
		this = gcm_reverse ( i );

		/* Construct entries */
		mult = &gcm_cached_mult[this];
		if ( this & 0x80 ) {

			/* Odd number: entry[i] = entry[i - 1] + poly */
			other = ( this & 0x7f ); /* bit-reversed (i - 1) */
			gcm_xor ( key, &gcm_cached_mult[other], mult,
				  sizeof ( *mult ) );
			reduce = gcm_cached_reduce[other];
			reduce ^= be16_to_cpu ( GCM_POLY << 8 );
			gcm_cached_reduce[this] = reduce;

		} else {

			/* Even number: entry[i] = entry[i/2] * (x) */
			other = ( this << 1 ); /* bit-reversed (i / 2) */
			gcm_multiply_x ( &gcm_cached_mult[other], mult );
			reduce = be16_to_cpu ( gcm_cached_reduce[other] );
			reduce >>= 1;
			gcm_cached_reduce[this] = cpu_to_be16 ( reduce );
		}
	}

	/* Record cached key */
	gcm_cached_key = key;
}

/**
 * Multiply polynomial by (x^8) in situ
 *
 * @v poly		Multiplicand and result
 */
static void gcm_multiply_x_8 ( union gcm_block *poly ) {
	uint8_t *byte;
	uint8_t msb;

	/* Reduction table must already have been calculated */
	assert ( gcm_cached_key != NULL );

	/* Record most significant byte */
	byte = &poly->byte[ sizeof ( poly->byte ) - 1 ];
	msb = *byte;

	/* Multiply least significant bytes by shifting */
	for ( ; byte > &poly->byte[0] ; byte-- )
		*byte = *( byte - 1 );
	*byte = 0;

	/* Multiply most significant byte via reduction table */
	poly->word[0] ^= gcm_cached_reduce[msb];
}

/**
 * Multiply polynomial by hash key in situ
 *
 * @v key		Hash key
 * @v poly		Multiplicand and result
 */
static void gcm_multiply_key ( const union gcm_block *key,
			       union gcm_block *poly ) {
	union gcm_block res;
	uint8_t *byte;

	/* Construct tables, if necessary */
	if ( gcm_cached_key != key )
		gcm_cache ( key );

	/* Multiply using Shoup's algorithm */
	byte = &poly->byte[ sizeof ( poly->byte ) - 1 ];
	memcpy ( &res, &gcm_cached_mult[ *byte ], sizeof ( res ) );
	for ( byte-- ; byte >= &poly->byte[0] ; byte-- ) {
		gcm_multiply_x_8 ( &res );
		gcm_xor_block ( &gcm_cached_mult[ *byte ], &res );
	}

	/* Overwrite result */
	memcpy ( poly, &res, sizeof ( *poly ) );
}

/**
 * Encrypt/decrypt/authenticate data
 *
 * @v context		Context
 * @v src		Input data
 * @v dst		Output data, or NULL to process additional data
 * @v len		Length of data
 * @v flags		Operation flags
 */
static void gcm_process ( struct gcm_context *context, const void *src,
			  void *dst, size_t len, unsigned int flags ) {
	union gcm_block tmp;
	uint64_t *total;
	size_t frag_len;
	unsigned int block;

	/* Calculate block number (for debugging) */
	block = ( ( ( context->len.len.add + 8 * sizeof ( tmp ) - 1 ) /
		    ( 8 * sizeof ( tmp ) ) ) +
		  ( ( context->len.len.data + 8 * sizeof ( tmp ) - 1 ) /
		    ( 8 * sizeof ( tmp ) ) ) + 1 );

	/* Update total length (in bits) */
	total = ( ( dst || ( flags & GCM_FL_IV ) ) ?
		  &context->len.len.data : &context->len.len.add );
	*total += ( len * 8 );

	/* Process data */
	for ( ; len ; src += frag_len, len -= frag_len, block++ ) {

		/* Calculate fragment length */
		frag_len = len;
		if ( frag_len > sizeof ( tmp ) )
			frag_len = sizeof ( tmp );

		/* Update hash with input data */
		gcm_xor ( src, &context->hash, &context->hash, frag_len );

		/* Encrypt/decrypt block, if applicable */
		if ( dst ) {

			/* Increment counter */
			gcm_count ( &context->ctr, 1 );

			/* Encrypt counter */
			DBGC2 ( context, "GCM %p Y[%d]:\n", context, block );
			DBGC2_HDA ( context, 0, &context->ctr,
				    sizeof ( context->ctr ) );
			cipher_encrypt ( context->raw_cipher, &context->raw_ctx,
					 &context->ctr, &tmp, sizeof ( tmp ) );
			DBGC2 ( context, "GCM %p E(K,Y[%d]):\n",
				context, block );
			DBGC2_HDA ( context, 0, &tmp, sizeof ( tmp ) );

			/* Encrypt/decrypt data */
			gcm_xor ( src, &tmp, dst, frag_len );
			dst += frag_len;

			/* Update hash with encrypted data, if applicable */
			gcm_xor ( &tmp, &context->hash, &context->hash,
				  ( frag_len & flags ) );
		}

		/* Update hash */
		gcm_multiply_key ( &context->key, &context->hash );
		DBGC2 ( context, "GCM %p X[%d]:\n", context, block );
		DBGC2_HDA ( context, 0, &context->hash,
			    sizeof ( context->hash ) );
	}
}

/**
 * Construct hash
 *
 * @v context		Context
 * @v hash		Hash to fill in
 */
static void gcm_hash ( struct gcm_context *context, union gcm_block *hash ) {

	/* Construct big-endian lengths block */
	hash->len.add = cpu_to_be64 ( context->len.len.add );
	hash->len.data = cpu_to_be64 ( context->len.len.data );
	DBGC2 ( context, "GCM %p len(A)||len(C):\n", context );
	DBGC2_HDA ( context, 0, hash, sizeof ( *hash ) );

	/* Update hash */
	gcm_xor_block ( &context->hash, hash );
	gcm_multiply_key ( &context->key, hash );
	DBGC2 ( context, "GCM %p GHASH(H,A,C):\n", context );
	DBGC2_HDA ( context, 0, hash, sizeof ( *hash ) );
}

/**
 * Construct tag
 *
 * @v context		Context
 * @v tag		Tag
 */
void gcm_tag ( struct gcm_context *context, union gcm_block *tag ) {
	union gcm_block tmp;
	uint32_t offset;

	/* Construct hash */
	gcm_hash ( context, tag );

	/* Construct encrypted initial counter value */
	memcpy ( &tmp, &context->ctr, sizeof ( tmp ) );
	offset = ( ( -context->len.len.data ) / ( 8 * sizeof ( tmp ) ) );
	gcm_count ( &tmp, offset );
	cipher_encrypt ( context->raw_cipher, &context->raw_ctx, &tmp,
			 &tmp, sizeof ( tmp ) );
	DBGC2 ( context, "GCM %p E(K,Y[0]):\n", context );
	DBGC2_HDA ( context, 0, &tmp, sizeof ( tmp ) );

	/* Construct tag */
	gcm_xor_block ( &tmp, tag );
	DBGC2 ( context, "GCM %p T:\n", context );
	DBGC2_HDA ( context, 0, tag, sizeof ( *tag ) );
}

/**
 * Set key
 *
 * @v context		Context
 * @v key		Key
 * @v keylen		Key length
 * @v raw_cipher	Underlying cipher
 * @ret rc		Return status code
 */
int gcm_setkey ( struct gcm_context *context, const void *key, size_t keylen,
		 struct cipher_algorithm *raw_cipher ) {
	int rc;

	/* Initialise GCM context */
	memset ( context, 0, sizeof ( *context ) );
	context->raw_cipher = raw_cipher;

	/* Set underlying block cipher key */
	if ( ( rc = cipher_setkey ( raw_cipher, context->raw_ctx, key,
				    keylen ) ) != 0 )
		return rc;

	/* Construct GCM hash key */
	cipher_encrypt ( raw_cipher, context->raw_ctx, &context->ctr,
			 &context->key, sizeof ( context->key ) );
	DBGC2 ( context, "GCM %p H:\n", context );
	DBGC2_HDA ( context, 0, &context->key, sizeof ( context->key ) );

	/* Reset counter */
	context->ctr.ctr.value = cpu_to_be32 ( 1 );

	/* Construct cached tables */
	gcm_cache ( &context->key );

	return 0;
}

/**
 * Set initialisation vector
 *
 * @v ctx		Context
 * @v iv		Initialisation vector
 * @v ivlen		Initialisation vector length
 */
void gcm_setiv ( struct gcm_context *context, const void *iv, size_t ivlen ) {

	/* Reset non-key state */
	memset ( context, 0, gcm_offset ( key ) );
	build_assert ( gcm_offset ( key ) > gcm_offset ( hash ) );
	build_assert ( gcm_offset ( key ) > gcm_offset ( len ) );
	build_assert ( gcm_offset ( key ) > gcm_offset ( ctr ) );
	build_assert ( gcm_offset ( key ) < gcm_offset ( raw_cipher ) );
	build_assert ( gcm_offset ( key ) < gcm_offset ( raw_ctx ) );

	/* Reset counter */
	context->ctr.ctr.value = cpu_to_be32 ( 1 );

	/* Process initialisation vector */
	if ( ivlen == sizeof ( context->ctr.ctr.iv ) ) {

		/* Initialisation vector is exactly 96 bits, use it as-is */
		memcpy ( context->ctr.ctr.iv, iv, ivlen );

	} else {

		/* Calculate hash over initialisation vector */
		gcm_process ( context, iv, NULL, ivlen, GCM_FL_IV );
		gcm_hash ( context, &context->ctr );
		assert ( context->len.len.add == 0 );

		/* Reset non-key, non-counter state */
		memset ( context, 0, gcm_offset ( ctr ) );
		build_assert ( gcm_offset ( ctr ) > gcm_offset ( hash ) );
		build_assert ( gcm_offset ( ctr ) > gcm_offset ( len ) );
		build_assert ( gcm_offset ( ctr ) < gcm_offset ( key ) );
		build_assert ( gcm_offset ( ctr ) < gcm_offset ( raw_cipher ) );
		build_assert ( gcm_offset ( ctr ) < gcm_offset ( raw_ctx ) );
	}

	DBGC2 ( context, "GCM %p Y[0]:\n", context );
	DBGC2_HDA ( context, 0, &context->ctr, sizeof ( context->ctr ) );
}

/**
 * Encrypt data
 *
 * @v context		Context
 * @v src		Data to encrypt
 * @v dst		Buffer for encrypted data, or NULL for additional data
 * @v len		Length of data
 */
void gcm_encrypt ( struct gcm_context *context, const void *src, void *dst,
		   size_t len ) {

	/* Process data */
	gcm_process ( context, src, dst, len, GCM_FL_ENCRYPT );
}

/**
 * Decrypt data
 *
 * @v context		Context
 * @v src		Data to decrypt
 * @v dst		Buffer for decrypted data, or NULL for additional data
 * @v len		Length of data
 */
void gcm_decrypt ( struct gcm_context *context, const void *src, void *dst,
		   size_t len ) {

	/* Process data */
	gcm_process ( context, src, dst, len, 0 );
}