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

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