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