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(dp >= datalen - 1)) 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(dp >= datalen - n)) 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 } 288 289 if (flags & FLAG_CONS) { 290 /* For expected compound forms, we stack the positions 291 * of the start and end of the data. 292 */ 293 if (unlikely(csp >= NR_CONS_STACK)) 294 goto cons_stack_overflow; 295 cons_dp_stack[csp] = dp; 296 cons_hdrlen_stack[csp] = hdr; 297 if (!(flags & FLAG_INDEFINITE_LENGTH)) { 298 cons_datalen_stack[csp] = datalen; 299 datalen = dp + len; 300 } else { 301 cons_datalen_stack[csp] = 0; 302 } 303 csp++; 304 } 305 306 pr_debug("- TAG: %02x %zu%s\n", 307 tag, len, flags & FLAG_CONS ? " CONS" : ""); 308 tdp = dp; 309 } 310 311 /* Decide how to handle the operation */ 312 switch (op) { 313 case ASN1_OP_MATCH_ANY_ACT: 314 case ASN1_OP_MATCH_ANY_ACT_OR_SKIP: 315 case ASN1_OP_COND_MATCH_ANY_ACT: 316 case ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP: 317 ret = actions[machine[pc + 1]](context, hdr, tag, data + dp, len); 318 if (ret < 0) 319 return ret; 320 goto skip_data; 321 322 case ASN1_OP_MATCH_ACT: 323 case ASN1_OP_MATCH_ACT_OR_SKIP: 324 case ASN1_OP_COND_MATCH_ACT_OR_SKIP: 325 ret = actions[machine[pc + 2]](context, hdr, tag, data + dp, len); 326 if (ret < 0) 327 return ret; 328 goto skip_data; 329 330 case ASN1_OP_MATCH: 331 case ASN1_OP_MATCH_OR_SKIP: 332 case ASN1_OP_MATCH_ANY: 333 case ASN1_OP_MATCH_ANY_OR_SKIP: 334 case ASN1_OP_COND_MATCH_OR_SKIP: 335 case ASN1_OP_COND_MATCH_ANY: 336 case ASN1_OP_COND_MATCH_ANY_OR_SKIP: 337 skip_data: 338 if (!(flags & FLAG_CONS)) { 339 if (flags & FLAG_INDEFINITE_LENGTH) { 340 ret = asn1_find_indefinite_length( 341 data, datalen, &dp, &len, &errmsg); 342 if (ret < 0) 343 goto error; 344 } else { 345 dp += len; 346 } 347 pr_debug("- LEAF: %zu\n", len); 348 } 349 pc += asn1_op_lengths[op]; 350 goto next_op; 351 352 case ASN1_OP_MATCH_JUMP: 353 case ASN1_OP_MATCH_JUMP_OR_SKIP: 354 case ASN1_OP_COND_MATCH_JUMP_OR_SKIP: 355 pr_debug("- MATCH_JUMP\n"); 356 if (unlikely(jsp == NR_JUMP_STACK)) 357 goto jump_stack_overflow; 358 jump_stack[jsp++] = pc + asn1_op_lengths[op]; 359 pc = machine[pc + 2]; 360 goto next_op; 361 362 case ASN1_OP_COND_FAIL: 363 if (unlikely(!(flags & FLAG_MATCHED))) 364 goto tag_mismatch; 365 pc += asn1_op_lengths[op]; 366 goto next_op; 367 368 case ASN1_OP_COMPLETE: 369 if (unlikely(jsp != 0 || csp != 0)) { 370 pr_err("ASN.1 decoder error: Stacks not empty at completion (%u, %u)\n", 371 jsp, csp); 372 return -EBADMSG; 373 } 374 return 0; 375 376 case ASN1_OP_END_SET: 377 case ASN1_OP_END_SET_ACT: 378 if (unlikely(!(flags & FLAG_MATCHED))) 379 goto tag_mismatch; 380 case ASN1_OP_END_SEQ: 381 case ASN1_OP_END_SET_OF: 382 case ASN1_OP_END_SEQ_OF: 383 case ASN1_OP_END_SEQ_ACT: 384 case ASN1_OP_END_SET_OF_ACT: 385 case ASN1_OP_END_SEQ_OF_ACT: 386 if (unlikely(csp <= 0)) 387 goto cons_stack_underflow; 388 csp--; 389 tdp = cons_dp_stack[csp]; 390 hdr = cons_hdrlen_stack[csp]; 391 len = datalen; 392 datalen = cons_datalen_stack[csp]; 393 pr_debug("- end cons t=%zu dp=%zu l=%zu/%zu\n", 394 tdp, dp, len, datalen); 395 if (datalen == 0) { 396 /* Indefinite length - check for the EOC. */ 397 datalen = len; 398 if (unlikely(datalen - dp < 2)) 399 goto data_overrun_error; 400 if (data[dp++] != 0) { 401 if (op & ASN1_OP_END__OF) { 402 dp--; 403 csp++; 404 pc = machine[pc + 1]; 405 pr_debug("- continue\n"); 406 goto next_op; 407 } 408 goto missing_eoc; 409 } 410 if (data[dp++] != 0) 411 goto invalid_eoc; 412 len = dp - tdp - 2; 413 } else { 414 if (dp < len && (op & ASN1_OP_END__OF)) { 415 datalen = len; 416 csp++; 417 pc = machine[pc + 1]; 418 pr_debug("- continue\n"); 419 goto next_op; 420 } 421 if (dp != len) 422 goto cons_length_error; 423 len -= tdp; 424 pr_debug("- cons len l=%zu d=%zu\n", len, dp - tdp); 425 } 426 427 if (op & ASN1_OP_END__ACT) { 428 unsigned char act; 429 if (op & ASN1_OP_END__OF) 430 act = machine[pc + 2]; 431 else 432 act = machine[pc + 1]; 433 ret = actions[act](context, hdr, 0, data + tdp, len); 434 } 435 pc += asn1_op_lengths[op]; 436 goto next_op; 437 438 case ASN1_OP_MAYBE_ACT: 439 if (!(flags & FLAG_LAST_MATCHED)) { 440 pc += asn1_op_lengths[op]; 441 goto next_op; 442 } 443 case ASN1_OP_ACT: 444 ret = actions[machine[pc + 1]](context, hdr, tag, data + tdp, len); 445 if (ret < 0) 446 return ret; 447 pc += asn1_op_lengths[op]; 448 goto next_op; 449 450 case ASN1_OP_RETURN: 451 if (unlikely(jsp <= 0)) 452 goto jump_stack_underflow; 453 pc = jump_stack[--jsp]; 454 flags |= FLAG_MATCHED | FLAG_LAST_MATCHED; 455 goto next_op; 456 457 default: 458 break; 459 } 460 461 /* Shouldn't reach here */ 462 pr_err("ASN.1 decoder error: Found reserved opcode (%u) pc=%zu\n", 463 op, pc); 464 return -EBADMSG; 465 466 data_overrun_error: 467 errmsg = "Data overrun error"; 468 goto error; 469 machine_overrun_error: 470 errmsg = "Machine overrun error"; 471 goto error; 472 jump_stack_underflow: 473 errmsg = "Jump stack underflow"; 474 goto error; 475 jump_stack_overflow: 476 errmsg = "Jump stack overflow"; 477 goto error; 478 cons_stack_underflow: 479 errmsg = "Cons stack underflow"; 480 goto error; 481 cons_stack_overflow: 482 errmsg = "Cons stack overflow"; 483 goto error; 484 cons_length_error: 485 errmsg = "Cons length error"; 486 goto error; 487 missing_eoc: 488 errmsg = "Missing EOC in indefinite len cons"; 489 goto error; 490 invalid_eoc: 491 errmsg = "Invalid length EOC"; 492 goto error; 493 length_too_long: 494 errmsg = "Unsupported length"; 495 goto error; 496 indefinite_len_primitive: 497 errmsg = "Indefinite len primitive not permitted"; 498 goto error; 499 tag_mismatch: 500 errmsg = "Unexpected tag"; 501 goto error; 502 long_tag_not_supported: 503 errmsg = "Long tag not supported"; 504 error: 505 pr_debug("\nASN1: %s [m=%zu d=%zu ot=%02x t=%02x l=%zu]\n", 506 errmsg, pc, dp, optag, tag, len); 507 return -EBADMSG; 508 } 509 EXPORT_SYMBOL_GPL(asn1_ber_decoder); 510 511 MODULE_LICENSE("GPL"); 512