lib/helix.c

   1 /* Cleanroom reference implementation of Helix */
   2
   3 /* HEAVILY modified by Chris Porter to support contexts. */
   4
   5 /* See Ferguson et. al, Fast Software Encryption 2003, or
   6  * http://www.macfergus.com/helix/helixPreproc.pdf
   7  */
   8
   9 #include <string.h>
  10 #include "helix.h"
  11
  12 /* some useful macros -- little-endian */
  13 #define B(x,i) ((UCHAR)(((x) >> (8*i)) & 0xFF))
  14 #define BYTE2WORD(b) ( \
  15         (((WORD)(b)[3] & 0xFF)<<24) | \
  16         (((WORD)(b)[2] & 0xFF)<<16) | \
  17         (((WORD)(b)[1] & 0xFF)<<8) | \
  18         (((WORD)(b)[0] & 0xFF)) \
  19 )
  20 #define WORD2BYTE(w, b) { \
  21         (b)[3] = B(w,3); \
  22         (b)[2] = B(w,2); \
  23         (b)[1] = B(w,1); \
  24         (b)[0] = B(w,0); \
  25 }
  26 #define XORWORD(w, b) { \
  27         (b)[3] ^= B(w,3); \
  28         (b)[2] ^= B(w,2); \
  29         (b)[1] ^= B(w,1); \
  30         (b)[0] ^= B(w,0); \
  31 }
  32 #define ROTL(w,x) (((w) << (x))|((w) >> (32 - (x))))
  33
  34 /* 3.2, figure 2, block function */
  35 WORD
  36 h_block(struct helix_ctx *ctx, WORD X_i0, WORD P_i, WORD X_i1)
  37 {
  38     WORD    r;
  39
  40     r = ctx->A; /* for returning later */
  41     ctx->A += ctx->D;       ctx->D = ROTL(ctx->D, 15);
  42     ctx->B += ctx->E;       ctx->E = ROTL(ctx->E, 25);
  43     ctx->C ^= ctx->A;       ctx->A = ROTL(ctx->A, 9);
  44     ctx->D ^= ctx->B;       ctx->B = ROTL(ctx->B, 10);
  45     ctx->E += ctx->C;       ctx->C = ROTL(ctx->C, 17);
  46     ctx->A ^= ctx->D + X_i0;  ctx->D = ROTL(ctx->D, 30);
  47     ctx->B ^= ctx->E;       ctx->E = ROTL(ctx->E, 13);
  48     ctx->C += ctx->A;       ctx->A = ROTL(ctx->A, 20);
  49     ctx->D += ctx->B;       ctx->B = ROTL(ctx->B, 11);
  50     ctx->E ^= ctx->C;       ctx->C = ROTL(ctx->C, 5);
  51     ctx->A += ctx->D ^ P_i;   ctx->D = ROTL(ctx->D, 15);
  52     ctx->B += ctx->E;       ctx->E = ROTL(ctx->E, 25);
  53     ctx->C ^= ctx->A;       ctx->A = ROTL(ctx->A, 9);
  54     ctx->D ^= ctx->B;       ctx->B = ROTL(ctx->B, 10);
  55     ctx->E += ctx->C;       ctx->C = ROTL(ctx->C, 17);
  56     ctx->A ^= ctx->D + X_i1;  ctx->D = ROTL(ctx->D, 30);
  57     ctx->B ^= ctx->E;       ctx->E = ROTL(ctx->E, 13);
  58     ctx->C += ctx->A;       ctx->A = ROTL(ctx->A, 20);
  59     ctx->D += ctx->B;       ctx->B = ROTL(ctx->B, 11);
  60     ctx->E ^= ctx->C;       ctx->C = ROTL(ctx->C, 5);
  61     /* increment i in funny way */
  62     if (++ctx->h_iplus8[0] == 0x80000000lu) {
  63         ++ctx->h_iplus8[1];
  64         ctx->h_iplus8[0] = 0;
  65     }
  66     return r;
  67 }
  68
  69 /* 3.7 Key schedule.
  70  * Could do feistel in place, but this follows description in paper.
  71  */
  72 void
  73 h_key(struct helix_ctx *ctx, unsigned char *U, int U_len)
  74 {
  75     WORD    k[40]; /* room for key schedule */
  76     int     i;
  77
  78     if (U_len > 32)
  79         U_len = 32; /* limit size of key */
  80     memset((void *)k, 0, sizeof k);
  81     memcpy((void *)&k[32], U, U_len);
  82     ctx->h_iplus8[0] = ctx->h_iplus8[1] = 0;
  83
  84     for (i = 32; i < 40; ++i)
  85         k[i] = BYTE2WORD(((unsigned char *)&k[i])); /* convert to words */
  86     for (i = 7; i >= 0; --i) {
  87         ctx->A = k[4*i+4];
  88         ctx->B = k[4*i+5];
  89         ctx->C = k[4*i+6];
  90         ctx->D = k[4*i+7];
  91         ctx->E = U_len + 64;
  92         (void)h_block(ctx, 0, 0, 0);
  93         k[4*i+0] = ctx->A ^ k[4*i+8];
  94         k[4*i+1] = ctx->B ^ k[4*i+9];
  95         k[4*i+2] = ctx->C ^ k[4*i+10];
  96         k[4*i+3] = ctx->D ^ k[4*i+11];
  97     }
  98     /* copy into K */
  99     for (i = 0; i < 8; ++i)
 100         ctx->K[i] = k[i];
 101     /* remember length of key */
 102     ctx->l_u = U_len;
 103 }
 104
 105 /* 3.3, nonce setup */
 106 void
 107 h_nonce(struct helix_ctx *ctx, UCHAR nonce[16])
 108 {
 109     ctx->N[0] = BYTE2WORD(&nonce[0]);
 110     ctx->N[1] = BYTE2WORD(&nonce[4]);
 111     ctx->N[2] = BYTE2WORD(&nonce[8]);
 112     ctx->N[3] = BYTE2WORD(&nonce[12]);
 113     ctx->N[4] = 0 - ctx->N[0];
 114     ctx->N[5] = 1 - ctx->N[1];
 115     ctx->N[6] = 2 - ctx->N[2];
 116     ctx->N[7] = 3 - ctx->N[3];
 117 }
 118
 119 /* 3.3, X_i functions */
 120 WORD
 121 X(struct helix_ctx *ctx, int one)
 122 {
 123     WORD    x = 0;
 124
 125     if (one) {
 126         x = ctx->K[(ctx->h_iplus8[0] + 4) & 0x07] + ctx->N[ctx->h_iplus8[0] & 0x07] + ctx->h_iplus8[0];
 127         if ((ctx->h_iplus8[0] & 0x03) == 3)
 128             x += ctx->h_iplus8[1];
 129         else if ((ctx->h_iplus8[0] & 0x03) == 1)
 130             x += ctx->l_u << 2;
 131     }
 132     else
 133         x = ctx->K[ctx->h_iplus8[0] & 0x07];
 134     return x;
 135 }
 136
 137 /* 3.4 initialisation */
 138 void
 139 h_init(struct helix_ctx *ctx)
 140 {
 141     int     i;
 142
 143     ctx->h_iplus8[0] = ctx->h_iplus8[1] = 0;
 144     ctx->A = ctx->K[3] ^ ctx->N[0];
 145     ctx->B = ctx->K[4] ^ ctx->N[1];
 146     ctx->C = ctx->K[5] ^ ctx->N[2];
 147     ctx->D = ctx->K[6] ^ ctx->N[3];
 148     ctx->E = ctx->K[7];
 149     for (i = 0; i < 8; ++i)
 150         (void) h_block(ctx, X(ctx, 0), 0, X(ctx, 1));
 151 }
 152
 153 /* 3.5 encryption, and 3.6 compute MAC */
 154 void
 155 h_encrypt(struct helix_ctx *ctx, UCHAR *buf, int n, UCHAR macbuf[16])
 156 {
 157     UCHAR   b[4];
 158     WORD    w;
 159     int     i;
 160
 161     h_init(ctx);
 162     while (n >= 4) {
 163         w = h_block(ctx, X(ctx, 0), BYTE2WORD(buf), X(ctx, 1));
 164         XORWORD(w, buf);
 165         buf += 4;
 166         n -= 4;
 167     }
 168     if (n != 0) {
 169         /* handle an odd bit at the end */
 170         for (i = 0; i < n; ++i)
 171             b[i] = buf[i];
 172         for (/*...*/; i < 4; ++i)
 173             b[i] = 0;
 174         w = BYTE2WORD(b);
 175         w = h_block(ctx, X(ctx,0), w, X(ctx,1));
 176         XORWORD(w, b);
 177         for (i = 0; i < n; ++i)
 178             buf[i] = b[i];
 179     }
 180     /* now compute MAC. Note that "n" is currently l(P) mod 4. */
 181     ctx->A ^= 0x912d94f1;
 182     for (i = 0; i < 8; ++i)
 183         (void) h_block(ctx, X(ctx,0), n, X(ctx,1));
 184     for (i = 0; i < 4; ++i) {
 185         w = h_block(ctx, X(ctx,0), n, X(ctx,1));
 186         WORD2BYTE(w, &macbuf[i*4]);
 187     }
 188 }
 189
 190 /* 3.8 decryption, and 3.6 compute MAC */
 191 void
 192 h_decrypt(struct helix_ctx *ctx, UCHAR *buf, int n, UCHAR macbuf[16])
 193 {
 194     UCHAR   b[4];
 195     WORD    w;
 196     int     i;
 197
 198     h_init(ctx);
 199     while (n >= 4) {
 200         /* rather than muck with h_block, we use knowledge of A */
 201         w = BYTE2WORD(buf) ^ ctx->A; /* plaintext */
 202         w = h_block(ctx, X(ctx,0), w, X(ctx,1));
 203         XORWORD(w, buf);
 204         buf += 4;
 205         n -= 4;
 206     }
 207     if (n != 0) {
 208         /* handle an odd bit at the end */
 209         for (i = 0; i < n; ++i)
 210             b[i] = buf[i];
 211         XORWORD(ctx->A, b);
 212         for (/*...*/; i < 4; ++i)
 213             b[i] = 0;
 214         w = BYTE2WORD(b);
 215         (void) h_block(ctx, X(ctx,0), w, X(ctx,1)); /* note decryption already done */
 216         for (i = 0; i < n; ++i)
 217             buf[i] = b[i];
 218     }
 219     /* now compute MAC. Note that "n" is currently l(P) mod 4. */
 220     ctx->A ^= 0x912d94f1;
 221     for (i = 0; i < 8; ++i)
 222         (void) h_block(ctx, X(ctx,0), n, X(ctx,1));
 223     for (i = 0; i < 4; ++i) {
 224         w = h_block(ctx, X(ctx,0), n, X(ctx,1));
 225         WORD2BYTE(w, &macbuf[i*4]);
 226     }
 227 }
 228
 229 #ifdef TEST
 230 /*--------------------------------------------------------------------------*/
 231 /* test harness                                                             */
 232 /*--------------------------------------------------------------------------*/
 233
 234 #include "hexlib.h"
 235 #include <stdlib.h>
 236 #include <stdio.h>
 237 #include <time.h>
 238
 239 /* self test */
 240 void
 241 test_helix(int quick)
 242 {
 243     extern int  keylen;
 244     UCHAR       key[32], nonce[16], buf[32], mac[16];
 245     struct helix_ctx ctx;
 246
 247     /* basic test */
 248     printf("Test Vector set 1:\n");
 249     hexprint("Initial Key", key, 0);
 250     memset((void *)nonce, 0, 16);
 251     hexprint("Nonce", nonce, 16);
 252     h_key(&ctx, key, 0);
 253     h_nonce(&ctx, nonce);
 254     hexwprint("Working Key", ctx.K, 32);
 255     hexwcheck(ctx.K, "a9 3b 6e 32 bc 23 4f 6c 32 6c 0f 82 74 ff a2 41"
 256                  "e3 da 57 7d ef 7c 1b 64 af 78 7c 38 dc ef e3 de", 32);
 257     hexwprint("Working N", ctx.N, 32);
 258     memset(buf, 0, 10);
 259     hexprint("Plaintext", buf, 10);
 260     h_encrypt(&ctx, buf, 10, mac);
 261     hexprint("Ciphertext", buf, 10);
 262     hexcheck(buf, "70 44 c9 be 48 ae 89 22 66 e4", 10);
 263     hexprint("MAC", mac, 16);
 264     hexcheck(mac, "65 be 7a 60 fd 3b 8a 5e 31 61 80 80 56 32 d8 10", 16);
 265     h_decrypt(&ctx, buf, 10, mac);
 266     hexprint("decrypted", buf, 10);
 267     hexprint("MAC", mac, 16);
 268     hexcheck(mac, "65 be 7a 60 fd 3b 8a 5e 31 61 80 80 56 32 d8 10", 16);
 269
 270     /* second vector */
 271     printf("\nTest Vector set 2:\n");
 272     hexread(key, "00 00 00 00 01 00 00 00 02 00 00 00 03 00 00 00"
 273                  "04 00 00 00 05 00 00 00 06 00 00 00 07 00 00 00", 32);
 274     hexprint("Initial Key", key, 32);
 275     hexread(nonce, "00 00 00 00 01 00 00 00 02 00 00 00 03 00 00 00", 16);
 276     hexprint("Nonce", nonce, 16);
 277     h_key(&ctx, key, 32);
 278     h_nonce(&ctx, nonce);
 279     hexwprint("Working Key", ctx.K, 32);
 280     hexwcheck(ctx.K, "6e e9 a7 6c bd 0b f6 20 a6 d9 b7 59 49 d3 39 95"
 281                  "04 f8 4a d6 83 12 f9 06 ed d1 a6 98 9e c8 9d 45", 32);
 282     hexread(buf, "00 00 00 00 01 00 00 00 02 00 00 00 03 00 00 00"
 283                  "04 00 00 00 05 00 00 00 06 00 00 00 07 00 00 00", 32);
 284     hexprint("Plaintext", buf, 32);
 285     h_encrypt(&ctx, buf, 32, mac);
 286     hexprint("Ciphertext", buf, 32);
 287     hexcheck(buf, "7a 72 a7 5b 62 50 38 0b 69 75 1c d1 28 30 8d 9a"
 288                   "0c 74 46 a3 bf 3f 99 e6 65 56 b9 c1 18 ca 7d 87", 32);
 289     hexprint("MAC", mac, 16);
 290     hexcheck(mac, "e4 e5 49 01 c5 0b 34 e7 80 c0 9c 39 b1 09 a1 17", 16);
 291     h_decrypt(&ctx, buf, 32, mac);
 292     hexprint("decrypted", buf, 32);
 293     hexprint("MAC", mac, 16);
 294     hexcheck(mac, "e4 e5 49 01 c5 0b 34 e7 80 c0 9c 39 b1 09 a1 17", 16);
 295
 296     /* third vector */
 297     printf("\nTest Vector set 3:\n");
 298     hexread(key, "48 65 6c 69 78", 5);
 299     hexprint("Initial Key", key, 5);
 300     hexread(nonce, "30 31 32 33 34 35 36 37 38 39 61 62 63 64 65 66", 16);
 301     hexprint("Nonce", nonce, 16);
 302     h_key(&ctx, key, 5);
 303     h_nonce(&ctx, nonce);
 304     hexwprint("Working Key", ctx.K, 32);
 305     hexwcheck(ctx.K, "6c 1e d7 7a cb a3 a1 d2 8f 1c d6 20 6d f1 15 da"
 306                  "f4 03 28 4a 73 9b b6 9f 35 7a 85 f5 51 32 11 39", 32);
 307     hexread(buf, "48 65 6c 6c 6f 2c 20 77 6f 72 6c 64 21", 13);
 308     hexprint("Plaintext", buf, 13);
 309     h_encrypt(&ctx, buf, 13, mac);
 310     hexprint("Ciphertext", buf, 13);
 311     hexcheck(buf, "6c 4c 27 b9 7a 82 a0 c5 80 2c 23 f2 0d", 13);
 312     hexprint("MAC", mac, 16);
 313     hexcheck(mac, "6c 82 d1 aa 3b 90 5f 12 f1 44 3f a7 f6 a1 01 d2", 16);
 314     h_decrypt(&ctx, buf, 13, mac);
 315     hexprint("decrypted", buf, 13);
 316     hexprint("MAC", mac, 16);
 317     hexcheck(mac, "6c 82 d1 aa 3b 90 5f 12 f1 44 3f a7 f6 a1 01 d2", 16);
 318 }
 319
 320 #define BLOCKSIZE       1600    /* for MAC-style tests */
 321 #define MACSIZE         16
 322 char    *testkey = "test key 128bits";
 323 UCHAR   testIV[16];
 324 UCHAR   testframe[BLOCKSIZE];
 325 UCHAR   testmac[16];
 326
 327 /* Perform various timing tests
 328  */
 329 UCHAR   bigbuf[1024*1024];
 330 UCHAR   macbuf[16];
 331 int
 332 main(int ac, char **av)
 333 {
 334     int         n, i;
 335     int         vflag = 0;
 336     UCHAR       key[32], IV[32];
 337     int         keysz, IVsz;
 338     extern int  keylen;
 339     extern WORD K[];
 340
 341     if (ac == 2 && strcmp(av[1], "-test") == 0) {
 342         test_helix(0);
 343         return nerrors;
 344     }
 345     if (ac >= 2 && strcmp(av[1], "-verbose") == 0) {
 346         vflag = 1;
 347         ++av, --ac;
 348     }
 349     return 0;
 350 }
 351 #endif /* TEST */