allow various ways of building AES

4 files changed, 309 insertions, 50 deletions

diff --git a/security/nss/lib/freebl/manifest.mn b/security/nss/lib/freebl/manifest.mn
index 53f5a883b..9a4830fcc 100644
--- a/security/nss/lib/freebl/manifest.mn
+++ b/security/nss/lib/freebl/manifest.mn
@@ -107,3 +107,20 @@ ALL_HDRS =  \
 	vis_proto.h \
 	$(NULL)
 
+ifdef AES_GEN_TBL
+DEFINES += -DRIJNDAEL_GENERATE_TABLES
+else 
+ifdef AES_GEN_TBL_M
+DEFINES += -DRIJNDAEL_GENERATE_TABLES_MACRO
+else
+ifdef AES_GEN_VAL
+DEFINES += -DRIJNDAEL_GENERATE_VALUES
+else
+ifdef AES_GEN_VAL_M
+DEFINES += -DRIJNDAEL_GENERATE_VALUES_MACRO
+else
+DEFINES += -DRIJNDAEL_INCLUDE_TABLES
+endif
+endif
+endif
+endif
diff --git a/security/nss/lib/freebl/rijndael.c b/security/nss/lib/freebl/rijndael.c
index 928c9d200..74be08507 100644
--- a/security/nss/lib/freebl/rijndael.c
+++ b/security/nss/lib/freebl/rijndael.c
@@ -33,6 +33,7 @@
  * $Id$
  */
 
+#include "prinit.h"
 #include "prerr.h"
 #include "secerr.h"
 
@@ -40,20 +41,34 @@
 #include "blapi.h"
 #include "rijndael.h"
 
-#ifndef RIJNDAEL_NO_TABLES
-/* includes S**-1, Rcon, T0, T1, T2, T3, T0**-1, T1**-1, T2**-1, T3**-1 */
-#include "rijndael32.tab"
-#endif
+/*
+ * There are currently five ways to build this code, varying in performance
+ * and code size.
+ *
+ * RIJNDAEL_INCLUDE_TABLES         Include all tables from rijndael32.tab
+ * RIJNDAEL_GENERATE_TABLES        Generate tables on first 
+ *                                 encryption/decryption, then store them;
+ *                                 use the function gfm
+ * RIJNDAEL_GENERATE_TABLES_MACRO  Same as above, but use macros to do
+ *                                 the generation
+ * RIJNDAEL_GENERATE_VALUES        Do not store tables, generate the table
+ *                                 values "on-the-fly", using gfm
+ * RIJNDAEL_GENERATE_VALUES_MACRO  Same as above, but use macros
+ *
+ * The default is RIJNDAEL_INCLUDE_TABLES.
+ */
 
-#ifdef IS_LITTLE_ENDIAN
-#define SBOX(b)    ((PRUint8)_T3[b])
-#else
-#define SBOX(b)    ((PRUint8)_T1[b])
-#endif
-#define SBOXINV(b) (_SInv[b])
+/*
+ * When building RIJNDAEL_INCLUDE_TABLES, includes S**-1, Rcon, T[0..4], 
+ *                                                 T**-1[0..4], IMXC[0..4]
+ * When building anything else, includes S, S**-1, Rcon
+ */
+#include "rijndael32.tab"
 
-#ifndef RIJNDAEL_NO_TABLES
-/* index the tables directly */
+#if defined(RIJNDAEL_INCLUDE_TABLES)
+/*
+ * RIJNDAEL_INCLUDE_TABLES
+ */
 #define T0(i)    _T0[i]
 #define T1(i)    _T1[i]
 #define T2(i)    _T2[i]
@@ -62,19 +77,24 @@
 #define TInv1(i) _TInv1[i]
 #define TInv2(i) _TInv2[i]
 #define TInv3(i) _TInv3[i]
-#define ME(i)    _ME[i]
-#define M9(i)    _M9[i]
-#define MB(i)    _MB[i]
-#define MD(i)    _MD[i]
 #define IMXC0(b) _IMXC0[b]
 #define IMXC1(b) _IMXC1[b]
 #define IMXC2(b) _IMXC2[b]
 #define IMXC3(b) _IMXC3[b]
+/* The S-box can be recovered from the T-tables */
+#ifdef IS_LITTLE_ENDIAN
+#define SBOX(b)    ((PRUint8)_T3[b])
 #else
-/* generate the tables on the fly */
-/* XXX not finished, just here for fun */
-#define XTIME(a) \
-    ((a & 0x80) ? ((a << 1) ^ 0x1b) : (a << 1))
+#define SBOX(b)    ((PRUint8)_T1[b])
+#endif
+#define SINV(b) (_SInv[b])
+
+#else /* not RIJNDAEL_INCLUDE_TABLES */
+
+/*
+ * Code for generating T-table values.
+ */
+
 #ifdef IS_LITTLE_ENDIAN
 #define WORD4(b0, b1, b2, b3) \
     (((b3) << 24) | ((b2) << 16) | ((b1) << 8) | (b0))
@@ -82,15 +102,192 @@
 #define WORD4(b0, b1, b2, b3) \
     (((b0) << 24) | ((b1) << 16) | ((b2) << 8) | (b3))
 #endif
-#define T0(i) \
-    (WORD4( XTIME(SBOX(i)), SBOX(i), SBOX(i), XTIME(SBOX(i)) ^ SBOX(i) ))
-#define T1(i) \
-    (WORD4( XTIME(SBOX(i)) ^ SBOX(i), XTIME(SBOX(i)), SBOX(i), SBOX(i) ))
-#define T2(i) \
-    (WORD4( SBOX(i), XTIME(SBOX(i)) ^ SBOX(i), XTIME(SBOX(i)), SBOX(i) ))
-#define T3(i) \
-    (WORD4( SBOX(i), SBOX(i), XTIME(SBOX(i)) ^ SBOX(i), XTIME(SBOX(i)) ))
-#endif
+
+/*
+ * Define the S and S**-1 tables (both have been stored)
+ */
+#define SBOX(b)    (_S[b])
+#define SINV(b) (_SInv[b])
+
+/*
+ * The function xtime, used for Galois field multiplication
+ */
+#define XTIME(a) \
+    ((a & 0x80) ? ((a << 1) ^ 0x1b) : (a << 1))
+
+/* Choose GFM method (macros or function) */
+#if defined(RIJNDAEL_GENERATE_TABLES_MACRO) ||  \
+    defined(RIJNDAEL_GENERATE_VALUES_MACRO)
+
+/*
+ * Galois field GF(2**8) multipliers, in macro form
+ */
+#define GFM01(a) \
+    (a)                                 /* a * 01 = a, the identity */
+#define GFM02(a) \
+    (XTIME(a) & 0xff)                   /* a * 02 = xtime(a) */
+#define GFM04(a) \
+    (GFM02(GFM02(a)))                   /* a * 04 = xtime**2(a) */
+#define GFM08(a) \
+    (GFM02(GFM04(a)))                   /* a * 08 = xtime**3(a) */
+#define GFM03(a) \
+    (GFM01(a) ^ GFM02(a))               /* a * 03 = a * (01 + 02) */
+#define GFM09(a) \
+    (GFM01(a) ^ GFM08(a))               /* a * 09 = a * (01 + 08) */
+#define GFM0B(a) \
+    (GFM01(a) ^ GFM02(a) ^ GFM08(a))    /* a * 0B = a * (01 + 02 + 08) */
+#define GFM0D(a) \
+    (GFM01(a) ^ GFM04(a) ^ GFM08(a))    /* a * 0D = a * (01 + 04 + 08) */
+#define GFM0E(a) \
+    (GFM02(a) ^ GFM04(a) ^ GFM08(a))    /* a * 0E = a * (02 + 04 + 08) */
+
+#else  /* RIJNDAEL_GENERATE_TABLES or RIJNDAEL_GENERATE_VALUES */
+
+/* GF_MULTIPLY
+ *
+ * multiply two bytes represented in GF(2**8), mod (x**4 + 1)
+ */
+PRUint8 gfm(PRUint8 a, PRUint8 b)
+{
+    PRUint8 res = 0;
+    while (b > 0) {
+	res = (b & 0x01) ? res ^ a : res;
+	a = XTIME(a);
+	b >>= 1;
+    }
+    return res;
+}
+
+#define GFM01(a) \
+    (a)                                 /* a * 01 = a, the identity */
+#define GFM02(a) \
+    (XTIME(a) & 0xff)                   /* a * 02 = xtime(a) */
+#define GFM03(a) \
+    (gfm(a, 0x03))                      /* a * 03 */
+#define GFM09(a) \
+    (gfm(a, 0x09))                      /* a * 09 */
+#define GFM0B(a) \
+    (gfm(a, 0x0B))                      /* a * 0B */
+#define GFM0D(a) \
+    (gfm(a, 0x0D))                      /* a * 0D */
+#define GFM0E(a) \
+    (gfm(a, 0x0E))                      /* a * 0E */
+
+#endif /* choosing GFM function */
+
+/*
+ * The T-tables
+ */
+#define G_T0(i) \
+    ( WORD4( GFM02(SBOX(i)), GFM01(SBOX(i)), GFM01(SBOX(i)), GFM03(SBOX(i)) ) )
+#define G_T1(i) \
+    ( WORD4( GFM03(SBOX(i)), GFM02(SBOX(i)), GFM01(SBOX(i)), GFM01(SBOX(i)) ) )
+#define G_T2(i) \
+    ( WORD4( GFM01(SBOX(i)), GFM03(SBOX(i)), GFM02(SBOX(i)), GFM01(SBOX(i)) ) )
+#define G_T3(i) \
+    ( WORD4( GFM01(SBOX(i)), GFM01(SBOX(i)), GFM03(SBOX(i)), GFM02(SBOX(i)) ) )
+
+/*
+ * The inverse T-tables
+ */
+#define G_TInv0(i) \
+    ( WORD4( GFM0E(SINV(i)), GFM09(SINV(i)), GFM0D(SINV(i)), GFM0B(SINV(i)) ) )
+#define G_TInv1(i) \
+    ( WORD4( GFM0B(SINV(i)), GFM0E(SINV(i)), GFM09(SINV(i)), GFM0D(SINV(i)) ) )
+#define G_TInv2(i) \
+    ( WORD4( GFM0D(SINV(i)), GFM0B(SINV(i)), GFM0E(SINV(i)), GFM09(SINV(i)) ) )
+#define G_TInv3(i) \
+    ( WORD4( GFM09(SINV(i)), GFM0D(SINV(i)), GFM0B(SINV(i)), GFM0E(SINV(i)) ) )
+
+/*
+ * The inverse mix column tables
+ */
+#define G_IMXC0(i) \
+    ( WORD4( GFM0E(i), GFM09(i), GFM0D(i), GFM0B(i) ) )
+#define G_IMXC1(i) \
+    ( WORD4( GFM0B(i), GFM0E(i), GFM09(i), GFM0D(i) ) )
+#define G_IMXC2(i) \
+    ( WORD4( GFM0D(i), GFM0B(i), GFM0E(i), GFM09(i) ) )
+#define G_IMXC3(i) \
+    ( WORD4( GFM09(i), GFM0D(i), GFM0B(i), GFM0E(i) ) )
+
+/* Now choose the T-table indexing method */
+#if defined(RIJNDAEL_GENERATE_VALUES) ||  \
+    defined(RIJNDAEL_GENERATE_VALUES_MACRO)
+/* generate values for the tables */
+#define T0(i)    G_T0(i)
+#define T1(i)    G_T1(i)
+#define T2(i)    G_T2(i)
+#define T3(i)    G_T3(i)
+#define TInv0(i) G_TInv0(i)
+#define TInv1(i) G_TInv1(i)
+#define TInv2(i) G_TInv2(i)
+#define TInv3(i) G_TInv3(i)
+#define IMXC0(b) G_IMXC0(b)
+#define IMXC1(b) G_IMXC1(b)
+#define IMXC2(b) G_IMXC2(b)
+#define IMXC3(b) G_IMXC3(b)
+#else  /* RIJNDAEL_GENERATE_TABLES or RIJNDAEL_GENERATE_TABLES_MACRO */
+/* Generate T and T**-1 table values and store, then index */
+/* The inverse mix column tables are still generated */
+#define T0(i)    rijndaelTables->T0[i]
+#define T1(i)    rijndaelTables->T1[i]
+#define T2(i)    rijndaelTables->T2[i]
+#define T3(i)    rijndaelTables->T3[i]
+#define TInv0(i) rijndaelTables->TInv0[i]
+#define TInv1(i) rijndaelTables->TInv1[i]
+#define TInv2(i) rijndaelTables->TInv2[i]
+#define TInv3(i) rijndaelTables->TInv3[i]
+#define IMXC0(b) G_IMXC0(b)
+#define IMXC1(b) G_IMXC1(b)
+#define IMXC2(b) G_IMXC2(b)
+#define IMXC3(b) G_IMXC3(b)
+#endif /* choose T-table indexing method */
+
+#endif /* not RIJNDAEL_INCLUDE_TABLES */
+
+#if defined(RIJNDAEL_GENERATE_TABLES) ||  \
+    defined(RIJNDAEL_GENERATE_TABLES_MACRO)
+
+/* Code to generate and store the tables */
+
+struct rijndael_tables_str {
+    PRUint32 T0[256];
+    PRUint32 T1[256];
+    PRUint32 T2[256];
+    PRUint32 T3[256];
+    PRUint32 TInv0[256];
+    PRUint32 TInv1[256];
+    PRUint32 TInv2[256];
+    PRUint32 TInv3[256];
+};
+
+static struct rijndael_tables_str *rijndaelTables = NULL;
+static PRCallOnceType coRTInit = { 0, 0, 0 };
+static PRStatus 
+init_rijndael_tables(void)
+{
+    PRUint32 i;
+    struct rijndael_tables_str *rts;
+    rts = (struct rijndael_tables_str *)
+                   PORT_Alloc(sizeof(struct rijndael_tables_str));
+    if (!rts) return PR_FAILURE;
+    for (i=0; i<256; i++) {
+	rts->T0[i] = G_T0(i);
+	rts->T1[i] = G_T1(i);
+	rts->T2[i] = G_T2(i);
+	rts->T3[i] = G_T3(i);
+	rts->TInv0[i] = G_TInv0(i);
+	rts->TInv1[i] = G_TInv1(i);
+	rts->TInv2[i] = G_TInv2(i);
+	rts->TInv3[i] = G_TInv3(i);
+    }
+    /* wait until all the values are in to set */
+    rijndaelTables = rts;
+    return PR_SUCCESS;
+}
+
+#endif /* code to generate tables */
 
 /**************************************************************************
  *
@@ -444,22 +641,22 @@ rijndael_decryptBlock128(AESContext *cx,
 	COLUMN_0(clone) = COLUMN_0(pOut) ^ *roundkeyw--;
     }
     /* inverse sub */
-    pOut[ 0] = SBOXINV(clone[ 0]);
-    pOut[ 1] = SBOXINV(clone[13]);
-    pOut[ 2] = SBOXINV(clone[10]);
-    pOut[ 3] = SBOXINV(clone[ 7]);
-    pOut[ 4] = SBOXINV(clone[ 4]);
-    pOut[ 5] = SBOXINV(clone[ 1]);
-    pOut[ 6] = SBOXINV(clone[14]);
-    pOut[ 7] = SBOXINV(clone[11]);
-    pOut[ 8] = SBOXINV(clone[ 8]);
-    pOut[ 9] = SBOXINV(clone[ 5]);
-    pOut[10] = SBOXINV(clone[ 2]);
-    pOut[11] = SBOXINV(clone[15]);
-    pOut[12] = SBOXINV(clone[12]);
-    pOut[13] = SBOXINV(clone[ 9]);
-    pOut[14] = SBOXINV(clone[ 6]);
-    pOut[15] = SBOXINV(clone[ 3]);
+    pOut[ 0] = SINV(clone[ 0]);
+    pOut[ 1] = SINV(clone[13]);
+    pOut[ 2] = SINV(clone[10]);
+    pOut[ 3] = SINV(clone[ 7]);
+    pOut[ 4] = SINV(clone[ 4]);
+    pOut[ 5] = SINV(clone[ 1]);
+    pOut[ 6] = SINV(clone[14]);
+    pOut[ 7] = SINV(clone[11]);
+    pOut[ 8] = SINV(clone[ 8]);
+    pOut[ 9] = SINV(clone[ 5]);
+    pOut[10] = SINV(clone[ 2]);
+    pOut[11] = SINV(clone[15]);
+    pOut[12] = SINV(clone[12]);
+    pOut[13] = SINV(clone[ 9]);
+    pOut[14] = SINV(clone[ 6]);
+    pOut[15] = SINV(clone[ 3]);
     /* final key addition */
     COLUMN_3(pOut) ^= *roundkeyw--;
     COLUMN_2(pOut) ^= *roundkeyw--;
@@ -564,7 +761,7 @@ rijndael_decryptBlock(AESContext *cx,
     }
     /* inverse sub */
     for (j=0; j<4*Nb; ++j) {
-	output[j] = SBOXINV(clone[j]);
+	output[j] = SINV(clone[j]);
     }
     /* final key addition */
     for (j=4*Nb; j>=0; j-=4) {
@@ -826,6 +1023,15 @@ AES_Encrypt(AESContext *cx, unsigned char *output,
 	return SECFailure;
     }
     *outputLen = inputLen;
+#if defined(RIJNDAEL_GENERATE_TABLES) ||  \
+    defined(RIJNDAEL_GENERATE_TABLES_MACRO)
+    if (rijndaelTables == NULL) {
+	if (PR_CallOnce(&coRTInit, init_rijndael_tables) 
+	      != PR_SUCCESS) {
+	    return PR_FAILURE;
+	}
+    }
+#endif
     return (*cx->worker)(cx, output, outputLen, maxOutputLen,	
                              input, inputLen, blocksize);
 }
@@ -857,6 +1063,16 @@ AES_Decrypt(AESContext *cx, unsigned char *output,
 	return SECFailure;
     }
     *outputLen = inputLen;
+#if defined(RIJNDAEL_GENERATE_TABLES) ||  \
+    defined(RIJNDAEL_GENERATE_TABLES_MACRO)
+    if (rijndaelTables == NULL) {
+	if (PR_CallOnce(&coRTInit, init_rijndael_tables) 
+	      != PR_SUCCESS) {
+	    return PR_FAILURE;
+	}
+    }
+#endif
     return (*cx->worker)(cx, output, outputLen, maxOutputLen,	
                              input, inputLen, blocksize);
 }
+
diff --git a/security/nss/lib/freebl/rijndael32.tab b/security/nss/lib/freebl/rijndael32.tab
index 01cf00364..6b78e2e8b 100644
--- a/security/nss/lib/freebl/rijndael32.tab
+++ b/security/nss/lib/freebl/rijndael32.tab
@@ -1,3 +1,25 @@
+#ifndef RIJNDAEL_INCLUDE_TABLES
+static const PRUint8 _S[256] = 
+{
+ 99, 124, 119, 123, 242, 107, 111, 197,  48,   1, 103,  43, 254, 215, 171, 118,
+202, 130, 201, 125, 250,  89,  71, 240, 173, 212, 162, 175, 156, 164, 114, 192,
+183, 253, 147,  38,  54,  63, 247, 204,  52, 165, 229, 241, 113, 216,  49,  21,
+  4, 199,  35, 195,  24, 150,   5, 154,   7,  18, 128, 226, 235,  39, 178, 117,
+  9, 131,  44,  26,  27, 110,  90, 160,  82,  59, 214, 179,  41, 227,  47, 132,
+ 83, 209,   0, 237,  32, 252, 177,  91, 106, 203, 190,  57,  74,  76,  88, 207,
+208, 239, 170, 251,  67,  77,  51, 133,  69, 249,   2, 127,  80,  60, 159, 168,
+ 81, 163,  64, 143, 146, 157,  56, 245, 188, 182, 218,  33,  16, 255, 243, 210,
+205,  12,  19, 236,  95, 151,  68,  23, 196, 167, 126,  61, 100,  93,  25, 115,
+ 96, 129,  79, 220,  34,  42, 144, 136,  70, 238, 184,  20, 222,  94,  11, 219,
+224,  50,  58,  10,  73,   6,  36,  92, 194, 211, 172,  98, 145, 149, 228, 121,
+231, 200,  55, 109, 141, 213,  78, 169, 108,  86, 244, 234, 101, 122, 174,   8,
+186, 120,  37,  46,  28, 166, 180, 198, 232, 221, 116,  31,  75, 189, 139, 138,
+112,  62, 181, 102,  72,   3, 246,  14,  97,  53,  87, 185, 134, 193,  29, 158,
+225, 248, 152,  17, 105, 217, 142, 148, 155,  30, 135, 233, 206,  85,  40, 223,
+140, 161, 137,  13, 191, 230,  66, 104,  65, 153,  45,  15, 176,  84, 187,  22 
+};
+#endif /* not RIJNDAEL_INCLUDE_TABLES */
+
 static const PRUint8 _SInv[256] = 
 {
  82,   9, 106, 213,  48,  54, 165,  56, 191,  64, 163, 158, 129, 243, 215, 251,
@@ -18,6 +40,7 @@ static const PRUint8 _SInv[256] =
  23,  43,   4, 126, 186, 119, 214,  38, 225, 105,  20,  99,  85,  33,  12, 125 
 };
 
+#ifdef RIJNDAEL_INCLUDE_TABLES
 #ifdef IS_LITTLE_ENDIAN
 static const PRUint32 _T0[256] = 
 {
@@ -1170,6 +1193,8 @@ static const PRUint32 _IMXC3[256] =
 };
 #endif
 
+#endif /* RIJNDAEL_INCLUDE_TABLES */
+
 #ifdef IS_LITTLE_ENDIAN
 static const PRUint32 Rcon[30] = {
 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
diff --git a/security/nss/lib/freebl/rijndael_tables.c b/security/nss/lib/freebl/rijndael_tables.c
index 198e0da8c..6f1957468 100644
--- a/security/nss/lib/freebl/rijndael_tables.c
+++ b/security/nss/lib/freebl/rijndael_tables.c
@@ -178,15 +178,14 @@ int main()
     PRUint32 tmp;
     FILE *optfile;
     optfile = fopen("rijndael32.tab", "w");
-    /* No need to output S, it is stored within the T tables */
-    /*
+    /* output S, if there are no T tables */
+    fprintf(optfile, "#ifndef RIJNDAEL_INCLUDE_TABLES\n");
     fprintf(optfile, "static const PRUint8 _S[256] = \n{\n");
     for (i=0; i<256; i++) {
 	fprintf(optfile, "%3d%c%c", __S[i],(i==255)?' ':',', 
 	                            (i%16==15)?'\n':' ');
     }
-    fprintf(optfile, "};\n\n");
-    */
+    fprintf(optfile, "};\n#endif /* not RIJNDAEL_INCLUDE_TABLES */\n\n");
     /* output S**-1 */
     fprintf(optfile, "static const PRUint8 _SInv[256] = \n{\n");
     for (i=0; i<256; i++) {
@@ -194,6 +193,7 @@ int main()
 	                            (i%16==15)?'\n':' ');
     }
     fprintf(optfile, "};\n\n");
+    fprintf(optfile, "#ifdef RIJNDAEL_INCLUDE_TABLES\n");
     /* The 32-bit word tables for optimized implementation */
     /* T0 = [ S[a] * 02, S[a], S[a], S[a] * 03 ] */
     make_T_Table("0", __S, optfile, 0x02, 0x01, 0x01, 0x03);
@@ -216,6 +216,7 @@ int main()
     make_InvMixCol_Table(1, optfile, 0x0b, 0x0E, 0x09, 0x0d);
     make_InvMixCol_Table(2, optfile, 0x0d, 0x0b, 0x0e, 0x09);
     make_InvMixCol_Table(3, optfile, 0x09, 0x0d, 0x0b, 0x0e);
+    fprintf(optfile, "#endif /* RIJNDAEL_INCLUDE_TABLES */\n\n");
     /* round constants for key expansion */
     fprintf(optfile, "#ifdef IS_LITTLE_ENDIAN\n");
     fprintf(optfile, "static const PRUint32 Rcon[30] = {\n");