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