src/lib/asn1/ASN1Writer.cpp

   1 /*
   2  *
   3  *    Copyright (c) 2020 Project CHIP Authors
   4  *    Copyright (c) 2013-2017 Nest Labs, Inc.
   5  *    All rights reserved.
   6  *
   7  *    Licensed under the Apache License, Version 2.0 (the "License");
   8  *    you may not use this file except in compliance with the License.
   9  *    You may obtain a copy of the License at
  10  *
  11  *        http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  *    Unless required by applicable law or agreed to in writing, software
  14  *    distributed under the License is distributed on an "AS IS" BASIS,
  15  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  *    See the License for the specific language governing permissions and
  17  *    limitations under the License.
  18  */
  19
  20 /**
  21  *    @file
  22  *      This file implements an object for writing Abstract Syntax
  23  *      Notation One (ASN.1) encoded data.
  24  *
  25  */
  26
  27 #ifndef __STDC_LIMIT_MACROS
  28 #define __STDC_LIMIT_MACROS
  29 #endif
  30 #include <ctype.h>
  31 #include <stdint.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 #include <asn1/ASN1.h>
  37 #include <core/CHIPCore.h>
  38 #include <core/CHIPEncoding.h>
  39 #include <core/CHIPTLV.h>
  40 #include <support/CodeUtils.h>
  41
  42 namespace chip {
  43 namespace ASN1 {
  44
  45 using namespace chip::Encoding;
  46
  47 enum
  48 {
  49     kLengthFieldReserveSize = 5,
  50     kMaxElementLength       = INT32_MAX,
  51     kUnkownLength           = -1,
  52     kUnknownLengthMarker    = 0xFF
  53 };
  54
  55 void ASN1Writer::Init(uint8_t * buf, uint32_t maxLen)
  56 {
  57     mBuf                = buf;
  58     mWritePoint         = buf;
  59     mBufEnd             = buf + maxLen;
  60     mBufEnd             = reinterpret_cast<uint8_t *>(reinterpret_cast<uintptr_t>(mBufEnd) & ~3); // align on 32bit boundary
  61     mDeferredLengthList = reinterpret_cast<uint8_t **>(mBufEnd);
  62 }
  63
  64 void ASN1Writer::InitNullWriter(void)
  65 {
  66     mBuf                = nullptr;
  67     mWritePoint         = nullptr;
  68     mBufEnd             = nullptr;
  69     mDeferredLengthList = nullptr;
  70 }
  71
  72 ASN1_ERROR ASN1Writer::Finalize()
  73 {
  74     if (mBuf != nullptr)
  75     {
  76         uint8_t * compactPoint = mBuf;
  77         uint8_t * spanStart    = mBuf;
  78
  79         for (uint8_t ** listEntry = reinterpret_cast<uint8_t **>(mBufEnd); listEntry > mDeferredLengthList;)
  80         {
  81             uint8_t * lenField        = *--listEntry;
  82             uint8_t lenFieldFirstByte = *lenField;
  83
  84             if (lenFieldFirstByte == kUnknownLengthMarker)
  85                 return ASN1_ERROR_INVALID_STATE;
  86
  87             uint8_t lenOfLen = (lenFieldFirstByte < 128) ? 1 : (lenFieldFirstByte & 0x7f) + 1;
  88
  89             uint8_t * spanEnd = lenField + lenOfLen;
  90
  91             if (spanStart == compactPoint)
  92                 compactPoint = spanEnd;
  93             else
  94             {
  95                 uint32_t spanLen = spanEnd - spanStart;
  96                 memmove(compactPoint, spanStart, spanLen);
  97                 compactPoint += spanLen;
  98             }
  99
 100             spanStart = lenField + kLengthFieldReserveSize;
 101         }
 102
 103         if (spanStart > compactPoint)
 104         {
 105             uint32_t spanLen = mWritePoint - spanStart;
 106             memmove(compactPoint, spanStart, spanLen);
 107             compactPoint += spanLen;
 108         }
 109
 110         mWritePoint = compactPoint;
 111     }
 112
 113     return ASN1_NO_ERROR;
 114 }
 115
 116 uint16_t ASN1Writer::GetLengthWritten() const
 117 {
 118     return (mBuf != nullptr) ? mWritePoint - mBuf : 0;
 119 }
 120
 121 ASN1_ERROR ASN1Writer::PutInteger(int64_t val)
 122 {
 123     uint8_t encodedVal[8];
 124     uint8_t valStart, valLen;
 125
 126     BigEndian::Put64(encodedVal, static_cast<uint64_t>(val));
 127
 128     for (valStart = 0; valStart < 7; valStart++)
 129     {
 130         if (encodedVal[valStart] == 0x00 && (encodedVal[valStart + 1] & 0x80) == 0)
 131             continue;
 132         if (encodedVal[valStart] == 0xFF && (encodedVal[valStart + 1] & 0x80) == 0x80)
 133             continue;
 134         break;
 135     }
 136     valLen = 8 - valStart;
 137
 138     return PutValue(kASN1TagClass_Universal, kASN1UniversalTag_Integer, false, encodedVal + valStart, valLen);
 139 }
 140
 141 ASN1_ERROR ASN1Writer::PutBoolean(bool val)
 142 {
 143     ASN1_ERROR err;
 144
 145     // Do nothing for a null writer.
 146     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 147
 148     err = EncodeHead(kASN1TagClass_Universal, kASN1UniversalTag_Boolean, false, 1);
 149     SuccessOrExit(err);
 150
 151     *mWritePoint++ = (val) ? 0xFF : 0;
 152
 153 exit:
 154     return err;
 155 }
 156
 157 ASN1_ERROR ASN1Writer::PutObjectId(const uint8_t * val, uint16_t valLen)
 158 {
 159     return PutValue(kASN1TagClass_Universal, kASN1UniversalTag_ObjectId, false, val, valLen);
 160 }
 161
 162 ASN1_ERROR ASN1Writer::PutString(uint32_t tag, const char * val, uint16_t valLen)
 163 {
 164     return PutValue(kASN1TagClass_Universal, tag, false, (const uint8_t *) val, valLen);
 165 }
 166
 167 ASN1_ERROR ASN1Writer::PutOctetString(const uint8_t * val, uint16_t valLen)
 168 {
 169     return PutValue(kASN1TagClass_Universal, kASN1UniversalTag_OctetString, false, val, valLen);
 170 }
 171
 172 ASN1_ERROR ASN1Writer::PutOctetString(uint8_t cls, uint32_t tag, const uint8_t * val, uint16_t valLen)
 173 {
 174     return PutValue(cls, tag, false, val, valLen);
 175 }
 176
 177 ASN1_ERROR ASN1Writer::PutOctetString(uint8_t cls, uint32_t tag, chip::TLV::TLVReader & val)
 178 {
 179     return PutValue(cls, tag, false, val);
 180 }
 181
 182 static uint8_t ReverseBits(uint8_t v)
 183 {
 184     // swap adjacent bits
 185     v = ((v >> 1) & 0x55) | ((v & 0x55) << 1);
 186     // swap adjacent bit pairs
 187     v = ((v >> 2) & 0x33) | ((v & 0x33) << 2);
 188     // swap nibbles
 189     v = (v >> 4) | (v << 4);
 190     return v;
 191 }
 192
 193 static uint8_t HighestBit(uint32_t v)
 194 {
 195     uint32_t highestBit = 0;
 196
 197     if (v > 0xFFFF)
 198     {
 199         highestBit = 16;
 200         v >>= 16;
 201     }
 202     if (v > 0xFF)
 203     {
 204         highestBit |= 8;
 205         v >>= 8;
 206     }
 207     if (v > 0xF)
 208     {
 209         highestBit |= 4;
 210         v >>= 4;
 211     }
 212     if (v > 0x3)
 213     {
 214         highestBit |= 2;
 215         v >>= 2;
 216     }
 217     highestBit |= (v >> 1);
 218
 219     return highestBit;
 220 }
 221
 222 ASN1_ERROR ASN1Writer::PutBitString(uint32_t val)
 223 {
 224     ASN1_ERROR err;
 225     uint8_t len;
 226
 227     // Do nothing for a null writer.
 228     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 229
 230     if (val == 0)
 231         len = 1;
 232     else if (val < 256)
 233         len = 2;
 234     else if (val < 65536)
 235         len = 3;
 236     else if (val < (1 << 24))
 237         len = 4;
 238     else
 239         len = 5;
 240
 241     err = EncodeHead(kASN1TagClass_Universal, kASN1UniversalTag_BitString, false, len);
 242     SuccessOrExit(err);
 243
 244     if (val == 0)
 245         mWritePoint[0] = 0;
 246     else
 247     {
 248         mWritePoint[1] = ReverseBits(static_cast<uint8_t>(val));
 249         if (len >= 3)
 250         {
 251             val >>= 8;
 252             mWritePoint[2] = ReverseBits(static_cast<uint8_t>(val));
 253             if (len >= 4)
 254             {
 255                 val >>= 8;
 256                 mWritePoint[3] = ReverseBits(static_cast<uint8_t>(val));
 257                 if (len == 5)
 258                 {
 259                     val >>= 8;
 260                     mWritePoint[4] = ReverseBits(static_cast<uint8_t>(val));
 261                 }
 262             }
 263         }
 264         mWritePoint[0] = 7 - HighestBit(val);
 265     }
 266
 267     mWritePoint += len;
 268
 269 exit:
 270     return err;
 271 }
 272
 273 ASN1_ERROR ASN1Writer::PutBitString(uint8_t unusedBitCount, const uint8_t * encodedBits, uint16_t encodedBitsLen)
 274 {
 275     ASN1_ERROR err;
 276
 277     // Do nothing for a null writer.
 278     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 279
 280     err = EncodeHead(kASN1TagClass_Universal, kASN1UniversalTag_BitString, false, encodedBitsLen + 1);
 281     SuccessOrExit(err);
 282
 283     *mWritePoint++ = unusedBitCount;
 284
 285     memcpy(mWritePoint, encodedBits, encodedBitsLen);
 286     mWritePoint += encodedBitsLen;
 287
 288 exit:
 289     return err;
 290 }
 291
 292 ASN1_ERROR ASN1Writer::PutBitString(uint8_t unusedBitCount, chip::TLV::TLVReader & encodedBits)
 293 {
 294     ASN1_ERROR err;
 295     uint32_t encodedBitsLen;
 296
 297     // Do nothing for a null writer.
 298     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 299
 300     encodedBitsLen = encodedBits.GetLength();
 301
 302     err = EncodeHead(kASN1TagClass_Universal, kASN1UniversalTag_BitString, false, encodedBitsLen + 1);
 303     SuccessOrExit(err);
 304
 305     *mWritePoint++ = unusedBitCount;
 306
 307     encodedBits.GetBytes(mWritePoint, encodedBitsLen);
 308     mWritePoint += encodedBitsLen;
 309
 310 exit:
 311     return err;
 312 }
 313
 314 static void itoa2(uint32_t val, uint8_t * buf)
 315 {
 316     buf[1] = '0' + (val % 10);
 317     val /= 10;
 318     buf[0] = '0' + (val % 10);
 319 }
 320
 321 ASN1_ERROR ASN1Writer::PutTime(const ASN1UniversalTime & val)
 322 {
 323     uint8_t buf[15];
 324
 325     itoa2(val.Year / 100, buf);
 326     itoa2(val.Year, buf + 2);
 327     itoa2(val.Month, buf + 4);
 328     itoa2(val.Day, buf + 6);
 329     itoa2(val.Hour, buf + 8);
 330     itoa2(val.Minute, buf + 10);
 331     itoa2(val.Second, buf + 12);
 332     buf[14] = 'Z';
 333
 334     // X.509/RFC5280 mandates that times before 2050 UTC must be encoded as ASN.1 UTCTime values, while
 335     // times equal or greater than 2050 must be encoded as GeneralizedTime values.  The only difference
 336     // (in the context of X.509 DER) is that GeneralizedTimes are encoded with a 4 digit year, while
 337     // UTCTimes are encoded with a two-digit year.
 338     //
 339     if (val.Year >= 2050)
 340         return PutValue(kASN1TagClass_Universal, kASN1UniversalTag_GeneralizedTime, false, buf, 15);
 341     else
 342         return PutValue(kASN1TagClass_Universal, kASN1UniversalTag_UTCTime, false, buf + 2, 13);
 343 }
 344
 345 ASN1_ERROR ASN1Writer::PutNull()
 346 {
 347     return EncodeHead(kASN1TagClass_Universal, kASN1UniversalTag_Null, false, 0);
 348 }
 349
 350 ASN1_ERROR ASN1Writer::StartConstructedType(uint8_t cls, uint32_t tag)
 351 {
 352     return EncodeHead(cls, tag, true, kUnkownLength);
 353 }
 354
 355 ASN1_ERROR ASN1Writer::EndConstructedType()
 356 {
 357     return WriteDeferredLength();
 358 }
 359
 360 ASN1_ERROR ASN1Writer::StartEncapsulatedType(uint8_t cls, uint32_t tag, bool bitStringEncoding)
 361 {
 362     ASN1_ERROR err;
 363
 364     // Do nothing for a null writer.
 365     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 366
 367     err = EncodeHead(cls, tag, false, kUnkownLength);
 368     SuccessOrExit(err);
 369
 370     // If the encapsulating type is BIT STRING, encode the unused bit count field.  Since the BIT
 371     // STRING contains an ASN.1 DER encoding, and ASN.1 DER encodings are always multiples of 8 bits,
 372     // the unused bit count is always 0.
 373     if (bitStringEncoding)
 374     {
 375         if (mWritePoint == reinterpret_cast<uint8_t *>(mDeferredLengthList))
 376             return ASN1_ERROR_OVERFLOW;
 377         *mWritePoint++ = 0;
 378     }
 379
 380 exit:
 381     return err;
 382 }
 383
 384 ASN1_ERROR ASN1Writer::EndEncapsulatedType()
 385 {
 386     return WriteDeferredLength();
 387 }
 388
 389 ASN1_ERROR ASN1Writer::PutValue(uint8_t cls, uint32_t tag, bool isConstructed, const uint8_t * val, uint16_t valLen)
 390 {
 391     ASN1_ERROR err;
 392
 393     // Do nothing for a null writer.
 394     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 395
 396     err = EncodeHead(cls, tag, isConstructed, valLen);
 397     SuccessOrExit(err);
 398
 399     memcpy(mWritePoint, val, valLen);
 400     mWritePoint += valLen;
 401
 402 exit:
 403     return err;
 404 }
 405
 406 ASN1_ERROR ASN1Writer::PutValue(uint8_t cls, uint32_t tag, bool isConstructed, chip::TLV::TLVReader & val)
 407 {
 408     ASN1_ERROR err;
 409     uint32_t valLen;
 410
 411     // Do nothing for a null writer.
 412     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 413
 414     valLen = val.GetLength();
 415
 416     err = EncodeHead(cls, tag, isConstructed, valLen);
 417     SuccessOrExit(err);
 418
 419     val.GetBytes(mWritePoint, valLen);
 420     mWritePoint += valLen;
 421
 422 exit:
 423     return err;
 424 }
 425
 426 ASN1_ERROR ASN1Writer::EncodeHead(uint8_t cls, uint32_t tag, bool isConstructed, int32_t len)
 427 {
 428     ASN1_ERROR err = ASN1_NO_ERROR;
 429     uint8_t bytesForLen;
 430     uint32_t totalLen;
 431
 432     // Do nothing for a null writer.
 433     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 434
 435     // Only tags <= 31 supported. The implication of this is that encoded tags are exactly 1 byte long.
 436     VerifyOrExit(tag <= 0x1F, err = ASN1_ERROR_UNSUPPORTED_ENCODING);
 437
 438     // Only positive and kUnkownLength values are supported for len input.
 439     VerifyOrExit(len >= 0 || len == kUnkownLength, err = ASN1_ERROR_UNSUPPORTED_ENCODING);
 440
 441     // Compute the number of bytes required to encode the length.
 442     bytesForLen = BytesForLength(len);
 443
 444     // If the element length is unknown, allocate a new entry in the deferred-length list.
 445     //
 446     // The deferred-length list is a list of "pointers" (represented as offsets into mBuf)
 447     // to length fields for which the length of the element was unknown at the time the element
 448     // head was written. Examples include constructed types such as SEQUENCE and SET, as well
 449     // non-constructed types that encapsulate other ASN.1 types (e.g. OCTET STRINGS that contain
 450     // BER/DER encodings). The final lengths are filled in later, at the time the encoding is
 451     // complete (e.g. when EndConstructed() is called).
 452     //
 453     if (len == kUnkownLength)
 454         mDeferredLengthList--;
 455
 456     // Make sure there's enough space to encode the entire value without bumping into the deferred length
 457     // list at the end of the buffer.
 458     totalLen = 1 + bytesForLen + (len != kUnkownLength ? len : 0);
 459     VerifyOrExit((mWritePoint + totalLen) <= reinterpret_cast<uint8_t *>(mDeferredLengthList), err = ASN1_ERROR_OVERFLOW);
 460
 461     // Write the tag byte.
 462     *mWritePoint++ = cls | (isConstructed ? 0x20 : 0) | tag;
 463
 464     // Encode the length if it is known.
 465     if (len != kUnkownLength)
 466         EncodeLength(mWritePoint, bytesForLen, len);
 467
 468     // ... otherwise place a marker in the first byte of the length to indicate that the length is unknown
 469     // and save a pointer to the length field in the deferred-length list.
 470     else
 471     {
 472         *mWritePoint         = kUnknownLengthMarker;
 473         *mDeferredLengthList = mWritePoint;
 474     }
 475
 476     mWritePoint += bytesForLen;
 477
 478 exit:
 479     return err;
 480 }
 481
 482 ASN1_ERROR ASN1Writer::WriteDeferredLength()
 483 {
 484     ASN1_ERROR err = ASN1_NO_ERROR;
 485     uint8_t ** listEntry;
 486     uint32_t lenAdj;
 487
 488     // Do nothing for a null writer.
 489     VerifyOrExit(mBuf != nullptr, err = ASN1_NO_ERROR);
 490
 491     lenAdj = kLengthFieldReserveSize;
 492
 493     // Scan the deferred-length list in reverse order looking for the most recent entry where
 494     // the length is still unknown. This entry represents the "container" element whose encoding
 495     // is now complete.
 496     for (listEntry = mDeferredLengthList; listEntry < reinterpret_cast<uint8_t **>(mBufEnd); listEntry++)
 497     {
 498         // Get a pointer to the deferred-length field.
 499         uint8_t * lenField = *listEntry;
 500
 501         // Get the first byte of the length field.
 502         uint8_t lenFieldFirstByte = *lenField;
 503
 504         // If the length is marked as unknown...
 505         if (lenFieldFirstByte == kUnknownLengthMarker)
 506         {
 507             // Compute the final length of the element's value (3 = bytes reserved for length).
 508             uint32_t elemLen = (mWritePoint - lenField) - lenAdj;
 509
 510             // Return an error if the length exceeds the maximum value that can be encoded in the
 511             // space reserved for the length.
 512             VerifyOrExit(elemLen <= kMaxElementLength, err = ASN1_ERROR_LENGTH_OVERFLOW);
 513
 514             // Encode the final length of the element, overwriting the unknown length marker
 515             // in the process.  Note that the number of bytes consumed by the final length field
 516             // may be smaller than the space that was reserved for the field.  This will be fixed
 517             // up when the Finalize() method is called.
 518             uint8_t bytesForLen = BytesForLength(static_cast<int32_t>(elemLen));
 519             EncodeLength(lenField, bytesForLen, elemLen);
 520
 521             ExitNow(err = ASN1_NO_ERROR);
 522         }
 523         else
 524         {
 525             uint8_t bytesForLen = (lenFieldFirstByte < 128) ? 1 : (lenFieldFirstByte & 0x7f) + 1;
 526             lenAdj += (kLengthFieldReserveSize - bytesForLen);
 527         }
 528     }
 529
 530     err = ASN1_ERROR_INVALID_STATE;
 531
 532 exit:
 533     return err;
 534 }
 535
 536 /**
 537  * Returns the number of bytes required to encode the length value.
 538  *
 539  * @param[in]   len     Parameter, which encoding length to be calculated.
 540  *
 541  * @return number of bytes required to encode the length value.
 542  */
 543 uint8_t ASN1Writer::BytesForLength(int32_t len)
 544 {
 545     if (len == kUnkownLength)
 546         return kLengthFieldReserveSize;
 547     if (len < 128)
 548         return 1;
 549     if (len < 256)
 550         return 2;
 551     if (len < 65536)
 552         return 3;
 553     if (len < (1 << 24))
 554         return 4;
 555     return 5;
 556 }
 557
 558 void ASN1Writer::EncodeLength(uint8_t * buf, uint8_t bytesForLen, int32_t lenToEncode)
 559 {
 560     if (bytesForLen == 1)
 561         buf[0] = static_cast<uint8_t>(lenToEncode);
 562     else
 563     {
 564         --bytesForLen;
 565         buf[0] = 0x80 | bytesForLen;
 566         do
 567         {
 568             buf[bytesForLen] = static_cast<uint8_t>(lenToEncode);
 569             lenToEncode >>= 8;
 570         } while (--bytesForLen);
 571     }
 572 }
 573
 574 } // namespace ASN1
 575 } // namespace chip