Back to home page

LXR

 
 

    


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