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