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