udpkey.c: Describe the proposed new forward-secure protocol.

[udpkey] / udpkey.c

/* -*-c-*-
 *
 * Request a key over UDP, or respond to such a request
 *
 * (c) 2012 Mark Wooding
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of udpkey.
 *
 * The udpkey program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * The udpkey program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with udpkey; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

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

#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include <sys/types.h>
#include <sys/time.h>
#include <unistd.h>
#include <fcntl.h>

#include <syslog.h>

#include <sys/socket.h>
#include <arpa/inet.h>
#include <netinet/in.h>
#include <netdb.h>

#include <mLib/alloc.h>
#include <mLib/buf.h>
#include <mLib/daemonize.h>
#include <mLib/dstr.h>
#include <mLib/fdflags.h>
#include <mLib/fwatch.h>
#include <mLib/hex.h>
#include <mLib/mdwopt.h>
#include <mLib/quis.h>
#include <mLib/report.h>
#include <mLib/sub.h>
#include <mLib/tv.h>

#include <catacomb/buf.h>
#include <catacomb/ct.h>
#include <catacomb/dh.h>
#include <catacomb/ec.h>
#include <catacomb/ec-keys.h>
#include <catacomb/gcipher.h>
#include <catacomb/gmac.h>
#include <catacomb/group.h>
#include <catacomb/key.h>
#include <catacomb/mp.h>
#include <catacomb/mprand.h>
#include <catacomb/noise.h>
#include <catacomb/rand.h>

#include <catacomb/rijndael-counter.h>
#include <catacomb/sha256.h>

#ifdef DEBUG
#  define D(x) x
#else
#  define D(x)
#endif

/*---- Static variables ---------------------------------------------------*/

static unsigned flags = 0;
#define f_bogus 1u
#define f_listen 2u
#define f_daemon 4u
#define f_syslog 8u

#define BUFSZ 65536
static unsigned char ibuf[BUFSZ], obuf[BUFSZ];

static key_file *kf;
static const char *kfname = "keyring";
static const char *pidfile;
static fwatch kfwatch;
static unsigned nq;

/*----- Miscellaneous utilities -------------------------------------------*/

/* Resolve NAME, storing the address in *ADDR.  Exit on error. */
static void resolve(const char *name, struct in_addr *addr)
{
  struct hostent *h;

  if ((h = gethostbyname(name)) == 0)
    die(1, "failed to resolve `%s': %s", name, hstrerror(h_errno));
  if (h->h_addrtype != AF_INET)
    die(1, "unexpected address type %d", h->h_addrtype);
  memcpy(addr, h->h_addr, sizeof(struct in_addr));
}

/* Convert PORT to a port number (in host byte order).  Exit on error. */
static unsigned short getport(const char *port)
{
  unsigned long i = 0;
  char *q;
  int e = errno;

  errno = 0;
  if (!isdigit(*port) ||
      (i = strtoul(port, &q, 0)) == 0 ||
      i >= 65536 || *q || errno)
    die(1, "invalid port number `%s'", port);
  errno = e;
  return ((unsigned short)i);
}

/* Read the file named by NAME into a buffer -- or at least an initial
 * portion of it; set *P to the start and *SZ to the length.  Return -1 if it
 * didn't work.  The buffer doesn't need to be freed: the data is stashed in
 * ibuf.
 */
static int snarf(const char *name, void **p, size_t *sz)
{
  ssize_t n;
  int fd;

  if ((fd = open(name, O_RDONLY)) < 0) return (-1);
  n = read(fd, ibuf, sizeof(ibuf));
  close(fd);
  if (n < 0) return (-1);
  *p = ibuf; *sz = n;
  return (0);
}

/* Complain about something.  If f_syslog is set then complain to that;
 * otherwise write to stderr.  Don't use `%m' because that won't work when
 * writing to stderr.
 */
static void PRINTF_LIKE(2, 3) complain(int sev, const char *msg, ...)
{
  va_list ap;

  va_start(ap, msg);
  if (flags & f_syslog)
    vsyslog(sev, msg, ap);
  else {
    fprintf(stderr, "%s: ", QUIS);
    vfprintf(stderr, msg, ap);
    fputc('\n', stderr);
  }
}

/*----- Reading key data --------------------------------------------------*/

struct kinfo {
  group *g;
  ge *X;
  mp *x;
  const gccipher *cc;
  const gcmac *mc; size_t tagsz;
  const gchash *hc;
};

/* Clear a kinfo structure so it can be freed without trouble. */
static void k_init(struct kinfo *k) { k->g = 0; k->x = 0; k->X = 0; }

/* Free a kinfo structure. This is safe on any initialized kinfo
 * structure.
 */
static void k_free(struct kinfo *k)
{
  if (k->X) { G_DESTROY(k->g, k->X); k->X = 0; }
  if (k->x) { MP_DROP(k->x); k->x = 0; }
  if (k->g) { G_DESTROYGROUP(k->g); k->g = 0; }
}

/* Empty macro arguments are forbidden.  But arguments are expended during
 * replacement, not while the call is being processed, so this hack is OK.
 * Unfortunately, if a potentially empty argument is passed on to another
 * macro then it needs to be guarded with a use of EMPTY too...
 */
#define EMPTY

/* Table of key types.  Entries have the form
 *
 *	_(name, NAME, SETGROUP, SETPRIV, SETPUB)
 *
 * The name and NAME are lower- and uppercase names for the type used for
 * constructing various type name constant names.  The code fragment SETGROUP
 * initializes k->g given the name_{pub,priv} structure in p; SETPRIV and
 * SETPUB set up k->x and k->X respectively.  (In this last case, k->X will
 * have been created as a group element already.)
 */
#define KEYTYPES(_)							\
									\
  _(dh, DH,								\
    { k->g = group_prime(&p.dp); },					\
    { k->x = MP_COPY(p.x); },						\
    { if (G_FROMINT(k->g, k->X, p.y)) {					\
	complain(LOG_ERR, "bad public key in `%s'", t->buf);		\
	goto fail;							\
      }									\
    })									\
									\
  _(ec, EC,								\
    { ec_info ei; const char *e;					\
      if ((e = ec_getinfo(&ei, p.cstr)) != 0) {				\
	complain(LOG_ERR, "bad elliptic curve in `%s': %s", t->buf, e);	\
	goto fail;							\
      }									\
      k->g = group_ec(&ei);						\
    },									\
    { k->x = MP_COPY(p.x); },						\
    { if (G_FROMEC(k->g, k->X, &p.p)) {					\
	complain(LOG_ERR, "bad public point in `%s'", t->buf);		\
	goto fail;							\
      }									\
    })

/* Define load_tywhich, where which is `pub' or `priv', to load a public or
 * private key.  Other parameters are as for the KEYTYPES list above.
 */
#define KLOAD(ty, TY, which, WHICH, setgroup, setpriv, setpub)		\
static int load_##ty##which(key_data *kd, struct kinfo *k, dstr *t)	\
{									\
  key_packstruct kps[TY##_##WHICH##FETCHSZ];				\
  key_packdef *kp;							\
  ty##_##which p;							\
  int rc;								\
									\
  /* Extract the key data from the keydata. */				\
  kp = key_fetchinit(ty##_##which##fetch, kps, &p);			\
  if ((rc = key_unpack(kp, kd, t)) != 0) {				\
    complain(LOG_ERR, "failed to unpack key `%s': %s",			\
	     t->buf, key_strerror(rc));					\
    goto fail;								\
  }									\
									\
  /* Extract the components as abstract group elements. */		\
  setgroup;								\
  setpriv;								\
  k->X = G_CREATE(k->g);						\
  setpub;								\
									\
  /* Dispose of stuff we don't need. */					\
  key_fetchdone(kp);							\
  return (0);								\
									\
  /* Tidy up after mishaps. */						\
fail:									\
  k_free(k);								\
  key_fetchdone(kp);							\
  return (-1);								\
}

/* Map over the KEYTYPES to declare the load_tywhich functions using KLOAD
 * above.
 */
#define KEYTYPE_KLOAD(ty, TY, setgroup, setpriv, setpub)		\
  KLOAD(ty, TY, priv, PRIV, setgroup, setpriv,				\
	{ G_EXP(k->g, k->X, k->g->g, k->x); })				\
  KLOAD(ty, TY, pub, PUB, setgroup, { }, setpub)
KEYTYPES(KEYTYPE_KLOAD)

/* Define a table of group key-loading operations. */
struct kload_ops {
  const char *name;
  int (*loadpriv)(key_data *, struct kinfo *, dstr *);
  int (*loadpub)(key_data *, struct kinfo *, dstr *);
};

static const struct kload_ops kload_ops[] = {
#define KEYTYPE_OPS(ty, TY, setgroup, setpriv, setpub)			\
  { #ty, load_##ty##priv, load_##ty##pub },
KEYTYPES(KEYTYPE_OPS)
  { 0 }
};

/* Load a private or public (indicated by PRIVP) key named TAG into a kinfo
 * structure K.  Also fill in the cipher suite selections extracted from the
 * key attributes.
 */
static int loadkey(const char *tag, struct kinfo *k, int privp)
{
  const struct kload_ops *ops;
  dstr d = DSTR_INIT, dd = DSTR_INIT;
  key *ky;
  key_data **kd;
  const char *ty, *p;
  char *q;
  int tsz;
  int rc;

  /* Find the key data. */
  if (key_qtag(kf, tag, &d, &ky, &kd)) {
    complain(LOG_ERR, "unknown key tag `%s'", tag);
    goto fail;
  }

  /* Find the key's group type and locate the group operations. */
  ty = key_getattr(kf, ky, "group");
  if (!ty && strncmp(ky->type, "udpkey-", 7) == 0) ty = ky->type + 7;
  if (!ty) {
    complain(LOG_ERR, "no group type for key %s", d.buf);
    goto fail;
  }
  for (ops = kload_ops; ops->name; ops++) {
    if (strcmp(ty, ops->name) == 0)
      goto found;
  }
  complain(LOG_ERR, "unknown group type `%s' in key %s", ty, d.buf);
  goto fail;

found:
  /* Extract the key data into an appropriately abstract form. */
  k->g = 0; k->x = 0; k->X = 0;
  if ((rc = (privp ? ops->loadpriv : ops->loadpub)(*kd, k, &d)) != 0)
    goto fail;

  /* Extract the chosen symmetric cipher. */
  if ((p = key_getattr(kf, ky, "cipher")) == 0)
    k->cc = &rijndael_counter;
  else if ((k->cc = gcipher_byname(p)) == 0) {
    complain(LOG_ERR, "unknown cipher `%s' in key %s", p, d.buf);
    goto fail;
  }

  /* And the chosen hash function. */
  if ((p = key_getattr(kf, ky, "hash")) == 0)
    k->hc = &sha256;
  else if ((k->hc = ghash_byname(p)) == 0) {
    complain(LOG_ERR, "unknown hash `%s' in key %s", p, d.buf);
    goto fail;
  }

  /* And finally a MAC.  This is more fiddly because we must handle (a)
   * truncation and (b) defaulting based on the hash.
   */
  if ((p = key_getattr(kf, ky, "mac")) == 0)
    dstr_putf(&dd, "%s-hmac", k->hc->name);
  else
    dstr_puts(&dd, p);
  if ((q = strchr(dd.buf, '/')) != 0) *q++ = 0;
  else q = 0;
  if ((k->mc = gmac_byname(dd.buf)) == 0) {
    complain(LOG_ERR, "unknown mac `%s' in key %s", dd.buf, d.buf);
    goto fail;
  }
  if (!q)
    k->tagsz = k->mc->hashsz/2;
  else {
    tsz = atoi(q);
    if (tsz <= 0 || tsz%8 || tsz/8 > k->mc->hashsz) {
      complain(LOG_ERR, "bad tag size `%s' for mac `%s' in key %s",
	       q, k->mc->name, d.buf);
      goto fail;
    }
    k->tagsz = tsz/8;
  }

  /* Done. */
  rc = 0;
  goto done;

fail:
  rc = -1;
done:
  dstr_destroy(&d);
  dstr_destroy(&dd);
  return (rc);
}

static void keymoan(const char *file, int line, const char *err, void *p)
  { complain(LOG_ERR, "%s:%d: %s", file, line, err); }

/* Update the keyring `kf' if the file has been changed since we last looked.
 */
static void kfupdate(void)
{
  key_file *kfnew;

  if (!fwatch_update(&kfwatch, kfname)) return;
  kfnew = CREATE(key_file);
  if (key_open(kfnew, kfname, KOPEN_READ, keymoan, 0)) {
    DESTROY(kfnew);
    return;
  }
  key_close(kf);
  DESTROY(kf);
  kf = kfnew;
}

/*----- Low-level crypto operations ---------------------------------------*/

/* Derive a key, writing its address to *KK and size to *N.  The size is
 * compatible with the keysz rules KSZ.  It is generated for the purpose of
 * keying a WHAT (used for key separation and in error messages), and NAME is
 * the name of the specific instance (e.g., `twofish-counter') from the class
 * name.  The kinfo structure K tells us which algorithms to use for the
 * derivation.  The group elements U and Z are the cryptographic inputs
 * for the derivation.
 *
 * Basically all we do is compute H(what || U || Z).
 */
static int derive(struct kinfo *k, ge *U, ge *Z,
		  const char *what, const char *name, const octet *ksz,
		  octet **kk, size_t *n)
{
  buf b;
  ghash *h;
  octet *p;

  /* Find a suitable key size. */
  if ((*n = keysz(k->hc->hashsz, ksz)) == 0) {
    complain(LOG_ERR,
	     "failed to find suitable key size for %s `%s' and hash `%s'",
	     what, name, k->hc->name);
    return (-1);
  }

  /* Build the hash preimage. */
  buf_init(&b, obuf, sizeof(obuf));
  buf_put(&b, "udpkey-", 7);
  buf_putstrz(&b, what);
  G_TORAW(k->g, &b, U);
  G_TORAW(k->g, &b, Z);
  if (BBAD(&b)) {
    complain(LOG_ERR, "overflow while deriving key (prepare preimage)!");
    return (-1);
  }

  /* Derive the output key. */
  h = GH_INIT(k->hc);
  GH_HASH(h, BBASE(&b), BLEN(&b));
  buf_init(&b, obuf, sizeof(obuf));
  if ((p = buf_get(&b, h->ops->c->hashsz)) == 0) {
    complain(LOG_ERR, "overflow while deriving key (output hash)!");
    GH_DESTROY(h);
    return (-1);
  }
  GH_DONE(h, p);
  GH_DESTROY(h);
  *kk = p;
  return (0);
}

#ifdef DEBUG
static void debug_mp(const char *what, mp *x)
  { fprintf(stderr, "%s: *** ", QUIS); MP_EPRINT(what, x); }
static void debug_ge(const char *what, group *g, ge *X)
{
  fprintf(stderr, "%s: *** %s = ", QUIS, what);
  group_writefile(g, X, stderr);
  fputc('\n', stderr);
}
#endif

/*----- Protocol summary --------------------------------------------------*
 *
 * There are two protocol versions.  The original version works as follows.
 *
 *   * Request
 *	memz		KEYTAG	tag of wanted secret
 *	ge		U	public vector
 *
 *   * Response
 *	ge		V	public vector: V = v P
 *	ge		W	encrypted clue: W = R - Y = r P - v U
 *	mem[TAGSZ]	TAG	MAC tag on ciphertext
 *	mem[KSZ]	CT	secret, encrypted with Z = r X
 *
 * The new version provides forward secrecy, which involves additional flows.
 *
 *   * Greeting
 *	u8		0	marker byte for new protocol
 *	u8		1	packet type
 *	mem8		KEYTAG	wanted secret tag
 *
 *   * Challenge
 *	u8		17	packet type
 *	u32		REF	server's reference
 *	ge		R	public DLIES vector: R = r P
 *	ge		W	masked DH vector: W = V - Y = v P - r X
 *
 *   * Response
 *	u8		0	marker byte for new protocol
 *	u8		2	packet type
 *	mem8		KEYTAG	wanted secret tag
 *	u32		REF	reference from challenge
 *	ge		U	public DH vector
 *	mem[HASHSZ]	H0	hash; H0||H1 = H(U, V, Z), where Z = v U
 *
 *   * Reply
 *	u8		18	packet type
 *	mem[TAGSZ]	TAG	MAC tag on ciphertext
 *	mem[KSZ]	CT	secret, encrypted with H1
 */

#define FWS_GREET 0x01
#define FWS_CHALL 0x11
#define FWS_RESP 0x02
#define FWS_REPLY 0x12

/*----- Listening for requests --------------------------------------------*/

/* Rate limiting parameters.
 *
 * There's a probabilistic rate-limiting mechanism.  A counter starts at 0.
 * Every time we process a request, we increment the counter.  The counter
 * drops by RATE_REFILL every second.  If the counter is below RATE_CREDIT
 * then the request is processed; otherwise it is processed with probability
 * 1/(counter - RATE_CREDIT).
 */
#define RATE_REFILL 10			/* Credits per second. */
#define RATE_CREDIT 1000		/* Initial credit. */

static time_t now;

/* Secrets table.
 *
 * The server doesn't want to maintain state for each client.  Instead, we
 * generate a global secret, and derive per-client secrets from it.  A secret
 * needs to have an expiry time (at which point we won't use it for new
 * requests) and a deletion time (at which point we just forget that it ever
 * existed).  This lets us roll over to a new secret without leaving existing
 * clients completely in the lurch.
 *
 * Secrets are kept in a linked list, ordered by expiry time.  At any given
 * time there is at most one unexpired secret (because we only make a new one
 * when the old one expires).
 */

struct secret {
  struct secret *next;
  uint32 seq;
  time_t t_exp, t_del;
  octet x[32];
};
static struct secret *secrets = 0, *live_secret = 0;
static uint32 next_secret_seq = 0;
#define T_SECEXP 30
#define T_SECDEL 45

static void kill_dead_secrets(void)
{
  struct secret *s = secrets, *ss;

  for (s = secrets; s && s->t_del <= now; s = ss) {
    ss = s->next;
    DESTROY(s);
  }
  secrets = 0;
  if (!s) live_secret = 0;
}

static struct secret *find_secret(uint32 seq)
{
  struct secret *s;

  kill_dead_secrets();
  for (s = secrets; s; s = s->next)
    if (s->seq == seq) return (s);
  return (0);
}

static struct secret *fresh_secret(void)
{
  struct secret *s;

  if (live_secret && live_secret->t_exp > now) return (live_secret);
  kill_dead_secrets();

  s = CREATE(struct secret);
  s->seq = next_secret_seq++;
  s->next = 0;
  rand_get(RAND_GLOBAL, s->x, sizeof(s->x));
  s->t_exp = now + T_SECEXP; s->t_del = now + T_SECDEL;
  if (live_secret) live_secret->next = s;
  else secrets = s;
  live_secret = s;
  return (s);
}

static int fetch_key(const char *tag, struct sockaddr_in *sin,
		     key **ky, struct kinfo *k)
{
  dstr d = DSTR_INIT, dd = DSTR_INIT;
  key_data **kkd;
  char *p, *q;
  const char *pp;
  struct in_addr in;
  int ch, mlen, rc = -1;

  /* Find the key. */
  kfupdate();
  if (key_qtag(kf, tag, &d, ky, &kkd)) {
    complain(LOG_WARNING, "unknown key tag `%s' from %s:%d",
	     tag, inet_ntoa(sin->sin_addr), ntohs(sin->sin_port));
    goto done;
  }

  /* And make sure that it has the right shape. */
  if (((*ky)->k->e & KF_ENCMASK) != KENC_BINARY) {
    complain(LOG_ERR, "key %s is not plain binary data", d.buf);
    goto done;
  }

  /* Find the list of clients, and look up the caller's address in the
   * list.  Entries have the form ADDRESS[/LEN][=TAG] and are separated by
   * `;'.
   */
  if ((pp = key_getattr(kf, *ky, "clients")) == 0) {
    complain(LOG_WARNING,
	     "key %s requested from %s:%d has no `clients' attribute",
	     d.buf, inet_ntoa(sin->sin_addr), ntohs(sin->sin_port));
    goto done;
  }
  dstr_puts(&dd, pp);
  p = dd.buf;
  while (*p) {
    q = p;
    while (isdigit((unsigned char)*q) || *q == '.') q++;
    ch = *q; *q++ = 0;
    if (!inet_aton(p, &in)) goto skip;
    if (ch != '/')
      mlen = 32;
    else {
      p = q;
      while (isdigit((unsigned char)*q)) q++;
      ch = *q; *q++ = 0;
      mlen = atoi(p);
    }
    if (((sin->sin_addr.s_addr ^ in.s_addr) &
	 htonl(0xffffffff << (32 - mlen))) == 0)
      goto match;
  skip:
    if (!ch) break;
    p = q;
    while (*p && *p != ';') p++;
    if (*p) p++;
  }
  complain(LOG_WARNING, "access to key %s denied to %s:%d",
	   d.buf, inet_ntoa(sin->sin_addr), ntohs(sin->sin_port));
  goto done;

match:
  /* Build a tag name for the caller's KEM key, either from the client
   * match or the source address.
   */
  if (ch != '=') {
    DRESET(&dd);
    dstr_puts(&dd, "client-");
    dstr_puts(&dd, inet_ntoa(sin->sin_addr));
    p = dd.buf;
  } else {
    p = q;
    while (*q && *q != ';') q++;
    if (*q == ';') *q++ = 0;
  }

  /* Report the match. */
  complain(LOG_NOTICE, "client %s:%d (`%s') requests key %s",
	   inet_ntoa(sin->sin_addr), ntohs(sin->sin_port), p, d.buf);

  /* Load the KEM key. */
  if (loadkey(p, k, 0)) goto done;
  D( debug_ge("X", k.g, k.X); )

  /* All complete. */
  rc = 0;

done:
  /* Clean everything up. */
  dstr_destroy(&d);
  dstr_destroy(&dd);
  if (rc) k_free(k);
  return (rc);
}

static int respond_v0(buf *bin, buf *bout, struct sockaddr_in *sin)
{
  ge *R = 0, *U = 0, *V = 0, *W = 0, *Y = 0, *Z = 0;
  mp *r = MP_NEW, *v = MP_NEW;
  octet *kk, *t, *tt;
  char *p;
  size_t sz;
  ghash *h = 0;
  gmac *m = 0;
  gcipher *c = 0;
  struct kinfo k;
  key *ky;
  size_t ksz;
  int rc = -1;

  /* Clear out the key state. */
  k_init(&k);

  /* Extract the key tag name. */
  if ((p = buf_getmemz(bin, &sz)) == 0) {
    complain(LOG_WARNING, "invalid key tag from %s:%d",
	     inet_ntoa(sin->sin_addr), ntohs(sin->sin_port));
    goto done;
  }

  /* Find the client's key and check that it's allowed. */
  if (fetch_key(p, sin, &ky, &k)) goto done;

  /* Read the caller's ephemeral key. */
  R = G_CREATE(k.g); W = G_CREATE(k.g);
  U = G_CREATE(k.g); V = G_CREATE(k.g);
  Y = G_CREATE(k.g); Z = G_CREATE(k.g);
  if (G_FROMBUF(k.g, bin, U)) {
    complain(LOG_WARNING, "failed to read ephemeral vector from %s:%d",
	     inet_ntoa(sin->sin_addr), ntohs(sin->sin_port));
    goto done;
  }
  D( debug_ge("U", k.g, U); )
  if (BLEFT(bin)) {
    complain(LOG_WARNING, "trailing junk in request from %s:%d",
	     inet_ntoa(sin->sin_addr), ntohs(sin->sin_port));
    goto done;
  }

  /* Ephemeral Diffie--Hellman.  Choose v in GF(q) at random; compute
   * V = v P and -Y = (-v) U.
   */
  v = mprand_range(v, k.g->r, &rand_global, 0);
  G_EXP(k.g, V, k.g->g, v);
  D( debug_mp("v", v); debug_ge("V", k.g, V); )
    v = mp_sub(v, k.g->r, v);
  G_EXP(k.g, Y, U, v);
  D( debug_ge("-Y", k.g, Y); )

  /* DLIES.  Choose r in GF(q) at random; compute R = r P and Z = r X.  Mask
   * the clue R as W = R - Y.  (Doing the subtraction here makes life easier
   * at the other end, since we can determine -Y by negating v whereas the
   * recipient must subtract vectors which may be less efficient.)
   */
  r = mprand_range(r, k.g->r, &rand_global, 0);
  G_EXP(k.g, R, k.g->g, r);
  D( debug_mp("r", r); debug_ge("R", k.g, R); )
    G_EXP(k.g, Z, k.X, r);
  G_MUL(k.g, W, R, Y);
  D( debug_ge("Z", k.g, Z); debug_ge("W", k.g, W); )

  /* Derive encryption and integrity keys. */
  derive(&k, R, Z, "cipher", k.cc->name, k.cc->keysz, &kk, &ksz);
  c = GC_INIT(k.cc, kk, ksz);
  derive(&k, R, Z, "mac", k.mc->name, k.mc->keysz, &kk, &ksz);
  m = GM_KEY(k.mc, kk, ksz);

  /* Build the ciphertext and compute a MAC tag over it. */
  rc = 0;
  if (G_TOBUF(k.g, bout, V) ||
      G_TOBUF(k.g, bout, W))
    goto done;
  if ((t = buf_get(bout, k.tagsz)) == 0) goto done;
  sz = ky->k->u.k.sz;
  if (BENSURE(bout, sz)) goto done;
  GC_ENCRYPT(c, ky->k->u.k.k, BCUR(bout), sz);
  h = GM_INIT(m);
  GH_HASH(h, BCUR(bout), sz);
  tt = GH_DONE(h, 0); memcpy(t, tt, k.tagsz);
  BSTEP(bout, sz);

done:
  /* Clear everything up and go home. */
  if (R) G_DESTROY(k.g, R);
  if (U) G_DESTROY(k.g, U);
  if (V) G_DESTROY(k.g, V);
  if (W) G_DESTROY(k.g, W);
  if (Y) G_DESTROY(k.g, Y);
  if (Z) G_DESTROY(k.g, Z);
  if (c) GC_DESTROY(c);
  if (m) GM_DESTROY(m);
  if (h) GH_DESTROY(h);
  if (r) MP_DROP(r);
  if (v) MP_DROP(v);
  k_free(&k);
  return (rc);
}

static int dolisten(int argc, char *argv[])
{
  int sk;
  char *p;
  char *aspec;
  ssize_t n;
  fd_set fdin;
  struct sockaddr_in sin;
  socklen_t len;
  buf bin, bout;
  FILE *fp = 0;
  unsigned bucket = 0, toks;
  time_t last = 0;

  /* Set up the socket address. */
  sin.sin_family = AF_INET;
  aspec = xstrdup(argv[0]);
  if ((p = strchr(aspec, ':')) == 0) {
    p = aspec;
    sin.sin_addr.s_addr = INADDR_ANY;
  } else {
    *p++ = 0;
    resolve(aspec, &sin.sin_addr);
  }
  sin.sin_port = htons(getport(p));

  /* Create and set up the socket itself. */
  if ((sk = socket(PF_INET, SOCK_DGRAM, 0)) < 0 ||
      fdflags(sk, O_NONBLOCK, O_NONBLOCK, FD_CLOEXEC, FD_CLOEXEC) ||
      bind(sk, (struct sockaddr *)&sin, sizeof(sin)))
    die(1, "failed to create socket: %s", strerror(errno));

  /* That's enough initialization.  If we should fork, then do that. */
  if (flags & f_daemon) {
    if (pidfile && (fp = fopen(pidfile, "w")) == 0)
      die(1, "failed to open pidfile `%s': %s", pidfile, strerror(errno));
    openlog(QUIS, LOG_PID, LOG_DAEMON);
    if (daemonize())
      die(1, "failed to become background process: %s", strerror(errno));
    if (pidfile) { fprintf(fp, "%ld\n", (long)getpid()); fclose(fp); }
    flags |= f_syslog;
  }

  for (;;) {

    /* Wait for something to happen. */
    FD_ZERO(&fdin);
    FD_SET(sk, &fdin);
    if (select(sk + 1, &fdin, 0, 0, 0) < 0)
      die(1, "select failed: %s", strerror(errno));
    noise_timer(RAND_GLOBAL);

    /* Fetch a packet. */
    len = sizeof(sin);
    n = recvfrom(sk, ibuf, sizeof(ibuf), 0, (struct sockaddr *)&sin, &len);
    if (n < 0) {
      if (errno != EAGAIN && errno != EINTR)
	complain(LOG_ERR, "unexpected receive error: %s", strerror(errno));
      continue;
    }

    /* Refill the bucket, and see whether we should reject this packet. */
    now = time(0);
    if (bucket && now != last) {
      toks = (now - last)*RATE_REFILL;
      bucket = bucket < toks ? 0 : bucket - toks;
    }
    last = now;
    if (bucket > RATE_CREDIT &&
	grand_range(&rand_global, bucket - RATE_CREDIT))
      continue;
    bucket++;

    /* Set up the input buffer for parsing the request. */
    buf_init(&bin, ibuf, n);
    buf_init(&bout, obuf, sizeof(obuf));

    /* Handle the client's message. */
    if (respond_v0(&bin, &bout, &sin)) continue;

    /* Send the reply packet back to the caller. */
    if (!BOK(&bout)) goto bad;
    if (sendto(sk, BBASE(&bout), BLEN(&bout), 0,
	       (struct sockaddr *)&sin, len) < 0) {
      complain(LOG_ERR, "failed to send response to %s:%d: %s",
	       inet_ntoa(sin.sin_addr), ntohs(sin.sin_port),
	       strerror(errno));
      continue;
    }

    continue;

  bad:
    /* Report a problem building the reply. */
    complain(LOG_ERR, "failed to construct response to %s:%d",
	     inet_ntoa(sin.sin_addr), ntohs(sin.sin_port));
  }

  return (-1);
}

/*----- Sending requests and processing responses -------------------------*/

struct query {
  struct query *next;
  const char *tag;
  octet *k;
  size_t sz;
  struct server *s;
};

struct server {
  struct server *next;
  struct sockaddr_in sin;
  struct kinfo k;
  const struct client_protocol *proto;
  mp *u;
  ge *U;
  octet *h;
};

struct client_protocol {
  const char *name;
  int (*setup)(struct query *, struct server *);
  int (*receive)(struct query *, struct server *, buf *, buf *);
  int (*retransmit)(struct query *, struct server *, buf *);
};

/* Record a successful fetch of key material for a query Q.  The data starts
 * at K and is SZ bytes long.  The data is copied: it's safe to overwrite it.
 */
static int donequery(struct query *q, struct server *s,
		      const void *k, size_t sz)
{
  octet *tt;
  ghash *h = 0;
  int diffp;

  /* If we have a hash, check that the fragment matches it. */
  if (s && s->h) {
    h = GH_INIT(s->k.hc);
    GH_HASH(h, k, sz);
    tt = GH_DONE(h, 0);
    diffp = memcmp(tt, s->h, h->ops->c->hashsz);
    GH_DESTROY(h);
    if (diffp) {
      moan("response from %s:%d doesn't match hash",
	   inet_ntoa(s->sin.sin_addr), ntohs(s->sin.sin_port));
      return (-1);
    }
  }

  /* Stash a copy of the key fragment for later. */
  q->k = xmalloc(sz);
  memcpy(q->k, k, sz);
  q->sz = sz; nq--;

  /* All good. */
  return (0);
}

static int setup_v0(struct query *q, struct server *s)
{
  /* Choose an ephemeral private key u.  Let x be our private key.  We
   * compute U = u P and transmit this.
   */
  s->u = mprand_range(MP_NEW, s->k.g->r, &rand_global, 0);
  s->U = G_CREATE(s->k.g);
  G_EXP(s->k.g, s->U, s->k.g->g, s->u);
  D( debug_mp("u", s->u); debug_ge("U", s->k.g, s->U); )

  return (0);
}

static int retransmit_v0(struct query *q, struct server *s, buf *bout)
{
  buf_putstrz(bout, q->tag);
  G_TOBUF(s->k.g, bout, s->U);
  return (0);
}

static int receive_v0(struct query *q, struct server *s, buf *bin, buf *bout)
{
  ge *R, *V = 0, *W = 0, *Y = 0, *Z = 0;
  octet *kk, *t, *tt;
  gcipher *c = 0;
  gmac *m = 0;
  ghash *h = 0;
  size_t n, ksz;
  octet *p;
  int rc = -1;

  R = G_CREATE(s->k.g);
  V = G_CREATE(s->k.g); W = G_CREATE(s->k.g);
  Y = G_CREATE(s->k.g); Z = G_CREATE(s->k.g);
  if (G_FROMBUF(s->k.g, bin, V)) {
    moan("invalid Diffie--Hellman vector from %s:%d",
	 inet_ntoa(s->sin.sin_addr), ntohs(s->sin.sin_port));
    goto done;
  }
  if (G_FROMBUF(s->k.g, bin, W)) {
    moan("invalid clue vector from %s:%d",
	 inet_ntoa(s->sin.sin_addr), ntohs(s->sin.sin_port));
    goto done;
  }
  D( debug_ge("V", s->k.g, V); debug_ge("W", s->k.g, W); )

  /* We have V and W from the server; determine Y = u V, R = W + Y and
   * Z = x R, and then derive the symmetric keys.
   */
  G_EXP(s->k.g, Y, V, s->u);
  G_MUL(s->k.g, R, W, Y);
  G_EXP(s->k.g, Z, R, s->k.x);
  D( debug_ge("R", s->k.g, R);
     debug_ge("Y", s->k.g, Y);
     debug_ge("Z", s->k.g, Z); )
  derive(&s->k, R, Z, "cipher", s->k.cc->name, s->k.cc->keysz, &kk, &ksz);
  c = GC_INIT(s->k.cc, kk, ksz);
  derive(&s->k, R, Z, "mac", s->k.cc->name, s->k.cc->keysz, &kk, &ksz);
  m = GM_KEY(s->k.mc, kk, ksz);

  /* Find where the MAC tag is. */
  if ((t = buf_get(bin, s->k.tagsz)) == 0) {
    moan("missing tag from %s:%d",
	 inet_ntoa(s->sin.sin_addr), ntohs(s->sin.sin_port));
    goto done;
  }

  /* Check the integrity of the ciphertext against the tag. */
  p = BCUR(bin); n = BLEFT(bin);
  h = GM_INIT(m);
  GH_HASH(h, p, n);
  tt = GH_DONE(h, 0);
  if (!ct_memeq(t, tt, s->k.tagsz)) {
    moan("incorrect tag from %s:%d",
	 inet_ntoa(s->sin.sin_addr), ntohs(s->sin.sin_port));
    goto done;
  }

  /* Decrypt the result and declare this server done. */
  GC_DECRYPT(c, p, p, n);
  rc = donequery(q, s, p, n);

done:
  /* Clear up and go home. */
  if (R) G_DESTROY(s->k.g, R);
  if (V) G_DESTROY(s->k.g, V);
  if (W) G_DESTROY(s->k.g, W);
  if (Y) G_DESTROY(s->k.g, Y);
  if (Z) G_DESTROY(s->k.g, Z);
  if (c) GC_DESTROY(c);
  if (m) GM_DESTROY(m);
  if (h) GH_DESTROY(h);
  return (rc);
}

static const struct client_protocol prototab[] = {
  { "v0", setup_v0, receive_v0, retransmit_v0 },
  { 0 }
};

/* Initialize a query to a remote server. */
static struct query *qinit_net(const char *tag, const char *spec)
{
  struct query *q;
  struct server *s, **stail;
  dstr d = DSTR_INIT, dd = DSTR_INIT;
  const struct client_protocol *proto;
  hex_ctx hc;
  char *p, *pp, ch;

  /* Allocate the query block. */
  q = CREATE(struct query);
  q->tag = tag;
  stail = &q->s;

  /* Put the spec somewhere we can hack at it. */
  dstr_puts(&d, spec);
  p = d.buf;

  /* Parse the query spec.  Entries have the form ADDRESS:PORT[=TAG][#HASH]
   * and are separated by `;'.
   */
  while (*p) {

    /* Allocate a new server node. */
    s = CREATE(struct server);
    s->sin.sin_family = AF_INET;

    /* Extract the server address. */
    if ((pp = strchr(p, ':')) == 0)
      die(1, "invalid syntax: missing `:PORT'");
    *pp++ = 0;
    resolve(p, &s->sin.sin_addr);

    /* Extract the port number. */
    p = pp;
    while (isdigit((unsigned char)*pp)) pp++;
    ch = *pp; *pp++ = 0;
    s->sin.sin_port = htons(getport(p));

    /* See if there's a protocol name. */
    if (ch != '?')
      p = "v0";
    else {
      p = pp;
      pp += strcspn(pp, ";#=");
      ch = *pp; *pp++ = 0;
    }
    for (proto = prototab; proto->name; proto++)
      if (strcmp(proto->name, p) == 0) goto found_proto;
    die(1, "unknown protocol name `%s'", p);
  found_proto:
    s->proto = proto;

    /* If there's a key tag then extract that; otherwise use a default. */
    if (ch != '=')
      p = "udpkey-kem";
    else {
      p = pp;
      pp += strcspn(pp, ";#");
      ch = *pp; *pp++ = 0;
    }
    if (loadkey(p, &s->k, 1)) exit(1);
    D( debug_mp("x", s->k.x); debug_ge("X", s->k.g, s->k.X); )

    /* Link the server on. */
    *stail = s; stail = &s->next;

    /* If there's a trailing hash then extract it. */
    if (ch != '#')
      s->h = 0;
    else {
      p = pp;
      while (*pp == '-' || isxdigit((unsigned char)*pp)) pp++;
      hex_init(&hc);
      DRESET(&dd);
      hex_decode(&hc, p, pp - p, &dd);
      if (dd.len != s->k.hc->hashsz) die(1, "incorrect hash length");
      s->h = xmalloc(dd.len);
      memcpy(s->h, dd.buf, dd.len);
      ch = *pp++;
    }

    /* Initialize the protocol. */
    if (s->proto->setup(q, s)) die(1, "failed to initialize protocol");

    /* If there are more servers, then continue parsing. */
    if (!ch) break;
    else if (ch != ';') die(1, "invalid syntax: expected `;'");
    p = pp;
  }

  /* Terminate the server list and return. */
  *stail = 0;
  q->k = 0;
  dstr_destroy(&d);
  dstr_destroy(&dd);
  return (q);
}

/* Handle a `query' to a local file. */
static struct query *qinit_file(const char *tag, const char *file)
{
  struct query *q;
  void *k;
  size_t sz;

  /* Snarf the file. */
  q = CREATE(struct query);
  if (snarf(file, &k, &sz))
    die(1, "failed to read `%s': %s", file, strerror(errno));
  q->s = 0;
  donequery(q, 0, k, sz);
  return (q);
}

/* Retransmission and timeout parameters. */
#define TO_NEXT(t) (((t) + 2)*4/3)	/* Timeout growth function */
#define TO_MAX 30			/* When to give up */

static int doquery(int argc, char *argv[])
{
  struct query *q = 0, *qq, **qtail = &qq;
  struct server *s = 0;
  const char *tag = argv[0];
  octet *p;
  int i;
  int sk;
  fd_set fdin;
  struct timeval now, when, tv;
  struct sockaddr_in sin;
  socklen_t len;
  unsigned next = 0;
  buf bin, bout;
  size_t n, j;
  ssize_t nn;

  /* Create a socket.  We just use the one socket for everything.  We don't
   * care which port we get allocated.
   */
  if ((sk = socket(PF_INET, SOCK_DGRAM, 0)) < 0 ||
      fdflags(sk, O_NONBLOCK, O_NONBLOCK, FD_CLOEXEC, FD_CLOEXEC))
    die(1, "failed to create socket: %s", strerror(errno));

  /* Parse the query target specifications.  The adjustments of `nq' aren't
   * in the right order but that doesn't matter.
   */
  for (i = 1; i < argc; i++) {
    if (*argv[i] == '.' || *argv[i] == '/') q = qinit_file(tag, argv[i]);
    else if (strchr(argv[i], ':')) q = qinit_net(tag, argv[i]);
    else die(1, "unrecognized query target `%s'", argv[i]);
    *qtail = q; qtail = &q->next; nq++;
  }
  *qtail = 0;

  /* Find the current time so we can compute retransmission times properly.
   */
  gettimeofday(&now, 0);
  when = now;

  /* Continue retransmitting until we have all the answers. */
  while (nq) {

    /* Work out when we next want to wake up. */
    if (TV_CMP(&now, >=, &when)) {
      do {
	if (next >= TO_MAX) die(1, "no responses: giving up");
	next = TO_NEXT(next);
	TV_ADDL(&when, &when, next, 0);
      } while (TV_CMP(&when, <=, &now));
      for (q = qq; q; q = q->next) {
	if (q->k) continue;
	for (s = q->s; s; s = s->next) {
	  buf_init(&bout, obuf, sizeof(obuf));
	  if (s->proto->retransmit(q, s, &bout)) continue;
	  if (BBAD(&bout)) {
	    moan("overflow while constructing request!");
	    continue;
	  }
	  sendto(sk, BBASE(&bout), BLEN(&bout), 0,
		 (struct sockaddr *)&s->sin, sizeof(s->sin));
	}
      }
    }

    /* Wait until something interesting happens. */
    FD_ZERO(&fdin);
    FD_SET(sk, &fdin);
    TV_SUB(&tv, &when, &now);
    if (select(sk + 1, &fdin, 0, 0, &tv) < 0)
      die(1, "select failed: %s", strerror(errno));
    gettimeofday(&now, 0);

    /* If we have an input event, process incoming packets. */
    if (FD_ISSET(sk, &fdin)) {
      for (;;) {

	/* Read a packet and capture its address. */
	len = sizeof(sin);
	nn = recvfrom(sk, ibuf, sizeof(ibuf), 0,
		      (struct sockaddr *)&sin, &len);
	if (nn < 0) {
	  if (errno == EAGAIN) break;
	  else if (errno == EINTR) continue;
	  else {
	    moan("error receiving reply: %s", strerror(errno));
	    continue;
	  }
	}

	/* See whether this corresponds to any of our servers.  Don't just
	 * check the active servers, since this may be late a reply caused by
	 * retransmissions or similar.
	 */
	for (q = qq; q; q = q->next) {
	  for (s = q->s; s; s = s->next) {
	    if (s->sin.sin_addr.s_addr == sin.sin_addr.s_addr &&
		s->sin.sin_port == sin.sin_port)
	      goto found;
	  }
	}
	moan("received reply from unexpected source %s:%d",
	     inet_ntoa(sin.sin_addr), ntohs(sin.sin_port));
	continue;

      found:
	/* If the query we found has now been satisfied, ignore this packet.
	 */
	if (q->k) continue;

	/* Parse the reply, and either finish the job or get a message to
	 * send back to the server.
	 */
	buf_init(&bin, ibuf, nn);
	buf_init(&bout, obuf, sizeof(obuf));
	if (s->proto->receive(q, s, &bin, &bout)) continue;
	if (q->k) continue;
	if (!BLEN(&bout) && s->proto->retransmit(q, s, &bout)) continue;
	if (BBAD(&bout)) {
	  moan("overflow while constructing request!");
	  continue;
	}
	sendto(sk, BBASE(&bout), BLEN(&bout), 0,
	       (struct sockaddr *)&s->sin, sizeof(s->sin));
      }
    }
  }

  /* Check that all of the responses match up and XOR them together. */
  n = qq->sz;
  if (n > BUFSZ) die(1, "response too large");
  memset(obuf, 0, n);
  for (q = qq; q; q = q->next) {
    if (!q->k) die(1, "INTERNAL: query not complete");
    if (q->sz != n) die(1, "inconsistent response sizes");
    for (j = 0; j < n; j++) obuf[j] ^= q->k[j];
  }

  /* Write out the completed answer. */
  p = obuf;
  while (n) {
    if ((nn = write(STDOUT_FILENO, p, n)) < 0)
      die(1, "error writing response: %s", strerror(errno));
    p += nn; n -= nn;
  }
  return (0);
}

/*----- Main program ------------------------------------------------------*/

static void usage(FILE *fp)
{
  pquis(fp, "Usage: \n\
	$ [-OPTS] LABEL {ADDR:PORT[=TAG][#HASH];... | FILE} ...\n\
	$ [-OPTS] -l [ADDR:]PORT\n\
");
}

static void version(FILE *fp)
  { pquis(fp, "$, version " VERSION "\n"); }

static void help(FILE *fp)
{
  version(fp);
  putc('\n', fp);
  usage(fp);
  fputs("\n\
Options:\n\
\n\
  -d, --daemon		Run in the background while listening.\n\
  -k, --keyring=FILE	Read keys from FILE. [default = `keyring']\n\
  -l, --listen		Listen for incoming requests and serve keys.\n\
  -p, --pidfile=FILE	Write process id to FILE if in daemon mode.\n\
  -r, --random=FILE	Key random number generator with contents of FILE.\n\
", fp);
}

int main(int argc, char *argv[])
{
  int argmin, argmax;
  void *k;
  size_t sz;

  ego(argv[0]);
  for (;;) {
    static const struct option opts[] = {
      { "help",			0,		0,	'h' },
      { "version",		0,		0,	'v' },
      { "usage",		0,		0,	'u' },
      { "daemon",		0,		0,	'd' },
      { "keyfile",		OPTF_ARGREQ,	0,	'k' },
      { "listen",		0,		0,	'l' },
      { "pidfile",		OPTF_ARGREQ,	0,	'p' },
      { "random",		OPTF_ARGREQ,	0,	'r' },
      { 0 }
    };

    int i = mdwopt(argc, argv, "hvu" "dk:lp:r:", opts, 0, 0, 0);
    if (i < 0) break;

    switch (i) {
      case 'h': help(stdout); exit(0);
      case 'v': version(stdout); exit(0);
      case 'u': usage(stdout); exit(0);

      case 'd': flags |= f_daemon; break;
      case 'k': kfname = optarg; break;
      case 'l': flags |= f_listen; break;
      case 'p': pidfile = optarg; break;
      case 'r':
	if (snarf(optarg, &k, &sz))
	  die(1, "failed to read `%s': %s", optarg, strerror(errno));
	rand_key(RAND_GLOBAL, k, sz);
	break;

      default: flags |= f_bogus; break;
    }
  }

  argv += optind; argc -= optind;
  if (flags & f_listen) argmin = argmax = 1;
  else argmin = 2, argmax = -1;
  if ((flags & f_bogus) || argc < argmin || (argmax >= 0 && argc > argmax))
    { usage(stderr); exit(1); }

  fwatch_init(&kfwatch, kfname);
  kf = CREATE(key_file);
  if (key_open(kf, kfname, KOPEN_READ, keymoan, 0))
    die(1, "failed to open keyring file `%s'", kfname);

  rand_noisesrc(RAND_GLOBAL, &noise_source);
  rand_seed(RAND_GLOBAL, 512);

  if (flags & f_listen) return dolisten(argc, argv);
  else return doquery(argc, argv);
}

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