[u/mdw/catacomb] / key-binary.c

/* -*-c-*-
 *
 * $Id: key-binary.c,v 1.6 2004/04/08 01:03:22 mdw Exp $
 *
 * Key binary encoding
 *
 * (c) 1999 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.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: key-binary.c,v $
 * Revision 1.6  2004/04/08 01:03:22  mdw
 * Force subkeys to be sorted in structured keys.
 *
 * Revision 1.5  2004/04/01 12:50:09  mdw
 * Add cyclic group abstraction, with test code.  Separate off exponentation
 * functions for better static linking.  Fix a buttload of bugs on the way.
 * Generally ensure that negative exponents do inversion correctly.  Add
 * table of standard prime-field subgroups.  (Binary field subgroups are
 * currently unimplemented but easy to add if anyone ever finds a good one.)
 *
 * Revision 1.4  2004/03/28 01:58:47  mdw
 * Generate, store and retreive elliptic curve keys.
 *
 * Revision 1.3  2001/02/03 11:57:00  mdw
 * Track mLib change: symbols no longer need to include a terminating
 * null.
 *
 * Revision 1.2  2000/06/17 11:25:20  mdw
 * Use secure memory interface from MP library.
 *
 * Revision 1.1  2000/02/12 18:21:02  mdw
 * Overhaul of key management (again).
 *
 */

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

#include <stdlib.h>
#include <string.h>

#include <mLib/bits.h>
#include <mLib/dstr.h>
#include <mLib/sub.h>
#include <mLib/sym.h>

#include "key-data.h"
#include "mp.h"
#include "mptext.h"

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

/* --- @key_decode@ --- *
 *
 * Arguments:	@const void *p@ = pointer to buffer to read
 *		@size_t sz@ = size of the buffer
 *		@key_data *k@ = pointer to key data block to write to
 *
 * Returns:	Zero if everything worked, nonzero otherwise.
 *
 * Use:		Decodes a binary representation of a key.
 */

int key_decode(const void *p, size_t sz, key_data *k)
{
  const octet *q = p;
  size_t psz;
  unsigned e;

  /* --- Parse the header information --- *
   *
   * Make sure the size matches external reality.  Security holes have been
   * known to creep in without this sort of check.  (No, this isn't an after-
   * the-fact patch-up.)
   */

  e = LOAD16(q);
  psz = LOAD16(q + 2);
  if (psz + 4 > sz)
    return (-1);
  k->e = e;

  /* --- Now decide what to do --- */

  switch (e & KF_ENCMASK) {

    /* --- Plain binary data --- */

    case KENC_BINARY:
    case KENC_ENCRYPT:
      k->u.k.k = sub_alloc(psz);
      memcpy(k->u.k.k, q + 4, psz);
      k->u.k.sz = psz;
      break;

    /* --- Multiprecision integer data --- */

    case KENC_MP:
      k->u.m = mp_loadb(k->e & KF_BURN ? MP_NEWSEC : MP_NEW, q + 4, psz);
      break;

    /* --- String data --- */

    case KENC_STRING:
      k->u.p = xmalloc(sz + 1);
      memcpy(k->u.p, q + 4, sz);
      k->u.p[sz] = 0;
      break;

    /* --- Elliptic curve point data --- */

    case KENC_EC: {
      size_t xsz, ysz;
      EC_CREATE(&k->u.e);
      if (!sz) break;
      if (sz < 2) return (-1);
      xsz = LOAD16(q + 4);
      if (sz < xsz + 4) return (-1);
      ysz = LOAD16(q + 6 + xsz);
      if (sz < xsz + ysz + 4) return (-1);
      k->u.e.x = mp_loadb(MP_NEW, q + 6, xsz);
      k->u.e.y = mp_loadb(MP_NEW, q + 6 + xsz, ysz);
    } break;

    /* --- Structured key data --- */

    case KENC_STRUCT: {
      dstr d = DSTR_INIT;
      key_struct *ks;
      unsigned f;

      if ((k->e & ~KF_ENCMASK) || (psz & 3))
	return (-1);
      q += 4;
      sym_create(&k->u.s);

      while (psz) {

	/* --- Read the tag string --- */

	DRESET(&d);
	sz = LOAD8(q);
	if (sz >= psz)
	  goto fail;
	DPUTM(&d, q + 1, sz);
	DPUTZ(&d);
	sz = (sz + 4) & ~3;
	q += sz; psz -= sz;

	/* --- Read the encoding and size --- */

	e = LOAD16(q);
	sz = (LOAD16(q + 2) + 7) & ~3;
	if (sz > psz)
	  goto fail;

	/* --- Create a table node and fill it in --- */

	ks = sym_find(&k->u.s, d.buf, d.len, sizeof(*ks), &f);
	if (f)
	  goto fail;
	if (key_decode(q, sz, &ks->k)) {
	  sym_remove(&k->u.s, ks);
	  goto fail;
	}
	psz -= sz;
	q += sz;
      }
      dstr_destroy(&d);
      break;

      /* --- Tidy up after a failure --- */

    fail:
      dstr_destroy(&d);
      key_destroy(k);
      return (-1);
    } break;

    /* --- Everything else --- */

    default:
      return (-1);
  }

  /* --- OK, that was good --- */

  return (0);
}

/* --- @key_encode@ --- *
 *
 * Arguments:	@key_data *k@ = pointer to key data block
 *		@dstr *d@ = pointer to destination string
 *		@const key_filter *kf@ = pointer to key selection block
 *
 * Returns:	Nonzero if an item was actually written.
 *
 * Use:		Encodes a key block as binary data.
 */

static int ksbyname(const void *a, const void *b) {
  key_struct *const *x = a, *const *y = b;
  return (strcmp(SYM_NAME(*x), SYM_NAME(*y)));
}

int key_encode(key_data *k, dstr *d, const key_filter *kf)
{
  int rc = 0;
  if (!KEY_MATCH(k, kf))
    return (0);
  switch (k->e & KF_ENCMASK) {
    case KENC_BINARY:
    case KENC_ENCRYPT: {
      char *p;

      DENSURE(d, (k->u.k.sz + 7) & ~3);
      p = d->buf + d->len;
      STORE16(p, k->e);
      STORE16(p + 2, k->u.k.sz);
      d->len += 4;
      DPUTM(d, k->u.k.k, k->u.k.sz);
      rc = 1;
    } break;

    case KENC_MP: {
      char *p;
      size_t sz = mp_octets(k->u.m);

      DENSURE(d, (sz + 7) & ~3);
      p = d->buf + d->len;
      STORE16(p, k->e);
      STORE16(p + 2, sz);
      mp_storeb(k->u.m, p + 4, sz);
      d->len += sz + 4;
      rc = 1;
    } break;

    case KENC_STRING: {
      char *p;
      size_t sz = strlen(k->u.p);

      DENSURE(d, (sz + 7) & ~3);
      p = d->buf + d->len;
      STORE16(p, k->e);
      STORE16(p + 2, sz);
      memcpy(p + 4, k->u.p, sz);
      d->len += sz + 4;
      rc = 1;
    } break;

    case KENC_EC: {
      char *p;
      size_t xsz = 0, ysz = 0;
      size_t sz;

      if (EC_ATINF(&k->u.e))
	sz = 0;
      else {
	xsz = mp_octets(k->u.e.x);
	ysz = mp_octets(k->u.e.y);
	sz = xsz + ysz + 4;
      }
      DENSURE(d, (sz + 7) & ~3);
      p = d->buf + d->len;
      STORE16(p, k->e);
      STORE16(p + 2, sz);
      if (!EC_ATINF(&k->u.e)) {
	STORE16(p + 4, xsz);
	mp_storeb(k->u.e.x, p + 6, xsz);
	STORE16(p + 6 + xsz, ysz);
	mp_storeb(k->u.e.y, p + 8 + xsz, ysz);
      }
      d->len += sz + 4;
      rc = 1;
    } break;

    case KENC_STRUCT: {
      size_t n;
      char *p;
      key_struct *ks, **ksv;
      size_t nks, j;
      sym_iter i;

      n = d->len;
      DENSURE(d, 4);
      p = d->buf + n;
      STORE16(p, k->e & KF_ENCMASK);
      d->len += 4;
      
      for (nks = 0, sym_mkiter(&i, &k->u.s);
	   (ks = sym_next(&i)) != 0;
	   nks++);
      if (nks) {
	ksv = xmalloc(nks * sizeof(*ksv));
	for (j = 0, sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; j++)
	  ksv[j] = ks;
	qsort(ksv, nks, sizeof(*ksv), ksbyname);
	for (j = 0; j < nks; j++) {
	  size_t o = d->len;
	  ks = ksv[j];
	  DENSURE(d, 1);
	  *(octet *)(d->buf + d->len++) = strlen(SYM_NAME(ks));
	  DPUTS(d, SYM_NAME(ks));
	  while (d->len & 3)
	    DPUTC(d, 0);
	  if (key_encode(&ks->k, d, kf))
	    rc = 1;
	  else
	    d->len = o;
	}
	xfree(ksv);
      }
      if (!rc)
        d->len = n;
      else {
	p = d->buf + n + 2;
	n = d->len - n - 4;
	STORE16(p,  n);
      }
    } break;
  }
  while (d->len & 3)
    DPUTC(d, 0);
  return (rc);
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
052b36d0	1	/* --c--
052b36d0	2	*
898a4e25	3	* $Id: key-binary.c,v 1.6 2004/04/08 01:03:22 mdw Exp $
052b36d0	4	*
	5	* Key binary encoding
	6	*
	7	* (c) 1999 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: key-binary.c,v $
898a4e25	33	* Revision 1.6 2004/04/08 01:03:22 mdw
	34	* Force subkeys to be sorted in structured keys.
	35	*
34e4f738	36	* Revision 1.5 2004/04/01 12:50:09 mdw
	37	* Add cyclic group abstraction, with test code. Separate off exponentation
	38	* functions for better static linking. Fix a buttload of bugs on the way.
	39	* Generally ensure that negative exponents do inversion correctly. Add
	40	* table of standard prime-field subgroups. (Binary field subgroups are
	41	* currently unimplemented but easy to add if anyone ever finds a good one.)
	42	*
1ba83484	43	* Revision 1.4 2004/03/28 01:58:47 mdw
	44	* Generate, store and retreive elliptic curve keys.
	45	*
0d4a06cd	46	* Revision 1.3 2001/02/03 11:57:00 mdw
	47	* Track mLib change: symbols no longer need to include a terminating
	48	* null.
	49	*
99163693	50	* Revision 1.2 2000/06/17 11:25:20 mdw
	51	* Use secure memory interface from MP library.
	52	*
052b36d0	53	* Revision 1.1 2000/02/12 18:21:02 mdw
	54	* Overhaul of key management (again).
	55	*
	56	*/
	57
	58	/----- Header files ------------------------------------------------------/
	59
	60	#include <stdlib.h>
	61	#include <string.h>
	62
	63	#include <mLib/bits.h>
	64	#include <mLib/dstr.h>
	65	#include <mLib/sub.h>
	66	#include <mLib/sym.h>
	67
	68	#include "key-data.h"
	69	#include "mp.h"
	70	#include "mptext.h"
	71
	72	/----- Main code ---------------------------------------------------------/
	73
	74	/* --- @key_decode@ --- *
	75	*
	76	* Arguments: @const void *p@ = pointer to buffer to read
	77	* @size_t sz@ = size of the buffer
	78	* @key_data *k@ = pointer to key data block to write to
	79	*
	80	* Returns: Zero if everything worked, nonzero otherwise.
	81	*
	82	* Use: Decodes a binary representation of a key.
	83	*/
	84
	85	int key_decode(const void p, size_t sz, key_data k)
	86	{
	87	const octet *q = p;
	88	size_t psz;
	89	unsigned e;
	90
	91	/* --- Parse the header information --- *
	92	*
	93	* Make sure the size matches external reality. Security holes have been
	94	* known to creep in without this sort of check. (No, this isn't an after-
	95	* the-fact patch-up.)
	96	*/
	97
	98	e = LOAD16(q);
	99	psz = LOAD16(q + 2);
	100	if (psz + 4 > sz)
	101	return (-1);
	102	k->e = e;
	103
	104	/* --- Now decide what to do --- */
	105
	106	switch (e & KF_ENCMASK) {
	107
	108	/* --- Plain binary data --- */
	109
	110	case KENC_BINARY:
	111	case KENC_ENCRYPT:
	112	k->u.k.k = sub_alloc(psz);
	113	memcpy(k->u.k.k, q + 4, psz);
	114	k->u.k.sz = psz;
	115	break;
	116
117	/* --- Multiprecision integer data --- */
118
119	case KENC_MP:
99163693	120	k->u.m = mp_loadb(k->e & KF_BURN ? MP_NEWSEC : MP_NEW, q + 4, psz);
052b36d0	121	break;
052b36d0	122
1ba83484	123	/* --- String data --- */
	124
	125	case KENC_STRING:
	126	k->u.p = xmalloc(sz + 1);
	127	memcpy(k->u.p, q + 4, sz);
	128	k->u.p[sz] = 0;
	129	break;
	130
	131	/* --- Elliptic curve point data --- */
	132
	133	case KENC_EC: {
	134	size_t xsz, ysz;
34e4f738	135	EC_CREATE(&k->u.e);
34e4f738	136	if (!sz) break;
1ba83484	137	if (sz < 2) return (-1);
	138	xsz = LOAD16(q + 4);
	139	if (sz < xsz + 4) return (-1);
	140	ysz = LOAD16(q + 6 + xsz);
	141	if (sz < xsz + ysz + 4) return (-1);
1ba83484	142	k->u.e.x = mp_loadb(MP_NEW, q + 6, xsz);
	143	k->u.e.y = mp_loadb(MP_NEW, q + 6 + xsz, ysz);
	144	} break;
	145
052b36d0	146	/* --- Structured key data --- */
	147
	148	case KENC_STRUCT: {
	149	dstr d = DSTR_INIT;
	150	key_struct *ks;
	151	unsigned f;
	152
	153	if ((k->e & ~KF_ENCMASK) \|\| (psz & 3))
	154	return (-1);
	155	q += 4;
	156	sym_create(&k->u.s);
	157
	158	while (psz) {
	159
	160	/* --- Read the tag string --- */
	161
	162	DRESET(&d);
	163	sz = LOAD8(q);
	164	if (sz >= psz)
	165	goto fail;
	166	DPUTM(&d, q + 1, sz);
	167	DPUTZ(&d);
	168	sz = (sz + 4) & ~3;
	169	q += sz; psz -= sz;
	170
	171	/* --- Read the encoding and size --- */
	172
	173	e = LOAD16(q);
	174	sz = (LOAD16(q + 2) + 7) & ~3;
	175	if (sz > psz)
	176	goto fail;
	177
	178	/* --- Create a table node and fill it in --- */
	179
0d4a06cd	180	ks = sym_find(&k->u.s, d.buf, d.len, sizeof(*ks), &f);
052b36d0	181	if (f)
	182	goto fail;
	183	if (key_decode(q, sz, &ks->k)) {
	184	sym_remove(&k->u.s, ks);
	185	goto fail;
	186	}
	187	psz -= sz;
	188	q += sz;
	189	}
	190	dstr_destroy(&d);
	191	break;
	192
	193	/* --- Tidy up after a failure --- */
	194
	195	fail:
	196	dstr_destroy(&d);
	197	key_destroy(k);
	198	return (-1);
	199	} break;
	200
	201	/* --- Everything else --- */
	202
	203	default:
	204	return (-1);
	205	}
	206
	207	/* --- OK, that was good --- */
	208
	209	return (0);
	210	}
	211
	212	/* --- @key_encode@ --- *
	213	*
	214	* Arguments: @key_data *k@ = pointer to key data block
	215	* @dstr *d@ = pointer to destination string
	216	* @const key_filter *kf@ = pointer to key selection block
	217	*
	218	* Returns: Nonzero if an item was actually written.
	219	*
	220	* Use: Encodes a key block as binary data.
	221	*/
	222
898a4e25	223	static int ksbyname(const void a, const void b) {
	224	key_struct const x = a, const y = b;
	225	return (strcmp(SYM_NAME(x), SYM_NAME(y)));
	226	}
	227
052b36d0	228	int key_encode(key_data k, dstr d, const key_filter *kf)
	229	{
	230	int rc = 0;
	231	if (!KEY_MATCH(k, kf))
	232	return (0);
	233	switch (k->e & KF_ENCMASK) {
	234	case KENC_BINARY:
	235	case KENC_ENCRYPT: {
	236	char *p;
	237
	238	DENSURE(d, (k->u.k.sz + 7) & ~3);
	239	p = d->buf + d->len;
	240	STORE16(p, k->e);
	241	STORE16(p + 2, k->u.k.sz);
	242	d->len += 4;
	243	DPUTM(d, k->u.k.k, k->u.k.sz);
	244	rc = 1;
	245	} break;
	246
	247	case KENC_MP: {
	248	char *p;
	249	size_t sz = mp_octets(k->u.m);
	250
	251	DENSURE(d, (sz + 7) & ~3);
	252	p = d->buf + d->len;
	253	STORE16(p, k->e);
	254	STORE16(p + 2, sz);
	255	mp_storeb(k->u.m, p + 4, sz);
	256	d->len += sz + 4;
	257	rc = 1;
	258	} break;
	259
1ba83484	260	case KENC_STRING: {
	261	char *p;
	262	size_t sz = strlen(k->u.p);
	263
	264	DENSURE(d, (sz + 7) & ~3);
	265	p = d->buf + d->len;
	266	STORE16(p, k->e);
	267	STORE16(p + 2, sz);
	268	memcpy(p + 4, k->u.p, sz);
	269	d->len += sz + 4;
	270	rc = 1;
	271	} break;
	272
	273	case KENC_EC: {
	274	char *p;
898a4e25	275	size_t xsz = 0, ysz = 0;
34e4f738	276	size_t sz;
1ba83484	277
34e4f738	278	if (EC_ATINF(&k->u.e))
	279	sz = 0;
	280	else {
	281	xsz = mp_octets(k->u.e.x);
	282	ysz = mp_octets(k->u.e.y);
	283	sz = xsz + ysz + 4;
	284	}
1ba83484	285	DENSURE(d, (sz + 7) & ~3);
	286	p = d->buf + d->len;
	287	STORE16(p, k->e);
	288	STORE16(p + 2, sz);
34e4f738	289	if (!EC_ATINF(&k->u.e)) {
	290	STORE16(p + 4, xsz);
	291	mp_storeb(k->u.e.x, p + 6, xsz);
	292	STORE16(p + 6 + xsz, ysz);
	293	mp_storeb(k->u.e.y, p + 8 + xsz, ysz);
	294	}
1ba83484	295	d->len += sz + 4;
	296	rc = 1;
	297	} break;
	298
052b36d0	299	case KENC_STRUCT: {
	300	size_t n;
	301	char *p;
898a4e25	302	key_struct ks, *ksv;
898a4e25	303	size_t nks, j;
052b36d0	304	sym_iter i;
	305
	306	n = d->len;
	307	DENSURE(d, 4);
	308	p = d->buf + n;
	309	STORE16(p, k->e & KF_ENCMASK);
	310	d->len += 4;
898a4e25	311
	312	for (nks = 0, sym_mkiter(&i, &k->u.s);
	313	(ks = sym_next(&i)) != 0;
	314	nks++);
	315	if (nks) {
	316	ksv = xmalloc(nks * sizeof(*ksv));
	317	for (j = 0, sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; j++)
	318	ksv[j] = ks;
	319	qsort(ksv, nks, sizeof(*ksv), ksbyname);
	320	for (j = 0; j < nks; j++) {
	321	size_t o = d->len;
	322	ks = ksv[j];
	323	DENSURE(d, 1);
	324	(octet )(d->buf + d->len++) = strlen(SYM_NAME(ks));
	325	DPUTS(d, SYM_NAME(ks));
	326	while (d->len & 3)
	327	DPUTC(d, 0);
	328	if (key_encode(&ks->k, d, kf))
	329	rc = 1;
	330	else
	331	d->len = o;
	332	}
	333	xfree(ksv);
052b36d0	334	}
	335	if (!rc)
	336	d->len = n;
	337	else {
	338	p = d->buf + n + 2;
	339	n = d->len - n - 4;
	340	STORE16(p, n);
	341	}
	342	} break;
	343	}
	344	while (d->len & 3)
	345	DPUTC(d, 0);
	346	return (rc);
	347	}
	348
	349	/----- That's all, folks -------------------------------------------------/