gcm.c File Reference

Galois/Counter Mode (GCM) More...

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

Go to the source code of this file.

Macros
#define	GCM_FL_ENCRYPT   0x00ff
	Perform encryption.
#define	GCM_FL_IV   0x0100
	Calculate hash over an initialisation vector value.
#define	GCM_POLY   0xe1
	GCM field polynomial.
#define	gcm_offset(field)
	Offset of a field within GCM context.

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
	FILE_SECBOOT (PERMITTED)
static uint8_t	gcm_reverse (const uint8_t byte)
	Reverse bits in a byte.
static void	gcm_count (union gcm_block *ctr, uint32_t delta)
	Update GCM counter.
static void	gcm_xor (const void *src1, const void *src2, void *dst, size_t len)
	XOR partial data block.
static void	gcm_xor_block (const union gcm_block *src, union gcm_block *dst)
	XOR whole data block in situ.
static void	gcm_multiply_x (const union gcm_block *mult, union gcm_block *res)
	Multiply polynomial by (x)
static void	gcm_cache (const union gcm_block *key)
	Construct cached tables.
static void	gcm_multiply_x_8 (union gcm_block *poly)
	Multiply polynomial by (x^8) in situ.
static void	gcm_multiply_key (const union gcm_block *key, union gcm_block *poly)
	Multiply polynomial by hash key in situ.
static void	gcm_process (struct gcm_context *context, const void *src, void *dst, size_t len, unsigned int flags)
	Encrypt/decrypt/authenticate data.
static void	gcm_hash (struct gcm_context *context, union gcm_block *hash)
	Construct hash.
void	gcm_tag (struct gcm_context *context, union gcm_block *tag)
	Construct tag.
int	gcm_setkey (struct gcm_context *context, const void *key, size_t keylen, struct cipher_algorithm *raw_cipher)
	Set key.
void	gcm_setiv (struct gcm_context *context, const void *iv, size_t ivlen)
	Set initialisation vector.
void	gcm_encrypt (struct gcm_context *context, const void *src, void *dst, size_t len)
	Encrypt data.
void	gcm_decrypt (struct gcm_context *context, const void *src, void *dst, size_t len)
	Decrypt data.

Variables
static const union gcm_block *	gcm_cached_key
	Hash key for which multiplication tables are cached.
static union gcm_block	gcm_cached_mult [256]
	Cached multiplication table (M0) for Shoup's method.
static uint16_t	gcm_cached_reduce [256]
	Cached reduction table (R) for Shoup's method.

Detailed Description

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

Definition in file gcm.c.

Macro Definition Documentation

GCM_FL_ENCRYPT

#define GCM_FL_ENCRYPT   0x00ff

Perform encryption.

This value is chosen to allow for ANDing with a fragment length.

Definition at line 49 of file gcm.c.

Referenced by gcm_encrypt().

GCM_FL_IV

#define GCM_FL_IV   0x0100

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.

Definition at line 58 of file gcm.c.

Referenced by gcm_process(), and gcm_setiv().

GCM_POLY

#define GCM_POLY   0xe1

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.

Definition at line 80 of file gcm.c.

Referenced by gcm_cache(), and gcm_multiply_x().

gcm_offset

#define gcm_offset

(

field

)

Value:

offsetof ( struct gcm_context, field )

Offset of a field within GCM context.

Definition at line 114 of file gcm.c.

Referenced by gcm_setiv().

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

FILE_SECBOOT()

FILE_SECBOOT

(

PERMITTED

)

gcm_reverse()

uint8_t gcm_reverse ( const uint8_t byte )

inlinestatic

Reverse bits in a byte.

Parameters

byte

Byte

Return values

etyb	Bit-reversed byte

Definition at line 123 of file gcm.c.

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

Referenced by gcm_cache().

gcm_count()

void gcm_count ( union gcm_block * ctr, uint32_t delta )

inlinestatic

Update GCM counter.

Parameters

ctr	Counter
delta	Amount to add to counter

Definition at line 142 of file gcm.c.

                                                   {
        uint32_t *value = &ctr->ctr.value;
 
        /* Update counter modulo 2^32 */
        *value = cpu_to_be32 ( be32_to_cpu ( *value ) + delta );
}

References be32_to_cpu, cpu_to_be32, gcm_block::ctr, gcm_counter::value, and value.

Referenced by gcm_process(), and gcm_tag().

gcm_xor()

void gcm_xor ( const void * src1, const void * src2, void * dst, size_t len )

inlinestatic

XOR partial data block.

Parameters

src1	Source buffer 1
src2	Source buffer 2
dst	Destination buffer
len	Length

Definition at line 157 of file gcm.c.

                                          {
        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++) );
}

References len.

Referenced by gcm_cache(), and gcm_process().

gcm_xor_block()

void gcm_xor_block ( const union gcm_block * src, union gcm_block * dst )

inlinestatic

XOR whole data block in situ.

Parameters

src	Source block
dst	Destination block

Definition at line 174 of file gcm.c.

                                                          {
 
        /* 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];
}

References gcm_block::dword, and src.

Referenced by gcm_hash(), gcm_multiply_key(), and gcm_tag().

gcm_multiply_x()

void gcm_multiply_x ( const union gcm_block * mult, union gcm_block * res )

static

Multiply polynomial by (x)

Parameters

mult	Multiplicand
res	Result

Definition at line 190 of file gcm.c.

                                                    {
        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;
}

References gcm_block::byte, carry, and GCM_POLY.

Referenced by gcm_cache().

gcm_cache()

void gcm_cache ( const union gcm_block * key )

static

Construct cached tables.

Parameters

key	Hash key
context	Context

Definition at line 214 of file gcm.c.

                                                     {
        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;
}

References be16_to_cpu, cpu_to_be16, gcm_cached_key, gcm_cached_mult, gcm_cached_reduce, gcm_multiply_x(), GCM_POLY, gcm_reverse(), gcm_xor(), and key.

Referenced by gcm_multiply_key(), and gcm_setkey().

gcm_multiply_x_8()

void gcm_multiply_x_8 ( union gcm_block * poly )

static

Multiply polynomial by (x^8) in situ.

Parameters

poly	Multiplicand and result

Definition at line 264 of file gcm.c.

                                                       {
        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];
}

References assert, gcm_block::byte, gcm_cached_key, gcm_cached_reduce, NULL, and gcm_block::word.

Referenced by gcm_multiply_key().

gcm_multiply_key()

void gcm_multiply_key ( const union gcm_block * key, union gcm_block * poly )

static

Multiply polynomial by hash key in situ.

Parameters

key	Hash key
poly	Multiplicand and result

Definition at line 290 of file gcm.c.

                                                       {
        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 ) );
}

References gcm_block::byte, gcm_cache(), gcm_cached_key, gcm_cached_mult, gcm_multiply_x_8(), gcm_xor_block(), key, and memcpy().

Referenced by gcm_hash(), and gcm_process().

gcm_process()

void gcm_process ( struct gcm_context * context, const void * src, void * dst, size_t len, unsigned int flags )

static

Encrypt/decrypt/authenticate data.

Parameters

context	Context
src	Input data
dst	Output data, or NULL to process additional data
len	Length of data
flags	Operation flags

Definition at line 320 of file gcm.c.

                                                                      {
        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 ) );
        }
}

References gcm_lengths::add, block, cipher_encrypt, gcm_context::ctr, gcm_lengths::data, DBGC2, DBGC2_HDA, flags, gcm_count(), GCM_FL_IV, gcm_multiply_key(), gcm_xor(), gcm_context::hash, gcm_context::key, gcm_block::len, gcm_context::len, len, gcm_context::raw_cipher, gcm_context::raw_ctx, src, and tmp.

Referenced by gcm_decrypt(), gcm_encrypt(), and gcm_setiv().

gcm_hash()

void gcm_hash ( struct gcm_context * context, union gcm_block * hash )

static

Construct hash.

Parameters

context	Context
hash	Hash to fill in

Definition at line 388 of file gcm.c.

                                                                            {
 
        /* 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 ) );
}

References gcm_lengths::add, cpu_to_be64, gcm_lengths::data, DBGC2, DBGC2_HDA, gcm_multiply_key(), gcm_xor_block(), gcm_context::hash, hash, gcm_context::key, gcm_block::len, and gcm_context::len.

Referenced by gcm_setiv(), and gcm_tag().

gcm_tag()

void gcm_tag	(	struct gcm_context *	context,
		union gcm_block *	tag )

Construct tag.

Parameters

context	Context
tag	Tag

Definition at line 409 of file gcm.c.

                                                                   {
        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 ) );
}

References cipher_encrypt, gcm_context::ctr, gcm_lengths::data, DBGC2, DBGC2_HDA, gcm_count(), gcm_hash(), gcm_xor_block(), gcm_block::len, gcm_context::len, memcpy(), offset, gcm_context::raw_cipher, gcm_context::raw_ctx, tag, and tmp.

gcm_setkey()

int gcm_setkey	(	struct gcm_context *	context,
		const void *	key,
		size_t	keylen,
		struct cipher_algorithm *	raw_cipher )

Set key.

Parameters

context	Context
key	Key
keylen	Key length
raw_cipher	Underlying cipher

Return values

rc	Return status code

Definition at line 440 of file gcm.c.

                                                       {
        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;
}

References cipher_encrypt, cipher_setkey(), cpu_to_be32, gcm_block::ctr, gcm_context::ctr, DBGC2, DBGC2_HDA, gcm_cache(), gcm_context::key, key, memset(), gcm_context::raw_cipher, gcm_context::raw_ctx, rc, and gcm_counter::value.

gcm_setiv()

void gcm_setiv	(	struct gcm_context *	context,
		const void *	iv,
		size_t	ivlen )

Set initialisation vector.

Parameters

ctx	Context
iv	Initialisation vector
ivlen	Initialisation vector length

Definition at line 475 of file gcm.c.

                                                                             {
 
        /* 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 ) );
}

References gcm_lengths::add, assert, build_assert, cpu_to_be32, gcm_block::ctr, gcm_context::ctr, DBGC2, DBGC2_HDA, GCM_FL_IV, gcm_hash(), gcm_offset, gcm_process(), hash, gcm_counter::iv, iv, key, gcm_block::len, gcm_context::len, len, memcpy(), memset(), NULL, and gcm_counter::value.

gcm_encrypt()

void gcm_encrypt	(	struct gcm_context *	context,
		const void *	src,
		void *	dst,
		size_t	len )

Encrypt data.

Parameters

context	Context
src	Data to encrypt
dst	Buffer for encrypted data, or NULL for additional data
len	Length of data

Definition at line 522 of file gcm.c.

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

References GCM_FL_ENCRYPT, gcm_process(), len, and src.

gcm_decrypt()

void gcm_decrypt	(	struct gcm_context *	context,
		const void *	src,
		void *	dst,
		size_t	len )

Decrypt data.

Parameters

context	Context
src	Data to decrypt
dst	Buffer for decrypted data, or NULL for additional data
len	Length of data

Definition at line 537 of file gcm.c.

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

References gcm_process(), len, and src.

Variable Documentation

gcm_cached_key

const union gcm_block* gcm_cached_key

static

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.

Definition at line 93 of file gcm.c.

Referenced by gcm_cache(), gcm_multiply_key(), and gcm_multiply_x_8().

gcm_cached_mult

union gcm_block gcm_cached_mult[256]

static

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.

Definition at line 101 of file gcm.c.

Referenced by gcm_cache(), and gcm_multiply_key().

gcm_cached_reduce

uint16_t gcm_cached_reduce[256]

static

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.

Definition at line 111 of file gcm.c.

Referenced by gcm_cache(), and gcm_multiply_x_8().