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