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