math/mpreduce.h: Missing include files.

[u/mdw/catacomb] / symm / seal.c

/* -*-c-*-
 *
 * The SEAL pseudo-random function family
 *
 * (c) 2000 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Header files ------------------------------------------------------*/

#include <assert.h>
#include <stdarg.h>
#include <stdio.h>

#include <mLib/bits.h>

#include "arena.h"
#include "gcipher.h"
#include "grand.h"
#include "paranoia.h"
#include "seal.h"
#include "sha.h"

/*----- Global variables --------------------------------------------------*/

const octet seal_keysz[] = { KSZ_ANY, SHA_HASHSZ };

/*----- Main code ---------------------------------------------------------*/

/* --- @gamma@ --- *
 *
 * Arguments:	@uint32 *p@ = output table
 *		@size_t sz@ = size of the output table
 *		@const void *k@ = pointer to key material
 *		@unsigned i@ = integer offset
 *
 * Returns:	---
 *
 * Use:		Initializes a SEAL key table.
 */

static void sealgamma(uint32 *p, size_t sz, const void *k, unsigned i)
{
  uint32 buf[80] = { 0 };
  const octet *kk = k;
  uint32 aa = LOAD32(kk);
  uint32 bb = LOAD32(kk + 4);
  uint32 cc = LOAD32(kk + 8);
  uint32 dd = LOAD32(kk + 12);
  uint32 ee = LOAD32(kk + 16);

  unsigned skip = i % 5;
  i /= 5;

  /* --- While there's hashing to do, do hashing --- */

  while (sz) {
    uint32 a = aa, b = bb, c = cc, d = dd, e = ee;
    int j;

    /* --- Initialize and expand the buffer --- */

    buf[0] = i++;

    for (j = 16; j < 80; j++) {
      uint32 x = buf[j - 3] ^ buf[j - 8] ^ buf[j - 14] ^ buf[j - 16];
      buf[j] = ROL32(x, 1);
    }

    /* --- Definitions for round functions --- */

#define F(x, y, z) (((x) & (y)) | (~(x) & (z)))
#define G(x, y, z) ((x) ^ (y) ^ (z))
#define H(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))

#define T(v, w, x, y, z, i, f, k) do {					\
  uint32 _x;								\
  z = ROL32(v, 5) + f(w, x, y) + z + buf[i] + k;			\
  w = ROR32(w, 2);							\
  _x = v; v = z; z = y; y = x; x = w; w = _x;				\
} while (0)

#define FF(v, w, x, y, z, i) T(v, w, x, y, z, i, F, 0x5a827999)
#define GG(v, w, x, y, z, i) T(v, w, x, y, z, i, G, 0x6ed9eba1)
#define HH(v, w, x, y, z, i) T(v, w, x, y, z, i, H, 0x8f1bbcdc)
#define II(v, w, x, y, z, i) T(v, w, x, y, z, i, G, 0xca62c1d6)

    /* --- The main compression function --- *
     *
     * Since this isn't doing bulk hashing, do it the easy way.
     */

    for (j = 0; j < 20; j++)
      FF(a, b, c, d, e, j);
    for (j = 20; j < 40; j++)
      GG(a, b, c, d, e, j);
    for (j = 40; j < 60; j++)
      HH(a, b, c, d, e, j);
    for (j = 60; j < 80; j++)
      II(a, b, c, d, e, j);

    /* --- Do the chaining at the end --- */

    a += aa; b += bb; c += cc; d += dd; e += ee;

    /* --- Write to the output buffer --- */

    switch (skip) {
      case 0:
	if (sz) { *p++ = a; sz--; }
      case 1:
	if (sz) { *p++ = b; sz--; }
      case 2:
	if (sz) { *p++ = c; sz--; }
      case 3:
	if (sz) { *p++ = d; sz--; }
      case 4:
	if (sz) { *p++ = e; sz--; }
	skip = 0;
    }
  }
}

/* --- @seal_initkey@ --- *
 *
 * Arguments:	@seal_key *k@ = pointer to key block
 *		@const void *buf@ = pointer to key material
 *		@size_t sz@ = size of the key material
 *
 * Returns:	---
 *
 * Use:		Initializes a SEAL key block.  The key material may be any
 *		size, but if it's not 20 bytes long it's passed to SHA for
 *		hashing first.
 */

void seal_initkey(seal_key *k, const void *buf, size_t sz)
{
  /* --- Hash the key if it's the wrong size --- */

  if (sz == SHA_HASHSZ)
    memcpy(k->k, buf, sizeof(k->k));
  else {
    sha_ctx c;
    sha_init(&c);
    sha_hash(&c, buf, sz);
    sha_done(&c, k->k);
  }

  /* --- Expand the key to fit the various tables --- */

  sealgamma(k->t, 512, k->k, 0);
  sealgamma(k->s, 256, k->k, 0x1000);
  sealgamma(k->r, SEAL_R, k->k, 0x2000);
}

/* --- @seal_reset@ --- *
 *
 * Arguments:	@seal_ctx *c@ = pointer to a SEAL context
 *
 * Returns:	---
 *
 * Use:		Resets the context so that more data can be extracted from
 *		it.
 */

static void seal_reset(seal_ctx *c)
{
  seal_key *k = c->k;
  uint32 n = c->n;
  uint32 A, B, C, D;
  unsigned p;

  /* --- Initialize the new chaining variables --- */

  if (c->l >= SEAL_R) {
    sealgamma(c->rbuf, SEAL_R, k->k, c->ri);
    c->ri += SEAL_R;
    c->l = 0;
    c->r = c->rbuf;
  }

  A = n ^ c->r[0];
  B = ROR32(n,	8) ^ c->r[1];
  C = ROR32(n, 16) ^ c->r[2];
  D = ROR32(n, 24) ^ c->r[3];
  c->l += 4;
  c->r += 4;

  /* --- Ensure that everything is sufficiently diffused --- */

  p = A & 0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9);
  p = B & 0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9);
  p = C & 0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9);
  p = D & 0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9);
  p = A & 0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9);
  p = B & 0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9);
  p = C & 0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9);
  p = D & 0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9);

  /* --- Write out some context --- */

  c->n1 = D; c->n2 = B; c->n3 = A; c->n4 = C;

  /* --- Diffuse some more --- */

  p = A & 0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9);
  p = B & 0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9);
  p = C & 0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9);
  p = D & 0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9);

  /* --- Write out the magic numbers --- */

  c->a = A; c->b = B; c->c = C; c->d = D;
  c->i = 0;
}

/* --- @seal_initctx@ --- *
 *
 * Arguments:	@seal_ctx *c@ = pointer to a SEAL context
 *		@seal_key *k@ = pointer to a SEAL key
 *		@uint32 n@ = integer sequence number
 *
 * Returns:	---
 *
 * Use:		Initializes a SEAL context which can be used for random
 *		number generation or whatever.
 */

void seal_initctx(seal_ctx *c, seal_key *k, uint32 n)
{
  c->k = k;
  c->n = n;
  c->l = 0;
  c->r = k->r;
  c->ri = 0x2000 + SEAL_R;
  c->qsz = 0;
  seal_reset(c);
}

/* --- @seal_encrypt@ --- *
 *
 * Arguments:	@seal_ctx *c@ = pointer to a SEAL context
 *		@const void *src@ = pointer to source data
 *		@void *dest@ = pointer to destination data
 *		@size_t sz@ = size of the data
 *
 * Returns:	---
 *
 * Use:		Encrypts a block of data using SEAL.  If @src@ is zero,
 *		@dest@ is filled with SEAL output.  If @dest@ is zero, the
 *		SEAL generator is just spun around for a bit.  This shouldn't
 *		be necessary, because SEAL isn't RC4.
 */

void seal_encrypt(seal_ctx *c, const void *src, void *dest, size_t sz)
{
  const octet *s = src;
  octet *d = dest;

  /* --- Expect a big dollop of bytes --- */

  if (sz > c->qsz) {
    seal_key *k = c->k;
    uint32 A = c->a, B = c->b, C = c->c, D = c->d;
    uint32 n1 = c->n1, n2 = c->n2, n3 = c->n3, n4 = c->n4;
    uint32 aa, bb, cc, dd;
    unsigned j = c->i;

    /* --- Empty the queue first --- */

    if (c->qsz) {
      if (d) {
	unsigned i;
	octet *p = c->q + sizeof(c->q) - c->qsz;
	for (i = 0; i < c->qsz; i++)
	  *d++ = (s ? *s++ ^ *p++ : *p++);
      }
      sz -= c->qsz;
    }

    /* --- Main sequence --- */

    for (;;) {
      unsigned P, Q;

      /* --- Reset if we've run out of steam on this iteration --- */

      if (j == 256) {
	seal_reset(c);
	A = c->a, B = c->b, C = c->c, D = c->d;
	n1 = c->n1, n2 = c->n2, n3 = c->n3, n4 = c->n4;
	j = 0;
      }

      /* --- Make some new numbers --- */

      P = A & 0x7fc; B += k->t[P >> 2]; A = ROR32(A, 9); B ^= A;
      Q = B & 0x7fc; C ^= k->t[Q >> 2]; B = ROR32(B, 9); C += B;
      P = (P + C) & 0x7fc; D += k->t[P >> 2]; C = ROR32(C, 9); D ^= C;
      Q = (Q + D) & 0x7fc; A ^= k->t[Q >> 2]; D = ROR32(D, 9); A += D;
      P = (P + A) & 0x7fc; B ^= k->t[P >> 2]; A = ROR32(A, 9);
      Q = (Q + B) & 0x7fc; C += k->t[Q >> 2]; B = ROR32(B, 9);
      P = (P + C) & 0x7fc; D ^= k->t[P >> 2]; C = ROR32(C, 9);
      Q = (Q + D) & 0x7fc; A += k->t[Q >> 2]; D = ROR32(D, 9);

      /* --- Remember the output and set up the next round --- */

      aa = B + k->s[j + 0];
      bb = C ^ k->s[j + 1];
      cc = D + k->s[j + 2];
      dd = A ^ k->s[j + 3];
      j += 4;

      if (j & 4)
	A += n1, B += n2, C ^= n1, D ^= n2;
      else
	A += n3, B += n4, C ^= n3, D ^= n4;

      /* --- Bail out here if we need to do buffering --- */

      if (sz < 16)
	break;

      /* --- Write the next 16 bytes --- */

      if (d) {
	if (s) {
	  aa ^= LOAD32_L(s + 0);
	  bb ^= LOAD32_L(s + 4);
	  cc ^= LOAD32_L(s + 8);
	  dd ^= LOAD32_L(s + 12);
	  s += 16;
	}
	STORE32_L(d + 0, aa);
	STORE32_L(d + 4, bb);
	STORE32_L(d + 8, cc);
	STORE32_L(d + 12, dd);
	d += 16;
      }
      sz -= 16;
    }

    /* --- Write the new queue --- */

    STORE32_L(c->q + 0, aa);
    STORE32_L(c->q + 4, bb);
    STORE32_L(c->q + 8, cc);
    STORE32_L(c->q + 12, dd);
    c->qsz = 16;

    c->a = A; c->b = B; c->c = C; c->d = D;
    c->i = j;
  }

  /* --- Deal with the rest from the queue --- */

  if (sz) {
    unsigned i;
    octet *p = c->q + sizeof(c->q) - c->qsz;
    if (d) {
      for (i = 0; i < sz; i++)
	*d++ = (s ? *s++ ^ *p++ : *p++);
    }
    c->qsz -= sz;
  }
}

/*----- Generic cipher interface ------------------------------------------*/

typedef struct gctx {
  gcipher c;
  seal_key k;
  seal_ctx cc;
} gctx;

static const gcipher_ops gops;

static gcipher *ginit(const void *k, size_t sz)
{
  gctx *g = S_CREATE(gctx);
  g->c.ops = &gops;
  seal_initkey(&g->k, k, sz);
  seal_initctx(&g->cc, &g->k, 0);
  return (&g->c);
}

static void gencrypt(gcipher *c, const void *s, void *t, size_t sz)
{
  gctx *g = (gctx *)c;
  seal_encrypt(&g->cc, s, t, sz);
}

static void gsetiv(gcipher *c, const void *iv)
{
  gctx *g = (gctx *)c;
  uint32 n = *(const uint32 *)iv;
  seal_initctx(&g->cc, &g->k, n);
}

static void gdestroy(gcipher *c)
{
  gctx *g = (gctx *)c;
  BURN(*g);
  S_DESTROY(g);
}

static const gcipher_ops gops = {
  &seal,
  gencrypt, gencrypt, gdestroy, gsetiv, 0
};

const gccipher seal = {
  "seal", seal_keysz, 0,
  ginit
};

/*----- Generic random number generator interface -------------------------*/

typedef struct grctx {
  grand r;
  seal_key k;
  seal_ctx cc;
} grctx;

static void grdestroy(grand *r)
{
  grctx *g = (grctx *)r;
  BURN(*g);
  S_DESTROY(g);
}

static int grmisc(grand *r, unsigned op, ...)
{
  grctx *g = (grctx *)r;
  va_list ap;
  int rc = 0;
  va_start(ap, op);

  switch (op) {
    case GRAND_CHECK:
      switch (va_arg(ap, unsigned)) {
	case GRAND_CHECK:
	case GRAND_SEEDINT:
	case GRAND_SEEDUINT32:
	case GRAND_SEEDBLOCK:
	case GRAND_SEEDRAND:
	  rc = 1;
	  break;
	default:
	  rc = 0;
	  break;
      }
      break;
    case GRAND_SEEDINT:
      seal_initctx(&g->cc, &g->k, va_arg(ap, int));
      break;
    case GRAND_SEEDUINT32:
      seal_initctx(&g->cc, &g->k, va_arg(ap, uint32));
      break;
    case GRAND_SEEDBLOCK: {
      const void *p = va_arg(ap, const void *);
      size_t sz = va_arg(ap, size_t);
      uint32 n;
      if (sz >= 4)
	n = LOAD32_L(p);
      else {
	octet buf[4] = { 0 };
	memcpy(buf, p, sz);
	n = LOAD32_L(p);
      }
      seal_initctx(&g->cc, &g->k, n);
    } break;
    case GRAND_SEEDRAND: {
      grand *rr = va_arg(ap, grand *);
      seal_initctx(&g->cc, &g->k, rr->ops->word(rr));
    } break;
    default:
      GRAND_BADOP;
      break;
  }

  va_end(ap);
  return (rc);
}

static octet grbyte(grand *r)
{
  grctx *g = (grctx *)r;
  octet o;
  seal_encrypt(&g->cc, 0, &o, 1);
  return (o);
}

static uint32 grword(grand *r)
{
  grctx *g = (grctx *)r;
  octet b[4];
  seal_encrypt(&g->cc, 0, b, 4);
  return (LOAD32(b));
}

static void grfill(grand *r, void *p, size_t sz)
{
  grctx *g = (grctx *)r;
  seal_encrypt(&g->cc, 0, p, sz);
}

static const grand_ops grops = {
  "seal",
  GRAND_CRYPTO, 0,
  grmisc, grdestroy,
  grword, grbyte, grword, grand_range, grfill
};

/* --- @seal_rand@ --- *
 *
 * Arguments:	@const void *k@ = pointer to key material
 *		@size_t sz@ = size of key material
 *		@uint32 n@ = sequence number
 *
 * Returns:	Pointer to generic random number generator interface.
 *
 * Use:		Creates a random number interface wrapper around a SEAL
 *		pseudorandom function.
 */

grand *seal_rand(const void *k, size_t sz, uint32 n)
{
  grctx *g = S_CREATE(grctx);
  g->r.ops = &grops;
  seal_initkey(&g->k, k, sz);
  seal_initctx(&g->cc, &g->k, n);
  return (&g->r);
}

/*----- Test rig ----------------------------------------------------------*/

#ifdef TEST_RIG

#include <string.h>

#include <mLib/testrig.h>

static int verify(dstr *v)
{
  seal_key k;
  seal_ctx c;
  uint32 n = *(uint32 *)v[1].buf;
  dstr d = DSTR_INIT;
  dstr z = DSTR_INIT;
  int i;
  int ok = 1;

  DENSURE(&d, v[2].len);
  DENSURE(&z, v[2].len);
  memset(z.buf, 0, v[2].len);
  z.len = d.len = v[2].len;
  seal_initkey(&k, v[0].buf, v[0].len);

  for (i = 0; i < v[2].len; i++) {
    seal_initctx(&c, &k, n);
    seal_encrypt(&c, 0, d.buf, i);
    seal_encrypt(&c, z.buf, d.buf + i, d.len - i);
    if (memcmp(d.buf, v[2].buf, d.len) != 0) {
      ok = 0;
      printf("*** seal failure\n");
      printf("*** k = "); type_hex.dump(&v[0], stdout); putchar('\n');
      printf("*** n = %08lx\n", (unsigned long)n);
      printf("*** i = %i\n", i);
      printf("*** expected = "); type_hex.dump(&v[2], stdout); putchar('\n');
      printf("*** computed = "); type_hex.dump(&d, stdout); putchar('\n');
    }
  }

  dstr_destroy(&d);
  dstr_destroy(&z);

  return (ok);
}

static test_chunk defs[] = {
  { "seal", verify, { &type_hex, &type_uint32, &type_hex, 0 } },
  { 0, 0, { 0 } }
};

int main(int argc, char *argv[])
{
  test_run(argc, argv, defs, SRCDIR"/t/seal");
  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/