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

   1 /* -*-c-*-
   2  *
   3  * $Id: rc2.c,v 1.2 2001/04/29 17:39:52 mdw Exp $
   4  *
   5  * The RC2 block 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: rc2.c,v $
  33  * Revision 1.2  2001/04/29 17:39:52  mdw
  34  * Moved big horrible table to a separate header.
  35  *
  36  * Revision 1.1  2000/06/17 11:54:34  mdw
  37  * New cipher.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include <assert.h>
  44 #include <stdio.h>
  45
  46 #include <mLib/bits.h>
  47
  48 #include "blkc.h"
  49 #include "gcipher.h"
  50 #include "paranoia.h"
  51 #include "rc2.h"
  52 #include "rc2-tab.h"
  53
  54 /*----- Global variables --------------------------------------------------*/
  55
  56 const octet rc2_keysz[] = { KSZ_RANGE, RC2_KEYSZ, 1, 128, 1 };
  57
  58 /*----- Important tables --------------------------------------------------*/
  59
  60 static const octet pi[256] = RC2_PI;
  61
  62 /*----- Main code ---------------------------------------------------------*/
  63
  64 /* --- @rc2_braindamage@ --- *
  65  *
  66  * Arguments:   @rc2_ctx *k@ = pointer to context to initialize
  67  *              @const void *buf@ = pointer to key material
  68  *              @size_t sz@ = size of key material in bytes
  69  *              @unsigned eb@ = desired effective key size, in bits
  70  *
  71  * Returns:     ---
  72  *
  73  * Use:         Initializes an RC2 expanded key, and braindamages it to the
  74  *              requested effective key size.  This is here for compatibility
  75  *              reasons.  You should be using @rc2_init@ in normal code,
  76  *              which doesn't actually apply braindamage.
  77  */
  78
  79 void rc2_braindamage(rc2_ctx *k, const void *buf, size_t sz, unsigned eb)
  80 {
  81   unsigned t8;
  82   uint16 tm;
  83   unsigned i;
  84   uint16 *kk;
  85   octet l[128];
  86
  87   KSZ_ASSERT(rc2, sz);
  88
  89   /* --- Compute the braindamage parameters --- */
  90
  91   t8 = (eb + 7) / 8;
  92   tm = 0xff & ((1 << (8 + eb - 8 * t8)) - 1);
  93
  94   /* --- Copy and expand the initial key --- */
  95
  96   if (sz > sizeof(l))
  97     sz = sizeof(l);
  98   memcpy(l, buf, sz);
  99
 100   for (i = sz; i < sizeof(l); i++)
 101     l[i] = pi[U8(l[i - 1] + l[i - sz])];
 102
 103   /* --- Braindamage the key --- */
 104
 105   i = sizeof(l) - t8;
 106   l[i] = pi[l[i] & tm];
 107   while (i) {
 108     i--;
 109     l[i] = pi[U8(l[i + 1] ^ l[i + t8])];
 110   }
 111
 112   /* --- Write it to the key block --- */
 113
 114   kk = k->k;
 115   for (i = 0; i < sizeof(l); i += 2)
 116     *kk++ = LOAD16_L(l + i);
 117   BURN(l);
 118 }
 119
 120 /* --- @rc2_init@ --- *
 121  *
 122  * Arguments:   @rc2_ctx *k@ = pointer to context to initialize
 123  *              @const void *buf@ = pointer to key material
 124  *              @size_t sz@ = size of key material in bytes
 125  *
 126  * Returns:     ---
 127  *
 128  * Use:         Initializes an RC2 expanded key.  The effective key size is
 129  *              set to be equal to the real key size, in bits.
 130  */
 131
 132 void rc2_init(rc2_ctx *k, const void *buf, size_t sz)
 133 {
 134   rc2_braindamage(k, buf, sz, sz * 8);
 135 }
 136
 137 /*----- Encryption and decryption -----------------------------------------*/
 138
 139 #define MIX(a, b, c, d, r, kk) do {                                     \
 140   a += *kk++ + (d & c) + (~d & b);                                      \
 141   a = ROL16(a, r);                                                      \
 142 } while (0)
 143
 144 #define MASH(a, d, k) do {                                              \
 145   a += k[d & 63];                                                       \
 146 } while (0)
 147
 148 #define UNMIX(a, b, c, d, r, kk) do {                                   \
 149   a = ROR16(a, r);                                                      \
 150   a -= *--kk + (d & c) + (~d & b);                                      \
 151 } while (0)
 152
 153 #define UNMASH(a, d, k) do {                                            \
 154   a -= k[d & 63];                                                       \
 155 } while (0)
 156
 157 /* --- @rc2_eblk@, @rc2_dblk@ --- *
 158  *
 159  * Arguments:   @const rc2_ctx *k@ = pointer to RC2 context
 160  *              @const uint32 s[2]@ = pointer to source block
 161  *              @const uint32 d[2]@ = pointer to destination block
 162  *
 163  * Returns:     ---
 164  *
 165  * Use:         Low-level block encryption and decryption.
 166  */
 167
 168 void rc2_eblk(const rc2_ctx *k, const uint32 *s, uint32 *dst)
 169 {
 170   uint16 a = U16(s[0] >>  0), b = U16(s[0] >> 16);
 171   uint16 c = U16(s[1] >>  0), d = U16(s[1] >> 16);
 172   const uint16 *kk = k->k;
 173
 174   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 175   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 176   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 177   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 178   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 179   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 180   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 181   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 182   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 183   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 184   MASH(a, d, k->k); MASH(b, a, k->k);
 185   MASH(c, b, k->k); MASH(d, c, k->k);
 186   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 187   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 188   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 189   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 190   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 191   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 192   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 193   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 194   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 195   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 196   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 197   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 198   MASH(a, d, k->k); MASH(b, a, k->k);
 199   MASH(c, b, k->k); MASH(d, c, k->k);
 200   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 201   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 202   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 203   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 204   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 205   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 206   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 207   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 208   MIX(a, b, c, d, 1, kk); MIX(b, c, d, a, 2, kk);
 209   MIX(c, d, a, b, 3, kk); MIX(d, a, b, c, 5, kk);
 210
 211   dst[0] = a | (b << 16); dst[1] = c | (d << 16);
 212 }
 213
 214 void rc2_dblk(const rc2_ctx *k, const uint32 *s, uint32 *dst)
 215 {
 216   uint16 a = U16(s[0] >>  0), b = U16(s[0] >> 16);
 217   uint16 c = U16(s[1] >>  0), d = U16(s[1] >> 16);
 218   const uint16 *kk = k->k + 64;
 219
 220   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 221   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 222   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 223   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 224   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 225   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 226   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 227   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 228   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 229   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 230   UNMASH(d, c, k->k); UNMASH(c, b, k->k);
 231   UNMASH(b, a, k->k); UNMASH(a, d, k->k);
 232   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 233   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 234   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 235   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 236   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 237   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 238   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 239   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 240   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 241   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 242   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 243   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 244   UNMASH(d, c, k->k); UNMASH(c, b, k->k);
 245   UNMASH(b, a, k->k); UNMASH(a, d, k->k);
 246   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 247   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 248   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 249   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 250   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 251   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 252   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 253   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 254   UNMIX(d, a, b, c, 5, kk); UNMIX(c, d, a, b, 3, kk);
 255   UNMIX(b, c, d, a, 2, kk); UNMIX(a, b, c, d, 1, kk);
 256
 257   dst[0] = a | (b << 16); dst[1] = c | (d << 16);
 258 }
 259
 260 /*----- Custom test rig ---------------------------------------------------*
 261  *
 262  * I need to test the braindamage feature.
 263  */
 264
 265 #ifdef TEST_RIG
 266
 267 #include <mLib/quis.h>
 268 #include <mLib/testrig.h>
 269
 270 static int verify(dstr *v)
 271 {
 272   rc2_ctx k;
 273   uint32 p[RC2_BLKSZ / 4];
 274   uint32 c[RC2_BLKSZ / 4];
 275   uint32 d[RC2_BLKSZ / 4];
 276   dstr b = DSTR_INIT;
 277   unsigned bd = *(unsigned *)v[1].buf;
 278   int ok = 1;
 279
 280   /* --- Initialize the key buffer --- */
 281
 282   dstr_ensure(&b, RC2_BLKSZ);
 283   b.len = RC2_BLKSZ;
 284   rc2_braindamage(&k, v[0].buf, v[0].len, bd);
 285   BLKC_LOAD(RC2, p, v[2].buf);
 286   BLKC_LOAD(RC2, c, v[3].buf);
 287
 288   /* --- Test encryption --- */
 289
 290   BLKC_MOVE(RC2, d, p);
 291   rc2_eblk(&k, d, d);
 292   BLKC_STORE(RC2, b.buf, d);
 293   if (memcmp(b.buf, v[3].buf, RC2_BLKSZ)) {
 294     ok = 0;
 295     printf("\nfail encryption:"
 296            "\n\tkey        = ");
 297     type_hex.dump(&v[0], stdout);
 298     printf("\n\tbraindamage= %u", bd);
 299     printf("\n\tplaintext  = "); type_hex.dump(&v[2], stdout);
 300     printf("\n\texpected   = "); type_hex.dump(&v[3], stdout);
 301     printf("\n\tcalculated = "); type_hex.dump(&b, stdout);
 302     putchar('\n');
 303   }
 304
 305   /* --- Test decryption --- */
 306
 307   BLKC_MOVE(RC2, d, c);
 308   rc2_dblk(&k, d, d);
 309   BLKC_STORE(RC2, b.buf, d);
 310   if (memcmp(b.buf, v[2].buf, RC2_BLKSZ)) {
 311     ok = 0;
 312     printf("\nfail decryption:"
 313            "\n\tkey        = ");
 314     type_hex.dump(&v[0], stdout);
 315     printf("\n\tbraindamage= %u", bd);
 316     printf("\n\tciphertext = "); type_hex.dump(&v[3], stdout);
 317     printf("\n\texpected   = "); type_hex.dump(&v[2], stdout);
 318     printf("\n\tcalculated = "); type_hex.dump(&b, stdout);
 319     putchar('\n');
 320   }
 321
 322   /* --- Return --- */
 323
 324   return (ok);
 325 }
 326
 327 static test_chunk defs[] = {
 328   { "rc2", verify, { &type_hex, &type_int, &type_hex, &type_hex, 0 } },
 329   { 0, 0, { 0 } }
 330 };
 331
 332 int main(int argc, char *argv[])
 333 {
 334   test_run(argc, argv, defs, SRCDIR"/tests/rc2");
 335   return (0);
 336 }
 337
 338 #endif
 339
 340 /*----- That's all, folks -------------------------------------------------*/