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