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 
00321     for (length -= 16; length >= 0; length -= 16)
00322     {
00323         uint32_t msg_32[4];
00324         uint32_t out_32[4];
00325         memcpy(msg_32, msg, AES_BLOCKSIZE);
00326         msg += AES_BLOCKSIZE;
00327 
00328         for (i = 0; i < 4; i++)
00329         {
00330             tin[i] = ntohl(msg_32[i]);
00331             data[i] = tin[i];
00332         }
00333 
00334         AES_decrypt(ctx, data);
00335 
00336         for (i = 0; i < 4; i++)
00337         {
00338             tout[i] = data[i]^xor[i];
00339             xor[i] = tin[i];
00340             out_32[i] = htonl(tout[i]);
00341         }
00342 
00343         memcpy(out, out_32, AES_BLOCKSIZE);
00344         out += AES_BLOCKSIZE;
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  * Encrypt a single block (16 bytes) of data
00354  */
00355 static void AES_encrypt(const AES_CTX *ctx, uint32_t *data)
00356 {
00357     /* To make this code smaller, generate the sbox entries on the fly.
00358      * This will have a really heavy effect upon performance.
00359      */
00360     uint32_t tmp[4];
00361     uint32_t tmp1, old_a0, a0, a1, a2, a3, row;
00362     int curr_rnd;
00363     int rounds = ctx->rounds; 
00364     const uint32_t *k = ctx->ks;
00365 
00366     /* Pre-round key addition */
00367     for (row = 0; row < 4; row++)
00368         data[row] ^= *(k++);
00369 
00370     /* Encrypt one block. */
00371     for (curr_rnd = 0; curr_rnd < rounds; curr_rnd++)
00372     {
00373         /* Perform ByteSub and ShiftRow operations together */
00374         for (row = 0; row < 4; row++)
00375         {
00376             a0 = (uint32_t)aes_sbox[(data[row%4]>>24)&0xFF];
00377             a1 = (uint32_t)aes_sbox[(data[(row+1)%4]>>16)&0xFF];
00378             a2 = (uint32_t)aes_sbox[(data[(row+2)%4]>>8)&0xFF]; 
00379             a3 = (uint32_t)aes_sbox[(data[(row+3)%4])&0xFF];
00380 
00381             /* Perform MixColumn iff not last round */
00382             if (curr_rnd < (rounds - 1))
00383             {
00384                 tmp1 = a0 ^ a1 ^ a2 ^ a3;
00385                 old_a0 = a0;
00386                 a0 ^= tmp1 ^ AES_xtime(a0 ^ a1);
00387                 a1 ^= tmp1 ^ AES_xtime(a1 ^ a2);
00388                 a2 ^= tmp1 ^ AES_xtime(a2 ^ a3);
00389                 a3 ^= tmp1 ^ AES_xtime(a3 ^ old_a0);
00390             }
00391 
00392             tmp[row] = ((a0 << 24) | (a1 << 16) | (a2 << 8) | a3);
00393         }
00394 
00395         /* KeyAddition - note that it is vital that this loop is separate from
00396            the MixColumn operation, which must be atomic...*/ 
00397         for (row = 0; row < 4; row++)
00398             data[row] = tmp[row] ^ *(k++);
00399     }
00400 }
00401 
00402 /**
00403  * Decrypt a single block (16 bytes) of data
00404  */
00405 static void AES_decrypt(const AES_CTX *ctx, uint32_t *data)
00406 { 
00407     uint32_t tmp[4];
00408     uint32_t xt0,xt1,xt2,xt3,xt4,xt5,xt6;
00409     uint32_t a0, a1, a2, a3, row;
00410     int curr_rnd;
00411     int rounds = ctx->rounds;
00412     const uint32_t *k = ctx->ks + ((rounds+1)*4);
00413 
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         /* Perform ByteSub and ShiftRow operations together */
00422         for (row = 4; row > 0; row--)
00423         {
00424             a0 = aes_isbox[(data[(row+3)%4]>>24)&0xFF];
00425             a1 = aes_isbox[(data[(row+2)%4]>>16)&0xFF];
00426             a2 = aes_isbox[(data[(row+1)%4]>>8)&0xFF];
00427             a3 = aes_isbox[(data[row%4])&0xFF];
00428 
00429             /* Perform MixColumn iff not last round */
00430             if (curr_rnd<(rounds-1))
00431             {
00432                 /* The MDS cofefficients (0x09, 0x0B, 0x0D, 0x0E)
00433                    are quite large compared to encryption; this 
00434                    operation slows decryption down noticeably. */
00435                 xt0 = AES_xtime(a0^a1);
00436                 xt1 = AES_xtime(a1^a2);
00437                 xt2 = AES_xtime(a2^a3);
00438                 xt3 = AES_xtime(a3^a0);
00439                 xt4 = AES_xtime(xt0^xt1);
00440                 xt5 = AES_xtime(xt1^xt2);
00441                 xt6 = AES_xtime(xt4^xt5);
00442 
00443                 xt0 ^= a1^a2^a3^xt4^xt6;
00444                 xt1 ^= a0^a2^a3^xt5^xt6;
00445                 xt2 ^= a0^a1^a3^xt4^xt6;
00446                 xt3 ^= a0^a1^a2^xt5^xt6;
00447                 tmp[row-1] = ((xt0<<24)|(xt1<<16)|(xt2<<8)|xt3);
00448             }
00449             else
00450                 tmp[row-1] = ((a0<<24)|(a1<<16)|(a2<<8)|a3);
00451         }
00452 
00453         for (row = 4; row > 0; row--)
00454             data[row-1] = tmp[row-1] ^ *(--k);
00455     }
00456 }
00457 
00458 #endif