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

   1 /* -*-c-*-
   2  *
   3  * The SEAL pseudo-random function family
   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 #include <stdarg.h>
  32 #include <stdio.h>
  33
  34 #include <mLib/bits.h>
  35
  36 #include "arena.h"
  37 #include "gcipher.h"
  38 #include "grand.h"
  39 #include "paranoia.h"
  40 #include "seal.h"
  41 #include "sha.h"
  42
  43 /*----- Global variables --------------------------------------------------*/
  44
  45 const octet seal_keysz[] = { KSZ_ANY, SHA_HASHSZ };
  46
  47 /*----- Main code ---------------------------------------------------------*/
  48
  49 /* --- @gamma@ --- *
  50  *
  51  * Arguments:   @uint32 *p@ = output table
  52  *              @size_t sz@ = size of the output table
  53  *              @const void *k@ = pointer to key material
  54  *              @unsigned i@ = integer offset
  55  *
  56  * Returns:     ---
  57  *
  58  * Use:         Initializes a SEAL key table.
  59  */
  60
  61 static void sealgamma(uint32 *p, size_t sz, const void *k, unsigned i)
  62 {
  63   uint32 buf[80] = { 0 };
  64   const octet *kk = k;
  65   uint32 a, aa = LOAD32(kk);
  66   uint32 b, bb = LOAD32(kk + 4);
  67   uint32 c, cc = LOAD32(kk + 8);
  68   uint32 d, dd = LOAD32(kk + 12);
  69   uint32 e, ee = LOAD32(kk + 16);
  70
  71   unsigned skip = i%5;
  72   uint32 x;
  73   int j;
  74
  75   i /= 5;
  76
  77   /* --- While there's hashing to do, do hashing --- */
  78
  79   while (sz) {
  80     a = aa, b = bb, c = cc, d = dd, e = ee;
  81
  82     /* --- Initialize and expand the buffer --- */
  83
  84     buf[0] = i++;
  85
  86     for (j = 16; j < 80; j++) {
  87       x = buf[j - 3] ^ buf[j - 8] ^ buf[j - 14] ^ buf[j - 16];
  88       buf[j] = ROL32(x, 1);
  89     }
  90
  91     /* --- Definitions for round functions --- */
  92
  93 #define F(x, y, z) (((x)&(y)) | (~(x)&(z)))
  94 #define G(x, y, z) ((x) ^ (y) ^ (z))
  95 #define H(x, y, z) (((x)&(y)) | ((x)&(z)) | ((y)&(z)))
  96
  97 #define T(v, w, x, y, z, i, f, k) do {                                  \
  98   uint32 _x;                                                            \
  99   z = ROL32(v, 5) + f(w, x, y) + z + buf[i] + k;                        \
 100   w = ROR32(w, 2);                                                      \
 101   _x = v; v = z; z = y; y = x; x = w; w = _x;                           \
 102 } while (0)
 103
 104 #define FF(v, w, x, y, z, i) T(v, w, x, y, z, i, F, 0x5a827999)
 105 #define GG(v, w, x, y, z, i) T(v, w, x, y, z, i, G, 0x6ed9eba1)
 106 #define HH(v, w, x, y, z, i) T(v, w, x, y, z, i, H, 0x8f1bbcdc)
 107 #define II(v, w, x, y, z, i) T(v, w, x, y, z, i, G, 0xca62c1d6)
 108
 109     /* --- The main compression function --- *
 110      *
 111      * Since this isn't doing bulk hashing, do it the easy way.
 112      */
 113
 114     for (j =  0; j < 20; j++) FF(a, b, c, d, e, j);
 115     for (j = 20; j < 40; j++) GG(a, b, c, d, e, j);
 116     for (j = 40; j < 60; j++) HH(a, b, c, d, e, j);
 117     for (j = 60; j < 80; j++) II(a, b, c, d, e, j);
 118
 119     /* --- Do the chaining at the end --- */
 120
 121     a += aa; b += bb; c += cc; d += dd; e += ee;
 122
 123     /* --- Write to the output buffer --- */
 124
 125     switch (skip) {
 126       case 0: if (sz) { *p++ = a; sz--; }
 127       case 1: if (sz) { *p++ = b; sz--; }
 128       case 2: if (sz) { *p++ = c; sz--; }
 129       case 3: if (sz) { *p++ = d; sz--; }
 130       case 4: if (sz) { *p++ = e; sz--; }
 131       skip = 0;
 132     }
 133   }
 134 }
 135
 136 /* --- @seal_initkey@ --- *
 137  *
 138  * Arguments:   @seal_key *k@ = pointer to key block
 139  *              @const void *buf@ = pointer to key material
 140  *              @size_t sz@ = size of the key material
 141  *
 142  * Returns:     ---
 143  *
 144  * Use:         Initializes a SEAL key block.  The key material may be any
 145  *              size, but if it's not 20 bytes long it's passed to SHA for
 146  *              hashing first.
 147  */
 148
 149 void seal_initkey(seal_key *k, const void *buf, size_t sz)
 150 {
 151   sha_ctx h;
 152
 153   /* --- Hash the key if it's the wrong size --- */
 154
 155   if (sz == SHA_HASHSZ) memcpy(k->k, buf, sizeof(k->k));
 156   else { sha_init(&h); sha_hash(&h, buf, sz); sha_done(&h, k->k); }
 157
 158   /* --- Expand the key to fit the various tables --- */
 159
 160   sealgamma(k->t, 512, k->k, 0);
 161   sealgamma(k->s, 256, k->k, 0x1000);
 162   sealgamma(k->r, SEAL_R, k->k, 0x2000);
 163 }
 164
 165 /* --- @seal_reset@ --- *
 166  *
 167  * Arguments:   @seal_ctx *c@ = pointer to a SEAL context
 168  *
 169  * Returns:     ---
 170  *
 171  * Use:         Resets the context so that more data can be extracted from
 172  *              it.
 173  */
 174
 175 static void seal_reset(seal_ctx *c)
 176 {
 177   seal_key *k = c->k;
 178   uint32 n = c->n;
 179   uint32 A, B, C, D;
 180   unsigned p;
 181
 182   /* --- Initialize the new chaining variables --- */
 183
 184   if (c->l >= SEAL_R) {
 185     sealgamma(c->rbuf, SEAL_R, k->k, c->ri);
 186     c->ri += SEAL_R;
 187     c->l = 0;
 188     c->r = c->rbuf;
 189   }
 190
 191   A = n ^ c->r[0];
 192   B = ROR32(n,  8) ^ c->r[1];
 193   C = ROR32(n, 16) ^ c->r[2];
 194   D = ROR32(n, 24) ^ c->r[3];
 195   c->l += 4;
 196   c->r += 4;
 197
 198   /* --- Ensure that everything is sufficiently diffused --- */
 199
 200   p = A&0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9);
 201   p = B&0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9);
 202   p = C&0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9);
 203   p = D&0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9);
 204   p = A&0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9);
 205   p = B&0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9);
 206   p = C&0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9);
 207   p = D&0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9);
 208
 209   /* --- Write out some context --- */
 210
 211   c->n1 = D; c->n2 = B; c->n3 = A; c->n4 = C;
 212
 213   /* --- Diffuse some more --- */
 214
 215   p = A&0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9);
 216   p = B&0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9);
 217   p = C&0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9);
 218   p = D&0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9);
 219
 220   /* --- Write out the magic numbers --- */
 221
 222   c->a = A; c->b = B; c->c = C; c->d = D;
 223   c->i = 0;
 224 }
 225
 226 /* --- @seal_initctx@ --- *
 227  *
 228  * Arguments:   @seal_ctx *c@ = pointer to a SEAL context
 229  *              @seal_key *k@ = pointer to a SEAL key
 230  *              @uint32 n@ = integer sequence number
 231  *
 232  * Returns:     ---
 233  *
 234  * Use:         Initializes a SEAL context which can be used for random
 235  *              number generation or whatever.
 236  */
 237
 238 void seal_initctx(seal_ctx *c, seal_key *k, uint32 n)
 239 {
 240   c->k = k;
 241   c->n = n;
 242   c->l = 0;
 243   c->r = k->r;
 244   c->ri = 0x2000 + SEAL_R;
 245   c->off = 16;
 246   seal_reset(c);
 247 }
 248
 249 /* --- @seal_encrypt@ --- *
 250  *
 251  * Arguments:   @seal_ctx *c@ = pointer to a SEAL context
 252  *              @const void *src@ = pointer to source data
 253  *              @void *dest@ = pointer to destination data
 254  *              @size_t sz@ = size of the data
 255  *
 256  * Returns:     ---
 257  *
 258  * Use:         Encrypts a block of data using SEAL.  If @src@ is zero,
 259  *              @dest@ is filled with SEAL output.  If @dest@ is zero, the
 260  *              SEAL generator is just spun around for a bit.  This shouldn't
 261  *              be necessary, because SEAL isn't RC4.
 262  */
 263
 264 void seal_encrypt(seal_ctx *c, const void *src, void *dest, size_t sz)
 265 {
 266   seal_key *k = c->k;
 267   const octet *s = src;
 268   octet *d = dest, *p;
 269   uint32 A = c->a, B = c->b, C = c->c, D = c->d;
 270   uint32 n1 = c->n1, n2 = c->n2, n3 = c->n3, n4 = c->n4;
 271   uint32 aa, bb, cc, dd;
 272   unsigned i, j;
 273   unsigned P, Q;
 274
 275   /* --- Expect a big dollop of bytes --- */
 276
 277   if (sz > 16 - c->off) {
 278     j = c->i;
 279
 280     /* --- Drain the buffer first --- */
 281
 282     if (c->off < 16) {
 283       p = c->buf + c->off; sz -= 16 - c->off;
 284       if (!d) /* nothing to do* */;
 285       else if (!s) memcpy(d, p, 16 - c->off);
 286       else for (i = c->off; i < 16; i++) *d++ = *s++ ^ *p++;
 287     }
 288
 289     /* --- Main sequence --- */
 290
 291     for (;;) {
 292
 293       /* --- Reset if we've run out of steam on this iteration --- */
 294
 295       if (j == 256) {
 296         seal_reset(c);
 297         A = c->a, B = c->b, C = c->c, D = c->d;
 298         n1 = c->n1, n2 = c->n2, n3 = c->n3, n4 = c->n4;
 299         j = 0;
 300       }
 301
 302       /* --- Make some new numbers --- */
 303
 304       P =       A&0x7fc; B += k->t[P >> 2]; A = ROR32(A, 9); B ^= A;
 305       Q =       B&0x7fc; C ^= k->t[Q >> 2]; B = ROR32(B, 9); C += B;
 306       P = (P + C)&0x7fc; D += k->t[P >> 2]; C = ROR32(C, 9); D ^= C;
 307       Q = (Q + D)&0x7fc; A ^= k->t[Q >> 2]; D = ROR32(D, 9); A += D;
 308       P = (P + A)&0x7fc; B ^= k->t[P >> 2]; A = ROR32(A, 9);
 309       Q = (Q + B)&0x7fc; C += k->t[Q >> 2]; B = ROR32(B, 9);
 310       P = (P + C)&0x7fc; D ^= k->t[P >> 2]; C = ROR32(C, 9);
 311       Q = (Q + D)&0x7fc; A += k->t[Q >> 2]; D = ROR32(D, 9);
 312
 313       /* --- Remember the output and set up the next round --- */
 314
 315       aa = B + k->s[j + 0]; bb = C ^ k->s[j + 1];
 316       cc = D + k->s[j + 2]; dd = A ^ k->s[j + 3];
 317       j += 4;
 318
 319       if (j&4) { A += n1; B += n2; C ^= n1; D ^= n2; }
 320       else     { A += n3; B += n4; C ^= n3; D ^= n4; }
 321
 322       /* --- Bail out here if we need to do buffering --- */
 323
 324       if (sz < 16) break;
 325
 326       /* --- Write the next 16 bytes --- */
 327
 328       if (!d) /* nothing to do */;
 329       else {
 330         if (s) {
 331           aa ^= LOAD32_L(s +  0); bb ^= LOAD32_L(s +  4);
 332           cc ^= LOAD32_L(s +  8); dd ^= LOAD32_L(s + 12);
 333           s += 16;
 334         }
 335         STORE32_L(d +  0, aa); STORE32_L(d +  4, bb);
 336         STORE32_L(d +  8, cc); STORE32_L(d + 12, dd);
 337         d += 16;
 338       }
 339       sz -= 16;
 340     }
 341
 342     /* --- Write the new buffer --- */
 343
 344     STORE32_L(c->buf +  0, aa);
 345     STORE32_L(c->buf +  4, bb);
 346     STORE32_L(c->buf +  8, cc);
 347     STORE32_L(c->buf + 12, dd);
 348     c->off = 0;
 349
 350     c->a = A; c->b = B; c->c = C; c->d = D;
 351     c->i = j;
 352   }
 353
 354   /* --- Deal with the rest from the buffer --- */
 355
 356   if (sz) {
 357     p = c->buf + c->off; c->off += sz;
 358     if (!d) /* nothing to do* */;
 359     else if (!s) memcpy(d, p, sz);
 360     else for (i = 0; i < sz; i++) *d++ = *s++ ^ *p++;
 361   }
 362 }
 363
 364 /*----- Generic cipher interface ------------------------------------------*/
 365
 366 typedef struct gctx {
 367   gcipher c;
 368   seal_key k;
 369   seal_ctx cc;
 370 } gctx;
 371
 372 static const gcipher_ops gops;
 373
 374 static gcipher *ginit(const void *k, size_t sz)
 375 {
 376   gctx *g = S_CREATE(gctx);
 377   g->c.ops = &gops;
 378   seal_initkey(&g->k, k, sz);
 379   seal_initctx(&g->cc, &g->k, 0);
 380   return (&g->c);
 381 }
 382
 383 static void gencrypt(gcipher *c, const void *s, void *t, size_t sz)
 384   { gctx *g = (gctx *)c; seal_encrypt(&g->cc, s, t, sz); }
 385
 386 static void gsetiv(gcipher *c, const void *iv)
 387 {
 388   gctx *g = (gctx *)c;
 389   const octet *ivp = iv;
 390   seal_initctx(&g->cc, &g->k, LOAD32(ivp));
 391 }
 392
 393 static void gdestroy(gcipher *c)
 394   { gctx *g = (gctx *)c; BURN(*g); S_DESTROY(g); }
 395
 396 static const gcipher_ops gops = {
 397   &seal,
 398   gencrypt, gencrypt, gdestroy, gsetiv, 0
 399 };
 400
 401 const gccipher seal = {
 402   "seal", seal_keysz, 4,
 403   ginit
 404 };
 405
 406 /*----- Generic random number generator interface -------------------------*/
 407
 408 typedef struct grctx {
 409   grand r;
 410   seal_key k;
 411   seal_ctx cc;
 412 } grctx;
 413
 414 static void grdestroy(grand *r)
 415   { grctx *g = (grctx *)r; BURN(*g); S_DESTROY(g); }
 416
 417 static int grmisc(grand *r, unsigned op, ...)
 418 {
 419   grctx *g = (grctx *)r;
 420   va_list ap;
 421   int rc = 0;
 422   va_start(ap, op);
 423
 424   switch (op) {
 425     case GRAND_CHECK:
 426       switch (va_arg(ap, unsigned)) {
 427         case GRAND_CHECK:
 428         case GRAND_SEEDINT:
 429         case GRAND_SEEDUINT32:
 430         case GRAND_SEEDBLOCK:
 431         case GRAND_SEEDRAND:
 432           rc = 1;
 433           break;
 434         default:
 435           rc = 0;
 436           break;
 437       }
 438       break;
 439     case GRAND_SEEDINT:
 440       seal_initctx(&g->cc, &g->k, va_arg(ap, int));
 441       break;
 442     case GRAND_SEEDUINT32:
 443       seal_initctx(&g->cc, &g->k, va_arg(ap, uint32));
 444       break;
 445     case GRAND_SEEDBLOCK: {
 446       const void *p = va_arg(ap, const void *);
 447       size_t sz = va_arg(ap, size_t);
 448       uint32 n;
 449       if (sz >= 4)
 450         n = LOAD32_L(p);
 451       else {
 452         octet buf[4] = { 0 };
 453         memcpy(buf, p, sz);
 454         n = LOAD32_L(p);
 455       }
 456       seal_initctx(&g->cc, &g->k, n);
 457     } break;
 458     case GRAND_SEEDRAND: {
 459       grand *rr = va_arg(ap, grand *);
 460       seal_initctx(&g->cc, &g->k, rr->ops->word(rr));
 461     } break;
 462     default:
 463       GRAND_BADOP;
 464       break;
 465   }
 466
 467   va_end(ap);
 468   return (rc);
 469 }
 470
 471 static octet grbyte(grand *r)
 472 {
 473   grctx *g = (grctx *)r;
 474   octet o;
 475   seal_encrypt(&g->cc, 0, &o, 1);
 476   return (o);
 477 }
 478
 479 static uint32 grword(grand *r)
 480 {
 481   grctx *g = (grctx *)r;
 482   octet b[4];
 483   seal_encrypt(&g->cc, 0, b, 4);
 484   return (LOAD32(b));
 485 }
 486
 487 static void grfill(grand *r, void *p, size_t sz)
 488   { grctx *g = (grctx *)r; seal_encrypt(&g->cc, 0, p, sz); }
 489
 490 static const grand_ops grops = {
 491   "seal",
 492   GRAND_CRYPTO, 0,
 493   grmisc, grdestroy,
 494   grword, grbyte, grword, grand_defaultrange, grfill
 495 };
 496
 497 /* --- @seal_rand@ --- *
 498  *
 499  * Arguments:   @const void *k@ = pointer to key material
 500  *              @size_t sz@ = size of key material
 501  *              @uint32 n@ = sequence number
 502  *
 503  * Returns:     Pointer to generic random number generator interface.
 504  *
 505  * Use:         Creates a random number interface wrapper around a SEAL
 506  *              pseudorandom function.
 507  */
 508
 509 grand *seal_rand(const void *k, size_t sz, uint32 n)
 510 {
 511   grctx *g = S_CREATE(grctx);
 512   g->r.ops = &grops;
 513   seal_initkey(&g->k, k, sz);
 514   seal_initctx(&g->cc, &g->k, n);
 515   return (&g->r);
 516 }
 517
 518 /*----- Test rig ----------------------------------------------------------*/
 519
 520 #ifdef TEST_RIG
 521
 522 #include <string.h>
 523
 524 #include <mLib/macros.h>
 525 #include <mLib/testrig.h>
 526
 527 static int verify(dstr *v)
 528 {
 529   seal_key k;
 530   seal_ctx c;
 531   uint32 n = *(uint32 *)v[1].buf;
 532   dstr d = DSTR_INIT;
 533   dstr z = DSTR_INIT;
 534   int i;
 535   int ok = 1;
 536
 537   DENSURE(&d, v[2].len);
 538   DENSURE(&z, v[2].len);
 539   memset(z.buf, 0, v[2].len);
 540   z.len = d.len = v[2].len;
 541   seal_initkey(&k, v[0].buf, v[0].len);
 542
 543   for (i = 0; i < v[2].len; i++) {
 544     seal_initctx(&c, &k, n);
 545     seal_encrypt(&c, 0, d.buf, i);
 546     seal_encrypt(&c, z.buf, d.buf + i, d.len - i);
 547     if (MEMCMP(d.buf, !=, v[2].buf, d.len)) {
 548       ok = 0;
 549       printf("*** seal failure\n");
 550       printf("*** k = "); type_hex.dump(&v[0], stdout); putchar('\n');
 551       printf("*** n = %08lx\n", (unsigned long)n);
 552       printf("*** i = %i\n", i);
 553       printf("*** expected = "); type_hex.dump(&v[2], stdout); putchar('\n');
 554       printf("*** computed = "); type_hex.dump(&d, stdout); putchar('\n');
 555     }
 556   }
 557
 558   dstr_destroy(&d);
 559   dstr_destroy(&z);
 560
 561   return (ok);
 562 }
 563
 564 static test_chunk defs[] = {
 565   { "seal", verify, { &type_hex, &type_uint32, &type_hex, 0 } },
 566   { 0, 0, { 0 } }
 567 };
 568
 569 int main(int argc, char *argv[])
 570 {
 571   test_run(argc, argv, defs, SRCDIR"/t/seal");
 572   return (0);
 573 }
 574
 575 #endif
 576
 577 /*----- That's all, folks -------------------------------------------------*/