x509.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

#include <u.h>
#include <libc.h>
#include <mp.h>
#include <libsec.h>

typedef DigestState*(*DigestFun)(uchar*,ulong,uchar*,DigestState*);

/* ANSI offsetof, backwards. */
#define	OFFSETOF(a, b)	offsetof(b, a)

/*=============================================================*/
/*  general ASN1 declarations and parsing
 *
 *  For now, this is used only for extracting the key from an
 *  X509 certificate, so the entire collection is hidden.  But
 *  someday we should probably make the functions visible and
 *  give them their own man page.
 */
typedef struct Elem Elem;
typedef struct Tag Tag;
typedef struct Value Value;
typedef struct Bytes Bytes;
typedef struct Ints Ints;
typedef struct Bits Bits;
typedef struct Elist Elist;

/* tag classes */
#define Universal 0
#define Context 0x80

/* universal tags */
#define BOOLEAN 1
#define INTEGER 2
#define BIT_STRING 3
#define OCTET_STRING 4
#define NULLTAG 5
#define OBJECT_ID 6
#define ObjectDescriptor 7
#define EXTERNAL 8
#define REAL 9
#define ENUMERATED 10
#define EMBEDDED_PDV 11
#define UTF8String 12
#define SEQUENCE 16		/* also SEQUENCE OF */
#define SETOF 17				/* also SETOF OF */
#define NumericString 18
#define PrintableString 19
#define TeletexString 20
#define VideotexString 21
#define IA5String 22
#define UTCTime 23
#define GeneralizedTime 24
#define GraphicString 25
#define VisibleString 26
#define GeneralString 27
#define UniversalString 28
#define BMPString 30

struct Bytes {
	int	len;
	uchar	data[1];
};

struct Ints {
	int	len;
	int	data[1];
};

struct Bits {
	int	len;		/* number of bytes */
	int	unusedbits;	/* unused bits in last byte */
	uchar	data[1];	/* most-significant bit first */
};

struct Tag {
	int	class;
	int	num;
};

enum { VBool, VInt, VOctets, VBigInt, VReal, VOther,
	VBitString, VNull, VEOC, VObjId, VString, VSeq, VSet };
struct Value {
	int	tag;		/* VBool, etc. */
	union {
		int	boolval;
		int	intval;
		Bytes*	octetsval;
		Bytes*	bigintval;
		Bytes*	realval;	/* undecoded; hardly ever used */
		Bytes*	otherval;
		Bits*	bitstringval;
		Ints*	objidval;
		char*	stringval;
		Elist*	seqval;
		Elist*	setval;
	} u;  /* (Don't use anonymous unions, for ease of porting) */
};

struct Elem {
	Tag	tag;
	Value	val;
};

struct Elist {
	Elist*	tl;
	Elem	hd;
};

/* decoding errors */
enum { ASN_OK, ASN_ESHORT, ASN_ETOOBIG, ASN_EVALLEN,
		ASN_ECONSTR, ASN_EPRIM, ASN_EINVAL, ASN_EUNIMPL };


/* here are the functions to consider making extern someday */
static Bytes*	newbytes(int len);
static Bytes*	makebytes(uchar* buf, int len);
static void	freebytes(Bytes* b);
static Bytes*	catbytes(Bytes* b1, Bytes* b2);
static Ints*	newints(int len);
static Ints*	makeints(int* buf, int len);
static void	freeints(Ints* b);
static Bits*	newbits(int len);
static Bits*	makebits(uchar* buf, int len, int unusedbits);
static void	freebits(Bits* b);
static Elist*	mkel(Elem e, Elist* tail);
static void	freeelist(Elist* el);
static int	elistlen(Elist* el);
static int	is_seq(Elem* pe, Elist** pseq);
static int	is_set(Elem* pe, Elist** pset);
static int	is_int(Elem* pe, int* pint);
static int	is_bigint(Elem* pe, Bytes** pbigint);
static int	is_bitstring(Elem* pe, Bits** pbits);
static int	is_octetstring(Elem* pe, Bytes** poctets);
static int	is_oid(Elem* pe, Ints** poid);
static int	is_string(Elem* pe, char** pstring);
static int	is_time(Elem* pe, char** ptime);
static int	decode(uchar* a, int alen, Elem* pelem);
static int	decode_seq(uchar* a, int alen, Elist** pelist);
static int	decode_value(uchar* a, int alen, int kind, int isconstr, Value* pval);
static int	encode(Elem e, Bytes** pbytes);
static int	oid_lookup(Ints* o, Ints** tab);
static void	freevalfields(Value* v);
static mpint	*asn1mpint(Elem *e);



#define TAG_MASK 0x1F
#define CONSTR_MASK 0x20
#define CLASS_MASK 0xC0
#define MAXOBJIDLEN 20

static int ber_decode(uchar** pp, uchar* pend, Elem* pelem);
static int tag_decode(uchar** pp, uchar* pend, Tag* ptag, int* pisconstr);
static int length_decode(uchar** pp, uchar* pend, int* plength);
static int value_decode(uchar** pp, uchar* pend, int length, int kind, int isconstr, Value* pval);
static int int_decode(uchar** pp, uchar* pend, int count, int unsgned, int* pint);
static int uint7_decode(uchar** pp, uchar* pend, int* pint);
static int octet_decode(uchar** pp, uchar* pend, int length, int isconstr, Bytes** pbytes);
static int seq_decode(uchar** pp, uchar* pend, int length, int isconstr, Elist** pelist);
static int enc(uchar** pp, Elem e, int lenonly);
static int val_enc(uchar** pp, Elem e, int *pconstr, int lenonly);
static void uint7_enc(uchar** pp, int num, int lenonly);
static void int_enc(uchar** pp, int num, int unsgned, int lenonly);

static void *
emalloc(int n)
{
	void *p;
	if(n==0)
		n=1;
	p = malloc(n);
	if(p == nil){
		exits("out of memory");
	}
	memset(p, 0, n);
	setmalloctag(p, getcallerpc(&n));
	return p;
}

static char*
estrdup(char *s)
{
	char *d, *d0;

	if(!s)
		return 0;
	d = d0 = emalloc(strlen(s)+1);
	while(*d++ = *s++)
		;
	return d0;
}


/*
 * Decode a[0..len] as a BER encoding of an ASN1 type.
 * The return value is one of ASN_OK, etc.
 * Depending on the error, the returned elem may or may not
 * be nil.
 */
static int
decode(uchar* a, int alen, Elem* pelem)
{
	uchar* p = a;

	return  ber_decode(&p, &a[alen], pelem);
}

/*
 * Like decode, but continue decoding after first element
 * of array ends.
 */
static int
decode_seq(uchar* a, int alen, Elist** pelist)
{
	uchar* p = a;

	return seq_decode(&p, &a[alen], -1, 1, pelist);
}

/*
 * Decode the whole array as a BER encoding of an ASN1 value,
 * (i.e., the part after the tag and length).
 * Assume the value is encoded as universal tag "kind".
 * The constr arg is 1 if the value is constructed, 0 if primitive.
 * If there's an error, the return string will contain the error.
 * Depending on the error, the returned value may or may not
 * be nil.
 */
static int
decode_value(uchar* a, int alen, int kind, int isconstr, Value* pval)
{
	uchar* p = a;

	return value_decode(&p, &a[alen], alen, kind, isconstr, pval);
}

/*
 * All of the following decoding routines take arguments:
 *	uchar **pp;
 *	uchar *pend;
 * Where parsing is supposed to start at **pp, and when parsing
 * is done, *pp is updated to point at next char to be parsed.
 * The pend pointer is just past end of string; an error should
 * be returned parsing hasn't finished by then.
 *
 * The returned int is ASN_OK if all went fine, else ASN_ESHORT, etc.
 * The remaining argument(s) are pointers to where parsed entity goes.
 */

/* Decode an ASN1 'Elem' (tag, length, value) */
static int
ber_decode(uchar** pp, uchar* pend, Elem* pelem)
{
	int err;
	int isconstr;
	int length;
	Tag tag;
	Value val;

	err = tag_decode(pp, pend, &tag, &isconstr);
	if(err == ASN_OK) {
		err = length_decode(pp, pend, &length);
		if(err == ASN_OK) {
			if(tag.class == Universal) {
				err = value_decode(pp, pend, length, tag.num, isconstr, &val);
				if(val.tag == VSeq || val.tag == VSet)
					setmalloctag(val.u.seqval, getcallerpc(&pp));
			}else
				err = value_decode(pp, pend, length, OCTET_STRING, 0, &val);
			if(err == ASN_OK) {
				pelem->tag = tag;
				pelem->val = val;
			}
		}
	}
	return err;
}

/* Decode a tag field */
static int
tag_decode(uchar** pp, uchar* pend, Tag* ptag, int* pisconstr)
{
	int err;
	int v;
	uchar* p;

	err = ASN_OK;
	p = *pp;
	if(pend-p >= 2) {
		v = *p++;
		ptag->class = v&CLASS_MASK;
		if(v&CONSTR_MASK)
			*pisconstr = 1;
		else
			*pisconstr = 0;
		v &= TAG_MASK;
		if(v == TAG_MASK)
			err = uint7_decode(&p, pend, &v);
		ptag->num = v;
	}
	else
		err = ASN_ESHORT;
	*pp = p;
	return err;
}

/* Decode a length field */
static int
length_decode(uchar** pp, uchar* pend, int* plength)
{
	int err;
	int num;
	int v;
	uchar* p;

	err = ASN_OK;
	num = 0;
	p = *pp;
	if(p < pend) {
		v = *p++;
		if(v&0x80)
			err = int_decode(&p, pend, v&0x7F, 1, &num);
		else
			num = v;
	}
	else
		err = ASN_ESHORT;
	*pp = p;
	*plength = num;
	return err;
}

/* Decode a value field  */
static int
value_decode(uchar** pp, uchar* pend, int length, int kind, int isconstr, Value* pval)
{
	int err;
	Bytes* va;
	int num;
	int bitsunused;
	int subids[MAXOBJIDLEN];
	int isubid;
	Elist*	vl;
	uchar* p;
	uchar* pe;

	err = ASN_OK;
	p = *pp;
	if(length == -1) {	/* "indefinite" length spec */
		if(!isconstr)
			err = ASN_EINVAL;
	}
	else if(p + length > pend)
		err = ASN_EVALLEN;
	if(err != ASN_OK)
		return err;

	switch(kind) {
	case 0:
		/* marker for end of indefinite constructions */
		if(length == 0)
			pval->tag = VNull;
		else
			err = ASN_EINVAL;
		break;

	case BOOLEAN:
		if(isconstr)
			err = ASN_ECONSTR;
		else if(length != 1)
			err = ASN_EVALLEN;
		else {
			pval->tag = VBool;
			pval->u.boolval = (*p++ != 0);
		}
		break;

	case INTEGER:
	case ENUMERATED:
		if(isconstr)
			err = ASN_ECONSTR;
		else if(length <= 4) {
			err = int_decode(&p, pend, length, 0, &num);
			if(err == ASN_OK) {
				pval->tag = VInt;
				pval->u.intval = num;
			}
		}
		else {
			pval->tag = VBigInt;
			pval->u.bigintval = makebytes(p, length);
			p += length;
		}
		break;

	case BIT_STRING:
		pval->tag = VBitString;
		if(isconstr) {
			if(length == -1 && p + 2 <= pend && *p == 0 && *(p+1) ==0) {
				pval->u.bitstringval = makebits(0, 0, 0);
				p += 2;
			}
			else
				/* TODO: recurse and concat results */
				err = ASN_EUNIMPL;
		}
		else {
			if(length < 2) {
				if(length == 1 && *p == 0) {
					pval->u.bitstringval = makebits(0, 0, 0);
					p++;
				}
				else
					err = ASN_EINVAL;
			}
			else {
				bitsunused = *p;
				if(bitsunused > 7)
					err = ASN_EINVAL;
				else if(length > 0x0FFFFFFF)
					err = ASN_ETOOBIG;
				else {
					pval->u.bitstringval = makebits(p+1, length-1, bitsunused);
					p += length;
				}
			}
		}
		break;

	case OCTET_STRING:
	case ObjectDescriptor:
		err = octet_decode(&p, pend, length, isconstr, &va);
		if(err == ASN_OK) {
			pval->tag = VOctets;
			pval->u.octetsval = va;
		}
		break;

	case NULLTAG:
		if(isconstr)
			err = ASN_ECONSTR;
		else if(length != 0)
			err = ASN_EVALLEN;
		else
			pval->tag = VNull;
		break;

	case OBJECT_ID:
		if(isconstr)
			err = ASN_ECONSTR;
		else if(length == 0)
			err = ASN_EVALLEN;
		else {
			isubid = 0;
			pe = p+length;
			while(p < pe && isubid < MAXOBJIDLEN) {
				err = uint7_decode(&p, pend, &num);
				if(err != ASN_OK)
					break;
				if(isubid == 0) {
					subids[isubid++] = num / 40;
					subids[isubid++] = num % 40;
				}
				else
					subids[isubid++] = num;
			}
			if(err == ASN_OK) {
				if(p != pe)
					err = ASN_EVALLEN;
				else {
					pval->tag = VObjId;
					pval->u.objidval = makeints(subids, isubid);
				}
			}
		}
		break;

	case EXTERNAL:
	case EMBEDDED_PDV:
		/* TODO: parse this internally */
		if(p+length > pend)
			err = ASN_EVALLEN;
		else {
			pval->tag = VOther;
			pval->u.otherval = makebytes(p, length);
			p += length;
		}
		break;

	case REAL:
		/* Let the application decode */
		if(isconstr)
			err = ASN_ECONSTR;
		else if(p+length > pend)
			err = ASN_EVALLEN;
		else {
			pval->tag = VReal;
			pval->u.realval = makebytes(p, length);
			p += length;
		}
		break;

	case SEQUENCE:
		err = seq_decode(&p, pend, length, isconstr, &vl);
		setmalloctag(vl, getcallerpc(&pp));
		if(err == ASN_OK) {
			pval->tag = VSeq ;
			pval->u.seqval = vl;
		}
		break;

	case SETOF:
		err = seq_decode(&p, pend, length, isconstr, &vl);
		setmalloctag(vl, getcallerpc(&pp));
		if(err == ASN_OK) {
			pval->tag = VSet;
			pval->u.setval = vl;
		}
		break;
	case UTF8String:
	case NumericString:
	case PrintableString:
	case TeletexString:
	case VideotexString:
	case IA5String:
	case UTCTime:
	case GeneralizedTime:
	case GraphicString:
	case VisibleString:
	case GeneralString:
	case UniversalString:
	case BMPString:
		/* TODO: figure out when character set conversion is necessary */
		err = octet_decode(&p, pend, length, isconstr, &va);
		if(err == ASN_OK) {
			pval->tag = VString;
			pval->u.stringval = (char*)emalloc(va->len+1);
			memmove(pval->u.stringval, va->data, va->len);
			pval->u.stringval[va->len] = 0;
			free(va);
		}
		break;

	default:
		if(p+length > pend)
			err = ASN_EVALLEN;
		else {
			pval->tag = VOther;
			pval->u.otherval = makebytes(p, length);
			p += length;
		}
		break;
	}
	*pp = p;
	return err;
}

/*
 * Decode an int in format where count bytes are
 * concatenated to form value.
 * Although ASN1 allows any size integer, we return
 * an error if the result doesn't fit in a 32-bit int.
 * If unsgned is not set, make sure to propagate sign bit.
 */
static int
int_decode(uchar** pp, uchar* pend, int count, int unsgned, int* pint)
{
	int err;
	int num;
	uchar* p;

	p = *pp;
	err = ASN_OK;
	num = 0;
	if(p+count <= pend) {
		if((count > 4) || (unsgned && count == 4 && (*p&0x80)))
			err = ASN_ETOOBIG;
		else {
			if(!unsgned && count > 0 && count < 4 && (*p&0x80))
				num = -1;		// set all bits, initially
			while(count--)
				num = (num << 8)|(*p++);
		}
	}
	else
		err = ASN_ESHORT;
	*pint = num;
	*pp = p;
	return err;
}

/*
 * Decode an unsigned int in format where each
 * byte except last has high bit set, and remaining
 * seven bits of each byte are concatenated to form value.
 * Although ASN1 allows any size integer, we return
 * an error if the result doesn't fit in a 32 bit int.
 */
static int
uint7_decode(uchar** pp, uchar* pend, int* pint)
{
	int err;
	int num;
	int more;
	int v;
	uchar* p;

	p = *pp;
	err = ASN_OK;
	num = 0;
	more = 1;
	while(more && p < pend) {
		v = *p++;
		if(num&0x7F000000) {
			err = ASN_ETOOBIG;
			break;
		}
		num <<= 7;
		more = v&0x80;
		num |= (v&0x7F);
	}
	if(p == pend)
		err = ASN_ESHORT;
	*pint = num;
	*pp = p;
	return err;
}

/*
 * Decode an octet string, recursively if isconstr.
 * We've already checked that length==-1 implies isconstr==1,
 * and otherwise that specified length fits within (*pp..pend)
 */
static int
octet_decode(uchar** pp, uchar* pend, int length, int isconstr, Bytes** pbytes)
{
	int err;
	uchar* p;
	Bytes* ans;
	Bytes* newans;
	uchar* pstart;