der-iterator.c

   1 /* der-iterator.c
   2
   3    Parsing of ASN.1 DER encoded objects.
   4
   5    Copyright (C) 2005 Niels Möller
   6
   7    This file is part of GNU Nettle.
   8
   9    GNU Nettle is free software: you can redistribute it and/or
  10    modify it under the terms of either:
  11
  12      * the GNU Lesser General Public License as published by the Free
  13        Software Foundation; either version 3 of the License, or (at your
  14        option) any later version.
  15
  16    or
  17
  18      * the GNU General Public License as published by the Free
  19        Software Foundation; either version 2 of the License, or (at your
  20        option) any later version.
  21
  22    or both in parallel, as here.
  23
  24    GNU Nettle is distributed in the hope that it will be useful,
  25    but WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    General Public License for more details.
  28
  29    You should have received copies of the GNU General Public License and
  30    the GNU Lesser General Public License along with this program.  If
  31    not, see http://www.gnu.org/licenses/.
  32 */
  33
  34 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include <assert.h>
  39 #include <stdlib.h>
  40
  41 #include "bignum.h"
  42
  43 #include "asn1.h"
  44
  45 #include "macros.h"
  46
  47 /* Basic DER syntax: (reference: A Layman's Guide to a Subset of ASN.1, BER, and DER,
  48    http://luca.ntop.org/Teaching/Appunti/asn1.html)
  49
  50    The DER header contains a tag and a length. First, the tag. cls is
  51    the class number, c is one if the object is "constructed" and zero
  52    if it is primitive. The tag is represented either using a single
  53    byte,
  54
  55      7 6   5   4 3 2 1 0
  56     _____________________
  57    |_cls_|_c_|_______tag_|   0 <= tag <= 30
  58
  59    or multiple bytes
  60
  61      7 6   5   4 3 2 1 0
  62     _____________________
  63    |_cls_|_c_|_1_1_1_1_1_|
  64
  65    followed by the real tag number, in base 128, with all but the
  66    final byte having the most significant bit set. The tag must be
  67    represented with as few bytes as possible. High tag numbers are
  68    currently *not* supported.
  69
  70    Next, the length, either a single byte with the most significant bit clear, or
  71
  72      7 6 5 4 3 2 1 0
  73     _________________
  74    |_1_|___________k_|
  75
  76    followed by k additional bytes that give the length, in network
  77    byte order. The length must be encoded using as few bytes as
  78    possible, and k = 0 is reserved for the "indefinite length form"
  79    which is not supported.
  80
  81    After the length comes the contets. For primitive objects (c == 0),
  82    it's depends on the type. For constructed objects, it's a
  83    concatenation of the DER encodings of zero or more other objects.
  84 */
  85
  86 enum {
  87   TAG_MASK = 0x1f,
  88   CLASS_MASK = 0xc0,
  89   CONSTRUCTED_MASK = 0x20,
  90 };
  91
  92 /* Initializes the iterator, but one has to call next to get to the
  93  * first element. */
  94 static void
  95 asn1_der_iterator_init(struct asn1_der_iterator *iterator,
  96                        size_t length, const uint8_t *input)
  97 {
  98   iterator->buffer_length = length;
  99   iterator->buffer = input;
 100   iterator->pos = 0;
 101   iterator->type = 0;
 102   iterator->length = 0;
 103   iterator->data = NULL;
 104 }
 105
 106 #define LEFT(i) ((i)->buffer_length - (i)->pos)
 107 #define NEXT(i) ((i)->buffer[(i)->pos++])
 108
 109 /* Gets type and length of the next object. */
 110 enum asn1_iterator_result
 111 asn1_der_iterator_next(struct asn1_der_iterator *i)
 112 {
 113   uint8_t tag;
 114
 115   if (!LEFT(i))
 116     return ASN1_ITERATOR_END;
 117
 118   tag = NEXT(i);
 119   if (!LEFT(i))
 120     return ASN1_ITERATOR_ERROR;
 121
 122   if ( (tag & TAG_MASK) == TAG_MASK)
 123     {
 124       /* FIXME: Long tags not supported */
 125       return ASN1_ITERATOR_ERROR;
 126     }
 127
 128   i->length = NEXT(i);
 129   if (i->length & 0x80)
 130     {
 131       unsigned k = i->length & 0x7f;
 132       unsigned j;
 133       const uint8_t *data = i->buffer + i->pos;
 134
 135       if (k == 0)
 136         /* Indefinite encoding. Not supported. */
 137         return ASN1_ITERATOR_ERROR;
 138
 139       if (LEFT(i) < k)
 140         return ASN1_ITERATOR_ERROR;
 141
 142       if (k > sizeof(i->length))
 143         return ASN1_ITERATOR_ERROR;
 144
 145       i->pos += k;
 146       i->length = data[0];
 147       if (i->length == 0
 148           || (k == 1 && i->length < 0x80))
 149         return ASN1_ITERATOR_ERROR;
 150
 151       for (j = 1; j < k; j++)
 152         i->length = (i->length << 8) | data[j];
 153     }
 154   if (LEFT(i) < i->length)
 155     return ASN1_ITERATOR_ERROR;
 156
 157   i->data = i->buffer + i->pos;
 158   i->pos += i->length;
 159
 160   i->type = tag & TAG_MASK;
 161   i->type |= (tag & CLASS_MASK) << (ASN1_CLASS_SHIFT - 6);
 162   if (tag & CONSTRUCTED_MASK)
 163     {
 164       i->type |= ASN1_TYPE_CONSTRUCTED;
 165       return ASN1_ITERATOR_CONSTRUCTED;
 166     }
 167   else
 168     return ASN1_ITERATOR_PRIMITIVE;
 169 }
 170
 171 enum asn1_iterator_result
 172 asn1_der_iterator_first(struct asn1_der_iterator *i,
 173                         size_t length, const uint8_t *input)
 174 {
 175   asn1_der_iterator_init(i, length, input);
 176   return asn1_der_iterator_next(i);
 177 }
 178
 179 enum asn1_iterator_result
 180 asn1_der_decode_constructed(struct asn1_der_iterator *i,
 181                             struct asn1_der_iterator *contents)
 182 {
 183   assert(i->type & ASN1_TYPE_CONSTRUCTED);
 184   return asn1_der_iterator_first(contents, i->length, i->data);
 185 }
 186
 187 enum asn1_iterator_result
 188 asn1_der_decode_constructed_last(struct asn1_der_iterator *i)
 189 {
 190   if (LEFT(i) > 0)
 191     return ASN1_ITERATOR_ERROR;
 192
 193   return asn1_der_decode_constructed(i, i);
 194 }
 195
 196 /* Decoding a DER object which is wrapped in a bit string. */
 197 enum asn1_iterator_result
 198 asn1_der_decode_bitstring(struct asn1_der_iterator *i,
 199                           struct asn1_der_iterator *contents)
 200 {
 201   assert(i->type == ASN1_BITSTRING);
 202   /* First byte is the number of padding bits, which must be zero. */
 203   if (i->length == 0  || i->data[0] != 0)
 204     return ASN1_ITERATOR_ERROR;
 205
 206   return asn1_der_iterator_first(contents, i->length - 1, i->data + 1);
 207 }
 208
 209 enum asn1_iterator_result
 210 asn1_der_decode_bitstring_last(struct asn1_der_iterator *i)
 211 {
 212   if (LEFT(i) > 0)
 213     return ASN1_ITERATOR_ERROR;
 214
 215   return asn1_der_decode_bitstring(i, i);
 216 }
 217
 218 int
 219 asn1_der_get_uint32(struct asn1_der_iterator *i,
 220                     uint32_t *x)
 221 {
 222   /* Big endian, two's complement, minimum number of octets (except 0,
 223      which is encoded as a single octet */
 224   uint32_t value = 0;
 225   size_t length = i->length;
 226   unsigned k;
 227
 228   if (!length || length > 5)
 229     return 0;
 230
 231   if (i->data[length - 1] >= 0x80)
 232     /* Signed number */
 233     return 0;
 234
 235   if (length > 1
 236       && i->data[length -1] == 0
 237       && i->data[length -2] < 0x80)
 238     /* Non-minimal number of digits */
 239     return 0;
 240
 241   if (length == 5)
 242     {
 243       if (i->data[4])
 244         return 0;
 245       length--;
 246     }
 247
 248   for (value = k = 0; k < length; k++)
 249     value = (value << 8) | i->data[k];
 250
 251   *x = value;
 252   return 1;
 253 }
 254
 255 /* NOTE: This is the only function in this file which needs bignums.
 256    One could split this file in two, one in libnettle and one in
 257    libhogweed. */
 258 int
 259 asn1_der_get_bignum(struct asn1_der_iterator *i,
 260                     mpz_t x, unsigned max_bits)
 261 {
 262   if (i->length > 1
 263       && ((i->data[0] == 0 && i->data[1] < 0x80)
 264           || (i->data[0] == 0xff && i->data[1] >= 0x80)))
 265     /* Non-minimal number of digits */
 266     return 0;
 267
 268   /* Allow some extra here, for leading sign octets. */
 269   if (max_bits && (8 * i->length > (16 + max_bits)))
 270     return 0;
 271
 272   nettle_mpz_set_str_256_s(x, i->length, i->data);
 273
 274   /* FIXME: How to interpret a max_bits for negative numbers? */
 275   if (max_bits && mpz_sizeinbase(x, 2) > max_bits)
 276     return 0;
 277
 278   return 1;
 279 }