[linux.git] / lib / asn1_decoder.c

/* Decoder for ASN.1 BER/DER/CER encoded bytestream
 *
 * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells ([email protected])
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public Licence
 * as published by the Free Software Foundation; either version
 * 2 of the Licence, or (at your option) any later version.
 */

#include <linux/export.h>
#include <linux/kernel.h>
#include <linux/errno.h>
#include <linux/asn1_decoder.h>
#include <linux/asn1_ber_bytecode.h>

static const unsigned char asn1_op_lengths[ASN1_OP__NR] = {
	/*					OPC TAG JMP ACT */
	[ASN1_OP_MATCH]				= 1 + 1,
	[ASN1_OP_MATCH_OR_SKIP]			= 1 + 1,
	[ASN1_OP_MATCH_ACT]			= 1 + 1     + 1,
	[ASN1_OP_MATCH_ACT_OR_SKIP]		= 1 + 1     + 1,
	[ASN1_OP_MATCH_JUMP]			= 1 + 1 + 1,
	[ASN1_OP_MATCH_JUMP_OR_SKIP]		= 1 + 1 + 1,
	[ASN1_OP_MATCH_ANY]			= 1,
	[ASN1_OP_MATCH_ANY_OR_SKIP]		= 1,
	[ASN1_OP_MATCH_ANY_ACT]			= 1         + 1,
	[ASN1_OP_MATCH_ANY_ACT_OR_SKIP]		= 1         + 1,
	[ASN1_OP_COND_MATCH_OR_SKIP]		= 1 + 1,
	[ASN1_OP_COND_MATCH_ACT_OR_SKIP]	= 1 + 1     + 1,
	[ASN1_OP_COND_MATCH_JUMP_OR_SKIP]	= 1 + 1 + 1,
	[ASN1_OP_COND_MATCH_ANY]		= 1,
	[ASN1_OP_COND_MATCH_ANY_OR_SKIP]	= 1,
	[ASN1_OP_COND_MATCH_ANY_ACT]		= 1         + 1,
	[ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP]	= 1         + 1,
	[ASN1_OP_COND_FAIL]			= 1,
	[ASN1_OP_COMPLETE]			= 1,
	[ASN1_OP_ACT]				= 1         + 1,
	[ASN1_OP_MAYBE_ACT]			= 1         + 1,
	[ASN1_OP_RETURN]			= 1,
	[ASN1_OP_END_SEQ]			= 1,
	[ASN1_OP_END_SEQ_OF]			= 1     + 1,
	[ASN1_OP_END_SET]			= 1,
	[ASN1_OP_END_SET_OF]			= 1     + 1,
	[ASN1_OP_END_SEQ_ACT]			= 1         + 1,
	[ASN1_OP_END_SEQ_OF_ACT]		= 1     + 1 + 1,
	[ASN1_OP_END_SET_ACT]			= 1         + 1,
	[ASN1_OP_END_SET_OF_ACT]		= 1     + 1 + 1,
};

/*
 * Find the length of an indefinite length object
 * @data: The data buffer
 * @datalen: The end of the innermost containing element in the buffer
 * @_dp: The data parse cursor (updated before returning)
 * @_len: Where to return the size of the element.
 * @_errmsg: Where to return a pointer to an error message on error
 */
static int asn1_find_indefinite_length(const unsigned char *data, size_t datalen,
				       size_t *_dp, size_t *_len,
				       const char **_errmsg)
{
	unsigned char tag, tmp;
	size_t dp = *_dp, len, n;
	int indef_level = 1;

next_tag:
	if (unlikely(datalen - dp < 2)) {
		if (datalen == dp)
			goto missing_eoc;
		goto data_overrun_error;
	}

	/* Extract a tag from the data */
	tag = data[dp++];
	if (tag == 0) {
		/* It appears to be an EOC. */
		if (data[dp++] != 0)
			goto invalid_eoc;
		if (--indef_level <= 0) {
			*_len = dp - *_dp;
			*_dp = dp;
			return 0;
		}
		goto next_tag;
	}

	if (unlikely((tag & 0x1f) == ASN1_LONG_TAG)) {
		do {
			if (unlikely(datalen - dp < 2))
				goto data_overrun_error;
			tmp = data[dp++];
		} while (tmp & 0x80);
	}

	/* Extract the length */
	len = data[dp++];
	if (len <= 0x7f) {
		dp += len;
		goto next_tag;
	}

	if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
		/* Indefinite length */
		if (unlikely((tag & ASN1_CONS_BIT) == ASN1_PRIM << 5))
			goto indefinite_len_primitive;
		indef_level++;
		goto next_tag;
	}

	n = len - 0x80;
	if (unlikely(n > sizeof(size_t) - 1))
		goto length_too_long;
	if (unlikely(n > datalen - dp))
		goto data_overrun_error;
	for (len = 0; n > 0; n--) {
		len <<= 8;
		len |= data[dp++];
	}
	dp += len;
	goto next_tag;

length_too_long:
	*_errmsg = "Unsupported length";
	goto error;
indefinite_len_primitive:
	*_errmsg = "Indefinite len primitive not permitted";
	goto error;
invalid_eoc:
	*_errmsg = "Invalid length EOC";
	goto error;
data_overrun_error:
	*_errmsg = "Data overrun error";
	goto error;
missing_eoc:
	*_errmsg = "Missing EOC in indefinite len cons";
error:
	*_dp = dp;
	return -1;
}

/**
 * asn1_ber_decoder - Decoder BER/DER/CER ASN.1 according to pattern
 * @decoder: The decoder definition (produced by asn1_compiler)
 * @context: The caller's context (to be passed to the action functions)
 * @data: The encoded data
 * @datalen: The size of the encoded data
 *
 * Decode BER/DER/CER encoded ASN.1 data according to a bytecode pattern
 * produced by asn1_compiler.  Action functions are called on marked tags to
 * allow the caller to retrieve significant data.
 *
 * LIMITATIONS:
 *
 * To keep down the amount of stack used by this function, the following limits
 * have been imposed:
 *
 *  (1) This won't handle datalen > 65535 without increasing the size of the
 *	cons stack elements and length_too_long checking.
 *
 *  (2) The stack of constructed types is 10 deep.  If the depth of non-leaf
 *	constructed types exceeds this, the decode will fail.
 *
 *  (3) The SET type (not the SET OF type) isn't really supported as tracking
 *	what members of the set have been seen is a pain.
 */
int asn1_ber_decoder(const struct asn1_decoder *decoder,
		     void *context,
		     const unsigned char *data,
		     size_t datalen)
{
	const unsigned char *machine = decoder->machine;
	const asn1_action_t *actions = decoder->actions;
	size_t machlen = decoder->machlen;
	enum asn1_opcode op;
	unsigned char tag = 0, csp = 0, jsp = 0, optag = 0, hdr = 0;
	const char *errmsg;
	size_t pc = 0, dp = 0, tdp = 0, len = 0;
	int ret;

	unsigned char flags = 0;
#define FLAG_INDEFINITE_LENGTH	0x01
#define FLAG_MATCHED		0x02
#define FLAG_LAST_MATCHED	0x04 /* Last tag matched */
#define FLAG_CONS		0x20 /* Corresponds to CONS bit in the opcode tag
				      * - ie. whether or not we are going to parse
				      *   a compound type.
				      */

#define NR_CONS_STACK 10
	unsigned short cons_dp_stack[NR_CONS_STACK];
	unsigned short cons_datalen_stack[NR_CONS_STACK];
	unsigned char cons_hdrlen_stack[NR_CONS_STACK];
#define NR_JUMP_STACK 10
	unsigned char jump_stack[NR_JUMP_STACK];

	if (datalen > 65535)
		return -EMSGSIZE;

next_op:
	pr_debug("next_op: pc=\e[32m%zu\e[m/%zu dp=\e[33m%zu\e[m/%zu C=%d J=%d\n",
		 pc, machlen, dp, datalen, csp, jsp);
	if (unlikely(pc >= machlen))
		goto machine_overrun_error;
	op = machine[pc];
	if (unlikely(pc + asn1_op_lengths[op] > machlen))
		goto machine_overrun_error;

	/* If this command is meant to match a tag, then do that before
	 * evaluating the command.
	 */
	if (op <= ASN1_OP__MATCHES_TAG) {
		unsigned char tmp;

		/* Skip conditional matches if possible */
		if ((op & ASN1_OP_MATCH__COND && flags & FLAG_MATCHED) ||
		    (op & ASN1_OP_MATCH__SKIP && dp == datalen)) {
			flags &= ~FLAG_LAST_MATCHED;
			pc += asn1_op_lengths[op];
			goto next_op;
		}

		flags = 0;
		hdr = 2;

		/* Extract a tag from the data */
		if (unlikely(dp >= datalen - 1))
			goto data_overrun_error;
		tag = data[dp++];
		if (unlikely((tag & 0x1f) == ASN1_LONG_TAG))
			goto long_tag_not_supported;

		if (op & ASN1_OP_MATCH__ANY) {
			pr_debug("- any %02x\n", tag);
		} else {
			/* Extract the tag from the machine
			 * - Either CONS or PRIM are permitted in the data if
			 *   CONS is not set in the op stream, otherwise CONS
			 *   is mandatory.
			 */
			optag = machine[pc + 1];
			flags |= optag & FLAG_CONS;

			/* Determine whether the tag matched */
			tmp = optag ^ tag;
			tmp &= ~(optag & ASN1_CONS_BIT);
			pr_debug("- match? %02x %02x %02x\n", tag, optag, tmp);
			if (tmp != 0) {
				/* All odd-numbered tags are MATCH_OR_SKIP. */
				if (op & ASN1_OP_MATCH__SKIP) {
					pc += asn1_op_lengths[op];
					dp--;
					goto next_op;
				}
				goto tag_mismatch;
			}
		}
		flags |= FLAG_MATCHED;

		len = data[dp++];
		if (len > 0x7f) {
			if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
				/* Indefinite length */
				if (unlikely(!(tag & ASN1_CONS_BIT)))
					goto indefinite_len_primitive;
				flags |= FLAG_INDEFINITE_LENGTH;
				if (unlikely(2 > datalen - dp))
					goto data_overrun_error;
			} else {
				int n = len - 0x80;
				if (unlikely(n > 2))
					goto length_too_long;
				if (unlikely(dp >= datalen - n))
					goto data_overrun_error;
				hdr += n;
				for (len = 0; n > 0; n--) {
					len <<= 8;
					len |= data[dp++];
				}
				if (unlikely(len > datalen - dp))
					goto data_overrun_error;
			}
		}

		if (flags & FLAG_CONS) {
			/* For expected compound forms, we stack the positions
			 * of the start and end of the data.
			 */
			if (unlikely(csp >= NR_CONS_STACK))
				goto cons_stack_overflow;
			cons_dp_stack[csp] = dp;
			cons_hdrlen_stack[csp] = hdr;
			if (!(flags & FLAG_INDEFINITE_LENGTH)) {
				cons_datalen_stack[csp] = datalen;
				datalen = dp + len;
			} else {
				cons_datalen_stack[csp] = 0;
			}
			csp++;
		}

		pr_debug("- TAG: %02x %zu%s\n",
			 tag, len, flags & FLAG_CONS ? " CONS" : "");
		tdp = dp;
	}

	/* Decide how to handle the operation */
	switch (op) {
	case ASN1_OP_MATCH_ANY_ACT:
	case ASN1_OP_MATCH_ANY_ACT_OR_SKIP:
	case ASN1_OP_COND_MATCH_ANY_ACT:
	case ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP:
		ret = actions[machine[pc + 1]](context, hdr, tag, data + dp, len);
		if (ret < 0)
			return ret;
		goto skip_data;

	case ASN1_OP_MATCH_ACT:
	case ASN1_OP_MATCH_ACT_OR_SKIP:
	case ASN1_OP_COND_MATCH_ACT_OR_SKIP:
		ret = actions[machine[pc + 2]](context, hdr, tag, data + dp, len);
		if (ret < 0)
			return ret;
		goto skip_data;

	case ASN1_OP_MATCH:
	case ASN1_OP_MATCH_OR_SKIP:
	case ASN1_OP_MATCH_ANY:
	case ASN1_OP_MATCH_ANY_OR_SKIP:
	case ASN1_OP_COND_MATCH_OR_SKIP:
	case ASN1_OP_COND_MATCH_ANY:
	case ASN1_OP_COND_MATCH_ANY_OR_SKIP:
	skip_data:
		if (!(flags & FLAG_CONS)) {
			if (flags & FLAG_INDEFINITE_LENGTH) {
				ret = asn1_find_indefinite_length(
					data, datalen, &dp, &len, &errmsg);
				if (ret < 0)
					goto error;
			} else {
				dp += len;
			}
			pr_debug("- LEAF: %zu\n", len);
		}
		pc += asn1_op_lengths[op];
		goto next_op;

	case ASN1_OP_MATCH_JUMP:
	case ASN1_OP_MATCH_JUMP_OR_SKIP:
	case ASN1_OP_COND_MATCH_JUMP_OR_SKIP:
		pr_debug("- MATCH_JUMP\n");
		if (unlikely(jsp == NR_JUMP_STACK))
			goto jump_stack_overflow;
		jump_stack[jsp++] = pc + asn1_op_lengths[op];
		pc = machine[pc + 2];
		goto next_op;

	case ASN1_OP_COND_FAIL:
		if (unlikely(!(flags & FLAG_MATCHED)))
			goto tag_mismatch;
		pc += asn1_op_lengths[op];
		goto next_op;

	case ASN1_OP_COMPLETE:
		if (unlikely(jsp != 0 || csp != 0)) {
			pr_err("ASN.1 decoder error: Stacks not empty at completion (%u, %u)\n",
			       jsp, csp);
			return -EBADMSG;
		}
		return 0;

	case ASN1_OP_END_SET:
	case ASN1_OP_END_SET_ACT:
		if (unlikely(!(flags & FLAG_MATCHED)))
			goto tag_mismatch;
	case ASN1_OP_END_SEQ:
	case ASN1_OP_END_SET_OF:
	case ASN1_OP_END_SEQ_OF:
	case ASN1_OP_END_SEQ_ACT:
	case ASN1_OP_END_SET_OF_ACT:
	case ASN1_OP_END_SEQ_OF_ACT:
		if (unlikely(csp <= 0))
			goto cons_stack_underflow;
		csp--;
		tdp = cons_dp_stack[csp];
		hdr = cons_hdrlen_stack[csp];
		len = datalen;
		datalen = cons_datalen_stack[csp];
		pr_debug("- end cons t=%zu dp=%zu l=%zu/%zu\n",
			 tdp, dp, len, datalen);
		if (datalen == 0) {
			/* Indefinite length - check for the EOC. */
			datalen = len;
			if (unlikely(datalen - dp < 2))
				goto data_overrun_error;
			if (data[dp++] != 0) {
				if (op & ASN1_OP_END__OF) {
					dp--;
					csp++;
					pc = machine[pc + 1];
					pr_debug("- continue\n");
					goto next_op;
				}
				goto missing_eoc;
			}
			if (data[dp++] != 0)
				goto invalid_eoc;
			len = dp - tdp - 2;
		} else {
			if (dp < len && (op & ASN1_OP_END__OF)) {
				datalen = len;
				csp++;
				pc = machine[pc + 1];
				pr_debug("- continue\n");
				goto next_op;
			}
			if (dp != len)
				goto cons_length_error;
			len -= tdp;
			pr_debug("- cons len l=%zu d=%zu\n", len, dp - tdp);
		}

		if (op & ASN1_OP_END__ACT) {
			unsigned char act;
			if (op & ASN1_OP_END__OF)
				act = machine[pc + 2];
			else
				act = machine[pc + 1];
			ret = actions[act](context, hdr, 0, data + tdp, len);
		}
		pc += asn1_op_lengths[op];
		goto next_op;

	case ASN1_OP_MAYBE_ACT:
		if (!(flags & FLAG_LAST_MATCHED)) {
			pc += asn1_op_lengths[op];
			goto next_op;
		}
	case ASN1_OP_ACT:
		ret = actions[machine[pc + 1]](context, hdr, tag, data + tdp, len);
		if (ret < 0)
			return ret;
		pc += asn1_op_lengths[op];
		goto next_op;

	case ASN1_OP_RETURN:
		if (unlikely(jsp <= 0))
			goto jump_stack_underflow;
		pc = jump_stack[--jsp];
		flags |= FLAG_MATCHED | FLAG_LAST_MATCHED;
		goto next_op;

	default:
		break;
	}

	/* Shouldn't reach here */
	pr_err("ASN.1 decoder error: Found reserved opcode (%u) pc=%zu\n",
	       op, pc);
	return -EBADMSG;

data_overrun_error:
	errmsg = "Data overrun error";
	goto error;
machine_overrun_error:
	errmsg = "Machine overrun error";
	goto error;
jump_stack_underflow:
	errmsg = "Jump stack underflow";
	goto error;
jump_stack_overflow:
	errmsg = "Jump stack overflow";
	goto error;
cons_stack_underflow:
	errmsg = "Cons stack underflow";
	goto error;
cons_stack_overflow:
	errmsg = "Cons stack overflow";
	goto error;
cons_length_error:
	errmsg = "Cons length error";
	goto error;
missing_eoc:
	errmsg = "Missing EOC in indefinite len cons";
	goto error;
invalid_eoc:
	errmsg = "Invalid length EOC";
	goto error;
length_too_long:
	errmsg = "Unsupported length";
	goto error;
indefinite_len_primitive:
	errmsg = "Indefinite len primitive not permitted";
	goto error;
tag_mismatch:
	errmsg = "Unexpected tag";
	goto error;
long_tag_not_supported:
	errmsg = "Long tag not supported";
error:
	pr_debug("\nASN1: %s [m=%zu d=%zu ot=%02x t=%02x l=%zu]\n",
		 errmsg, pc, dp, optag, tag, len);
	return -EBADMSG;
}
EXPORT_SYMBOL_GPL(asn1_ber_decoder);
Commit	Line	Data
42d5ec27 DH	1	/* Decoder for ASN.1 BER/DER/CER encoded bytestream
	2	*
	3	* Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
	4	* Written by David Howells ([email protected])
	5	*
	6	* This program is free software; you can redistribute it and/or
	7	* modify it under the terms of the GNU General Public Licence
	8	* as published by the Free Software Foundation; either version
	9	* 2 of the Licence, or (at your option) any later version.
	10	*/
	11
	12	#include <linux/export.h>
	13	#include <linux/kernel.h>
	14	#include <linux/errno.h>
	15	#include <linux/asn1_decoder.h>
	16	#include <linux/asn1_ber_bytecode.h>
	17
	18	static const unsigned char asn1_op_lengths[ASN1_OP__NR] = {
	19	/* OPC TAG JMP ACT */
	20	[ASN1_OP_MATCH] = 1 + 1,
	21	[ASN1_OP_MATCH_OR_SKIP] = 1 + 1,
	22	[ASN1_OP_MATCH_ACT] = 1 + 1 + 1,
	23	[ASN1_OP_MATCH_ACT_OR_SKIP] = 1 + 1 + 1,
	24	[ASN1_OP_MATCH_JUMP] = 1 + 1 + 1,
	25	[ASN1_OP_MATCH_JUMP_OR_SKIP] = 1 + 1 + 1,
	26	[ASN1_OP_MATCH_ANY] = 1,
233ce79d	27	[ASN1_OP_MATCH_ANY_OR_SKIP] = 1,
42d5ec27	28	[ASN1_OP_MATCH_ANY_ACT] = 1 + 1,
233ce79d	29	[ASN1_OP_MATCH_ANY_ACT_OR_SKIP] = 1 + 1,
42d5ec27 DH	30	[ASN1_OP_COND_MATCH_OR_SKIP] = 1 + 1,
	31	[ASN1_OP_COND_MATCH_ACT_OR_SKIP] = 1 + 1 + 1,
	32	[ASN1_OP_COND_MATCH_JUMP_OR_SKIP] = 1 + 1 + 1,
	33	[ASN1_OP_COND_MATCH_ANY] = 1,
233ce79d	34	[ASN1_OP_COND_MATCH_ANY_OR_SKIP] = 1,
42d5ec27	35	[ASN1_OP_COND_MATCH_ANY_ACT] = 1 + 1,
233ce79d	36	[ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP] = 1 + 1,
42d5ec27 DH	37	[ASN1_OP_COND_FAIL] = 1,
	38	[ASN1_OP_COMPLETE] = 1,
	39	[ASN1_OP_ACT] = 1 + 1,
3f3af97d	40	[ASN1_OP_MAYBE_ACT] = 1 + 1,
42d5ec27 DH	41	[ASN1_OP_RETURN] = 1,
	42	[ASN1_OP_END_SEQ] = 1,
	43	[ASN1_OP_END_SEQ_OF] = 1 + 1,
	44	[ASN1_OP_END_SET] = 1,
	45	[ASN1_OP_END_SET_OF] = 1 + 1,
	46	[ASN1_OP_END_SEQ_ACT] = 1 + 1,
	47	[ASN1_OP_END_SEQ_OF_ACT] = 1 + 1 + 1,
	48	[ASN1_OP_END_SET_ACT] = 1 + 1,
	49	[ASN1_OP_END_SET_OF_ACT] = 1 + 1 + 1,
	50	};
	51
	52	/*
	53	* Find the length of an indefinite length object
dbadc176 DH	54	* @data: The data buffer
	55	* @datalen: The end of the innermost containing element in the buffer
	56	* @_dp: The data parse cursor (updated before returning)
	57	* @_len: Where to return the size of the element.
	58	* @_errmsg: Where to return a pointer to an error message on error
42d5ec27 DH	59	*/
42d5ec27 DH	60	static int asn1_find_indefinite_length(const unsigned char *data, size_t datalen,
dbadc176 DH	61	size_t _dp, size_t _len,
dbadc176 DH	62	const char **_errmsg)
42d5ec27 DH	63	{
42d5ec27 DH	64	unsigned char tag, tmp;
dbadc176	65	size_t dp = *_dp, len, n;
42d5ec27 DH	66	int indef_level = 1;
	67
	68	next_tag:
	69	if (unlikely(datalen - dp < 2)) {
	70	if (datalen == dp)
	71	goto missing_eoc;
	72	goto data_overrun_error;
	73	}
	74
	75	/* Extract a tag from the data */
	76	tag = data[dp++];
	77	if (tag == 0) {
	78	/* It appears to be an EOC. */
	79	if (data[dp++] != 0)
	80	goto invalid_eoc;
dbadc176 DH	81	if (--indef_level <= 0) {
	82	_len = dp - _dp;
	83	*_dp = dp;
	84	return 0;
	85	}
42d5ec27 DH	86	goto next_tag;
	87	}
	88
99cca91e	89	if (unlikely((tag & 0x1f) == ASN1_LONG_TAG)) {
42d5ec27 DH	90	do {
	91	if (unlikely(datalen - dp < 2))
	92	goto data_overrun_error;
	93	tmp = data[dp++];
	94	} while (tmp & 0x80);
	95	}
	96
	97	/* Extract the length */
	98	len = data[dp++];
f3537f91	99	if (len <= 0x7f) {
42d5ec27 DH	100	dp += len;
	101	goto next_tag;
	102	}
	103
99cca91e	104	if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
42d5ec27 DH	105	/* Indefinite length */
	106	if (unlikely((tag & ASN1_CONS_BIT) == ASN1_PRIM << 5))
	107	goto indefinite_len_primitive;
	108	indef_level++;
	109	goto next_tag;
	110	}
	111
	112	n = len - 0x80;
	113	if (unlikely(n > sizeof(size_t) - 1))
	114	goto length_too_long;
	115	if (unlikely(n > datalen - dp))
	116	goto data_overrun_error;
	117	for (len = 0; n > 0; n--) {
	118	len <<= 8;
	119	len \|= data[dp++];
	120	}
	121	dp += len;
	122	goto next_tag;
	123
	124	length_too_long:
	125	*_errmsg = "Unsupported length";
	126	goto error;
	127	indefinite_len_primitive:
	128	*_errmsg = "Indefinite len primitive not permitted";
	129	goto error;
	130	invalid_eoc:
	131	*_errmsg = "Invalid length EOC";
	132	goto error;
	133	data_overrun_error:
	134	*_errmsg = "Data overrun error";
	135	goto error;
	136	missing_eoc:
	137	*_errmsg = "Missing EOC in indefinite len cons";
	138	error:
dbadc176	139	*_dp = dp;
42d5ec27 DH	140	return -1;
	141	}
	142
	143	/**
	144	* asn1_ber_decoder - Decoder BER/DER/CER ASN.1 according to pattern
	145	* @decoder: The decoder definition (produced by asn1_compiler)
	146	* @context: The caller's context (to be passed to the action functions)
	147	* @data: The encoded data
548bbff9	148	* @datalen: The size of the encoded data
42d5ec27 DH	149	*
	150	* Decode BER/DER/CER encoded ASN.1 data according to a bytecode pattern
	151	* produced by asn1_compiler. Action functions are called on marked tags to
	152	* allow the caller to retrieve significant data.
	153	*
	154	* LIMITATIONS:
	155	*
	156	* To keep down the amount of stack used by this function, the following limits
	157	* have been imposed:
	158	*
	159	* (1) This won't handle datalen > 65535 without increasing the size of the
	160	* cons stack elements and length_too_long checking.
	161	*
	162	* (2) The stack of constructed types is 10 deep. If the depth of non-leaf
	163	* constructed types exceeds this, the decode will fail.
	164	*
	165	* (3) The SET type (not the SET OF type) isn't really supported as tracking
	166	* what members of the set have been seen is a pain.
	167	*/
	168	int asn1_ber_decoder(const struct asn1_decoder *decoder,
	169	void *context,
	170	const unsigned char *data,
	171	size_t datalen)
	172	{
	173	const unsigned char *machine = decoder->machine;
	174	const asn1_action_t *actions = decoder->actions;
	175	size_t machlen = decoder->machlen;
	176	enum asn1_opcode op;
	177	unsigned char tag = 0, csp = 0, jsp = 0, optag = 0, hdr = 0;
	178	const char *errmsg;
	179	size_t pc = 0, dp = 0, tdp = 0, len = 0;
	180	int ret;
	181
	182	unsigned char flags = 0;
	183	#define FLAG_INDEFINITE_LENGTH 0x01
	184	#define FLAG_MATCHED 0x02
3f3af97d	185	#define FLAG_LAST_MATCHED 0x04 /* Last tag matched */
42d5ec27 DH	186	#define FLAG_CONS 0x20 /* Corresponds to CONS bit in the opcode tag
	187	* - ie. whether or not we are going to parse
	188	* a compound type.
	189	*/
	190
	191	#define NR_CONS_STACK 10
	192	unsigned short cons_dp_stack[NR_CONS_STACK];
	193	unsigned short cons_datalen_stack[NR_CONS_STACK];
	194	unsigned char cons_hdrlen_stack[NR_CONS_STACK];
	195	#define NR_JUMP_STACK 10
	196	unsigned char jump_stack[NR_JUMP_STACK];
	197
	198	if (datalen > 65535)
	199	return -EMSGSIZE;
	200
	201	next_op:
	202	pr_debug("next_op: pc=\e[32m%zu\e[m/%zu dp=\e[33m%zu\e[m/%zu C=%d J=%d\n",
	203	pc, machlen, dp, datalen, csp, jsp);
	204	if (unlikely(pc >= machlen))
	205	goto machine_overrun_error;
	206	op = machine[pc];
	207	if (unlikely(pc + asn1_op_lengths[op] > machlen))
	208	goto machine_overrun_error;
	209
	210	/* If this command is meant to match a tag, then do that before
	211	* evaluating the command.
	212	*/
	213	if (op <= ASN1_OP__MATCHES_TAG) {
	214	unsigned char tmp;
	215
	216	/* Skip conditional matches if possible */
0d62e9dd DH	217	if ((op & ASN1_OP_MATCH__COND && flags & FLAG_MATCHED) \|\|
0d62e9dd DH	218	(op & ASN1_OP_MATCH__SKIP && dp == datalen)) {
3f3af97d	219	flags &= ~FLAG_LAST_MATCHED;
42d5ec27 DH	220	pc += asn1_op_lengths[op];
	221	goto next_op;
	222	}
	223
	224	flags = 0;
	225	hdr = 2;
	226
	227	/* Extract a tag from the data */
	228	if (unlikely(dp >= datalen - 1))
	229	goto data_overrun_error;
	230	tag = data[dp++];
99cca91e	231	if (unlikely((tag & 0x1f) == ASN1_LONG_TAG))
42d5ec27 DH	232	goto long_tag_not_supported;
	233
	234	if (op & ASN1_OP_MATCH__ANY) {
	235	pr_debug("- any %02x\n", tag);
	236	} else {
	237	/* Extract the tag from the machine
	238	* - Either CONS or PRIM are permitted in the data if
	239	* CONS is not set in the op stream, otherwise CONS
	240	* is mandatory.
	241	*/
	242	optag = machine[pc + 1];
	243	flags \|= optag & FLAG_CONS;
	244
	245	/* Determine whether the tag matched */
	246	tmp = optag ^ tag;
	247	tmp &= ~(optag & ASN1_CONS_BIT);
	248	pr_debug("- match? %02x %02x %02x\n", tag, optag, tmp);
	249	if (tmp != 0) {
	250	/* All odd-numbered tags are MATCH_OR_SKIP. */
	251	if (op & ASN1_OP_MATCH__SKIP) {
	252	pc += asn1_op_lengths[op];
	253	dp--;
	254	goto next_op;
	255	}
	256	goto tag_mismatch;
	257	}
	258	}
	259	flags \|= FLAG_MATCHED;
	260
	261	len = data[dp++];
	262	if (len > 0x7f) {
99cca91e	263	if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
42d5ec27 DH	264	/* Indefinite length */
	265	if (unlikely(!(tag & ASN1_CONS_BIT)))
	266	goto indefinite_len_primitive;
	267	flags \|= FLAG_INDEFINITE_LENGTH;
	268	if (unlikely(2 > datalen - dp))
	269	goto data_overrun_error;
	270	} else {
	271	int n = len - 0x80;
	272	if (unlikely(n > 2))
	273	goto length_too_long;
	274	if (unlikely(dp >= datalen - n))
	275	goto data_overrun_error;
	276	hdr += n;
	277	for (len = 0; n > 0; n--) {
	278	len <<= 8;
	279	len \|= data[dp++];
	280	}
	281	if (unlikely(len > datalen - dp))
	282	goto data_overrun_error;
	283	}
	284	}
	285
	286	if (flags & FLAG_CONS) {
	287	/* For expected compound forms, we stack the positions
	288	* of the start and end of the data.
	289	*/
	290	if (unlikely(csp >= NR_CONS_STACK))
	291	goto cons_stack_overflow;
	292	cons_dp_stack[csp] = dp;
	293	cons_hdrlen_stack[csp] = hdr;
	294	if (!(flags & FLAG_INDEFINITE_LENGTH)) {
	295	cons_datalen_stack[csp] = datalen;
	296	datalen = dp + len;
	297	} else {
	298	cons_datalen_stack[csp] = 0;
	299	}
	300	csp++;
	301	}
	302
	303	pr_debug("- TAG: %02x %zu%s\n",
	304	tag, len, flags & FLAG_CONS ? " CONS" : "");
	305	tdp = dp;
	306	}
	307
	308	/* Decide how to handle the operation */
	309	switch (op) {
	310	case ASN1_OP_MATCH_ANY_ACT:
233ce79d	311	case ASN1_OP_MATCH_ANY_ACT_OR_SKIP:
42d5ec27	312	case ASN1_OP_COND_MATCH_ANY_ACT:
233ce79d	313	case ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP:
42d5ec27 DH	314	ret = actions[machine[pc + 1]](context, hdr, tag, data + dp, len);
	315	if (ret < 0)
	316	return ret;
	317	goto skip_data;
	318
	319	case ASN1_OP_MATCH_ACT:
	320	case ASN1_OP_MATCH_ACT_OR_SKIP:
	321	case ASN1_OP_COND_MATCH_ACT_OR_SKIP:
	322	ret = actions[machine[pc + 2]](context, hdr, tag, data + dp, len);
	323	if (ret < 0)
	324	return ret;
	325	goto skip_data;
	326
	327	case ASN1_OP_MATCH:
	328	case ASN1_OP_MATCH_OR_SKIP:
	329	case ASN1_OP_MATCH_ANY:
233ce79d	330	case ASN1_OP_MATCH_ANY_OR_SKIP:
42d5ec27 DH	331	case ASN1_OP_COND_MATCH_OR_SKIP:
42d5ec27 DH	332	case ASN1_OP_COND_MATCH_ANY:
233ce79d	333	case ASN1_OP_COND_MATCH_ANY_OR_SKIP:
42d5ec27 DH	334	skip_data:
	335	if (!(flags & FLAG_CONS)) {
	336	if (flags & FLAG_INDEFINITE_LENGTH) {
dbadc176 DH	337	ret = asn1_find_indefinite_length(
	338	data, datalen, &dp, &len, &errmsg);
	339	if (ret < 0)
42d5ec27	340	goto error;
dbadc176 DH	341	} else {
dbadc176 DH	342	dp += len;
42d5ec27 DH	343	}
42d5ec27 DH	344	pr_debug("- LEAF: %zu\n", len);
42d5ec27 DH	345	}
	346	pc += asn1_op_lengths[op];
	347	goto next_op;
	348
	349	case ASN1_OP_MATCH_JUMP:
	350	case ASN1_OP_MATCH_JUMP_OR_SKIP:
	351	case ASN1_OP_COND_MATCH_JUMP_OR_SKIP:
	352	pr_debug("- MATCH_JUMP\n");
	353	if (unlikely(jsp == NR_JUMP_STACK))
	354	goto jump_stack_overflow;
	355	jump_stack[jsp++] = pc + asn1_op_lengths[op];
	356	pc = machine[pc + 2];
	357	goto next_op;
	358
	359	case ASN1_OP_COND_FAIL:
	360	if (unlikely(!(flags & FLAG_MATCHED)))
	361	goto tag_mismatch;
	362	pc += asn1_op_lengths[op];
	363	goto next_op;
	364
	365	case ASN1_OP_COMPLETE:
	366	if (unlikely(jsp != 0 \|\| csp != 0)) {
	367	pr_err("ASN.1 decoder error: Stacks not empty at completion (%u, %u)\n",
	368	jsp, csp);
	369	return -EBADMSG;
	370	}
	371	return 0;
	372
	373	case ASN1_OP_END_SET:
	374	case ASN1_OP_END_SET_ACT:
	375	if (unlikely(!(flags & FLAG_MATCHED)))
	376	goto tag_mismatch;
	377	case ASN1_OP_END_SEQ:
	378	case ASN1_OP_END_SET_OF:
	379	case ASN1_OP_END_SEQ_OF:
	380	case ASN1_OP_END_SEQ_ACT:
	381	case ASN1_OP_END_SET_OF_ACT:
	382	case ASN1_OP_END_SEQ_OF_ACT:
	383	if (unlikely(csp <= 0))
	384	goto cons_stack_underflow;
	385	csp--;
	386	tdp = cons_dp_stack[csp];
	387	hdr = cons_hdrlen_stack[csp];
	388	len = datalen;
	389	datalen = cons_datalen_stack[csp];
	390	pr_debug("- end cons t=%zu dp=%zu l=%zu/%zu\n",
	391	tdp, dp, len, datalen);
	392	if (datalen == 0) {
	393	/* Indefinite length - check for the EOC. */
	394	datalen = len;
	395	if (unlikely(datalen - dp < 2))
	396	goto data_overrun_error;
	397	if (data[dp++] != 0) {
	398	if (op & ASN1_OP_END__OF) {
	399	dp--;
	400	csp++;
	401	pc = machine[pc + 1];
	402	pr_debug("- continue\n");
	403	goto next_op;
	404	}
	405	goto missing_eoc;
	406	}
	407	if (data[dp++] != 0)
	408	goto invalid_eoc;
409	len = dp - tdp - 2;
410	} else {
411	if (dp < len && (op & ASN1_OP_END__OF)) {
412	datalen = len;
413	csp++;
414	pc = machine[pc + 1];
415	pr_debug("- continue\n");
416	goto next_op;
417	}
418	if (dp != len)
419	goto cons_length_error;
420	len -= tdp;
421	pr_debug("- cons len l=%zu d=%zu\n", len, dp - tdp);
422	}
423
424	if (op & ASN1_OP_END__ACT) {
425	unsigned char act;
426	if (op & ASN1_OP_END__OF)
427	act = machine[pc + 2];
428	else
429	act = machine[pc + 1];
430	ret = actions[act](context, hdr, 0, data + tdp, len);
431	}
432	pc += asn1_op_lengths[op];
433	goto next_op;
434
3f3af97d DH	435	case ASN1_OP_MAYBE_ACT:
	436	if (!(flags & FLAG_LAST_MATCHED)) {
	437	pc += asn1_op_lengths[op];
	438	goto next_op;
	439	}
42d5ec27 DH	440	case ASN1_OP_ACT:
42d5ec27 DH	441	ret = actions[machine[pc + 1]](context, hdr, tag, data + tdp, len);
3f3af97d DH	442	if (ret < 0)
3f3af97d DH	443	return ret;
42d5ec27 DH	444	pc += asn1_op_lengths[op];
	445	goto next_op;
	446
	447	case ASN1_OP_RETURN:
	448	if (unlikely(jsp <= 0))
	449	goto jump_stack_underflow;
	450	pc = jump_stack[--jsp];
3f3af97d	451	flags \|= FLAG_MATCHED \| FLAG_LAST_MATCHED;
42d5ec27 DH	452	goto next_op;
	453
	454	default:
	455	break;
	456	}
	457
	458	/* Shouldn't reach here */
3f3af97d DH	459	pr_err("ASN.1 decoder error: Found reserved opcode (%u) pc=%zu\n",
3f3af97d DH	460	op, pc);
42d5ec27 DH	461	return -EBADMSG;
	462
	463	data_overrun_error:
	464	errmsg = "Data overrun error";
	465	goto error;
	466	machine_overrun_error:
	467	errmsg = "Machine overrun error";
	468	goto error;
	469	jump_stack_underflow:
	470	errmsg = "Jump stack underflow";
	471	goto error;
	472	jump_stack_overflow:
	473	errmsg = "Jump stack overflow";
	474	goto error;
	475	cons_stack_underflow:
	476	errmsg = "Cons stack underflow";
	477	goto error;
	478	cons_stack_overflow:
	479	errmsg = "Cons stack overflow";
	480	goto error;
	481	cons_length_error:
	482	errmsg = "Cons length error";
	483	goto error;
	484	missing_eoc:
	485	errmsg = "Missing EOC in indefinite len cons";
	486	goto error;
	487	invalid_eoc:
	488	errmsg = "Invalid length EOC";
	489	goto error;
	490	length_too_long:
	491	errmsg = "Unsupported length";
	492	goto error;
	493	indefinite_len_primitive:
	494	errmsg = "Indefinite len primitive not permitted";
	495	goto error;
	496	tag_mismatch:
	497	errmsg = "Unexpected tag";
	498	goto error;
	499	long_tag_not_supported:
	500	errmsg = "Long tag not supported";
	501	error:
	502	pr_debug("\nASN1: %s [m=%zu d=%zu ot=%02x t=%02x l=%zu]\n",
	503	errmsg, pc, dp, optag, tag, len);
	504	return -EBADMSG;
	505	}
	506	EXPORT_SYMBOL_GPL(asn1_ber_decoder);