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 | */ |
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 | */ |
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, dp: &tmp, len: &len, errmsg: &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 | |