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