der-iterator.c

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