OpenSSL misinterprets BER constructed BIT STRINGs

(ASN.1 snippets use der-ascii syntax, from https://github.com/google/der-ascii.)

Summary

OpenSSL's decoding of constructed BIT STRINGs does not interoperate with the specification or other implementations. It injects extra bits into the resulting value due to flipping the order of padding and concatenation.

Details

BER, unlike DER, has a number of overcomplicated encodings for streaming, notably constructed strings. String types are normally encoded as primitive elements, such as OCTET_STRING { "hello, world" }. BER additionally allows a constructed string where the outer element is constructed and inner elements are concatenated:

[OCTET_STRING CONSTRUCTED] {
  OCTET_STRING { "hello, " }
  OCTET_STRING { "world" }
}

(This, when combined with indefinite-length encoding, lets the encoder stream a large string without knowing the length ahead of time, though none of the uses in OpenSSL actually rely on streaming.) The rules for most strings are described in 8.7.3 of X.690 (08/2015). OpenSSL implements this in asn1_collect.

BIT STRINGs are different. A BIT STRING is a sequence of bits, possibly not a multiple of 8 of them. They are encoded by appending 0 <= N <= 7 bits up to multiple of 8. N is then prepended as a byte. Thus BIT_STRING { `00abcd` } is a 16-bit BIT STRING (N = 0), and BIT_STRING { `04abc0` } is a 12-bit BIT STRING (N = 4).

BIT STRINGs can also be constructed, and OpenSSL runs the same asn1_collect logic for them.
https://github.com/openssl/openssl/blob/master/crypto/asn1/tasn_dec.c#L731-L756

But constructed BIT STRINGs work differently. See 8.6.3 and 8.6.4 of X.690 (08/2015). Each segment has its own leading byte, so a streaming encoder does not need to commit to the length mod 8. (Although only the final segment can have padding bits. This means those bytes are redundant, but a streaming receiver doesn't know the segment is the last one.) OpenSSL instead flips the order: it concatenates first, then resolves padding. That is, the 12-bit string BIT_STRING { `04abc0` } can be encoded as:

[BIT_STRING CONSTRUCTED] {
  BIT_STRING { `00ab` }
  BIT_STRING { `04c0` }
}

But OpenSSL misinterprets it as the 24-bit string BIT_STRING { `00ab04c0` }. Instead, OpenSSL accepts the following as the 12-bit input:

[BIT_STRING CONSTRUCTED] {
  BIT_STRING { `04ab` }
  BIT_STRING { `c0` }
}

This is not a valid BER BIT STRING encoding at all because c0 is greater than 7. See also the test program below. It compares OpenSSL's behavior with that of NSS, which seems to handle it correctly.

Recommendation

Since this BIT STRING handling doesn't match spec or other implementations, and will misinterpret valid inputs (quite risky in a security-sensitive library), OpenSSL should either switch to the correct handling, or reject constructed BIT STRINGs altogether. I would suggest the latter (i.e. don't support constructed BIT STRINGs). BER is unnecessarily complicated, and this bug means constructed BIT STRINGs aren't usable in anything which needs to work with existing OpenSSLs anyway.

As far as I can tell, OpenSSL will never produce constructed BIT STRINGs, so I don't think the current behavior is particularly indicative compatibility-wise. Indeed most uses of cryptography like X.509 require DER, so using a BER parser at all is too loose. PKCS#7 and PKCS#12 blobs sadly do often use BER, but BIT STRINGs only carry public keys and signature values, neither of which are large enough to bother streaming. (I would argue the entirety of PKCS#7 and PKCS#12 aren't worth streaming in the first place. Indeed OpenSSL doesn't stream them.) This is probably why no one's noticed this before.

Test program

/*
Input:   030300abcd
OpenSSL: num_bits=16 abcd
NSS:     num_bits=16 abcd

Input:   2308030200ab030200cd
OpenSSL: num_bits=24 ab00cd
NSS:     num_bits=16 abcd

Input:   2307030200ab0301cd
OpenSSL: num_bits=16 abcd
NSS:     invalid input

Input:   030304abc0
OpenSSL: num_bits=12 abc0
NSS:     num_bits=12 abc0

Input:   2308030200ab030204c0
OpenSSL: num_bits=24 ab04c0
NSS:     num_bits=12 abc0

Input:   2307030204ab0301cd
OpenSSL: num_bits=12 abc0
NSS:     invalid input

Input:   0303000000
OpenSSL: num_bits=16 0000
NSS:     num_bits=16 0000

Input:   23080302000003020000
OpenSSL: num_bits=24 000000
NSS:     num_bits=16 0000

Input:   230703020000030100
OpenSSL: num_bits=16 0000
NSS:     num_bits=8 00
*/

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

#include <openssl/asn1.h>
#include <secasn1.h>

static void print_bytes(const unsigned char *in, size_t len) {
  for (size_t i = 0; i < len; i++) {
    printf("%02x", in[i]);
  }
}

static void test_openssl(const unsigned char *in, size_t len) {
  ASN1_BIT_STRING *str = d2i_ASN1_BIT_STRING(NULL, &in, len);
  if (!str) {
    printf("OpenSSL: invalid input\n");
    return;
  }
  assert(str->flags & ASN1_STRING_FLAG_BITS_LEFT);
  int num_bits = 8 * ASN1_STRING_length(str) - (str->flags & 0x7);
  printf("OpenSSL: num_bits=%d ", num_bits);
  print_bytes(ASN1_STRING_get0_data(str), ASN1_STRING_length(str));
  printf("\n");
  ASN1_STRING_free(str);
}

static void test_nss(const unsigned char *in, size_t len) {
  SECItem input;
  input.type = siBuffer;
  input.data = (unsigned char *)in;
  input.len = len;

  SECItem output;
  output.type = siBuffer;
  output.data = NULL;
  output.len = 0;

  if (SEC_ASN1DecodeItem(NULL, &output, SEC_ASN1_GET(SEC_BitStringTemplate),
                         &input) != SECSuccess) {
    printf("NSS:     invalid input\n");
    return;
  }

  /* NSS returns BIT STRINGs as SECItems whose length is measured in bits
   * rather than bytes. */
  printf("NSS:     num_bits=%u ", output.len);
  print_bytes(output.data, (output.len + 7) / 8);
  printf("\n");
  PORT_Free(output.data);
}

static void test(const unsigned char *in, size_t len) {
  printf("Input:   ");
  print_bytes(in, len);
  printf("\n");
  test_openssl(in, len);
  test_nss(in, len);
  printf("\n");
}

int main() {
  // BIT_STRING { `00abcd` }
  static const unsigned char kDER0[] = {0x03, 0x03, 0x00, 0xab, 0xcd};
  test(kDER0, sizeof(kDER0));

  // Valid BER constructed version of the above:
  // [BIT_STRING CONSTRUCTED] {
  //   BIT_STRING { `00ab` }
  //   BIT_STRING { `00cd` }
  // }
  static const unsigned char kBER0[] = {0x23, 0x08, 0x03, 0x02, 0x00,
                                        0xab, 0x03, 0x02, 0x00, 0xcd};
  test(kBER0, sizeof(kBER0));

  // Invalid BER constructed version of the above:
  // [BIT_STRING CONSTRUCTED] {
  //   BIT_STRING { `00ab` }
  //   BIT_STRING { `cd` }
  // }
  static const unsigned char kInvalidBER0[] = {0x23, 0x07, 0x03, 0x02, 0x00,
                                               0xab, 0x03, 0x01, 0xcd};
  test(kInvalidBER0, sizeof(kInvalidBER0));

  // BIT_STRING { `04abc0` }
  static const unsigned char kDER1[] = {0x03, 0x03, 0x04, 0xab, 0xc0};
  test(kDER1, sizeof(kDER1));

  // Valid BER constructed version of the above:
  // [BIT_STRING CONSTRUCTED] {
  //   BIT_STRING { `00ab` }
  //   BIT_STRING { `04c0` }
  // }
  static const unsigned char kBER1[] = {0x23, 0x08, 0x03, 0x02, 0x00,
                                        0xab, 0x03, 0x02, 0x04, 0xc0};
  test(kBER1, sizeof(kBER1));

  // Invalid BER constructed version of the above:
  // [BIT_STRING CONSTRUCTED] {
  //   BIT_STRING { `04ab` }
  //   BIT_STRING { `cd` }
  // }
  static const unsigned char kInvalidBER1[] = {0x23, 0x07, 0x03, 0x02, 0x04,
                                               0xab, 0x03, 0x01, 0xcd};
  test(kInvalidBER1, sizeof(kInvalidBER1));

  // BIT_STRING { `000000` }
  static const unsigned char kDER2[] = {0x03, 0x03, 0x00, 0x00, 0x00};
  test(kDER2, sizeof(kDER2));

  // Valid BER constructed version of the above:
  // [BIT_STRING CONSTRUCTED] {
  //   BIT_STRING { `0000` }
  //   BIT_STRING { `0000` }
  // }
  static const unsigned char kBER2[] = {0x23, 0x08, 0x03, 0x02, 0x00,
                                        0x00, 0x03, 0x02, 0x00, 0x00};
  test(kBER2, sizeof(kBER2));

  // Invalid BER constructed version of the above:
  // [BIT_STRING CONSTRUCTED] {
  //   BIT_STRING { `0000` }
  //   BIT_STRING { `00` }
  // }
  static const unsigned char kInvalidBER2[] = {0x23, 0x07, 0x03, 0x02, 0x00,
                                               0x00, 0x03, 0x01, 0x00};
  test(kInvalidBER2, sizeof(kInvalidBER2));
}

Description

Contributor guide

First steps

Research direction

Assessment