aes.c

00001 /*
00002  * Copyright (c) 2007, Cameron Rich
00003  * 
00004  * All rights reserved.
00005  * 
00006  * Redistribution and use in source and binary forms, with or without 
00007  * modification, are permitted provided that the following conditions are met:
00008  *
00009  * * Redistributions of source code must retain the above copyright notice, 
00010  *   this list of conditions and the following disclaimer.
00011  * * Redistributions in binary form must reproduce the above copyright notice, 
00012  *   this list of conditions and the following disclaimer in the documentation 
00013  *   and/or other materials provided with the distribution.
00014  * * Neither the name of the axTLS project nor the names of its contributors 
00015  *   may be used to endorse or promote products derived from this software 
00016  *   without specific prior written permission.
00017  *
00018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00019  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00020  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00021  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
00022  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00023  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00024  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00025  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00026  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00027  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  */
00030 
00031 /**
00032  * AES implementation - this is a small code version. There are much faster
00033  * versions around but they are much larger in size (i.e. they use large 
00034  * submix tables).
00035  */
00036 
00037 #include <string.h>
00038 //#include "os_port.h"
00039 #include "crypto.h "
00040 #include <lwip/def.h>
00041 
00042 /* all commented out in skeleton mode */
00043 #ifndef CONFIG_SSL_SKELETON_MODE
00044 
00045 #define rot1(x) (((x) << 24) | ((x) >> 8))
00046 #define rot2(x) (((x) << 16) | ((x) >> 16))
00047 #define rot3(x) (((x) <<  8) | ((x) >> 24))
00048 
00049 /* 
00050  * This cute trick does 4 'mul by two' at once.  Stolen from
00051  * Dr B. R. Gladman <brg@gladman.uk.net> but I'm sure the u-(u>>7) is
00052  * a standard graphics trick
00053  * The key to this is that we need to xor with 0x1b if the top bit is set.
00054  * a 1xxx xxxx   0xxx 0xxx First we mask the 7bit,
00055  * b 1000 0000   0000 0000 then we shift right by 7 putting the 7bit in 0bit,
00056  * c 0000 0001   0000 0000 we then subtract (c) from (b)
00057  * d 0111 1111   0000 0000 and now we and with our mask
00058  * e 0001 1011   0000 0000
00059  */
00060 #define mt  0x80808080
00061 #define ml  0x7f7f7f7f
00062 #define mh  0xfefefefe
00063 #define mm  0x1b1b1b1b
00064 #define mul2(x,t)    ((t)=((x)&mt), \
00065             ((((x)+(x))&mh)^(((t)-((t)>>7))&mm)))
00066 
00067 #define inv_mix_col(x,f2,f4,f8,f9) (\
00068             (f2)=mul2(x,f2), \
00069             (f4)=mul2(f2,f4), \
00070             (f8)=mul2(f4,f8), \
00071             (f9)=(x)^(f8), \
00072             (f8)=((f2)^(f4)^(f8)), \
00073             (f2)^=(f9), \
00074             (f4)^=(f9), \
00075             (f8)^=rot3(f2), \
00076             (f8)^=rot2(f4), \
00077             (f8)^rot1(f9))
00078 
00079 /*
00080  * AES S-box
00081  */
00082 static const uint8_t aes_sbox[256] =
00083 {
00084     0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,
00085     0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
00086     0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,
00087     0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
00088     0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,
00089     0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
00090     0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,
00091     0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
00092     0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,
00093     0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
00094     0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,
00095     0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
00096     0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,
00097     0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
00098     0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,
00099     0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
00100     0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,
00101     0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
00102     0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,
00103     0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
00104     0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,
00105     0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
00106     0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,
00107     0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
00108     0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,
00109     0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
00110     0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,
00111     0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
00112     0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,
00113     0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
00114     0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,
00115     0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16,
00116 };
00117 
00118 /*
00119  * AES is-box
00120  */
00121 static const uint8_t aes_isbox[256] = 
00122 {
00123     0x52,0x09,0x6a,0xd5,0x30,0x36,0xa5,0x38,
00124     0xbf,0x40,0xa3,0x9e,0x81,0xf3,0xd7,0xfb,
00125     0x7c,0xe3,0x39,0x82,0x9b,0x2f,0xff,0x87,
00126     0x34,0x8e,0x43,0x44,0xc4,0xde,0xe9,0xcb,
00127     0x54,0x7b,0x94,0x32,0xa6,0xc2,0x23,0x3d,
00128     0xee,0x4c,0x95,0x0b,0x42,0xfa,0xc3,0x4e,
00129     0x08,0x2e,0xa1,0x66,0x28,0xd9,0x24,0xb2,
00130     0x76,0x5b,0xa2,0x49,0x6d,0x8b,0xd1,0x25,
00131     0x72,0xf8,0xf6,0x64,0x86,0x68,0x98,0x16,
00132     0xd4,0xa4,0x5c,0xcc,0x5d,0x65,0xb6,0x92,
00133     0x6c,0x70,0x48,0x50,0xfd,0xed,0xb9,0xda,
00134     0x5e,0x15,0x46,0x57,0xa7,0x8d,0x9d,0x84,
00135     0x90,0xd8,0xab,0x00,0x8c,0xbc,0xd3,0x0a,
00136     0xf7,0xe4,0x58,0x05,0xb8,0xb3,0x45,0x06,
00137     0xd0,0x2c,0x1e,0x8f,0xca,0x3f,0x0f,0x02,
00138     0xc1,0xaf,0xbd,0x03,0x01,0x13,0x8a,0x6b,
00139     0x3a,0x91,0x11,0x41,0x4f,0x67,0xdc,0xea,
00140     0x97,0xf2,0xcf,0xce,0xf0,0xb4,0xe6,0x73,
00141     0x96,0xac,0x74,0x22,0xe7,0xad,0x35,0x85,
00142     0xe2,0xf9,0x37,0xe8,0x1c,0x75,0xdf,0x6e,
00143     0x47,0xf1,0x1a,0x71,0x1d,0x29,0xc5,0x89,
00144     0x6f,0xb7,0x62,0x0e,0xaa,0x18,0xbe,0x1b,
00145     0xfc,0x56,0x3e,0x4b,0xc6,0xd2,0x79,0x20,
00146     0x9a,0xdb,0xc0,0xfe,0x78,0xcd,0x5a,0xf4,
00147     0x1f,0xdd,0xa8,0x33,0x88,0x07,0xc7,0x31,
00148     0xb1,0x12,0x10,0x59,0x27,0x80,0xec,0x5f,
00149     0x60,0x51,0x7f,0xa9,0x19,0xb5,0x4a,0x0d,
00150     0x2d,0xe5,0x7a,0x9f,0x93,0xc9,0x9c,0xef,
00151     0xa0,0xe0,0x3b,0x4d,0xae,0x2a,0xf5,0xb0,
00152     0xc8,0xeb,0xbb,0x3c,0x83,0x53,0x99,0x61,
00153     0x17,0x2b,0x04,0x7e,0xba,0x77,0xd6,0x26,
00154     0xe1,0x69,0x14,0x63,0x55,0x21,0x0c,0x7d
00155 };
00156 
00157 static const unsigned char Rcon[30]=
00158 {
00159     0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,
00160     0x1b,0x36,0x6c,0xd8,0xab,0x4d,0x9a,0x2f,
00161     0x5e,0xbc,0x63,0xc6,0x97,0x35,0x6a,0xd4,
00162     0xb3,0x7d,0xfa,0xef,0xc5,0x91,
00163 };
00164 
00165 /* ----- static functions ----- */
00166 static void AES_encrypt(const AES_CTX *ctx, uint32_t *data);
00167 static void AES_decrypt(const AES_CTX *ctx, uint32_t *data);
00168 
00169 /* Perform doubling in Galois Field GF(2^8) using the irreducible polynomial
00170    x^8+x^4+x^3+x+1 */
00171 static unsigned char AES_xtime(uint32_t x)
00172 {
00173     return (x&0x80) ? (x<<1)^0x1b : x<<1;
00174 }
00175 
00176 /**
00177  * Set up AES with the key/iv and cipher size.
00178  */
00179 void AES_set_key(AES_CTX *ctx, const uint8_t *key, 
00180         const uint8_t *iv, AES_MODE mode)
00181 {
00182     int i, ii;
00183     uint32_t *W, tmp, tmp2;
00184     const unsigned char *ip;
00185     int words;
00186 
00187     switch (mode)
00188     {
00189         case AES_MODE_128:
00190             i = 10;
00191             words = 4;
00192             break;
00193 
00194         case AES_MODE_256:
00195             i = 14;
00196             words = 8;
00197             break;
00198 
00199         default:        /* fail silently */
00200             return;
00201     }
00202 
00203     ctx->rounds = i;
00204     ctx->key_size = words;
00205     W = ctx->ks;
00206     for (i = 0; i < words; i+=2)
00207     {
00208         W[i+0]=    ((uint32_t)key[ 0]<<24)|
00209             ((uint32_t)key[ 1]<<16)|
00210             ((uint32_t)key[ 2]<< 8)|
00211             ((uint32_t)key[ 3]    );
00212         W[i+1]=    ((uint32_t)key[ 4]<<24)|
00213             ((uint32_t)key[ 5]<<16)|
00214             ((uint32_t)key[ 6]<< 8)|
00215             ((uint32_t)key[ 7]    );
00216         key += 8;
00217     }
00218 
00219     ip = Rcon;
00220     ii = 4 * (ctx->rounds+1);
00221     for (i = words; i<ii; i++)
00222     {
00223         tmp = W[i-1];
00224 
00225         if ((i % words) == 0)
00226         {
00227             tmp2 =(uint32_t)aes_sbox[(tmp    )&0xff]<< 8;
00228             tmp2|=(uint32_t)aes_sbox[(tmp>> 8)&0xff]<<16;
00229             tmp2|=(uint32_t)aes_sbox[(tmp>>16)&0xff]<<24;
00230             tmp2|=(uint32_t)aes_sbox[(tmp>>24)     ];
00231             tmp=tmp2^(((unsigned int)*ip)<<24);
00232             ip++;
00233         }
00234 
00235         if ((words == 8) && ((i % words) == 4))
00236         {
00237             tmp2 =(uint32_t)aes_sbox[(tmp    )&0xff]    ;
00238             tmp2|=(uint32_t)aes_sbox[(tmp>> 8)&0xff]<< 8;
00239             tmp2|=(uint32_t)aes_sbox[(tmp>>16)&0xff]<<16;
00240             tmp2|=(uint32_t)aes_sbox[(tmp>>24)     ]<<24;
00241             tmp=tmp2;
00242         }
00243 
00244         W[i]=W[i-words]^tmp;
00245     }
00246 
00247     /* copy the iv across */
00248     memcpy(ctx->iv, iv, 16);
00249 }
00250 
00251 /**
00252  * Change a key for decryption.
00253  */
00254 void AES_convert_key(AES_CTX *ctx)
00255 {
00256     int i;
00257     uint32_t *k,w,t1,t2,t3,t4;
00258 
00259     k = ctx->ks;
00260     k += 4;
00261 
00262     for (i= ctx->rounds*4; i > 4; i--)
00263     {
00264         w= *k;
00265         w = inv_mix_col(w,t1,t2,t3,t4);
00266         *k++ =w;
00267     }
00268 }
00269 
00270 /**
00271  * Encrypt a byte sequence (with a block size 16) using the AES cipher.
00272  */
00273 void AES_cbc_encrypt(AES_CTX *ctx, const uint8_t *msg, uint8_t *out, int length)
00274 {
00275     int i;
00276     uint32_t tin[4], tout[4], iv[4];
00277 
00278     memcpy(iv, ctx->iv, AES_IV_SIZE);
00279     for (i = 0; i < 4; i++)
00280         tout[i] = ntohl(iv[i]);
00281 
00282     for (length -= AES_BLOCKSIZE; length >= 0; length -= AES_BLOCKSIZE)
00283     {
00284         uint32_t msg_32[4];
00285         uint32_t out_32[4];
00286         memcpy(msg_32, msg, AES_BLOCKSIZE);
00287         msg += AES_BLOCKSIZE;
00288 
00289         for (i = 0; i < 4; i++)
00290             tin[i] = ntohl(msg_32[i])^tout[i];
00291 
00292         AES_encrypt(ctx, tin);
00293 
00294         for (i = 0; i < 4; i++)
00295         {
00296             tout[i] = tin[i]; 
00297             out_32[i] = htonl(tout[i]);
00298         }
00299 
00300         memcpy(out, out_32, AES_BLOCKSIZE);
00301         out += AES_BLOCKSIZE;
00302     }
00303 
00304     for (i = 0; i < 4; i++)
00305         iv[i] = htonl(tout[i]);
00306     memcpy(ctx->iv, iv, AES_IV_SIZE);
00307 }
00308 
00309 /**
00310  * Decrypt a byte sequence (with a block size 16) using the AES cipher.
00311  */
00312 void AES_cbc_decrypt(AES_CTX *ctx, const uint8_t *msg, uint8_t *out, int length)
00313 {
00314     int i;
00315     uint32_t tin[4], xor[4], tout[4], data[4], iv[4];
00316 
00317     memcpy(iv, ctx->iv, AES_IV_SIZE);
00318     for (i = 0; i < 4; i++)
00319         xor[i] = ntohl(iv[i]);
00320     for (length -= 16; length >= 0; length -= 16)
00321     {
00322         uint32_t msg_32[4];
00323         uint32_t out_32[4];
00324         memcpy(msg_32, msg, AES_BLOCKSIZE);
00325         msg += AES_BLOCKSIZE;
00326 
00327         for (i = 0; i < 4; i++)
00328         {
00329             tin[i] = ntohl(msg_32[i]);
00330             data[i] = tin[i];
00331         }
00332 
00333         AES_decrypt(ctx, data);
00334 
00335         for (i = 0; i < 4; i++)
00336         {
00337             tout[i] = data[i]^xor[i];
00338             xor[i] = tin[i];
00339             out_32[i] = htonl(tout[i]);
00340         }
00341 
00342         memcpy(out, out_32, AES_BLOCKSIZE);
00343         out += AES_BLOCKSIZE;
00344 
00345     }
00346 
00347     for (i = 0; i < 4; i++)
00348         iv[i] = htonl(xor[i]);
00349     memcpy(ctx->iv, iv, AES_IV_SIZE);
00350 
00351 }
00352 
00353 /**
00354  * Encrypt a single block (16 bytes) of data
00355  */
00356 static void AES_encrypt(const AES_CTX *ctx, uint32_t *data)
00357 {
00358     /* To make this code smaller, generate the sbox entries on the fly.
00359      * This will have a really heavy effect upon performance.
00360      */
00361     uint32_t tmp[4];
00362     uint32_t tmp1, old_a0, a0, a1, a2, a3, row;
00363     int curr_rnd;
00364     int rounds = ctx->rounds; 
00365     const uint32_t *k = ctx->ks;
00366 
00367     /* Pre-round key addition */
00368     for (row = 0; row < 4; row++)
00369         data[row] ^= *(k++);
00370 
00371     /* Encrypt one block. */
00372     for (curr_rnd = 0; curr_rnd < rounds; curr_rnd++)
00373     {
00374         /* Perform ByteSub and ShiftRow operations together */
00375         for (row = 0; row < 4; row++)
00376         {
00377             a0 = (uint32_t)aes_sbox[(data[row%4]>>24)&0xFF];
00378             a1 = (uint32_t)aes_sbox[(data[(row+1)%4]>>16)&0xFF];
00379             a2 = (uint32_t)aes_sbox[(data[(row+2)%4]>>8)&0xFF]; 
00380             a3 = (uint32_t)aes_sbox[(data[(row+3)%4])&0xFF];
00381 
00382             /* Perform MixColumn iff not last round */
00383             if (curr_rnd < (rounds - 1))
00384             {
00385                 tmp1 = a0 ^ a1 ^ a2 ^ a3;
00386                 old_a0 = a0;
00387                 a0 ^= tmp1 ^ AES_xtime(a0 ^ a1);
00388                 a1 ^= tmp1 ^ AES_xtime(a1 ^ a2);
00389                 a2 ^= tmp1 ^ AES_xtime(a2 ^ a3);
00390                 a3 ^= tmp1 ^ AES_xtime(a3 ^ old_a0);
00391             }
00392 
00393             tmp[row] = ((a0 << 24) | (a1 << 16) | (a2 << 8) | a3);
00394         }
00395 
00396         /* KeyAddition - note that it is vital that this loop is separate from
00397            the MixColumn operation, which must be atomic...*/ 
00398         for (row = 0; row < 4; row++)
00399             data[row] = tmp[row] ^ *(k++);
00400     }
00401 }
00402 
00403 /**
00404  * Decrypt a single block (16 bytes) of data
00405  */
00406 static void AES_decrypt(const AES_CTX *ctx, uint32_t *data)
00407 { 
00408     uint32_t tmp[4];
00409     uint32_t xt0,xt1,xt2,xt3,xt4,xt5,xt6;
00410     uint32_t a0, a1, a2, a3, row;
00411     int curr_rnd;
00412     int rounds = ctx->rounds;
00413     const uint32_t *k = ctx->ks + ((rounds+1)*4);
00414     /* pre-round key addition */
00415     for (row=4; row > 0;row--)
00416         data[row-1] ^= *(--k);
00417 
00418     /* Decrypt one block */
00419     for (curr_rnd = 0; curr_rnd < rounds; curr_rnd++)
00420     {
00421 
00422         /* Perform ByteSub and ShiftRow operations together */
00423         for (row = 4; row > 0; row--)
00424         {
00425 
00426             a0 = aes_isbox[(data[(row+3)%4]>>24)&0xFF];
00427             a1 = aes_isbox[(data[(row+2)%4]>>16)&0xFF];
00428             a2 = aes_isbox[(data[(row+1)%4]>>8)&0xFF];
00429             a3 = aes_isbox[(data[row%4])&0xFF];
00430 
00431             /* Perform MixColumn iff not last round */
00432             if (curr_rnd<(rounds-1))
00433             {
00434                 /* The MDS cofefficients (0x09, 0x0B, 0x0D, 0x0E)
00435                    are quite large compared to encryption; this 
00436                    operation slows decryption down noticeably. */
00437                 xt0 = AES_xtime(a0^a1);
00438                 xt1 = AES_xtime(a1^a2);
00439                 xt2 = AES_xtime(a2^a3);
00440                 xt3 = AES_xtime(a3^a0);
00441                 xt4 = AES_xtime(xt0^xt1);
00442                 xt5 = AES_xtime(xt1^xt2);
00443                 xt6 = AES_xtime(xt4^xt5);
00444 
00445                 xt0 ^= a1^a2^a3^xt4^xt6;
00446                 xt1 ^= a0^a2^a3^xt5^xt6;
00447                 xt2 ^= a0^a1^a3^xt4^xt6;
00448                 xt3 ^= a0^a1^a2^xt5^xt6;
00449                 tmp[row-1] = ((xt0<<24)|(xt1<<16)|(xt2<<8)|xt3);
00450             }
00451             else
00452                 tmp[row-1] = ((a0<<24)|(a1<<16)|(a2<<8)|a3);
00453         }
00454 
00455         for (row = 4; row > 0; row--)
00456             data[row-1] = tmp[row-1] ^ *(--k);
00457     }
00458 }
00459 
00460 #endif