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

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