chiark - git - mdw - catacomb/blob - twofish.c

   1 /* -*-c-*-
   2  *
   3  * $Id: twofish.c,v 1.5 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Implementation of the Twofish cipher
   6  *
   7  * (c) 2000 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <assert.h>
  33
  34 #include <mLib/bits.h>
  35
  36 #include "blkc.h"
  37 #include "gcipher.h"
  38 #include "twofish.h"
  39 #include "twofish-tab.h"
  40 #include "paranoia.h"
  41
  42 /*----- Global variables --------------------------------------------------*/
  43
  44 const octet twofish_keysz[] = { KSZ_RANGE, TWOFISH_KEYSZ, 0, 32, 1 };
  45
  46 /*----- Important tables --------------------------------------------------*/
  47
  48 static const octet q0[256] = TWOFISH_Q0, q1[256] = TWOFISH_Q1;
  49 static const uint32 qmds[4][256] = TWOFISH_QMDS;
  50 static const octet rslog[] = TWOFISH_RSLOG, rsexp[] = TWOFISH_RSEXP;
  51 static const octet rs[32] = TWOFISH_RS;
  52
  53 /*----- Key initialization ------------------------------------------------*/
  54
  55 /* --- @h@ --- *
  56  *
  57  * Arguments:   @uint32 x@ = input to the function
  58  *              @const uint32 *l@ = key values to mix in
  59  *              @unsigned k@ = number of key values there are
  60  *
  61  * Returns:     The output of the function @h@.
  62  *
  63  * Use:         Implements the Twofish function @h@.
  64  */
  65
  66 static uint32 h(uint32 x, const uint32 *l, unsigned k)
  67 {
  68   /* --- Apply a series of @q@ tables to an integer --- */
  69
  70 # define Q(x, qa, qb, qc, qd)                                           \
  71   ((qa[((x) >>  0) & 0xff] <<  0) |                                     \
  72    (qb[((x) >>  8) & 0xff] <<  8) |                                     \
  73    (qc[((x) >> 16) & 0xff] << 16) |                                     \
  74    (qd[((x) >> 24) & 0xff] << 24))
  75
  76   /* --- Grind through the tables --- */
  77
  78   switch (k) {
  79     case 4: x = Q(x, q1, q0, q0, q1) ^ l[3];
  80     case 3: x = Q(x, q1, q1, q0, q0) ^ l[2];
  81     case 2: x = Q(x, q0, q1, q0, q1) ^ l[1];
  82             x = Q(x, q0, q0, q1, q1) ^ l[0];
  83       break;
  84   }
  85
  86 #undef Q
  87
  88   /* --- Apply the MDS matrix --- */
  89
  90   return (qmds[0][U8(x >>  0)] ^ qmds[1][U8(x >>  8)] ^
  91           qmds[2][U8(x >> 16)] ^ qmds[3][U8(x >> 24)]);
  92 }
  93
  94 /* --- @twofish_initfk@ --- *
  95  *
  96  * Arguments:   @twofish_ctx *k@ = pointer to key block to fill in
  97  *              @const void *buf@ = pointer to buffer of key material
  98  *              @size_t sz@ = size of key material
  99  *              @const twofish_fk *fk@ = family-key information
 100  *
 101  * Returns:     ---
 102  *
 103  * Use:         Does the underlying Twofish key initialization with family
 104  *              key.  Pass in a family-key structure initialized to
 105  *              all-bits-zero for a standard key schedule.
 106  */
 107
 108 void twofish_initfk(twofish_ctx *k, const void *buf, size_t sz,
 109                     const twofish_fk *fk)
 110 {
 111 # define KMAX 4
 112
 113   uint32 mo[KMAX], me[KMAX];
 114   octet s[4][KMAX];
 115
 116   /* --- Expand the key into the three word arrays --- */
 117
 118   {
 119     size_t ssz;
 120     const octet *p, *q;
 121     octet b[32];
 122     int i;
 123
 124     /* --- Sort out the key size --- */
 125
 126     KSZ_ASSERT(twofish, sz);
 127     if (sz <= 16)
 128       ssz = 16;
 129     else if (sz <= 24)
 130       ssz = 24;
 131     else if (sz <= 32)
 132       ssz = 32;
 133     else
 134       assert(((void)"This can't happen (bad key size in twofish_init)", 0));
 135
 136     /* --- Extend the key if necessary --- */
 137
 138     if (sz == ssz)
 139       p = buf;
 140     else {
 141       memcpy(b, buf, sz);
 142       memset(b + sz, 0, ssz - sz);
 143       p = b;
 144     }
 145
 146     /* --- Finally get the word count --- */
 147
 148     sz = ssz / 8;
 149
 150     /* --- Extract words from the key --- *
 151      *
 152      * The @s@ table, constructed using the Reed-Solomon matrix, is cut into
 153      * sequences of bytes, since this is actually more useful for computing
 154      * the S-boxes.
 155      */
 156
 157     q = p;
 158     for (i = 0; i < sz; i++) {
 159       octet ss[4];
 160       const octet *r = rs;
 161       int j;
 162
 163       /* --- Extract the easy subkeys --- */
 164
 165       me[i] = LOAD32_L(q) ^ fk->t0[2 * i];
 166       mo[i] = LOAD32_L(q + 4) ^ fk->t0[2 * i + 1];
 167
 168       /* --- Now do the Reed-Solomon thing --- */
 169
 170       for (j = 0; j < 4; j++) {
 171         const octet *qq = q;
 172         unsigned a = 0;
 173         int k;
 174
 175         for (k = 0; k < 8; k++) {
 176           unsigned char x = *qq ^ fk->t1[i * 8 + k];
 177           if (x) a ^= rsexp[rslog[x] + *r];
 178           qq++;
 179           r++;
 180         }
 181
 182         s[j][sz - 1 - i] = ss[j] = a;
 183       }
 184       q += 8;
 185     }
 186
 187     /* --- Clear away the temporary buffer --- */
 188
 189     if (p == b)
 190       BURN(b);
 191   }
 192
 193   /* --- Construct the expanded key --- */
 194
 195   {
 196     uint32 p = 0x01010101;
 197     uint32 ip = 0;
 198     int i;
 199
 200     for (i = 0; i < 40; i += 2) {
 201       uint32 a, b;
 202       a = h(ip, me, sz);
 203       b = h(ip + p, mo, sz);
 204       b = ROL32(b, 8);
 205       a += b; b += a;
 206       k->k[i] = U32(a);
 207       k->k[i + 1] = ROL32(b, 9);
 208       ip += 2 * p;
 209     }
 210
 211     for (i = 0; i < 8; i++)
 212       k->k[i] ^= fk->t23[i];
 213     for (i = 8; i < 40; i += 2) {
 214       k->k[i] ^= fk->t4[0];
 215       k->k[i + 1] ^= fk->t4[1];
 216     }
 217   }
 218
 219   /* --- Construct the S-box tables --- */
 220
 221   {
 222     unsigned i;
 223     static const octet *q[4][KMAX + 1] = {
 224       { q1, q0, q0, q1, q1 },
 225       { q0, q0, q1, q1, q0 },
 226       { q1, q1, q0, q0, q0 },
 227       { q0, q1, q1, q0, q1 }
 228     };
 229
 230     for (i = 0; i < 4; i++) {
 231       unsigned j;
 232       uint32 x;
 233
 234       for (j = 0; j < 256; j++) {
 235         x = j;
 236
 237         /* --- Push the byte through the q tables --- */
 238
 239         switch (sz) {
 240           case 4: x = q[i][4][x] ^ s[i][3];
 241           case 3: x = q[i][3][x] ^ s[i][2];
 242           case 2: x = q[i][2][x] ^ s[i][1];
 243                   x = q[i][1][x] ^ s[i][0];
 244             break;
 245         }
 246
 247         /* --- Write it in the key schedule --- */
 248
 249         k->g[i][j] = qmds[i][x];
 250       }
 251     }
 252   }
 253
 254   /* --- Clear everything away --- */
 255
 256   BURN(me);
 257   BURN(mo);
 258   BURN(s);
 259 }
 260
 261 /* --- @twofish_init@ --- *
 262  *
 263  * Arguments:   @twofish_ctx *k@ = pointer to key block to fill in
 264  *              @const void *buf@ = pointer to buffer of key material
 265  *              @size_t sz@ = size of key material
 266  *
 267  * Returns:     ---
 268  *
 269  * Use:         Initializes a Twofish key buffer.  Twofish accepts key sizes
 270  *              of up to 256 bits (32 bytes).
 271  */
 272
 273 void twofish_init(twofish_ctx *k, const void *buf, size_t sz)
 274 {
 275   static const twofish_fk fk = { { 0 } };
 276   twofish_initfk(k, buf, sz, &fk);
 277 }
 278
 279 /* --- @twofish_fkinit@ --- *
 280  *
 281  * Arguments:   @twofish_fk *fk@ = pointer to family key block
 282  *              @const void *buf@ = pointer to buffer of key material
 283  *              @size_t sz@ = size of key material
 284  *
 285  * Returns:     ---
 286  *
 287  * Use:         Initializes a family-key buffer.  This implementation allows
 288  *              family keys of any size acceptable to the Twofish algorithm.
 289  */
 290
 291 void twofish_fkinit(twofish_fk *fk, const void *buf, size_t sz)
 292 {
 293   twofish_ctx k;
 294   uint32 pt[4], ct[4];
 295   const octet *kk;
 296   unsigned i;
 297
 298   twofish_init(&k, buf, sz);
 299
 300   for (i = 0; i < 4; i++) pt[i] = (uint32)-1;
 301   twofish_eblk(&k, pt, fk->t0 + 4);
 302
 303   kk = buf; sz /= 4;
 304   for (i = 0; i < sz; i++) { fk->t0[i] = LOAD32_L(kk); kk += 4; }
 305
 306   for (i = 0; i < 4; i++) pt[i] = 0; twofish_eblk(&k, pt, ct);
 307   for (i = 0; i < 4; i++) STORE32_L(fk->t1 + i * 4, ct[i]);
 308   pt[0] = 1; twofish_eblk(&k, pt, ct);
 309   for (i = 0; i < 4; i++) STORE32_L(fk->t1 + 4 + i * 4, ct[i]);
 310
 311   pt[0] = 2; twofish_eblk(&k, pt, fk->t23 + 0);
 312   pt[0] = 3; twofish_eblk(&k, pt, fk->t23 + 4);
 313   pt[0] = 4; twofish_eblk(&k, pt, ct);
 314   fk->t4[0] = ct[0]; fk->t4[1] = ct[1];
 315
 316   BURN(k);
 317 }
 318
 319 /*----- Main encryption ---------------------------------------------------*/
 320
 321 /* --- Feistel function --- */
 322
 323 #define GG(k, t0, t1, x, y, kk) do {                                    \
 324   t0 = (k->g[0][U8(x >>  0)] ^                                          \
 325         k->g[1][U8(x >>  8)] ^                                          \
 326         k->g[2][U8(x >> 16)] ^                                          \
 327         k->g[3][U8(x >> 24)]);                                          \
 328   t1 = (k->g[1][U8(y >>  0)] ^                                          \
 329         k->g[2][U8(y >>  8)] ^                                          \
 330         k->g[3][U8(y >> 16)] ^                                          \
 331         k->g[0][U8(y >> 24)]);                                          \
 332   t0 += t1;                                                             \
 333   t1 += t0;                                                             \
 334   t0 += kk[0];                                                          \
 335   t1 += kk[1];                                                          \
 336 } while (0)
 337
 338 /* --- Round operations --- */
 339
 340 #define EROUND(k, w, x, y, z, kk) do {                                  \
 341   uint32 _t0, _t1;                                                      \
 342   GG(k, _t0, _t1, w, x, kk);                                            \
 343   kk += 2;                                                              \
 344   y ^= _t0; y = ROR32(y, 1);                                            \
 345   z = ROL32(z, 1); z ^= _t1;                                            \
 346 } while (0)
 347
 348 #define DROUND(k, w, x, y, z, kk) do {                                  \
 349   uint32 _t0, _t1;                                                      \
 350   kk -= 2;                                                              \
 351   GG(k, _t0, _t1, w, x, kk);                                            \
 352   y = ROL32(y, 1); y ^= _t0;                                            \
 353   z ^= _t1; z = ROR32(z, 1);                                            \
 354 } while (0)
 355
 356 /* --- Complete encryption functions --- */
 357
 358 #define EBLK(k, a, b, c, d, w, x, y, z) do {                            \
 359   const uint32 *_kk = k->k + 8;                                         \
 360   uint32 _a = a, _b = b, _c = c, _d = d;                                \
 361   _a ^= k->k[0]; _b ^= k->k[1]; _c ^= k->k[2]; _d ^= k->k[3];           \
 362   EROUND(k, _a, _b, _c, _d, _kk);                                       \
 363   EROUND(k, _c, _d, _a, _b, _kk);                                       \
 364   EROUND(k, _a, _b, _c, _d, _kk);                                       \
 365   EROUND(k, _c, _d, _a, _b, _kk);                                       \
 366   EROUND(k, _a, _b, _c, _d, _kk);                                       \
 367   EROUND(k, _c, _d, _a, _b, _kk);                                       \
 368   EROUND(k, _a, _b, _c, _d, _kk);                                       \
 369   EROUND(k, _c, _d, _a, _b, _kk);                                       \
 370   EROUND(k, _a, _b, _c, _d, _kk);                                       \
 371   EROUND(k, _c, _d, _a, _b, _kk);                                       \
 372   EROUND(k, _a, _b, _c, _d, _kk);                                       \
 373   EROUND(k, _c, _d, _a, _b, _kk);                                       \
 374   EROUND(k, _a, _b, _c, _d, _kk);                                       \
 375   EROUND(k, _c, _d, _a, _b, _kk);                                       \
 376   EROUND(k, _a, _b, _c, _d, _kk);                                       \
 377   EROUND(k, _c, _d, _a, _b, _kk);                                       \
 378   _c ^= k->k[4]; _d ^= k->k[5]; _a ^= k->k[6]; _b ^= k->k[7];           \
 379   w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b);                   \
 380 } while (0)
 381
 382 #define DBLK(k, a, b, c, d, w, x, y, z) do {                            \
 383   const uint32 *_kk = k->k + 40;                                        \
 384   uint32 _a = a, _b = b, _c = c, _d = d;                                \
 385   _a ^= k->k[4]; _b ^= k->k[5]; _c ^= k->k[6]; _d ^= k->k[7];           \
 386   DROUND(k, _a, _b, _c, _d, _kk);                                       \
 387   DROUND(k, _c, _d, _a, _b, _kk);                                       \
 388   DROUND(k, _a, _b, _c, _d, _kk);                                       \
 389   DROUND(k, _c, _d, _a, _b, _kk);                                       \
 390   DROUND(k, _a, _b, _c, _d, _kk);                                       \
 391   DROUND(k, _c, _d, _a, _b, _kk);                                       \
 392   DROUND(k, _a, _b, _c, _d, _kk);                                       \
 393   DROUND(k, _c, _d, _a, _b, _kk);                                       \
 394   DROUND(k, _a, _b, _c, _d, _kk);                                       \
 395   DROUND(k, _c, _d, _a, _b, _kk);                                       \
 396   DROUND(k, _a, _b, _c, _d, _kk);                                       \
 397   DROUND(k, _c, _d, _a, _b, _kk);                                       \
 398   DROUND(k, _a, _b, _c, _d, _kk);                                       \
 399   DROUND(k, _c, _d, _a, _b, _kk);                                       \
 400   DROUND(k, _a, _b, _c, _d, _kk);                                       \
 401   DROUND(k, _c, _d, _a, _b, _kk);                                       \
 402   _c ^= k->k[0]; _d ^= k->k[1]; _a ^= k->k[2]; _b ^= k->k[3];           \
 403   w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b);                   \
 404 } while (0)
 405
 406 /* --- @twofish_eblk@, @twofish_dblk@ --- *
 407  *
 408  * Arguments:   @const twofish_ctx *k@ = pointer to key block
 409  *              @const uint32 s[4]@ = pointer to source block
 410  *              @uint32 d[4]@ = pointer to destination block
 411  *
 412  * Returns:     ---
 413  *
 414  * Use:         Low-level block encryption and decryption.
 415  */
 416
 417 void twofish_eblk(const twofish_ctx *k, const uint32 *s, uint32 *d)
 418 {
 419   EBLK(k, s[0], s[1], s[2], s[3], d[0], d[1], d[2], d[3]);
 420 }
 421
 422 void twofish_dblk(const twofish_ctx *k, const uint32 *s, uint32 *d)
 423 {
 424   DBLK(k, s[0], s[1], s[2], s[3], d[0], d[1], d[2], d[3]);
 425 }
 426
 427 BLKC_TEST(TWOFISH, twofish)
 428
 429 /*----- That's all, folks -------------------------------------------------*/