[u/mdw/catacomb] / rc4.c

/* -*-c-*-
 *
 * $Id: rc4.c,v 1.6 2004/04/08 01:36:15 mdw Exp $
 *
 * The alleged RC4 stream cipher
 *
 * (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.
 */

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

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

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

#include "arena.h"
#include "gcipher.h"
#include "grand.h"
#include "paranoia.h"
#include "rc4.h"

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

const octet rc4_keysz[] = { KSZ_RANGE, RC4_KEYSZ, 1, 255, 1 };

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

/* --- @rc4_addkey@ --- *
 *
 * Arguments:	@rc4_ctx *ctx@ = pointer to context to key
 *		@const void *k@ = pointer to key data to use
 *		@size_t sz@ = size of the key data
 *
 * Returns:	---
 *
 * Use:		Mixes key data with an RC4 context.  The RC4 context is not
 *		reset before mixing.  This may be used to mix new key
 *		material with an existing RC4 context.
 */

void rc4_addkey(rc4_ctx *ctx, const void *k, size_t sz)
{
  unsigned i, j;
  const octet *p = k, *q = p + sz;

  KSZ_ASSERT(rc4, sz);

  for (i = j = 0; i < 256; i++) {
    unsigned si = ctx->s[i];
    j = (j + si + *p++) & 0xff;
    ctx->s[i] = ctx->s[j];
    ctx->s[j] = si;
    if (p == q)
      p = k;
  }

  ctx->i = ctx->j = 0;
}

/* --- @rc4_init@ --- *
 *
 * Arguments:	@rc4_ctx *ctx@ = pointer to context to initialize
 *		@const void *k@ = pointer to key data to use
 *		@size_t sz@ = size of the key data
 *
 * Returns:	---
 *
 * Use:		Initializes an RC4 context ready for use.
 */

void rc4_init(rc4_ctx *ctx, const void *k, size_t sz)
{
  unsigned i;

  for (i = 0; i < 256; i++)
    ctx->s[i] = i;
  ctx->f = 0;
  rc4_addkey(ctx, k, sz);
}

/* --- @rc4_encrypt@ --- *
 *
 * Arguments:	@rc4_ctx *ctx@ = pointer to context to use
 *		@const void *src@ = pointer to the source block
 *		@void *dest@ = pointer to the destination block
 *		@size_t sz@ = size of the block
 *
 * Returns:	---
 *
 * Use:		Encrypts or decrypts a block of data.  The destination may
 *		be null to just grind the generator around for a while.  It's
 *		recommended that you say `@rc4_encrypt(&ctx, 0, 0, 1024)@'
 *		after initializing a new context, to prevent keystream
 *		guessing attacks.  The source may be null to just extract a
 *		big lump of data from the generator.
 */

void rc4_encrypt(rc4_ctx *ctx, const void *src, void *dest, size_t sz)
{
  const octet *s = src;
  octet *d = dest;

  if (!d)
    RC4_OPEN(ctx, while (sz) { unsigned x; RC4_BYTE(x); sz--; });
  else if (!s)
    RC4_OPEN(ctx, while (sz) { RC4_BYTE(*d++); sz--; });
  else
    RC4_OPEN(ctx,
	     while (sz) { unsigned x; RC4_BYTE(x); *d++ = *s++ ^ x; sz--; });
}

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

typedef struct gctx {
  gcipher c;
  rc4_ctx rc4;
} gctx;

static const gcipher_ops gops;

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

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

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

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

const gccipher rc4 = {
  "rc4", rc4_keysz, 0,
  ginit
};

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

typedef struct grctx {
  grand r;
  rc4_ctx rc4;
} 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;
  uint32 i;
  octet buf[4];
  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:
      i = va_arg(ap, unsigned);
      STORE32(buf, i);
      rc4_addkey(&g->rc4, buf, sizeof(buf));
      break;
    case GRAND_SEEDUINT32:
      i = va_arg(ap, uint32);
      STORE32(buf, i);
      rc4_addkey(&g->rc4, buf, sizeof(buf));
      break;
    case GRAND_SEEDBLOCK: {
      const void *p = va_arg(ap, const void *);
      size_t sz = va_arg(ap, size_t);
      rc4_addkey(&g->rc4, p, sz);
    } break;
    case GRAND_SEEDRAND: {
      grand *rr = va_arg(ap, grand *);
      octet buf[16];
      rr->ops->fill(rr, buf, sizeof(buf));
      rc4_addkey(&g->rc4, buf, sizeof(buf));
    } break;
    default:
      GRAND_BADOP;
      break;
  }

  va_end(ap);
  return (rc);
}

static octet grbyte(grand *r)
{
  grctx *g = (grctx *)r;
  octet o;
  RC4_OPEN(&g->rc4, RC4_BYTE(o););
  return (o);
}

static uint32 grword(grand *r)
{
  grctx *g = (grctx *)r;
  octet b[4];
  int i;
  RC4_OPEN(&g->rc4,
	   for (i = 0; i < sizeof(b); i++)
	     RC4_BYTE(b[i]););
  return (LOAD32(b));
}

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

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

/* --- @rc4_rand@ --- *
 *
 * Arguments:	@const void *k@ = pointer to key material
 *		@size_t sz@ = size of key material
 *
 * Returns:	Pointer to generic random number generator interface.
 *
 * Use:		Creates a random number interface wrapper around an
 *		OFB-mode block cipher.
 */

grand *rc4_rand(const void *k, size_t sz)
{
  grctx *g = S_CREATE(grctx);
  g->r.ops = &grops;
  rc4_init(&g->rc4, k, sz);
  return (&g->r);
}

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

#ifdef TEST_RIG

#include <stdio.h>
#include <string.h>

#include <mLib/quis.h>
#include <mLib/testrig.h>

static int v_encrypt(dstr *v)
{
  rc4_ctx ctx;
  dstr d = DSTR_INIT;
  int ok = 1;

  rc4_init(&ctx, v[0].buf, v[0].len);
  dstr_ensure(&d, v[1].len);
  d.len = v[1].len;
  rc4_encrypt(&ctx, v[1].buf, d.buf, d.len);

  if (memcmp(v[2].buf, d.buf, d.len) != 0) {
    ok = 0;
    printf("\nfail encryption:"
	   "\n\tkey	   = ");
    type_hex.dump(&v[0], stdout);
    printf("\n\tplaintext  = "); type_hex.dump(&v[1], stdout);
    printf("\n\texpected   = "); type_hex.dump(&v[2], stdout);
    printf("\n\tcalculated = "); type_hex.dump(&d, stdout);
    putchar('\n');
  }

  return (ok);
}

static int v_generate(dstr *v)
{
  rc4_ctx ctx;
  dstr d = DSTR_INIT;
  int ok = 1;

  rc4_init(&ctx, v[0].buf, v[0].len);
  rc4_encrypt(&ctx, 0, 0, *(int *)v[1].buf);
  dstr_ensure(&d, v[2].len);
  d.len = v[2].len;
  rc4_encrypt(&ctx, 0, d.buf, d.len);

  if (memcmp(v[2].buf, d.buf, d.len) != 0) {
    ok = 0;
    printf("\nfail generation:"
	   "\n\tkey	   = ");
    type_hex.dump(&v[0], stdout);
    printf("\n\tskip len   = %i", *(int *)v[1].buf);
    printf("\n\texpected   = "); type_hex.dump(&v[2], stdout);
    printf("\n\tcalculated = "); type_hex.dump(&d, stdout);
    putchar('\n');
  }

  return (ok);
}

static test_chunk defs[] = {
  { "rc4-encrypt", v_encrypt, { &type_hex, &type_hex, &type_hex, 0 } },
  { "rc4-generate", v_generate, { &type_hex, &type_int, &type_hex, 0 } },
  { 0, 0, { 0 } }
};

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

#endif

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
d03ab969	1	/* --c--
d03ab969	2	*
b817bfc6	3	* $Id: rc4.c,v 1.6 2004/04/08 01:36:15 mdw Exp $
d03ab969	4	*
	5	* The alleged RC4 stream cipher
	6	*
	7	* (c) 1999 Straylight/Edgeware
	8	*/
	9
45c0fd36	10	/----- Licensing notice --------------------------------------------------
d03ab969	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.
45c0fd36	18	*
d03ab969	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.
45c0fd36	23	*
d03ab969	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
d03ab969	30	/----- Header files ------------------------------------------------------/
	31
	32	#include <assert.h>
41f91aa3	33	#include <stdarg.h>
d03ab969	34	#include <stdio.h>
	35
	36	#include <mLib/bits.h>
41f91aa3	37	#include <mLib/sub.h>
d03ab969	38
4b8968dd	39	#include "arena.h"
41f91aa3	40	#include "gcipher.h"
41f91aa3	41	#include "grand.h"
4b8968dd	42	#include "paranoia.h"
d03ab969	43	#include "rc4.h"
d03ab969	44
4b8968dd	45	/----- Global variables --------------------------------------------------/
	46
	47	const octet rc4_keysz[] = { KSZ_RANGE, RC4_KEYSZ, 1, 255, 1 };
	48
d03ab969	49	/----- Main code ---------------------------------------------------------/
d03ab969	50
4b8968dd	51	/* --- @rc4_addkey@ --- *
d03ab969	52	*
4b8968dd	53	* Arguments: @rc4_ctx *ctx@ = pointer to context to key
d03ab969	54	* @const void *k@ = pointer to key data to use
	55	* @size_t sz@ = size of the key data
	56	*
	57	* Returns: ---
	58	*
4b8968dd	59	* Use: Mixes key data with an RC4 context. The RC4 context is not
	60	* reset before mixing. This may be used to mix new key
	61	* material with an existing RC4 context.
d03ab969	62	*/
d03ab969	63
4b8968dd	64	void rc4_addkey(rc4_ctx ctx, const void k, size_t sz)
d03ab969	65	{
	66	unsigned i, j;
	67	const octet p = k, q = p + sz;
	68
4b8968dd	69	KSZ_ASSERT(rc4, sz);
d03ab969	70
d03ab969	71	for (i = j = 0; i < 256; i++) {
	72	unsigned si = ctx->s[i];
	73	j = (j + si + *p++) & 0xff;
	74	ctx->s[i] = ctx->s[j];
	75	ctx->s[j] = si;
	76	if (p == q)
	77	p = k;
45c0fd36	78	}
4b8968dd	79
	80	ctx->i = ctx->j = 0;
	81	}
	82
	83	/* --- @rc4_init@ --- *
	84	*
	85	* Arguments: @rc4_ctx *ctx@ = pointer to context to initialize
	86	* @const void *k@ = pointer to key data to use
	87	* @size_t sz@ = size of the key data
	88	*
	89	* Returns: ---
	90	*
	91	* Use: Initializes an RC4 context ready for use.
	92	*/
	93
	94	void rc4_init(rc4_ctx ctx, const void k, size_t sz)
	95	{
	96	unsigned i;
	97
	98	for (i = 0; i < 256; i++)
	99	ctx->s[i] = i;
	100	ctx->f = 0;
	101	rc4_addkey(ctx, k, sz);
d03ab969	102	}
	103
	104	/* --- @rc4_encrypt@ --- *
	105	*
	106	* Arguments: @rc4_ctx *ctx@ = pointer to context to use
	107	* @const void *src@ = pointer to the source block
	108	* @void *dest@ = pointer to the destination block
	109	* @size_t sz@ = size of the block
	110	*
	111	* Returns: ---
	112	*
	113	* Use: Encrypts or decrypts a block of data. The destination may
	114	* be null to just grind the generator around for a while. It's
	115	* recommended that you say `@rc4_encrypt(&ctx, 0, 0, 1024)@'
	116	* after initializing a new context, to prevent keystream
	117	* guessing attacks. The source may be null to just extract a
	118	* big lump of data from the generator.
	119	*/
	120
	121	void rc4_encrypt(rc4_ctx ctx, const void src, void *dest, size_t sz)
	122	{
	123	const octet *s = src;
	124	octet *d = dest;
	125
	126	if (!d)
	127	RC4_OPEN(ctx, while (sz) { unsigned x; RC4_BYTE(x); sz--; });
	128	else if (!s)
	129	RC4_OPEN(ctx, while (sz) { RC4_BYTE(*d++); sz--; });
	130	else
	131	RC4_OPEN(ctx,
	132	while (sz) { unsigned x; RC4_BYTE(x); d++ = s++ ^ x; sz--; });
	133	}
	134
41f91aa3	135	/----- Generic cipher interface ------------------------------------------/
	136
	137	typedef struct gctx {
	138	gcipher c;
	139	rc4_ctx rc4;
	140	} gctx;
	141
	142	static const gcipher_ops gops;
	143
	144	static gcipher ginit(const void k, size_t sz)
	145	{
4b8968dd	146	gctx *g = S_CREATE(gctx);
41f91aa3	147	g->c.ops = &gops;
	148	rc4_init(&g->rc4, k, sz);
	149	return (&g->c);
	150	}
	151
	152	static void gencrypt(gcipher c, const void s, void *t, size_t sz)
	153	{
	154	gctx g = (gctx )c;
	155	rc4_encrypt(&g->rc4, s, t, sz);
	156	}
	157
	158	static void gdestroy(gcipher *c)
	159	{
	160	gctx g = (gctx )c;
4b8968dd	161	BURN(*g);
4b8968dd	162	S_DESTROY(g);
41f91aa3	163	}
	164
	165	static const gcipher_ops gops = {
4b8968dd	166	&rc4,
41f91aa3	167	gencrypt, gencrypt, gdestroy, 0, 0
	168	};
	169
	170	const gccipher rc4 = {
4b8968dd	171	"rc4", rc4_keysz, 0,
41f91aa3	172	ginit
	173	};
	174
	175	/----- Generic random number generator interface -------------------------/
	176
	177	typedef struct grctx {
	178	grand r;
	179	rc4_ctx rc4;
	180	} grctx;
	181
	182	static void grdestroy(grand *r)
	183	{
	184	grctx g = (grctx )r;
4b8968dd	185	BURN(*g);
4b8968dd	186	S_DESTROY(g);
41f91aa3	187	}
	188
	189	static int grmisc(grand *r, unsigned op, ...)
	190	{
	191	grctx g = (grctx )r;
	192	va_list ap;
	193	int rc = 0;
360c232e	194	uint32 i;
41f91aa3	195	octet buf[4];
	196	va_start(ap, op);
	197
	198	switch (op) {
	199	case GRAND_CHECK:
	200	switch (va_arg(ap, unsigned)) {
	201	case GRAND_CHECK:
	202	case GRAND_SEEDINT:
	203	case GRAND_SEEDUINT32:
	204	case GRAND_SEEDBLOCK:
4ab1268f	205	case GRAND_SEEDRAND:
41f91aa3	206	rc = 1;
	207	break;
	208	default:
	209	rc = 0;
	210	break;
	211	}
	212	break;
	213	case GRAND_SEEDINT:
360c232e	214	i = va_arg(ap, unsigned);
360c232e	215	STORE32(buf, i);
4b8968dd	216	rc4_addkey(&g->rc4, buf, sizeof(buf));
41f91aa3	217	break;
41f91aa3	218	case GRAND_SEEDUINT32:
360c232e	219	i = va_arg(ap, uint32);
360c232e	220	STORE32(buf, i);
4b8968dd	221	rc4_addkey(&g->rc4, buf, sizeof(buf));
41f91aa3	222	break;
	223	case GRAND_SEEDBLOCK: {
	224	const void p = va_arg(ap, const void );
	225	size_t sz = va_arg(ap, size_t);
4b8968dd	226	rc4_addkey(&g->rc4, p, sz);
41f91aa3	227	} break;
4ab1268f	228	case GRAND_SEEDRAND: {
	229	grand rr = va_arg(ap, grand );
	230	octet buf[16];
	231	rr->ops->fill(rr, buf, sizeof(buf));
4b8968dd	232	rc4_addkey(&g->rc4, buf, sizeof(buf));
4ab1268f	233	} break;
	234	default:
	235	GRAND_BADOP;
	236	break;
41f91aa3	237	}
	238
	239	va_end(ap);
	240	return (rc);
	241	}
	242
	243	static octet grbyte(grand *r)
	244	{
	245	grctx g = (grctx )r;
	246	octet o;
	247	RC4_OPEN(&g->rc4, RC4_BYTE(o););
	248	return (o);
	249	}
	250
	251	static uint32 grword(grand *r)
	252	{
	253	grctx g = (grctx )r;
	254	octet b[4];
	255	int i;
	256	RC4_OPEN(&g->rc4,
	257	for (i = 0; i < sizeof(b); i++)
	258	RC4_BYTE(b[i]););
	259	return (LOAD32(b));
	260	}
	261
	262	static void grfill(grand r, void p, size_t sz)
	263	{
	264	grctx g = (grctx )r;
	265	rc4_encrypt(&g->rc4, 0, p, sz);
	266	}
	267
	268	static const grand_ops grops = {
	269	"rc4",
4b8968dd	270	GRAND_CRYPTO, 0,
41f91aa3	271	grmisc, grdestroy,
	272	grword, grbyte, grword, grand_range, grfill
	273	};
	274
	275	/* --- @rc4_rand@ --- *
	276	*
	277	* Arguments: @const void *k@ = pointer to key material
	278	* @size_t sz@ = size of key material
	279	*
	280	* Returns: Pointer to generic random number generator interface.
	281	*
	282	* Use: Creates a random number interface wrapper around an
	283	* OFB-mode block cipher.
	284	*/
	285
	286	grand rc4_rand(const void k, size_t sz)
	287	{
4b8968dd	288	grctx *g = S_CREATE(grctx);
41f91aa3	289	g->r.ops = &grops;
	290	rc4_init(&g->rc4, k, sz);
	291	return (&g->r);
	292	}
	293
d03ab969	294	/----- Test rig ----------------------------------------------------------/
	295
	296	#ifdef TEST_RIG
	297
	298	#include <stdio.h>
	299	#include <string.h>
	300
	301	#include <mLib/quis.h>
	302	#include <mLib/testrig.h>
	303
	304	static int v_encrypt(dstr *v)
	305	{
	306	rc4_ctx ctx;
	307	dstr d = DSTR_INIT;
	308	int ok = 1;
	309
	310	rc4_init(&ctx, v[0].buf, v[0].len);
	311	dstr_ensure(&d, v[1].len);
	312	d.len = v[1].len;
	313	rc4_encrypt(&ctx, v[1].buf, d.buf, d.len);
	314
	315	if (memcmp(v[2].buf, d.buf, d.len) != 0) {
	316	ok = 0;
	317	printf("\nfail encryption:"
45c0fd36	318	"\n\tkey = ");
d03ab969	319	type_hex.dump(&v[0], stdout);
	320	printf("\n\tplaintext = "); type_hex.dump(&v[1], stdout);
	321	printf("\n\texpected = "); type_hex.dump(&v[2], stdout);
	322	printf("\n\tcalculated = "); type_hex.dump(&d, stdout);
	323	putchar('\n');
	324	}
	325
	326	return (ok);
	327	}
	328
	329	static int v_generate(dstr *v)
	330	{
	331	rc4_ctx ctx;
	332	dstr d = DSTR_INIT;
	333	int ok = 1;
	334
	335	rc4_init(&ctx, v[0].buf, v[0].len);
	336	rc4_encrypt(&ctx, 0, 0, (int )v[1].buf);
	337	dstr_ensure(&d, v[2].len);
	338	d.len = v[2].len;
	339	rc4_encrypt(&ctx, 0, d.buf, d.len);
	340
	341	if (memcmp(v[2].buf, d.buf, d.len) != 0) {
	342	ok = 0;
	343	printf("\nfail generation:"
45c0fd36	344	"\n\tkey = ");
d03ab969	345	type_hex.dump(&v[0], stdout);
	346	printf("\n\tskip len = %i", (int )v[1].buf);
	347	printf("\n\texpected = "); type_hex.dump(&v[2], stdout);
	348	printf("\n\tcalculated = "); type_hex.dump(&d, stdout);
	349	putchar('\n');
	350	}
	351
	352	return (ok);
	353	}
	354
	355	static test_chunk defs[] = {
	356	{ "rc4-encrypt", v_encrypt, { &type_hex, &type_hex, &type_hex, 0 } },
	357	{ "rc4-generate", v_generate, { &type_hex, &type_int, &type_hex, 0 } },
	358	{ 0, 0, { 0 } }
	359	};
	360
	361	int main(int argc, char *argv[])
	362	{
	363	test_run(argc, argv, defs, SRCDIR"/tests/rc4");
	364	return (0);
	365	}
	366
	367	#endif
	368
	369	/----- That's all, folks -------------------------------------------------/