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

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