src/crypto/asn1.c

/*
 * Copyright (C) 2007 Michael Brown <mbrown@fensystems.co.uk>.
 *
 * This 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 any later version.
 *
 * This 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 this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 *
 * You can also choose to distribute this program under the terms of
 * the Unmodified Binary Distribution Licence (as given in the file
 * COPYING.UBDL), provided that you have satisfied its requirements.
 */

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
FILE_SECBOOT ( PERMITTED );

#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include <time.h>
#include <ipxe/tables.h>
#include <ipxe/image.h>
#include <ipxe/crypto.h>
#include <ipxe/asn1.h>

/** @file
 *
 * ASN.1 encoding
 *
 * @anchor asn1parse
 *
 * The ASN.1 parsing helper functions are designed to be safe to use
 * on untrusted input, including malformed input.  Any parsing error
 * will cause the function to invalidate the cursor by setting its
 * length field to zero before returning.
 *
 * All parsing helper functions will strictly respect the cursor's
 * bounds for all purposes (including for determining the tag type and
 * the tag length).  An invalidated cursor (or any cursor that happens
 * to naturally end up with a zero length, e.g. by skipping the only
 * existent object) may therefore safely be passed in to any parsing
 * helper function.
 *
 * A consequence of this design is that it is not necessary to check
 * the return status from all parsing helper functions in a sequence,
 * only to check the return status from the last.  The standard C
 * comma operator may safely be used to connect a sequence of ASN.1
 * parsing operations.  For example:
 *
 * @code
 *
 *	if ( ( rc = ( asn1_enter ( cursor, ASN1_SEQUENCE ),
 *		      asn1_skip ( cursor, ASN1_INTEGER ),
 *		      asn1_enter ( cursor, ASN1_SEQUENCE ) ) ) != 0 ) {
 *		return rc;
 *	}
 *
 * @endcode
 *
 * or equivalently, just:
 *
 * @code
 *
 *	asn1_enter ( cursor, ASN1_SEQUENCE );
 *	asn1_skip ( cursor, ASN1_INTEGER );
 *	if ( ( rc = asn1_enter ( cursor, ASN1_SEQUENCE ) ) != 0 )
 *		return rc;
 *
 * @endcode
 *
 * The caller may not need to check the return status from the parsing
 * helper functions at all.  For example, a caller that is trying to
 * extract a fixed-length octet string from within a deeply nested
 * ASN.1 structure may simply check that the resulting cursor length
 * is correct (which it would have to check anyway).  Since any error
 * will produce a zero-length cursor, this check would also suffice to
 * catch any parsing errors.
 *
 * The cursor navigation functions such as asn1_enter() and
 * asn1_skip() will validate the type and length bytes (which they
 * consume themselves), but will not otherwise validate the contents
 * of the cursor.  Callers must perform their own validation after
 * navigating to the expected data structure (e.g. by checking that
 * the resulting length is correct), or use the higher-level helpers
 * such as asn1_boolean() and asn1_integer() that validate and extract
 * the semantic contents of cursors.
 *
 * The type @c ASN1_ANY may be used as a wildcard type to enter or
 * skip an object of any type.
 *
 * The function asn1_skip_if_exists() may be useful when parsing
 * objects where an encountered type is not knowable in advance
 * (e.g. for sequences containing optional elements).  If the
 * potential type is not found, then asn1_skip_if_exists() will return
 * an error but will not invalidate the cursor (since a missing
 * optional object is not a parsing error).
 *
 * The function asn1_type() may be used to determine the type of an
 * unknown object.  Calling asn1_type() on an invalidated cursor will
 * return @c ASN1_END (and the cursor will remain invalidated).
 *
 */

/* Disambiguate the various error causes */
#define EINVAL_ASN1_EMPTY \
	__einfo_error ( EINFO_EINVAL_ASN1_EMPTY )
#define EINFO_EINVAL_ASN1_EMPTY \
	__einfo_uniqify ( EINFO_EINVAL, 0x01, "Empty or underlength cursor" )
#define EINVAL_ASN1_LEN_LEN \
	__einfo_error ( EINFO_EINVAL_ASN1_LEN_LEN )
#define EINFO_EINVAL_ASN1_LEN_LEN \
	__einfo_uniqify ( EINFO_EINVAL, 0x02, "Length field overruns cursor" )
#define EINVAL_ASN1_LEN \
	__einfo_error ( EINFO_EINVAL_ASN1_LEN )
#define EINFO_EINVAL_ASN1_LEN \
	__einfo_uniqify ( EINFO_EINVAL, 0x03, "Field overruns cursor" )
#define EINVAL_ASN1_BOOLEAN \
	__einfo_error ( EINFO_EINVAL_ASN1_BOOLEAN )
#define EINFO_EINVAL_ASN1_BOOLEAN \
	__einfo_uniqify ( EINFO_EINVAL, 0x04, "Invalid boolean" )
#define EINVAL_ASN1_INTEGER \
	__einfo_error ( EINFO_EINVAL_ASN1_INTEGER )
#define EINFO_EINVAL_ASN1_INTEGER \
	__einfo_uniqify ( EINFO_EINVAL, 0x04, "Invalid integer" )
#define EINVAL_ASN1_TIME \
	__einfo_error ( EINFO_EINVAL_ASN1_TIME )
#define EINFO_EINVAL_ASN1_TIME \
	__einfo_uniqify ( EINFO_EINVAL, 0x05, "Invalid time" )
#define EINVAL_ASN1_ALGORITHM \
	__einfo_error ( EINFO_EINVAL_ASN1_ALGORITHM )
#define EINFO_EINVAL_ASN1_ALGORITHM \
	__einfo_uniqify ( EINFO_EINVAL, 0x06, "Invalid algorithm" )
#define EINVAL_BIT_STRING \
	__einfo_error ( EINFO_EINVAL_BIT_STRING )
#define EINFO_EINVAL_BIT_STRING \
	__einfo_uniqify ( EINFO_EINVAL, 0x07, "Invalid bit string" )
#define ENOTSUP_ALGORITHM \
	__einfo_error ( EINFO_ENOTSUP_ALGORITHM )
#define EINFO_ENOTSUP_ALGORITHM \
	__einfo_uniqify ( EINFO_ENOTSUP, 0x01, "Unsupported algorithm" )
#define ENOTSUP_HIGH \
	__einfo_error ( EINFO_ENOTSUP_HIGH )
#define EINFO_ENOTSUP_HIGH \
	__einfo_uniqify ( EINFO_ENOTSUP, 0x02, "Unsupported high tag number" )
#define ENOTTY_ALGORITHM \
	__einfo_error ( EINFO_ENOTTY_ALGORITHM )
#define EINFO_ENOTTY_ALGORITHM \
	__einfo_uniqify ( EINFO_ENOTTY, 0x01, "Inappropriate algorithm" )

/**
 * Start parsing ASN.1 object
 *
 * @v cursor		ASN.1 object cursor
 * @v type		Expected type, or ASN1_ANY
 * @ret len		Length of object body, or negative error
 *
 * The object cursor will be updated to point to the start of the
 * object body (i.e. the first byte following the length byte(s)), and
 * the length of the object body (i.e. the number of bytes until the
 * following object tag, if any) is returned.
 *
 * If the expected type is not found, the object cursor will not be
 * modified.  If any other error occurs, the object cursor will be
 * invalidated.
 */
static int asn1_start ( struct asn1_cursor *cursor, unsigned int type ) {
	unsigned int len_len;
	unsigned int len;
	uint8_t high_byte;

	/* Sanity check */
	if ( cursor->len < 2 /* Tag byte and first length byte */ ) {
		if ( cursor->len )
			DBGC ( cursor, "ASN1 %p too short\n", cursor );
		asn1_invalidate_cursor ( cursor );
		return -EINVAL_ASN1_EMPTY;
	}

	/* Refuse to handle multi-byte tags */
	if ( ( asn1_type ( cursor ) & ASN1_HIGH ) == ASN1_HIGH ) {
		DBGC ( cursor, "ASN1 %p has unsupported high tag number\n",
		       cursor );
		asn1_invalidate_cursor ( cursor );
		return -ENOTSUP_HIGH;
	}

	/* Check the tag byte */
	if ( ( type != ASN1_ANY ) && ( type != asn1_type ( cursor ) ) ) {
		DBGC ( cursor, "ASN1 %p type mismatch (expected %d, got %d)\n",
		       cursor, type, *( ( uint8_t * ) cursor->data ) );
		return -ENXIO;
	}
	cursor->data++;
	cursor->len--;

	/* Extract length of the length field and sanity check */
	len_len = *( ( uint8_t * ) cursor->data );
	if ( len_len & 0x80 ) {
		len_len = ( len_len & 0x7f );
		cursor->data++;
		cursor->len--;
	} else {
		len_len = 1;
	}
	if ( ( len_len == 0 ) || ( cursor->len < len_len ) ) {
		DBGC ( cursor, "ASN1 %p bad length field length %d (min 0, "
		       "max %zd)\n", cursor, len_len, cursor->len );
		asn1_invalidate_cursor ( cursor );
		return -EINVAL_ASN1_LEN_LEN;
	}

	/* Extract the length and sanity check */
	for ( len = 0 ; len_len ; len_len-- ) {
		high_byte = ( len >> ( 8 * ( sizeof ( len ) - 1 ) ) );
		if ( high_byte ) {
			DBGC ( cursor, "ASN1 %p unrepresentable length\n",
			       cursor );
			asn1_invalidate_cursor ( cursor );
			return -EINVAL_ASN1_LEN;
		}
		len <<= 8;
		len |= *( ( uint8_t * ) cursor->data );
		cursor->data++;
		cursor->len--;
	}
	if ( ( cursor->len < len ) || ( ( ( int ) len ) < 0 ) ) {
		DBGC ( cursor, "ASN1 %p bad length %d (min 0, max %zd)\n",
		       cursor, len, cursor->len );
		asn1_invalidate_cursor ( cursor );
		return -EINVAL_ASN1_LEN;
	}

	return len;
}

/**
 * Enter ASN.1 object
 *
 * @v cursor		ASN.1 object cursor
 * @v type		Expected type, or ASN1_ANY
 * @ret rc		Return status code
 *
 * The object cursor will be updated to point to the body of the
 * current ASN.1 object.
 *
 * If any error occurs, the object cursor will be invalidated.
 */
int asn1_enter ( struct asn1_cursor *cursor, unsigned int type ) {
	int len;

	/* Parse current object */
	len = asn1_start ( cursor, type );
	if ( len < 0 ) {
		asn1_invalidate_cursor ( cursor );
		return len;
	}

	/* Update cursor */
	if ( ( ( size_t ) len ) <= cursor->len )
		cursor->len = len;

	DBGC ( cursor, "ASN1 %p entered object type %02x (len %x)\n",
	       cursor, type, len );
	return 0;
}

/**
 * Skip ASN.1 object if present
 *
 * @v cursor		ASN.1 object cursor
 * @v type		Expected type, or ASN1_ANY
 * @ret rc		Return status code
 *
 * The object cursor will be updated to point to the next ASN.1
 * object.
 *
 * If the expected type is not found, the object cursor will not be
 * modified.  If any other error occurs, the object cursor will be
 * invalidated.
 */
int asn1_skip_if_exists ( struct asn1_cursor *cursor, unsigned int type ) {
	int len;

	/* Parse current object */
	len = asn1_start ( cursor, type );
	if ( len < 0 )
		return len;

	/* Update cursor */
	cursor->data += len;
	cursor->len -= len;

	DBGC ( cursor, "ASN1 %p skipped object type %02x (len %x)\n",
	       cursor, type, len );
	return 0;
}

/**
 * Skip ASN.1 object
 *
 * @v cursor		ASN.1 object cursor
 * @v type		Expected type, or ASN1_ANY
 * @ret rc		Return status code
 *
 * The object cursor will be updated to point to the next ASN.1
 * object.
 *
 * If any error occurs, the object cursor will be invalidated.
 */
int asn1_skip ( struct asn1_cursor *cursor, unsigned int type ) {
	int rc;

	if ( ( rc = asn1_skip_if_exists ( cursor, type ) ) != 0 ) {
		asn1_invalidate_cursor ( cursor );
		return rc;
	}

	return 0;
}

/**
 * Shrink ASN.1 cursor to fit object
 *
 * @v cursor		ASN.1 object cursor
 * @v type		Expected type, or ASN1_ANY
 * @ret rc		Return status code
 *
 * The object cursor will be shrunk to contain only the current ASN.1
 * object.
 *
 * If any error occurs, the object cursor will be invalidated.
 */
int asn1_shrink ( struct asn1_cursor *cursor, unsigned int type ) {
	struct asn1_cursor temp;
	const void *end;
	int len;

	/* Find end of object */
	memcpy ( &temp, cursor, sizeof ( temp ) );
	len = asn1_start ( &temp, type );
	if ( len < 0 ) {
		asn1_invalidate_cursor ( cursor );
		return len;
	}
	end = ( temp.data + len );

	/* Shrink original cursor to contain only its first object */
	cursor->len = ( end - cursor->data );

	return 0;
}

/**
 * Enter ASN.1 object of any type
 *
 * @v cursor		ASN.1 object cursor
 * @ret rc		Return status code
 */
int asn1_enter_any ( struct asn1_cursor *cursor ) {
	return asn1_enter ( cursor, ASN1_ANY );
}

/**
 * Skip ASN.1 object of any type
 *
 * @v cursor		ASN.1 object cursor
 * @ret rc		Return status code
 */
int asn1_skip_any ( struct asn1_cursor *cursor ) {
	return asn1_skip ( cursor, ASN1_ANY );
}

/**
 * Shrink ASN.1 object of any type
 *
 * @v cursor		ASN.1 object cursor
 * @ret rc		Return status code
 */
int asn1_shrink_any ( struct asn1_cursor *cursor ) {
	return asn1_shrink ( cursor, ASN1_ANY );
}

/**
 * Enter ASN.1 bit string
 *
 * @v cursor		ASN.1 cursor
 * @v unused		Unused bits to fill in (or NULL to require all used)
 * @ret rc		Return status code
 */
int asn1_enter_bits ( struct asn1_cursor *cursor, unsigned int *unused ) {
	const struct {
		uint8_t unused;
		uint8_t data[0];
	} __attribute__ (( packed )) *bit_string;
	const uint8_t *last;
	unsigned int unused_bits;
	int rc;

	/* Enter bit string */
	if ( ( rc = asn1_enter ( cursor, ASN1_BIT_STRING ) ) != 0 )
		return rc;

	/* Check that bit string header exists */
	if ( cursor->len < sizeof ( *bit_string ) ) {
		DBGC ( cursor, "ASN1 %p invalid bit string:\n", cursor );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		asn1_invalidate_cursor ( cursor );
		return -EINVAL_BIT_STRING;
	}
	bit_string = cursor->data;
	last = ( cursor->data + cursor->len - 1 );
	cursor->data = &bit_string->data;
	cursor->len -= offsetof ( typeof ( *bit_string ), data );
	unused_bits = bit_string->unused;

	/* Check validity of unused bits */
	if ( ( unused_bits >= 8 ) ||
	     ( ( unused_bits > 0 ) && ( cursor->len == 0 ) ) ||
	     ( ( *last & ( 0xffU >> ( 8 - unused_bits ) ) ) != 0 ) ) {
		DBGC ( cursor, "ASN1 %p invalid bit string:\n", cursor );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		asn1_invalidate_cursor ( cursor );
		return -EINVAL_BIT_STRING;
	}

	/* Record or check number of unused bits, as applicable */
	if ( unused ) {
		*unused = unused_bits;
	} else if ( unused_bits ) {
		DBGC ( cursor, "ASN1 %p invalid integral bit string:\n",
		       cursor );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		asn1_invalidate_cursor ( cursor );
		return -EINVAL_BIT_STRING;
	}

	return 0;
}

/**
 * Enter ASN.1 unsigned integer
 *
 * @v cursor		ASN.1 object cursor
 * @ret rc		Return status code
 */
int asn1_enter_unsigned ( struct asn1_cursor *cursor ) {
	uint8_t msb;
	int rc;

	/* Enter integer */
	if ( ( rc = asn1_enter ( cursor, ASN1_INTEGER ) ) != 0 )
		return rc;

	/* Reject empty integers */
	if ( ! cursor->len ) {
		DBGC ( cursor, "ASN1 %p empty unsigned integer\n", cursor );
		/* Cursor is already invalid */
		return -EINVAL;
	}

	/* Reject negative values */
	msb = *( ( uint8_t * ) cursor->data );
	if ( msb & 0x80 ) {
		DBGC ( cursor, "ASN1 %p negative unsigned integer:\n",
		       cursor );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		asn1_invalidate_cursor ( cursor );
		return -EINVAL;
	}

	/* Skip any initial positive sign byte(s) */
	while ( ( cursor->len > 1 ) && ( msb == 0x00 ) ) {
		cursor->data++;
		cursor->len--;
		msb = *( ( uint8_t * ) cursor->data );
	}

	return 0;
}

/**
 * Parse value of ASN.1 boolean
 *
 * @v cursor		ASN.1 object cursor
 * @ret value		Value, or negative error
 */
int asn1_boolean ( const struct asn1_cursor *cursor ) {
	struct asn1_cursor contents;
	const struct {
		uint8_t value;
	} __attribute__ (( packed )) *boolean;

	/* Enter boolean */
	memcpy ( &contents, cursor, sizeof ( contents ) );
	asn1_enter ( &contents, ASN1_BOOLEAN );
	if ( contents.len != sizeof ( *boolean ) )
		return -EINVAL_ASN1_BOOLEAN;

	/* Extract value */
	boolean = contents.data;
	return boolean->value;
}

/**
 * Parse value of ASN.1 integer
 *
 * @v cursor		ASN.1 object cursor
 * @v value		Value to fill in
 * @ret rc		Return status code
 */
int asn1_integer ( const struct asn1_cursor *cursor, int *value ) {
	struct asn1_cursor contents;
	uint8_t high_byte;
	int rc;

	/* Enter integer */
	memcpy ( &contents, cursor, sizeof ( contents ) );
	if ( ( rc = asn1_enter ( &contents, ASN1_INTEGER ) ) != 0 )
		return rc;
	if ( contents.len < 1 )
		return -EINVAL_ASN1_INTEGER;

	/* Initialise value according to sign byte */
	*value = *( ( int8_t * ) contents.data );
	contents.data++;
	contents.len--;

	/* Process value */
	while ( contents.len ) {
		high_byte = ( (*value) >> ( 8 * ( sizeof ( *value ) - 1 ) ) );
		if ( ( high_byte != 0x00 ) && ( high_byte != 0xff ) ) {
			DBGC ( cursor, "ASN1 %p integer overflow\n", cursor );
			return -EINVAL_ASN1_INTEGER;
		}
		*value = ( ( *value << 8 ) | *( ( uint8_t * ) contents.data ) );
		contents.data++;
		contents.len--;
	}

	return 0;
}

/**
 * Compare two ASN.1 objects
 *
 * @v cursor1		ASN.1 object cursor
 * @v cursor2		ASN.1 object cursor
 * @ret difference	Difference as returned by memcmp()
 *
 * Note that invalid and empty cursors will compare as equal with each
 * other.
 */
int asn1_compare ( const struct asn1_cursor *cursor1,
		   const struct asn1_cursor *cursor2 ) {
	int difference;

	difference = ( cursor2->len - cursor1->len );
	return ( difference ? difference :
		 memcmp ( cursor1->data, cursor2->data, cursor1->len ) );
}

/**
 * Identify ASN.1 algorithm by OID
 *
 * @v cursor		ASN.1 object cursor

 * @ret algorithm	Algorithm, or NULL
 */
static struct asn1_algorithm *
asn1_find_algorithm ( const struct asn1_cursor *cursor ) {
	struct asn1_algorithm *algorithm;

	for_each_table_entry ( algorithm, ASN1_ALGORITHMS ) {
		if ( asn1_compare ( &algorithm->oid, cursor ) == 0 )
			return algorithm;
	}

	return NULL;
}

/**
 * Parse ASN.1 OID-identified algorithm
 *
 * @v cursor		ASN.1 object cursor
 * @ret algorithm	Algorithm
 * @ret params		Algorithm parameters, or NULL
 * @ret rc		Return status code
 */
int asn1_algorithm ( const struct asn1_cursor *cursor,
		     struct asn1_algorithm **algorithm,
		     struct asn1_cursor *params ) {
	struct asn1_cursor contents;
	int rc;

	/* Enter algorithm */
	memcpy ( &contents, cursor, sizeof ( contents ) );
	asn1_enter ( &contents, ASN1_SEQUENCE );

	/* Get raw parameters, if applicable */
	if ( params ) {
		memcpy ( params, &contents, sizeof ( *params ) );
		asn1_skip_any ( params );
	}

	/* Enter algorithm identifier */
	if ( ( rc = asn1_enter ( &contents, ASN1_OID ) ) != 0 ) {
		DBGC ( cursor, "ASN1 %p cannot locate algorithm OID:\n",
		       cursor );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -EINVAL_ASN1_ALGORITHM;
	}

	/* Identify algorithm */
	*algorithm = asn1_find_algorithm ( &contents );
	if ( ! *algorithm ) {
		DBGC ( cursor, "ASN1 %p unrecognised algorithm:\n", cursor );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -ENOTSUP_ALGORITHM;
	}

	/* Parse parameters, if applicable */
	if ( params && (*algorithm)->parse &&
	     ( ( rc = (*algorithm)->parse ( *algorithm, params ) ) != 0 ) ) {
		DBGC ( cursor, "ASN1 %p cannot parse %s parameters: %s\n",
		       cursor, (*algorithm)->name, strerror ( rc ) );
		return rc;
	}

	return 0;
}

/**
 * Parse ASN.1 OID-identified public-key algorithm
 *
 * @v cursor		ASN.1 object cursor
 * @ret algorithm	Algorithm
 * @ret rc		Return status code
 */
int asn1_pubkey_algorithm ( const struct asn1_cursor *cursor,
			    struct asn1_algorithm **algorithm ) {
	int rc;

	/* Parse algorithm */
	if ( ( rc = asn1_algorithm ( cursor, algorithm, NULL ) ) != 0 )
		return rc;

	/* Check algorithm has a public key */
	if ( ! (*algorithm)->pubkey ) {
		DBGC ( cursor, "ASN1 %p algorithm %s is not a public-key "
		       "algorithm:\n", cursor, (*algorithm)->name );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -ENOTTY_ALGORITHM;
	}

	return 0;
}

/**
 * Parse ASN.1 OID-identified digest algorithm
 *
 * @v cursor		ASN.1 object cursor
 * @ret algorithm	Algorithm
 * @ret rc		Return status code
 */
int asn1_digest_algorithm ( const struct asn1_cursor *cursor,
			    struct asn1_algorithm **algorithm ) {
	int rc;

	/* Parse algorithm */
	if ( ( rc = asn1_algorithm ( cursor, algorithm, NULL ) ) != 0 )
		return rc;

	/* Check algorithm has a digest */
	if ( ! (*algorithm)->digest ) {
		DBGC ( cursor, "ASN1 %p algorithm %s is not a digest "
		       "algorithm:\n", cursor, (*algorithm)->name );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -ENOTTY_ALGORITHM;
	}

	return 0;
}

/**
 * Parse ASN.1 OID-identified cipher algorithm
 *
 * @v cursor		ASN.1 object cursor
 * @ret algorithm	Algorithm
 * @ret params		Algorithm parameters, or NULL
 * @ret rc		Return status code
 */
int asn1_cipher_algorithm ( const struct asn1_cursor *cursor,
			    struct asn1_algorithm **algorithm,
			    struct asn1_cursor *params ) {
	int rc;

	/* Parse algorithm */
	if ( ( rc = asn1_algorithm ( cursor, algorithm, params ) ) != 0 )
		return rc;

	/* Check algorithm has a cipher */
	if ( ! (*algorithm)->cipher ) {
		DBGC ( cursor, "ASN1 %p algorithm %s is not a cipher "
		       "algorithm:\n", cursor, (*algorithm)->name );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -ENOTTY_ALGORITHM;
	}

	return 0;
}

/**
 * Parse ASN.1 OID-identified signature algorithm
 *
 * @v cursor		ASN.1 object cursor
 * @ret algorithm	Algorithm
 * @ret rc		Return status code
 */
int asn1_signature_algorithm ( const struct asn1_cursor *cursor,
			       struct asn1_algorithm **algorithm ) {
	int rc;

	/* Parse algorithm */
	if ( ( rc = asn1_algorithm ( cursor, algorithm, NULL ) ) != 0 )
		return rc;

	/* Check algorithm has a public key */
	if ( ! (*algorithm)->pubkey ) {
		DBGC ( cursor, "ASN1 %p algorithm %s is not a signature "
		       "algorithm:\n", cursor, (*algorithm)->name );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -ENOTTY_ALGORITHM;
	}

	/* Check algorithm has a digest */
	if ( ! (*algorithm)->digest ) {
		DBGC ( cursor, "ASN1 %p algorithm %s is not a signature "
		       "algorithm:\n", cursor, (*algorithm)->name );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -ENOTTY_ALGORITHM;
	}

	return 0;
}

/**
 * Parse ASN.1 OID-identified elliptic curve algorithm
 *
 * @v cursor		ASN.1 object cursor
 * @v wrapper		Optional wrapper algorithm, or NULL
 * @ret algorithm	Algorithm
 * @ret rc		Return status code
 */
int asn1_curve_algorithm ( const struct asn1_cursor *cursor,
			   struct asn1_algorithm *wrapper,
			   struct asn1_algorithm **algorithm ) {
	struct asn1_cursor curve;

	/* Elliptic curves are identified as either:
	 *
	 * - a wrapper algorithm "id-ecPublicKey" with the actual
	 *   curve specified in the algorithm parameters, or
	 *
	 * - a standalone object identifier for the curve
	 */
	if ( ( wrapper == NULL ) ||
	     ( asn1_check_algorithm ( cursor, wrapper, &curve ) != 0 ) ) {
		memcpy ( &curve, cursor, sizeof ( curve ) );
	}

	/* Identify curve */
	asn1_enter ( &curve, ASN1_OID );
	*algorithm = asn1_find_algorithm ( &curve );
	if ( ! *algorithm ) {
		DBGC ( cursor, "ASN1 %p unrecognised EC algorithm:\n",
		       cursor );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -ENOTSUP_ALGORITHM;
	}

	/* Check algorithm has an elliptic curve */
	if ( ! (*algorithm)->curve ) {
		DBGC ( cursor, "ASN1 %p algorithm %s is not an elliptic curve "
		       "algorithm:\n", cursor, (*algorithm)->name );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -ENOTTY_ALGORITHM;
	}

	return 0;
}

/**
 * Check ASN.1 OID-identified algorithm
 *
 * @v cursor		ASN.1 object cursor
 * @v expected		Expected algorithm
 * @ret params		Algorithm parameters, or NULL
 * @ret rc		Return status code
 */
int asn1_check_algorithm ( const struct asn1_cursor *cursor,
			   struct asn1_algorithm *expected,
			   struct asn1_cursor *params ) {
	struct asn1_algorithm *actual;
	int rc;

	/* Parse algorithm */
	if ( ( rc = asn1_algorithm ( cursor, &actual, params ) ) != 0 )
		return rc;

	/* Check algorithm matches */
	if ( actual != expected ) {
		DBGC ( cursor, "ASN1 %p algorithm %s does not match %s\n",
		       cursor, actual->name, expected->name );
		return -ENOTTY_ALGORITHM;
	}

	return 0;
}

/**
 * Parse ASN.1 CBC cipher parameters
 *
 * @v algorithm		Algorithm
 * @v param		Parameters to parse
 * @ret rc		Return status code
 */
int asn1_parse_cbc ( struct asn1_algorithm *algorithm,
		     struct asn1_cursor *params ) {
	struct cipher_algorithm *cipher = algorithm->cipher;

	/* Sanity check */
	assert ( cipher != NULL );

	/* Enter parameters */
	asn1_enter ( params, ASN1_OCTET_STRING );

	/* Check length */
	if ( params->len != cipher->blocksize )
		return -EINVAL;

	return 0;
}

/**
 * Parse ASN.1 GCM cipher parameters
 *
 * @v algorithm		Algorithm
 * @v param		Parameters to parse
 * @ret rc		Return status code
 */
int asn1_parse_gcm ( struct asn1_algorithm *algorithm __unused,
		     struct asn1_cursor *params ) {

	/* Enter parameters */
	asn1_enter ( params, ASN1_SEQUENCE );

	/* Enter nonce */
	return asn1_enter ( params, ASN1_OCTET_STRING );
}

/**
 * Parse ASN.1 GeneralizedTime
 *
 * @v cursor		ASN.1 cursor
 * @v time		Time to fill in
 * @ret rc		Return status code
 *
 * RFC 5280 section 4.1.2.5 places several restrictions on the allowed
 * formats for UTCTime and GeneralizedTime, and mandates the
 * interpretation of centuryless year values.
 */
int asn1_generalized_time ( const struct asn1_cursor *cursor, time_t *time ) {
	struct asn1_cursor contents;
	unsigned int have_century;
	unsigned int type;
	union {
		struct {
			uint8_t century;
			uint8_t year;
			uint8_t month;
			uint8_t day;
			uint8_t hour;
			uint8_t minute;
			uint8_t second;
		} __attribute__ (( packed )) named;
		uint8_t raw[7];
	} pairs;
	struct tm tm;
	const uint8_t *data;
	size_t remaining;
	unsigned int tens;
	unsigned int units;
	unsigned int i;
	int rc;

	/* Determine time format utcTime/generalizedTime */
	memcpy ( &contents, cursor, sizeof ( contents ) );
	type = asn1_type ( &contents );
	switch ( type ) {
	case ASN1_UTC_TIME:
		have_century = 0;
		break;
	case ASN1_GENERALIZED_TIME:
		have_century = 1;
		break;
	default:
		DBGC ( cursor, "ASN1 %p invalid time type %02x\n",
		       cursor, type );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -EINVAL_ASN1_TIME;
	}

	/* Enter utcTime/generalizedTime */
	if ( ( rc = asn1_enter ( &contents, type ) ) != 0 ) {
		DBGC ( cursor, "ASN1 %p cannot locate %s time:\n", cursor,
		       ( ( type == ASN1_UTC_TIME ) ? "UTC" : "generalized" ) );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return rc;
	}

	/* Parse digit string a pair at a time */
	memset ( &pairs, 0, sizeof ( pairs ) );
	data = contents.data;
	remaining = contents.len;
	for ( i = ( have_century ? 0 : 1 ) ; i < sizeof ( pairs.raw ) ; i++ ) {
		if ( remaining < 2 ) {
			/* Some certificates violate the X.509 RFC by
			 * omitting the "seconds" value.
			 */
			if ( i == ( sizeof ( pairs.raw ) - 1 ) )
				break;
			DBGC ( cursor, "ASN1 %p invalid time:\n", cursor );
			DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
			return -EINVAL_ASN1_TIME;
		}
		tens = data[0];
		units = data[1];
		if ( ! ( isdigit ( tens ) && isdigit ( units ) ) ) {
			DBGC ( cursor, "ASN1 %p invalid time:\n", cursor );
			DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
			return -EINVAL_ASN1_TIME;
		}
		pairs.raw[i] = ( ( 10 * ( tens - '0' ) ) + ( units - '0' ) );
		data += 2;
		remaining -= 2;
	}

	/* Determine century if applicable */
	if ( ! have_century )
		pairs.named.century = ( ( pairs.named.year >= 50 ) ? 19 : 20 );

	/* Check for trailing "Z" */
	if ( ( remaining != 1 ) || ( data[0] != 'Z' ) ) {
		DBGC ( cursor, "ASN1 %p invalid time:\n", cursor );
		DBGC_HDA ( cursor, 0, cursor->data, cursor->len );
		return -EINVAL_ASN1_TIME;
	}

	/* Fill in time */
	tm.tm_year = ( ( ( pairs.named.century - 19 ) * 100 ) +
		       pairs.named.year );
	tm.tm_mon = ( pairs.named.month - 1 );
	tm.tm_mday = pairs.named.day;
	tm.tm_hour = pairs.named.hour;
	tm.tm_min = pairs.named.minute;
	tm.tm_sec = pairs.named.second;

	/* Convert to seconds since the Epoch */
	*time = mktime ( &tm );

	return 0;
}

/**
 * Construct ASN.1 header
 *
 * @v header		ASN.1 builder header
 * @v type		Type
 * @v len		Content length
 * @ret header_len	Header length
 */
static size_t asn1_header ( struct asn1_builder_header *header,
			    unsigned int type, size_t len ) {
	unsigned int header_len = 2;
	unsigned int len_len = 0;
	size_t temp;

	/* Construct header */
	header->type = type;
	if ( len < 0x80 ) {
		header->length[0] = len;
	} else {
		for ( temp = len ; temp ; temp >>= 8 )
			len_len++;
		header->length[0] = ( 0x80 | len_len );
		header_len += len_len;
		for ( temp = len ; temp ; temp >>= 8 )
			header->length[len_len--] = ( temp & 0xff );
	}

	return header_len;
}

/**
 * Calculate ASN.1 header length
 *
 * @v len		Content length
 * @ret header_len	Header length
 */
size_t asn1_header_len ( size_t len ) {
	struct asn1_builder_header header;

	return asn1_header ( &header, ASN1_ANY, len );
}

/**
 * Grow ASN.1 builder
 *
 * @v builder		ASN.1 builder
 * @v extra		Extra space to prepend
 * @ret rc		Return status code
 */
int asn1_grow ( struct asn1_builder *builder, size_t extra ) {
	size_t new_len;
	void *new;

	/* As with the ASN1 parsing functions, make errors permanent */
	if ( builder->len && ! builder->data )
		return -ENOMEM;

	/* Reallocate data buffer */
	new_len = ( builder->len + extra );
	new = realloc ( builder->data, new_len );
	if ( ! new ) {
		zfree ( builder->data );
		builder->data = NULL;
		return -ENOMEM;
	}
	builder->data = new;

	/* Move existing data to end of buffer */
	memmove ( ( builder->data + extra ), builder->data, builder->len );
	builder->len = new_len;

	return 0;
}

/**
 * Prepend raw data to ASN.1 builder
 *
 * @v builder		ASN.1 builder
 * @v data		Data to prepend
 * @v len		Length of data to prepend
 * @ret rc		Return status code
 */
int asn1_prepend_raw ( struct asn1_builder *builder, const void *data,
		       size_t len ) {
	int rc;

	/* Grow buffer */
	if ( ( rc = asn1_grow ( builder, len ) ) != 0 )
		return rc;

	/* Populate data buffer */
	memcpy ( builder->data, data, len );

	return 0;
}

/**
 * Prepend data to ASN.1 builder
 *
 * @v builder		ASN.1 builder
 * @v type		Type
 * @v data		Data to prepend
 * @v len		Length of data to prepend
 * @ret rc		Return status code
 */
int asn1_prepend ( struct asn1_builder *builder, unsigned int type,
		   const void *data, size_t len ) {
	struct asn1_builder_header header;
	size_t header_len;
	int rc;

	/* Construct header */
	header_len = asn1_header ( &header, type, len );

	/* Grow buffer */
	if ( ( rc = asn1_grow ( builder, header_len + len ) ) != 0 )
		return rc;

	/* Populate data buffer */
	memcpy ( builder->data, &header, header_len );
	memcpy ( ( builder->data + header_len ), data, len );

	return 0;
}

/**
 * Wrap ASN.1 builder
 *
 * @v builder		ASN.1 builder
 * @v type		Type
 * @ret rc		Return status code
 */
int asn1_wrap ( struct asn1_builder *builder, unsigned int type ) {
	struct asn1_builder_header header;
	size_t header_len;
	int rc;

	/* Construct header */
	header_len = asn1_header ( &header, type, builder->len );

	/* Grow buffer */
	if ( ( rc = asn1_grow ( builder, header_len ) ) != 0 )
		return rc;

	/* Populate data buffer */
	memcpy ( builder->data, &header, header_len );

	return 0;
}

/**
 * Extract ASN.1 object from image
 *
 * @v image		Image
 * @v offset		Offset within image
 * @v cursor		ASN.1 cursor to fill in
 * @ret next		Offset to next image, or negative error
 *
 * The caller is responsible for eventually calling free() on the
 * allocated ASN.1 cursor.
 */
int image_asn1 ( struct image *image, size_t offset,
		 struct asn1_cursor **cursor ) {
	int next;
	int rc;

	/* Sanity check */
	assert ( offset <= image->len );

	/* Check that this image can be used to extract an ASN.1 object */
	if ( ! ( image->type && image->type->asn1 ) )
		return -ENOTSUP;

	/* Try creating ASN.1 cursor */
	next = image->type->asn1 ( image, offset, cursor );
	if ( next < 0 ) {
		rc = next;
		DBGC ( image, "IMAGE %s could not extract ASN.1 object: %s\n",
		       image->name, strerror ( rc ) );
		return rc;
	}

	return next;
}

/* Drag in objects via image_asn1() */
REQUIRING_SYMBOL ( image_asn1 );

/* Drag in ASN.1 image formats */
REQUIRE_OBJECT ( config_asn1 );