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