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

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