The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/lib/asn1_decoder.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: 7016433a7725699f0eaab51ca40b8cc1


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.