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