aes.c

Fast and transparent file system and swap encryption package for linux. No source code changes to li

// I retain copyright in this code but I encourage its free use provided
// that I don't carry any responsibility for the results. I am especially 
// happy to see it used in free and open source software. If you do use 
// it I would appreciate an acknowledgement of its origin in the code or
// the product that results and I would also appreciate knowing a little
// about the use to which it is being put. I am grateful to Frank Yellin
// for some ideas that are used in this implementation.
//
// Dr B. R. Gladman <[e-mail]> 6th April 2001.
//
// This is an implementation of the AES encryption algorithm (Rijndael)
// designed by Joan Daemen and Vincent Rijmen. This version is designed
// to provide both fixed and dynamic block and key lengths and can also 
// run with either big or little endian internal byte order (see aes.h). 
// It inputs block and key lengths in bytes with the legal values being 
// 16, 24 and 32.

/*
 * Modified by Jari Ruusu,  May 1 2001
 *  - Fixed some compile warnings, code was ok but gcc warned anyway.
 *  - Changed basic types: byte -> unsigned char, word -> u_int32_t
 *  - Major name space cleanup: Names visible to outside now begin
 *    with "aes_" or "AES_". A lot of stuff moved from aes.h to aes.c
 *  - Removed C++ and DLL support as part of name space cleanup.
 *  - Eliminated unnecessary recomputation of tables. (actual bug fix)
 *  - Merged precomputed constant tables to aes.c file.
 *  - Removed data alignment restrictions for portability reasons.
 *  - Made block and key lengths accept bit count (128/192/256)
 *    as well byte count (16/24/32).
 *  - Removed all error checks. This change also eliminated the need
 *    to preinitialize the context struct to zero.
 *  - Removed some totally unused constants.
 */
/*
 * Modified by Jari Ruusu,  April 21 2004
 *  - Added back code that avoids byte swaps on big endian boxes.
 */

#include "aes.h"

// CONFIGURATION OPTIONS (see also aes.h)
//
// 1.  Define UNROLL for full loop unrolling in encryption and decryption.
// 2.  Define PARTIAL_UNROLL to unroll two loops in encryption and decryption.
// 3.  Define FIXED_TABLES for compiled rather than dynamic tables.
// 4.  Define FF_TABLES to use tables for field multiplies and inverses.
//     Do not enable this without understanding stack space requirements.
// 5.  Define ARRAYS to use arrays to hold the local state block. If this
//     is not defined, individually declared 32-bit words are used.
// 6.  Define FAST_VARIABLE if a high speed variable block implementation
//     is needed (essentially three separate fixed block size code sequences)
// 7.  Define either ONE_TABLE or FOUR_TABLES for a fast table driven 
//     version using 1 table (2 kbytes of table space) or 4 tables (8
//     kbytes of table space) for higher speed.
// 8.  Define either ONE_LR_TABLE or FOUR_LR_TABLES for a further speed 
//     increase by using tables for the last rounds but with more table
//     space (2 or 8 kbytes extra).
// 9.  If neither ONE_TABLE nor FOUR_TABLES is defined, a compact but 
//     slower version is provided.
// 10. If fast decryption key scheduling is needed define ONE_IM_TABLE
//     or FOUR_IM_TABLES for higher speed (2 or 8 kbytes extra).

#define UNROLL
//#define PARTIAL_UNROLL

#define FIXED_TABLES
//#define FF_TABLES
//#define ARRAYS
#define FAST_VARIABLE

//#define ONE_TABLE
#define FOUR_TABLES

//#define ONE_LR_TABLE
#define FOUR_LR_TABLES

//#define ONE_IM_TABLE
#define FOUR_IM_TABLES

#if defined(UNROLL) && defined (PARTIAL_UNROLL)
#error both UNROLL and PARTIAL_UNROLL are defined
#endif

#if defined(ONE_TABLE) && defined (FOUR_TABLES)
#error both ONE_TABLE and FOUR_TABLES are defined
#endif

#if defined(ONE_LR_TABLE) && defined (FOUR_LR_TABLES)
#error both ONE_LR_TABLE and FOUR_LR_TABLES are defined
#endif

#if defined(ONE_IM_TABLE) && defined (FOUR_IM_TABLES)
#error both ONE_IM_TABLE and FOUR_IM_TABLES are defined
#endif

#if defined(AES_BLOCK_SIZE) && AES_BLOCK_SIZE != 16 && AES_BLOCK_SIZE != 24 && AES_BLOCK_SIZE != 32
#error an illegal block size has been specified
#endif  

/* INTERNAL_BYTE_ORDER: 0=unknown, 1=little endian, 2=big endian */
#if defined(INTERNAL_BYTE_ORDER)
#elif defined(__i386__)||defined(__i386)||defined(__x86_64__)||defined(__x86_64)||defined(__amd64__)||defined(__amd64)||defined(__AMD64__)||defined(__AMD64)
# define INTERNAL_BYTE_ORDER 1
# undef DATA_ALWAYS_ALIGNED
# define DATA_ALWAYS_ALIGNED 1  /* unaligned access is always ok */
#elif defined(__ppc__)||defined(__ppc)||defined(__PPC__)||defined(__PPC)||defined(__powerpc__)||defined(__powerpc)||defined(__POWERPC__)||defined(__POWERPC)||defined(__PowerPC__)||defined(__PowerPC)||defined(__ppc64__)||defined(__ppc64)||defined(__PPC64__)||defined(__PPC64)||defined(__powerpc64__)||defined(__powerpc64)||defined(__s390__)||defined(__s390)
# define INTERNAL_BYTE_ORDER 2
# undef DATA_ALWAYS_ALIGNED
# define DATA_ALWAYS_ALIGNED 1  /* unaligned access is always ok */
#elif defined(__alpha__)||defined(__alpha)||defined(__ia64__)||defined(__ia64)
# define INTERNAL_BYTE_ORDER 1
#elif defined(__hppa__)||defined(__hppa)||defined(__HPPA__)||defined(__HPPA)||defined(__parisc__)||defined(__parisc)||defined(__sparc__)||defined(__sparc)||defined(__sparc_v9__)||defined(__sparc_v9)||defined(__sparc64__)||defined(__sparc64)||defined(__mc68000__)||defined(__mc68000)
# define INTERNAL_BYTE_ORDER 2
#elif defined(CONFIGURE_DETECTS_BYTE_ORDER)
# if WORDS_BIGENDIAN
#  define INTERNAL_BYTE_ORDER 2
# else
#  define INTERNAL_BYTE_ORDER 1
# endif
#elif defined(__linux__) && defined(__KERNEL__)
# include <asm/byteorder.h>
# if defined(__BIG_ENDIAN)
#  define INTERNAL_BYTE_ORDER 2
# else
#  define INTERNAL_BYTE_ORDER 1
# endif
#else
# include <sys/param.h>
# if (defined(BYTE_ORDER) && defined(LITTLE_ENDIAN) && (BYTE_ORDER == LITTLE_ENDIAN)) || (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && (__BYTE_ORDER == __LITTLE_ENDIAN))
#  define INTERNAL_BYTE_ORDER 1
# elif WORDS_BIGENDIAN || defined(__BIG_ENDIAN__) || (defined(BYTE_ORDER) && defined(BIG_ENDIAN) && (BYTE_ORDER == BIG_ENDIAN)) || (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && (__BYTE_ORDER == __BIG_ENDIAN))
#  define INTERNAL_BYTE_ORDER 2
# else
#  define INTERNAL_BYTE_ORDER 0
# endif
#endif

#if defined(DATA_ALWAYS_ALIGNED) && (INTERNAL_BYTE_ORDER > 0)
# define word_in(x)      *(u_int32_t*)(x)
# define word_out(x,v)   *(u_int32_t*)(x) = (v)
#elif defined(__linux__) && defined(__KERNEL__)
# include <asm/unaligned.h>
# define word_in(x)      get_unaligned((u_int32_t*)(x))
# define word_out(x,v)   put_unaligned((v),(u_int32_t*)(x))
#else
/* unknown endianness and/or unable to handle unaligned data */
# undef INTERNAL_BYTE_ORDER
# define INTERNAL_BYTE_ORDER 1
# define word_in(x)      ((u_int32_t)(((unsigned char *)(x))[0])|((u_int32_t)(((unsigned char *)(x))[1])<<8)|((u_int32_t)(((unsigned char *)(x))[2])<<16)|((u_int32_t)(((unsigned char *)(x))[3])<<24))
# define word_out(x,v)   ((unsigned char *)(x))[0]=(v),((unsigned char *)(x))[1]=((v)>>8),((unsigned char *)(x))[2]=((v)>>16),((unsigned char *)(x))[3]=((v)>>24)
#endif

// upr(x,n): rotates bytes within words by n positions, moving bytes 
// to higher index positions with wrap around into low positions
// ups(x,n): moves bytes by n positions to higher index positions in 
// words but without wrap around
// bval(x,n): extracts a byte from a word

#if (INTERNAL_BYTE_ORDER < 2)
/* little endian */
#define upr(x,n)        (((x) << 8 * (n)) | ((x) >> (32 - 8 * (n))))
#define ups(x,n)        ((x) << 8 * (n))
#define bval(x,n)       ((unsigned char)((x) >> 8 * (n)))
#define bytes2word(b0, b1, b2, b3)  \
        ((u_int32_t)(b3) << 24 | (u_int32_t)(b2) << 16 | (u_int32_t)(b1) << 8 | (b0))
#else
/* big endian */
#define upr(x,n)        (((x) >> 8 * (n)) | ((x) << (32 - 8 * (n))))
#define ups(x,n)        ((x) >> 8 * (n)))
#define bval(x,n)       ((unsigned char)((x) >> (24 - 8 * (n))))
#define bytes2word(b0, b1, b2, b3)  \
        ((u_int32_t)(b0) << 24 | (u_int32_t)(b1) << 16 | (u_int32_t)(b2) << 8 | (b3))
#endif

// Disable at least some poor combinations of options

#if !defined(ONE_TABLE) && !defined(FOUR_TABLES)
#define FIXED_TABLES
#undef  UNROLL
#undef  ONE_LR_TABLE
#undef  FOUR_LR_TABLES
#undef  ONE_IM_TABLE
#undef  FOUR_IM_TABLES
#elif !defined(FOUR_TABLES)
#ifdef  FOUR_LR_TABLES
#undef  FOUR_LR_TABLES
#define ONE_LR_TABLE
#endif
#ifdef  FOUR_IM_TABLES
#undef  FOUR_IM_TABLES
#define ONE_IM_TABLE
#endif
#elif !defined(AES_BLOCK_SIZE)
#if defined(UNROLL)
#define PARTIAL_UNROLL
#undef UNROLL
#endif
#endif

// the finite field modular polynomial and elements

#define ff_poly 0x011b
#define ff_hi   0x80

// multiply four bytes in GF(2^8) by 'x' {02} in parallel

#define m1  0x80808080
#define m2  0x7f7f7f7f
#define m3  0x0000001b
#define FFmulX(x)  ((((x) & m2) << 1) ^ ((((x) & m1) >> 7) * m3))

// The following defines provide alternative definitions of FFmulX that might
// give improved performance if a fast 32-bit multiply is not available. Note
// that a temporary variable u needs to be defined where FFmulX is used.

// #define FFmulX(x) (u = (x) & m1, u |= (u >> 1), ((x) & m2) << 1) ^ ((u >> 3) | (u >> 6)) 
// #define m4  0x1b1b1b1b
// #define FFmulX(x) (u = (x) & m1, ((x) & m2) << 1) ^ ((u - (u >> 7)) & m4) 

// perform column mix operation on four bytes in parallel

#define fwd_mcol(x) (f2 = FFmulX(x), f2 ^ upr(x ^ f2,3) ^ upr(x,2) ^ upr(x,1))

#if defined(FIXED_TABLES)

// the S-Box table

static const unsigned char s_box[256] =
{
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
    0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0,
    0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
    0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a,
    0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0,
    0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b,
    0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85,
    0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
    0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17,
    0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88,
    0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c,
    0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9,
    0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
    0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e,
    0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94,
    0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68,
    0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
};

// the inverse S-Box table

static const unsigned char inv_s_box[256] =
{
    0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38,
    0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
    0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87,
    0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
    0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d,
    0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
    0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2,
    0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
    0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16,
    0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
    0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda,
    0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
    0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a,
    0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
    0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02,
    0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
    0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea,
    0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
    0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85,
    0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
    0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89,
    0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
    0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20,
    0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
    0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31,
    0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
    0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d,
    0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
    0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0,
    0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26,
    0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d
};

// used to ensure table is generated in the right format
// depending on the internal byte order required

#if (INTERNAL_BYTE_ORDER < 2)
/* little endian */
#define w0(p)          0x000000##p
#else
/* big endian */
#define w0(p)        0x##p##000000
#endif

// Number of elements required in this table for different
// block and key lengths is:
//
// Nk =      4  6  8
//        ----------
// Nb = 4 | 10  8  7
//      6 | 19 12 11
//      8 | 29 19 14
//
// this table can be a table of bytes if the key schedule
// code is adjusted accordingly

static const u_int32_t rcon_tab[29] =
{
    w0(01), w0(02), w0(04), w0(08),
    w0(10), w0(20), w0(40), w0(80),
    w0(1b), w0(36), w0(6c), w0(d8),
    w0(ab), w0(4d), w0(9a), w0(2f),
    w0(5e), w0(bc), w0(63), w0(c6),
    w0(97), w0(35), w0(6a), w0(d4),
    w0(b3), w0(7d), w0(fa), w0(ef),
    w0(c5)
};

#undef  w0

// used to ensure table is generated in the right format
// depending on the internal byte order required

#if (INTERNAL_BYTE_ORDER < 2)
/* little endian */
#define r0(p,q,r,s) 0x##p##q##r##s
#define r1(p,q,r,s) 0x##q##r##s##p
#define r2(p,q,r,s) 0x##r##s##p##q
#define r3(p,q,r,s) 0x##s##p##q##r
#define w0(p)          0x000000##p
#define w1(p)        0x0000##p##00
#define w2(p)        0x00##p##0000
#define w3(p)        0x##p##000000
#else
/* big endian */
#define r0(p,q,r,s) 0x##s##r##q##p
#define r1(p,q,r,s) 0x##p##s##r##q
#define r2(p,q,r,s) 0x##q##p##s##r
#define r3(p,q,r,s) 0x##r##q##p##s
#define w0(p)        0x##p##000000
#define w1(p)        0x00##p##0000
#define w2(p)        0x0000##p##00
#define w3(p)          0x000000##p
#endif

#if defined(FIXED_TABLES) && (defined(ONE_TABLE) || defined(FOUR_TABLES)) 

//  data for forward tables (other than last round)

#define f_table \
    r(a5,63,63,c6), r(84,7c,7c,f8), r(99,77,77,ee), r(8d,7b,7b,f6),\
    r(0d,f2,f2,ff), r(bd,6b,6b,d6), r(b1,6f,6f,de), r(54,c5,c5,91),\