the-tree/lib/asn1_decoder.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /* Decoder for ASN.1 BER/DER/CER encoded bytestream
0003  *
0004  * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
0005  * Written by David Howells (dhowells@redhat.com)
0006  */
0007
0008 #include <linux/export.h>
0009 #include <linux/kernel.h>
0010 #include <linux/errno.h>
0011 #include <linux/module.h>
0012 #include <linux/asn1_decoder.h>
0013 #include <linux/asn1_ber_bytecode.h>
0014
0015 static const unsigned char asn1_op_lengths[ASN1_OP__NR] = {
0016     /*                  OPC TAG JMP ACT */
0017     [ASN1_OP_MATCH]             = 1 + 1,
0018     [ASN1_OP_MATCH_OR_SKIP]         = 1 + 1,
0019     [ASN1_OP_MATCH_ACT]         = 1 + 1     + 1,
0020     [ASN1_OP_MATCH_ACT_OR_SKIP]     = 1 + 1     + 1,
0021     [ASN1_OP_MATCH_JUMP]            = 1 + 1 + 1,
0022     [ASN1_OP_MATCH_JUMP_OR_SKIP]        = 1 + 1 + 1,
0023     [ASN1_OP_MATCH_ANY]         = 1,
0024     [ASN1_OP_MATCH_ANY_OR_SKIP]     = 1,
0025     [ASN1_OP_MATCH_ANY_ACT]         = 1         + 1,
0026     [ASN1_OP_MATCH_ANY_ACT_OR_SKIP]     = 1         + 1,
0027     [ASN1_OP_COND_MATCH_OR_SKIP]        = 1 + 1,
0028     [ASN1_OP_COND_MATCH_ACT_OR_SKIP]    = 1 + 1     + 1,
0029     [ASN1_OP_COND_MATCH_JUMP_OR_SKIP]   = 1 + 1 + 1,
0030     [ASN1_OP_COND_MATCH_ANY]        = 1,
0031     [ASN1_OP_COND_MATCH_ANY_OR_SKIP]    = 1,
0032     [ASN1_OP_COND_MATCH_ANY_ACT]        = 1         + 1,
0033     [ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP]    = 1         + 1,
0034     [ASN1_OP_COND_FAIL]         = 1,
0035     [ASN1_OP_COMPLETE]          = 1,
0036     [ASN1_OP_ACT]               = 1         + 1,
0037     [ASN1_OP_MAYBE_ACT]         = 1         + 1,
0038     [ASN1_OP_RETURN]            = 1,
0039     [ASN1_OP_END_SEQ]           = 1,
0040     [ASN1_OP_END_SEQ_OF]            = 1     + 1,
0041     [ASN1_OP_END_SET]           = 1,
0042     [ASN1_OP_END_SET_OF]            = 1     + 1,
0043     [ASN1_OP_END_SEQ_ACT]           = 1         + 1,
0044     [ASN1_OP_END_SEQ_OF_ACT]        = 1     + 1 + 1,
0045     [ASN1_OP_END_SET_ACT]           = 1         + 1,
0046     [ASN1_OP_END_SET_OF_ACT]        = 1     + 1 + 1,
0047 };
0048
0049 /*
0050  * Find the length of an indefinite length object
0051  * @data: The data buffer
0052  * @datalen: The end of the innermost containing element in the buffer
0053  * @_dp: The data parse cursor (updated before returning)
0054  * @_len: Where to return the size of the element.
0055  * @_errmsg: Where to return a pointer to an error message on error
0056  */
0057 static int asn1_find_indefinite_length(const unsigned char *data, size_t datalen,
0058                        size_t *_dp, size_t *_len,
0059                        const char **_errmsg)
0060 {
0061     unsigned char tag, tmp;
0062     size_t dp = *_dp, len, n;
0063     int indef_level = 1;
0064
0065 next_tag:
0066     if (unlikely(datalen - dp < 2)) {
0067         if (datalen == dp)
0068             goto missing_eoc;
0069         goto data_overrun_error;
0070     }
0071
0072     /* Extract a tag from the data */
0073     tag = data[dp++];
0074     if (tag == ASN1_EOC) {
0075         /* It appears to be an EOC. */
0076         if (data[dp++] != 0)
0077             goto invalid_eoc;
0078         if (--indef_level <= 0) {
0079             *_len = dp - *_dp;
0080             *_dp = dp;
0081             return 0;
0082         }
0083         goto next_tag;
0084     }
0085
0086     if (unlikely((tag & 0x1f) == ASN1_LONG_TAG)) {
0087         do {
0088             if (unlikely(datalen - dp < 2))
0089                 goto data_overrun_error;
0090             tmp = data[dp++];
0091         } while (tmp & 0x80);
0092     }
0093
0094     /* Extract the length */
0095     len = data[dp++];
0096     if (len <= 0x7f)
0097         goto check_length;
0098
0099     if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
0100         /* Indefinite length */
0101         if (unlikely((tag & ASN1_CONS_BIT) == ASN1_PRIM << 5))
0102             goto indefinite_len_primitive;
0103         indef_level++;
0104         goto next_tag;
0105     }
0106
0107     n = len - 0x80;
0108     if (unlikely(n > sizeof(len) - 1))
0109         goto length_too_long;
0110     if (unlikely(n > datalen - dp))
0111         goto data_overrun_error;
0112     len = 0;
0113     for (; n > 0; n--) {
0114         len <<= 8;
0115         len |= data[dp++];
0116     }
0117 check_length:
0118     if (len > datalen - dp)
0119         goto data_overrun_error;
0120     dp += len;
0121     goto next_tag;
0122
0123 length_too_long:
0124     *_errmsg = "Unsupported length";
0125     goto error;
0126 indefinite_len_primitive:
0127     *_errmsg = "Indefinite len primitive not permitted";
0128     goto error;
0129 invalid_eoc:
0130     *_errmsg = "Invalid length EOC";
0131     goto error;
0132 data_overrun_error:
0133     *_errmsg = "Data overrun error";
0134     goto error;
0135 missing_eoc:
0136     *_errmsg = "Missing EOC in indefinite len cons";
0137 error:
0138     *_dp = dp;
0139     return -1;
0140 }
0141
0142 /**
0143  * asn1_ber_decoder - Decoder BER/DER/CER ASN.1 according to pattern
0144  * @decoder: The decoder definition (produced by asn1_compiler)
0145  * @context: The caller's context (to be passed to the action functions)
0146  * @data: The encoded data
0147  * @datalen: The size of the encoded data
0148  *
0149  * Decode BER/DER/CER encoded ASN.1 data according to a bytecode pattern
0150  * produced by asn1_compiler.  Action functions are called on marked tags to
0151  * allow the caller to retrieve significant data.
0152  *
0153  * LIMITATIONS:
0154  *
0155  * To keep down the amount of stack used by this function, the following limits
0156  * have been imposed:
0157  *
0158  *  (1) This won't handle datalen > 65535 without increasing the size of the
0159  *  cons stack elements and length_too_long checking.
0160  *
0161  *  (2) The stack of constructed types is 10 deep.  If the depth of non-leaf
0162  *  constructed types exceeds this, the decode will fail.
0163  *
0164  *  (3) The SET type (not the SET OF type) isn't really supported as tracking
0165  *  what members of the set have been seen is a pain.
0166  */
0167 int asn1_ber_decoder(const struct asn1_decoder *decoder,
0168              void *context,
0169              const unsigned char *data,
0170              size_t datalen)
0171 {
0172     const unsigned char *machine = decoder->machine;
0173     const asn1_action_t *actions = decoder->actions;
0174     size_t machlen = decoder->machlen;
0175     enum asn1_opcode op;
0176     unsigned char tag = 0, csp = 0, jsp = 0, optag = 0, hdr = 0;
0177     const char *errmsg;
0178     size_t pc = 0, dp = 0, tdp = 0, len = 0;
0179     int ret;
0180
0181     unsigned char flags = 0;
0182 #define FLAG_INDEFINITE_LENGTH  0x01
0183 #define FLAG_MATCHED        0x02
0184 #define FLAG_LAST_MATCHED   0x04 /* Last tag matched */
0185 #define FLAG_CONS       0x20 /* Corresponds to CONS bit in the opcode tag
0186                       * - ie. whether or not we are going to parse
0187                       *   a compound type.
0188                       */
0189
0190 #define NR_CONS_STACK 10
0191     unsigned short cons_dp_stack[NR_CONS_STACK];
0192     unsigned short cons_datalen_stack[NR_CONS_STACK];
0193     unsigned char cons_hdrlen_stack[NR_CONS_STACK];
0194 #define NR_JUMP_STACK 10
0195     unsigned char jump_stack[NR_JUMP_STACK];
0196
0197     if (datalen > 65535)
0198         return -EMSGSIZE;
0199
0200 next_op:
0201     pr_debug("next_op: pc=\e[32m%zu\e[m/%zu dp=\e[33m%zu\e[m/%zu C=%d J=%d\n",
0202          pc, machlen, dp, datalen, csp, jsp);
0203     if (unlikely(pc >= machlen))
0204         goto machine_overrun_error;
0205     op = machine[pc];
0206     if (unlikely(pc + asn1_op_lengths[op] > machlen))
0207         goto machine_overrun_error;
0208
0209     /* If this command is meant to match a tag, then do that before
0210      * evaluating the command.
0211      */
0212     if (op <= ASN1_OP__MATCHES_TAG) {
0213         unsigned char tmp;
0214
0215         /* Skip conditional matches if possible */
0216         if ((op & ASN1_OP_MATCH__COND && flags & FLAG_MATCHED) ||
0217             (op & ASN1_OP_MATCH__SKIP && dp == datalen)) {
0218             flags &= ~FLAG_LAST_MATCHED;
0219             pc += asn1_op_lengths[op];
0220             goto next_op;
0221         }
0222
0223         flags = 0;
0224         hdr = 2;
0225
0226         /* Extract a tag from the data */
0227         if (unlikely(datalen - dp < 2))
0228             goto data_overrun_error;
0229         tag = data[dp++];
0230         if (unlikely((tag & 0x1f) == ASN1_LONG_TAG))
0231             goto long_tag_not_supported;
0232
0233         if (op & ASN1_OP_MATCH__ANY) {
0234             pr_debug("- any %02x\n", tag);
0235         } else {
0236             /* Extract the tag from the machine
0237              * - Either CONS or PRIM are permitted in the data if
0238              *   CONS is not set in the op stream, otherwise CONS
0239              *   is mandatory.
0240              */
0241             optag = machine[pc + 1];
0242             flags |= optag & FLAG_CONS;
0243
0244             /* Determine whether the tag matched */
0245             tmp = optag ^ tag;
0246             tmp &= ~(optag & ASN1_CONS_BIT);
0247             pr_debug("- match? %02x %02x %02x\n", tag, optag, tmp);
0248             if (tmp != 0) {
0249                 /* All odd-numbered tags are MATCH_OR_SKIP. */
0250                 if (op & ASN1_OP_MATCH__SKIP) {
0251                     pc += asn1_op_lengths[op];
0252                     dp--;
0253                     goto next_op;
0254                 }
0255                 goto tag_mismatch;
0256             }
0257         }
0258         flags |= FLAG_MATCHED;
0259
0260         len = data[dp++];
0261         if (len > 0x7f) {
0262             if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
0263                 /* Indefinite length */
0264                 if (unlikely(!(tag & ASN1_CONS_BIT)))
0265                     goto indefinite_len_primitive;
0266                 flags |= FLAG_INDEFINITE_LENGTH;
0267                 if (unlikely(2 > datalen - dp))
0268                     goto data_overrun_error;
0269             } else {
0270                 int n = len - 0x80;
0271                 if (unlikely(n > 2))
0272                     goto length_too_long;
0273                 if (unlikely(n > datalen - dp))
0274                     goto data_overrun_error;
0275                 hdr += n;
0276                 for (len = 0; n > 0; n--) {
0277                     len <<= 8;
0278                     len |= data[dp++];
0279                 }
0280                 if (unlikely(len > datalen - dp))
0281                     goto data_overrun_error;
0282             }
0283         } else {
0284             if (unlikely(len > datalen - dp))
0285                 goto data_overrun_error;
0286         }
0287
0288         if (flags & FLAG_CONS) {
0289             /* For expected compound forms, we stack the positions
0290              * of the start and end of the data.
0291              */
0292             if (unlikely(csp >= NR_CONS_STACK))
0293                 goto cons_stack_overflow;
0294             cons_dp_stack[csp] = dp;
0295             cons_hdrlen_stack[csp] = hdr;
0296             if (!(flags & FLAG_INDEFINITE_LENGTH)) {
0297                 cons_datalen_stack[csp] = datalen;
0298                 datalen = dp + len;
0299             } else {
0300                 cons_datalen_stack[csp] = 0;
0301             }
0302             csp++;
0303         }
0304
0305         pr_debug("- TAG: %02x %zu%s\n",
0306              tag, len, flags & FLAG_CONS ? " CONS" : "");
0307         tdp = dp;
0308     }
0309
0310     /* Decide how to handle the operation */
0311     switch (op) {
0312     case ASN1_OP_MATCH:
0313     case ASN1_OP_MATCH_OR_SKIP:
0314     case ASN1_OP_MATCH_ACT:
0315     case ASN1_OP_MATCH_ACT_OR_SKIP:
0316     case ASN1_OP_MATCH_ANY:
0317     case ASN1_OP_MATCH_ANY_OR_SKIP:
0318     case ASN1_OP_MATCH_ANY_ACT:
0319     case ASN1_OP_MATCH_ANY_ACT_OR_SKIP:
0320     case ASN1_OP_COND_MATCH_OR_SKIP:
0321     case ASN1_OP_COND_MATCH_ACT_OR_SKIP:
0322     case ASN1_OP_COND_MATCH_ANY:
0323     case ASN1_OP_COND_MATCH_ANY_OR_SKIP:
0324     case ASN1_OP_COND_MATCH_ANY_ACT:
0325     case ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP:
0326
0327         if (!(flags & FLAG_CONS)) {
0328             if (flags & FLAG_INDEFINITE_LENGTH) {
0329                 size_t tmp = dp;
0330
0331                 ret = asn1_find_indefinite_length(
0332                     data, datalen, &tmp, &len, &errmsg);
0333                 if (ret < 0)
0334                     goto error;
0335             }
0336             pr_debug("- LEAF: %zu\n", len);
0337         }
0338
0339         if (op & ASN1_OP_MATCH__ACT) {
0340             unsigned char act;
0341
0342             if (op & ASN1_OP_MATCH__ANY)
0343                 act = machine[pc + 1];
0344             else
0345                 act = machine[pc + 2];
0346             ret = actions[act](context, hdr, tag, data + dp, len);
0347             if (ret < 0)
0348                 return ret;
0349         }
0350
0351         if (!(flags & FLAG_CONS))
0352             dp += len;
0353         pc += asn1_op_lengths[op];
0354         goto next_op;
0355
0356     case ASN1_OP_MATCH_JUMP:
0357     case ASN1_OP_MATCH_JUMP_OR_SKIP:
0358     case ASN1_OP_COND_MATCH_JUMP_OR_SKIP:
0359         pr_debug("- MATCH_JUMP\n");
0360         if (unlikely(jsp == NR_JUMP_STACK))
0361             goto jump_stack_overflow;
0362         jump_stack[jsp++] = pc + asn1_op_lengths[op];
0363         pc = machine[pc + 2];
0364         goto next_op;
0365
0366     case ASN1_OP_COND_FAIL:
0367         if (unlikely(!(flags & FLAG_MATCHED)))
0368             goto tag_mismatch;
0369         pc += asn1_op_lengths[op];
0370         goto next_op;
0371
0372     case ASN1_OP_COMPLETE:
0373         if (unlikely(jsp != 0 || csp != 0)) {
0374             pr_err("ASN.1 decoder error: Stacks not empty at completion (%u, %u)\n",
0375                    jsp, csp);
0376             return -EBADMSG;
0377         }
0378         return 0;
0379
0380     case ASN1_OP_END_SET:
0381     case ASN1_OP_END_SET_ACT:
0382         if (unlikely(!(flags & FLAG_MATCHED)))
0383             goto tag_mismatch;
0384         fallthrough;
0385
0386     case ASN1_OP_END_SEQ:
0387     case ASN1_OP_END_SET_OF:
0388     case ASN1_OP_END_SEQ_OF:
0389     case ASN1_OP_END_SEQ_ACT:
0390     case ASN1_OP_END_SET_OF_ACT:
0391     case ASN1_OP_END_SEQ_OF_ACT:
0392         if (unlikely(csp <= 0))
0393             goto cons_stack_underflow;
0394         csp--;
0395         tdp = cons_dp_stack[csp];
0396         hdr = cons_hdrlen_stack[csp];
0397         len = datalen;
0398         datalen = cons_datalen_stack[csp];
0399         pr_debug("- end cons t=%zu dp=%zu l=%zu/%zu\n",
0400              tdp, dp, len, datalen);
0401         if (datalen == 0) {
0402             /* Indefinite length - check for the EOC. */
0403             datalen = len;
0404             if (unlikely(datalen - dp < 2))
0405                 goto data_overrun_error;
0406             if (data[dp++] != 0) {
0407                 if (op & ASN1_OP_END__OF) {
0408                     dp--;
0409                     csp++;
0410                     pc = machine[pc + 1];
0411                     pr_debug("- continue\n");
0412                     goto next_op;
0413                 }
0414                 goto missing_eoc;
0415             }
0416             if (data[dp++] != 0)
0417                 goto invalid_eoc;
0418             len = dp - tdp - 2;
0419         } else {
0420             if (dp < len && (op & ASN1_OP_END__OF)) {
0421                 datalen = len;
0422                 csp++;
0423                 pc = machine[pc + 1];
0424                 pr_debug("- continue\n");
0425                 goto next_op;
0426             }
0427             if (dp != len)
0428                 goto cons_length_error;
0429             len -= tdp;
0430             pr_debug("- cons len l=%zu d=%zu\n", len, dp - tdp);
0431         }
0432
0433         if (op & ASN1_OP_END__ACT) {
0434             unsigned char act;
0435             if (op & ASN1_OP_END__OF)
0436                 act = machine[pc + 2];
0437             else
0438                 act = machine[pc + 1];
0439             ret = actions[act](context, hdr, 0, data + tdp, len);
0440             if (ret < 0)
0441                 return ret;
0442         }
0443         pc += asn1_op_lengths[op];
0444         goto next_op;
0445
0446     case ASN1_OP_MAYBE_ACT:
0447         if (!(flags & FLAG_LAST_MATCHED)) {
0448             pc += asn1_op_lengths[op];
0449             goto next_op;
0450         }
0451         fallthrough;
0452
0453     case ASN1_OP_ACT:
0454         ret = actions[machine[pc + 1]](context, hdr, tag, data + tdp, len);
0455         if (ret < 0)
0456             return ret;
0457         pc += asn1_op_lengths[op];
0458         goto next_op;
0459
0460     case ASN1_OP_RETURN:
0461         if (unlikely(jsp <= 0))
0462             goto jump_stack_underflow;
0463         pc = jump_stack[--jsp];
0464         flags |= FLAG_MATCHED | FLAG_LAST_MATCHED;
0465         goto next_op;
0466
0467     default:
0468         break;
0469     }
0470
0471     /* Shouldn't reach here */
0472     pr_err("ASN.1 decoder error: Found reserved opcode (%u) pc=%zu\n",
0473            op, pc);
0474     return -EBADMSG;
0475
0476 data_overrun_error:
0477     errmsg = "Data overrun error";
0478     goto error;
0479 machine_overrun_error:
0480     errmsg = "Machine overrun error";
0481     goto error;
0482 jump_stack_underflow:
0483     errmsg = "Jump stack underflow";
0484     goto error;
0485 jump_stack_overflow:
0486     errmsg = "Jump stack overflow";
0487     goto error;
0488 cons_stack_underflow:
0489     errmsg = "Cons stack underflow";
0490     goto error;
0491 cons_stack_overflow:
0492     errmsg = "Cons stack overflow";
0493     goto error;
0494 cons_length_error:
0495     errmsg = "Cons length error";
0496     goto error;
0497 missing_eoc:
0498     errmsg = "Missing EOC in indefinite len cons";
0499     goto error;
0500 invalid_eoc:
0501     errmsg = "Invalid length EOC";
0502     goto error;
0503 length_too_long:
0504     errmsg = "Unsupported length";
0505     goto error;
0506 indefinite_len_primitive:
0507     errmsg = "Indefinite len primitive not permitted";
0508     goto error;
0509 tag_mismatch:
0510     errmsg = "Unexpected tag";
0511     goto error;
0512 long_tag_not_supported:
0513     errmsg = "Long tag not supported";
0514 error:
0515     pr_debug("\nASN1: %s [m=%zu d=%zu ot=%02x t=%02x l=%zu]\n",
0516          errmsg, pc, dp, optag, tag, len);
0517     return -EBADMSG;
0518 }
0519 EXPORT_SYMBOL_GPL(asn1_ber_decoder);
0520
0521 MODULE_LICENSE("GPL");