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