iPXE
Data Structures | Enumerations | Functions | Variables
aes.c File Reference

AES algorithm. More...

#include <stdint.h>
#include <string.h>
#include <errno.h>
#include <assert.h>
#include <byteswap.h>
#include <ipxe/rotate.h>
#include <ipxe/crypto.h>
#include <ipxe/ecb.h>
#include <ipxe/cbc.h>
#include <ipxe/aes.h>

Go to the source code of this file.

Data Structures

union  aes_table_entry
 A single AES lookup table entry. More...
struct  aes_table
 An AES lookup table. More...

Enumerations

enum  aes_stride { AES_STRIDE_SHIFTROWS = +5, AES_STRIDE_INVSHIFTROWS = -3 }
 AES strides. More...

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
union aes_table_entry __attribute__ ((packed))
struct aes_table __attribute__ ((aligned(8)))
static __attribute__ ((always_inline))
 Multiply [Inv]MixColumns matrix column by scalar multiplicand.
static __attribute__ ((noinline))
 Perform encryption intermediate rounds.
static void aes_final (const struct aes_table *table, size_t stride, const union aes_matrix *in, union aes_matrix *out, const union aes_matrix *key)
 Perform final round.
static void aes_encrypt (void *ctx, const void *src, void *dst, size_t len)
 Encrypt data.
static void aes_decrypt (void *ctx, const void *src, void *dst, size_t len)
 Decrypt data.
static __attribute__ ((const ))
 Multiply a polynomial by (x) modulo (x^8 + x^4 + x^3 + x^2 + 1) in GF(2^8)
static void aes_mixcolumns_entry (union aes_table_entry *entry)
 Fill in MixColumns lookup table entry.
static void aes_invmixcolumns_entry (union aes_table_entry *entry)
 Fill in InvMixColumns lookup table entry.
static void aes_generate (void)
 Generate AES lookup tables.
static uint32_t aes_key_sbox (uint32_t column)
 Apply S-box to key column.
static int aes_setkey (void *ctx, const void *key, size_t keylen)
 Set key.
static void aes_setiv (void *ctx __unused, const void *iv __unused)
 Set initialisation vector.
 ECB_CIPHER (aes_ecb, aes_ecb_algorithm, aes_algorithm, struct aes_context, AES_BLOCKSIZE)
 CBC_CIPHER (aes_cbc, aes_cbc_algorithm, aes_algorithm, struct aes_context, AES_BLOCKSIZE)

Variables

uint8_t byte [8]
 Viewed as an array of bytes.
union aes_table_entry entry [256]
 Table entries, indexed by S(N)
static struct aes_table aes_mixcolumns
 AES MixColumns lookup table.
static struct aes_table aes_invmixcolumns
 AES InvMixColumns lookup table.
struct cipher_algorithm aes_algorithm
 Basic AES algorithm.

Detailed Description

AES algorithm.

Definition in file aes.c.


Enumeration Type Documentation

enum aes_stride

AES strides.

These are the strides (modulo 16) used to walk through the AES input state bytes in order of byte position after [Inv]ShiftRows.

Enumerator:
AES_STRIDE_SHIFTROWS 

Input stride for ShiftRows.

0 4 8 c \ \ \ 1 5 9 d \ \ \ 2 6 a e \ \ \ 3 7 b f

AES_STRIDE_INVSHIFTROWS 

Input stride for InvShiftRows.

0 4 8 c / / / 1 5 9 d / / / 2 6 a e / / / 3 7 b f

Definition at line 48 of file aes.c.

                {
        /** Input stride for ShiftRows
         *
         *    0 4 8 c
         *     \ \ \
         *    1 5 9 d
         *     \ \ \
         *    2 6 a e
         *     \ \ \
         *    3 7 b f
         */
        AES_STRIDE_SHIFTROWS = +5,
        /** Input stride for InvShiftRows
         *
         *    0 4 8 c
         *     / / /
         *    1 5 9 d
         *     / / /
         *    2 6 a e
         *     / / /
         *    3 7 b f
         */
        AES_STRIDE_INVSHIFTROWS = -3,
};

Function Documentation

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )
union aes_table_entry __attribute__ ( (packed)  )
struct aes_table __attribute__ ( (aligned(8))  )
static __attribute__ ( (always_inline)  ) [inline, static]

Multiply [Inv]MixColumns matrix column by scalar multiplicand.

Apply schedule round constant to key column.

Rotate key column.

Perform standalone AddRoundKey.

Perform a single intermediate round.

Calculate intermediate round output column.

Multiply [Inv]MixColumns matrix column by S-boxed input byte.

Parameters:
entryAES lookup table entry for scalar multiplicand
column[Inv]MixColumns matrix column index
Return values:
productProduct of matrix column with scalar multiplicand
Parameters:
tableAES lookup table
strideAES row shift stride
inAES input state
offsetOutput byte offset (after [Inv]ShiftRows)
Return values:
productProduct of matrix column with S(input byte)

Note that the specified offset is not the offset of the input byte; it is the offset of the output byte which corresponds to the input byte. This output byte offset is used to calculate both the input byte offset and to select the appropriate matric column.

With a compile-time constant offset, this function will optimise down to a single "movzbl" (to extract the input byte) and will generate a single x86 memory reference expression which can then be used directly within a single "xorl" instruction.

Parameters:
tableAES lookup table
strideAES row shift stride
inAES input state
keyAES round key
columnColumn index
Return values:
outputOutput column value
Parameters:
tableAES lookup table
strideAES row shift stride
inAES input state
outAES output state
keyAES round key
stateAES state
keyAES round key
columnKey column
Return values:
columnUpdated key column
Parameters:
columnKey column
rconRound constant
Return values:
columnUpdated key column

Definition at line 157 of file aes.c.

References __attribute__, byte, column, container_of, and product.

                                                                             {
        const union {
                uint8_t byte;
                uint32_t column;
        } __attribute__ (( may_alias )) *product;

        /* Locate relevant four-byte subset */
        product = container_of ( &entry->byte[ 4 - column ],
                                 typeof ( *product ), byte );

        /* Extract this four-byte subset */
        return product->column;
}
static __attribute__ ( (noinline)  ) [static]

Perform encryption intermediate rounds.

Perform decryption intermediate rounds.

Parameters:
inAES input state
outAES output state
keyRound keys
roundsNumber of rounds (must be odd)

This function is deliberately marked as non-inlinable to ensure maximal availability of registers for GCC's register allocator, which has a tendency to otherwise spill performance-critical registers to the stack.

Parameters:
inAES input state
outAES output state
keyRound keys
roundsNumber of rounds (must be odd)

As with aes_encrypt_rounds(), this function is deliberately marked as non-inlinable.

This function could potentially use the same binary code as is used for encryption. To compensate for the difference between ShiftRows and InvShiftRows, half of the input byte offsets would have to be modifiable at runtime (half by an offset of +4/-4, half by an offset of -4/+4 for ShiftRows/InvShiftRows). This can be accomplished in x86 assembly within the number of available registers, but GCC's register allocator struggles to do so, resulting in a significant performance decrease due to registers being spilled to the stack. We therefore use two separate but very similar binary functions based on the same C source.

Definition at line 277 of file aes.c.

References aes_mixcolumns, AES_STRIDE_SHIFTROWS, in, and out.

                                                                        {
        union aes_matrix *tmp;

        /* Perform intermediate rounds */
        do {
                /* Perform one intermediate round */
                aes_round ( &aes_mixcolumns, AES_STRIDE_SHIFTROWS,
                            in, out, key++ );

                /* Swap input and output states for next round */
                tmp = in;
                in = out;
                out = tmp;

        } while ( --rounds );
}
static void aes_final ( const struct aes_table table,
size_t  stride,
const union aes_matrix in,
union aes_matrix out,
const union aes_matrix key 
) [static]

Perform final round.

Parameters:
tableAES lookup table
strideAES row shift stride
inAES input state
outAES output state
keyAES round key

Definition at line 361 of file aes.c.

References aes_matrix::byte, aes_table_entry::byte, byte, aes_table::entry, and entry.

Referenced by aes_decrypt(), aes_encrypt(), and aes_setkey().

                                                      {
        const union aes_table_entry *entry;
        unsigned int byte;
        size_t out_offset;
        size_t in_offset;

        /* Perform [Inv]ShiftRows and [Inv]SubBytes */
        for ( out_offset = 0, in_offset = 0 ; out_offset < 16 ;
              out_offset++, in_offset = ( ( in_offset + stride ) & 0xf ) ) {

                /* Extract input byte (i.e. perform [Inv]ShiftRows) */
                byte = in->byte[in_offset];

                /* Locate lookup table entry for this input byte
                 * (i.e. perform [Inv]SubBytes).
                 */
                entry = &table->entry[byte];

                /* Store output byte */
                out->byte[out_offset] = entry->byte[0];
        }

        /* Perform AddRoundKey */
        aes_addroundkey ( out, key );
}
static void aes_encrypt ( void *  ctx,
const void *  src,
void *  dst,
size_t  len 
) [static]

Encrypt data.

Parameters:
ctxContext
srcData to encrypt
dstBuffer for encrypted data
lenLength of data

Definition at line 397 of file aes.c.

References aes_final(), aes_mixcolumns, AES_STRIDE_SHIFTROWS, assert, ctx, aes_context::encrypt, aes_round_keys::key, memcpy(), out, and aes_context::rounds.

                                                                              {
        struct aes_context *aes = ctx;
        union aes_matrix buffer[2];
        union aes_matrix *in = &buffer[0];
        union aes_matrix *out = &buffer[1];
        unsigned int rounds = aes->rounds;

        /* Sanity check */
        assert ( len == sizeof ( *in ) );

        /* Initialise input state */
        memcpy ( in, src, sizeof ( *in ) );

        /* Perform initial round (AddRoundKey) */
        aes_addroundkey ( in, &aes->encrypt.key[0] );

        /* Perform intermediate rounds (ShiftRows, SubBytes,
         * MixColumns, AddRoundKey).
         */
        aes_encrypt_rounds ( in, out, &aes->encrypt.key[1], ( rounds - 2 ) );
        in = out;

        /* Perform final round (ShiftRows, SubBytes, AddRoundKey) */
        out = dst;
        aes_final ( &aes_mixcolumns, AES_STRIDE_SHIFTROWS, in, out,
                    &aes->encrypt.key[ rounds - 1 ] );
}
static void aes_decrypt ( void *  ctx,
const void *  src,
void *  dst,
size_t  len 
) [static]

Decrypt data.

Parameters:
ctxContext
srcData to decrypt
dstBuffer for decrypted data
lenLength of data

Definition at line 433 of file aes.c.

References aes_final(), aes_invmixcolumns, AES_STRIDE_INVSHIFTROWS, assert, ctx, aes_context::decrypt, aes_round_keys::key, memcpy(), out, and aes_context::rounds.

                                                                              {
        struct aes_context *aes = ctx;
        union aes_matrix buffer[2];
        union aes_matrix *in = &buffer[0];
        union aes_matrix *out = &buffer[1];
        unsigned int rounds = aes->rounds;

        /* Sanity check */
        assert ( len == sizeof ( *in ) );

        /* Initialise input state */
        memcpy ( in, src, sizeof ( *in ) );

        /* Perform initial round (AddRoundKey) */
        aes_addroundkey ( in, &aes->decrypt.key[0] );

        /* Perform intermediate rounds (InvShiftRows, InvSubBytes,
         * InvMixColumns, AddRoundKey).
         */
        aes_decrypt_rounds ( in, out, &aes->decrypt.key[1], ( rounds - 2 ) );
        in = out;

        /* Perform final round (InvShiftRows, InvSubBytes, AddRoundKey) */
        out = dst;
        aes_final ( &aes_invmixcolumns, AES_STRIDE_INVSHIFTROWS, in, out,
                    &aes->decrypt.key[ rounds - 1 ] );
}
static __attribute__ ( (const )  ) [static]

Multiply a polynomial by (x) modulo (x^8 + x^4 + x^3 + x^2 + 1) in GF(2^8)

Parameters:
polyPolynomial to be multiplied
Return values:
resultResult

Definition at line 467 of file aes.c.

                                                                               {

        /* Multiply polynomial by (x), placing the resulting x^8
         * coefficient in the LSB (i.e. rotate byte left by one).
         */
        poly = rol8 ( poly, 1 );

        /* If coefficient of x^8 (in LSB) is non-zero, then reduce by
         * subtracting (x^8 + x^4 + x^3 + x^2 + 1) in GF(2^8).
         */
        if ( poly & 0x01 ) {
                poly ^= 0x01; /* Subtract x^8 (currently in LSB) */
                poly ^= 0x1b; /* Subtract (x^4 + x^3 + x^2 + 1) */
        }

        return poly;
}
static void aes_mixcolumns_entry ( union aes_table_entry entry) [static]

Fill in MixColumns lookup table entry.

Parameters:
entryAES lookup table entry for scalar multiplicand

The MixColumns lookup table vector multiplier is {1,1,1,3,2,1,1,3}.

Definition at line 492 of file aes.c.

References aes_table_entry::byte.

Referenced by aes_generate().

                                                                  {
        unsigned int scalar_x_1;
        unsigned int scalar_x;
        unsigned int scalar;

        /* Retrieve scalar multiplicand */
        scalar = entry->byte[0];
        entry->byte[1] = scalar;
        entry->byte[2] = scalar;
        entry->byte[5] = scalar;
        entry->byte[6] = scalar;

        /* Calculate scalar multiplied by (x) */
        scalar_x = aes_double ( scalar );
        entry->byte[4] = scalar_x;

        /* Calculate scalar multiplied by (x + 1) */
        scalar_x_1 = ( scalar_x ^ scalar );
        entry->byte[3] = scalar_x_1;
        entry->byte[7] = scalar_x_1;
}
static void aes_invmixcolumns_entry ( union aes_table_entry entry) [static]

Fill in InvMixColumns lookup table entry.

Parameters:
entryAES lookup table entry for scalar multiplicand

The InvMixColumns lookup table vector multiplier is {1,9,13,11,14,9,13,11}.

Definition at line 521 of file aes.c.

References aes_table_entry::byte.

Referenced by aes_generate().

                                                                     {
        unsigned int scalar_x3_x2_x;
        unsigned int scalar_x3_x2_1;
        unsigned int scalar_x3_x2;
        unsigned int scalar_x3_x_1;
        unsigned int scalar_x3_1;
        unsigned int scalar_x3;
        unsigned int scalar_x2;
        unsigned int scalar_x;
        unsigned int scalar;

        /* Retrieve scalar multiplicand */
        scalar = entry->byte[0];

        /* Calculate scalar multiplied by (x) */
        scalar_x = aes_double ( scalar );

        /* Calculate scalar multiplied by (x^2) */
        scalar_x2 = aes_double ( scalar_x );

        /* Calculate scalar multiplied by (x^3) */
        scalar_x3 = aes_double ( scalar_x2 );

        /* Calculate scalar multiplied by (x^3 + 1) */
        scalar_x3_1 = ( scalar_x3 ^ scalar );
        entry->byte[1] = scalar_x3_1;
        entry->byte[5] = scalar_x3_1;

        /* Calculate scalar multiplied by (x^3 + x + 1) */
        scalar_x3_x_1 = ( scalar_x3_1 ^ scalar_x );
        entry->byte[3] = scalar_x3_x_1;
        entry->byte[7] = scalar_x3_x_1;

        /* Calculate scalar multiplied by (x^3 + x^2) */
        scalar_x3_x2 = ( scalar_x3 ^ scalar_x2 );

        /* Calculate scalar multiplied by (x^3 + x^2 + 1) */
        scalar_x3_x2_1 = ( scalar_x3_x2 ^ scalar );
        entry->byte[2] = scalar_x3_x2_1;
        entry->byte[6] = scalar_x3_x2_1;

        /* Calculate scalar multiplied by (x^3 + x^2 + x) */
        scalar_x3_x2_x = ( scalar_x3_x2 ^ scalar_x );
        entry->byte[4] = scalar_x3_x2_x;
}
static void aes_generate ( void  ) [static]

Generate AES lookup tables.

Definition at line 571 of file aes.c.

References aes_invmixcolumns, aes_invmixcolumns_entry(), aes_mixcolumns, aes_mixcolumns_entry(), aes_table_entry::byte, aes_table::entry, and entry.

Referenced by aes_setkey().

                                  {
        union aes_table_entry *entry;
        union aes_table_entry *inventry;
        unsigned int poly = 0x01;
        unsigned int invpoly = 0x01;
        unsigned int transformed;
        unsigned int i;

        /* Iterate over non-zero values of GF(2^8) using generator (x + 1) */
        do {

                /* Multiply polynomial by (x + 1) */
                poly ^= aes_double ( poly );

                /* Divide inverse polynomial by (x + 1).  This code
                 * fragment is taken directly from the Wikipedia page
                 * on the Rijndael S-box.  An explanation of why it
                 * works would be greatly appreciated.
                 */
                invpoly ^= ( invpoly << 1 );
                invpoly ^= ( invpoly << 2 );
                invpoly ^= ( invpoly << 4 );
                if ( invpoly & 0x80 )
                        invpoly ^= 0x09;
                invpoly &= 0xff;

                /* Apply affine transformation */
                transformed = ( 0x63 ^ invpoly ^ rol8 ( invpoly, 1 ) ^
                                rol8 ( invpoly, 2 ) ^ rol8 ( invpoly, 3 ) ^
                                rol8 ( invpoly, 4 ) );

                /* Populate S-box (within MixColumns lookup table) */
                aes_mixcolumns.entry[poly].byte[0] = transformed;

        } while ( poly != 0x01 );

        /* Populate zeroth S-box entry (which has no inverse) */
        aes_mixcolumns.entry[0].byte[0] = 0x63;

        /* Fill in MixColumns and InvMixColumns lookup tables */
        for ( i = 0 ; i < 256 ; i++ ) {

                /* Fill in MixColumns lookup table entry */
                entry = &aes_mixcolumns.entry[i];
                aes_mixcolumns_entry ( entry );

                /* Populate inverse S-box (within InvMixColumns lookup table) */
                inventry = &aes_invmixcolumns.entry[ entry->byte[0] ];
                inventry->byte[0] = i;

                /* Fill in InvMixColumns lookup table entry */
                aes_invmixcolumns_entry ( inventry );
        }
}
static uint32_t aes_key_sbox ( uint32_t  column) [static]

Apply S-box to key column.

Parameters:
columnKey column
Return values:
columnUpdated key column

Definition at line 645 of file aes.c.

References aes_mixcolumns, aes_table_entry::byte, byte, column, aes_table::entry, and rol32().

Referenced by aes_setkey().

                                                 {
        unsigned int i;
        uint8_t byte;

        for ( i = 0 ; i < 4 ; i++ ) {
                byte = ( column & 0xff );
                byte = aes_mixcolumns.entry[byte].byte[0];
                column = ( ( column & ~0xff ) | byte );
                column = rol32 ( column, 8 );
        }
        return column;
}
static int aes_setkey ( void *  ctx,
const void *  key,
size_t  keylen 
) [static]

Set key.

Parameters:
ctxContext
keyKey
keylenKey length
Return values:
rcReturn status code

Definition at line 680 of file aes.c.

References aes_final(), aes_generate(), aes_key_sbox(), aes_mixcolumns, AES_STRIDE_SHIFTROWS, aes_table_entry::byte, aes_matrix::column, ctx, DBGC, DBGC2, DBGC2_HDA, aes_context::decrypt, EINVAL, aes_context::encrypt, end, aes_table::entry, aes_round_keys::key, memcpy(), memset(), next, and aes_context::rounds.

                                                                    {
        struct aes_context *aes = ctx;
        union aes_matrix *enc;
        union aes_matrix *dec;
        union aes_matrix temp;
        union aes_matrix zero;
        unsigned int rcon = 0x01;
        unsigned int rounds;
        size_t offset = 0;
        uint32_t *prev;
        uint32_t *next;
        uint32_t *end;
        uint32_t tmp;

        /* Generate lookup tables, if not already done */
        if ( ! aes_mixcolumns.entry[0].byte[0] )
                aes_generate();

        /* Validate key length and calculate number of intermediate rounds */
        switch ( keylen ) {
        case ( 128 / 8 ) :
                rounds = 11;
                break;
        case ( 192 / 8 ) :
                rounds = 13;
                break;
        case ( 256 / 8 ) :
                rounds = 15;
                break;
        default:
                DBGC ( aes, "AES %p unsupported key length (%zd bits)\n",
                       aes, ( keylen * 8 ) );
                return -EINVAL;
        }
        aes->rounds = rounds;
        enc = aes->encrypt.key;
        end = enc[rounds].column;

        /* Copy raw key */
        memcpy ( enc, key, keylen );
        prev = enc->column;
        next = ( ( ( void * ) prev ) + keylen );
        tmp = next[-1];

        /* Construct expanded key */
        while ( next < end ) {

                /* If this is the first column of an expanded key
                 * block, or the middle column of an AES-256 key
                 * block, then apply the S-box.
                 */
                if ( ( offset == 0 ) || ( ( offset | keylen ) == 48 ) )
                        tmp = aes_key_sbox ( tmp );

                /* If this is the first column of an expanded key
                 * block then rotate and apply the round constant.
                 */
                if ( offset == 0 ) {
                        tmp = aes_key_rotate ( tmp );
                        tmp = aes_key_rcon ( tmp, rcon );
                        rcon = aes_double ( rcon );
                }

                /* XOR with previous key column */
                tmp ^= *prev;

                /* Store column */
                *next = tmp;

                /* Move to next column */
                offset += sizeof ( *next );
                if ( offset == keylen )
                        offset = 0;
                next++;
                prev++;
        }
        DBGC2 ( aes, "AES %p expanded %zd-bit key:\n", aes, ( keylen * 8 ) );
        DBGC2_HDA ( aes, 0, &aes->encrypt, ( rounds * sizeof ( *enc ) ) );

        /* Convert to decryption key */
        memset ( &zero, 0, sizeof ( zero ) );
        dec = &aes->decrypt.key[ rounds - 1 ];
        memcpy ( dec--, enc++, sizeof ( *dec ) );
        while ( dec > aes->decrypt.key ) {
                /* Perform InvMixColumns (by reusing the encryption
                 * final-round code to perform ShiftRows+SubBytes and
                 * reusing the decryption intermediate-round code to
                 * perform InvShiftRows+InvSubBytes+InvMixColumns, all
                 * with a zero encryption key).
                 */
                aes_final ( &aes_mixcolumns, AES_STRIDE_SHIFTROWS,
                            enc++, &temp, &zero );
                aes_decrypt_rounds ( &temp, dec--, &zero, 1 );
        }
        memcpy ( dec--, enc++, sizeof ( *dec ) );
        DBGC2 ( aes, "AES %p inverted %zd-bit key:\n", aes, ( keylen * 8 ) );
        DBGC2_HDA ( aes, 0, &aes->decrypt, ( rounds * sizeof ( *dec ) ) );

        return 0;
}
static void aes_setiv ( void *ctx  __unused,
const void *iv  __unused 
) [static]

Set initialisation vector.

Parameters:
ctxContext
ivInitialisation vector

Definition at line 787 of file aes.c.

                                                                      {
        /* Nothing to do */
}
ECB_CIPHER ( aes_ecb  ,
aes_ecb_algorithm  ,
aes_algorithm  ,
struct aes_context  ,
AES_BLOCKSIZE   
)
CBC_CIPHER ( aes_cbc  ,
aes_cbc_algorithm  ,
aes_algorithm  ,
struct aes_context  ,
AES_BLOCKSIZE   
)

Variable Documentation

union aes_table_entry entry[256]
struct aes_table aes_mixcolumns [static]

AES MixColumns lookup table.

Definition at line 145 of file aes.c.

Referenced by __attribute__(), aes_encrypt(), aes_generate(), aes_key_sbox(), and aes_setkey().

struct aes_table aes_invmixcolumns [static]

AES InvMixColumns lookup table.

Definition at line 148 of file aes.c.

Referenced by aes_decrypt(), and aes_generate().

Initial value:
 {
        .name = "aes",
        .ctxsize = sizeof ( struct aes_context ),
        .blocksize = AES_BLOCKSIZE,
        .setkey = aes_setkey,
        .setiv = aes_setiv,
        .encrypt = aes_encrypt,
        .decrypt = aes_decrypt,
}

Basic AES algorithm.

Definition at line 792 of file aes.c.

Referenced by aes_unwrap(), aes_wrap(), ccmp_cbc_mac(), ccmp_ctr_xor(), ccmp_feed_cbc_mac(), and ccmp_init().