Part 2

In my previous post CSR, My Old Friend, I talked about the circumstances that lead me to dive into ASN.1.

Now I'm getting to the meat of the issue. My goal is that by the end of this post you'll have enough knowledge to write your own ASN.1 decoder if you need to.

You'll be able to decode and re-encode one of these bad boys:

If you like the sound of that, keep reading!

(otherwise go away... I guess)

First: Recap

ASN.1 is an Abstract Syntax Notation. As was often the way in the dark ages, it's a "meta" description of a standard without actually really standardizing anything that you could concretely implement (kinda like OAuth2).

It basically enumerates theoretical primitive and non-primitive types, such as number, string, array, object.

As such, it would be correct to say that the output of my asn1-parser demo is valid ASN.1... just in a format no one else happens to use.

x.509 is a suite of schemas (including PKCS#1, SEC1, PKCS#8, SPKI, PKIX, CSR, and others) that describe specific ways to store ASN.1 data. This is similar to json-schema.org or XLST.

Just as a JSON schema narrows the dozen ways to express "a person has a first name and a last name" (such as firstName, first_name, firstname and first) down to just one (perhaps first), x509 does the same for DER (and ASN.1).

DER (a subset of BER) is a concrete binary representation used as a wire format to describe ASN.1 schemas. It's the only commonly used ASN.1 serialization that I'm aware of.

It's basically like JSON (or Protobuf), which defines how to serialize and deserialize types of values (i.e. [] for Array vs 0x30 for Sequence or "" for String vs 0x0c for UTF8String).

PEM is nothing more than a base64-encoded DER.

Down and Dirty Overview

ASN.1 seems pretty mysterious at first (as is only natural for anything that gets encoded as binary), but as you break it down, it's actually quite logical... mostly.

DER-encoded ASN.1 data has three parts:

Type
Length
Value

The whole shpeal is just that sequence, one after another.

This is what a PEM file looks like:

It's just a Base64-encoded DER with a type header (and, if encrypted, a header for that).

If you cut off the -----BEGIN .* and -----END .*, and decode the base64 to a buffer (and re-encode that to hex), it looks like this:

30 81 87 02 01 00 30 13  06 07 2A 86 48 CE 3D 02
01 06 08 2A 86 48 CE 3D  03 01 07 04 6D 30 6B 02
01 01 04 20 89 8C 9D A3  6E DA 34 63 BD 0C 15 16
78 61 0F 0F CA 0D 8B 52  D9 0E A7 F1 3E 64 25 89
E2 C1 8D 54 A1 44 03 42  00 04 21 3D 52 58 BC 6C
69 C3 E2 13 96 75 EA 39  28 A4 09 FC FF EF 39 AC
C8 E0 C8 2A 24 AE 78 C3  7E DE 98 FD 89 C0 E0 0E
74 C9 97 BB 0A 71 6C A9  E0 DC A6 73 DB B9 B3 FA
72 96 22 55 C9 DE BC D2  18 CA

If you instead take the PEM and throw it into https://lapo.it/asn1js/ you'll see both the hex and the abstract ASN.1 notation (redundant...) in more-or-less "plain" English:

SEQUENCE (3 elem)
  INTEGER 0
  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.10045.2.1 ecPublicKey (ANSI X9.62 public key type)
    OBJECT IDENTIFIER 1.2.840.10045.3.1.7 prime256v1 (ANSI X9.62 named elliptic curve)
  OCTET STRING (1 elem)
    SEQUENCE (3 elem)
      INTEGER 1
      OCTET STRING (32 byte) 898C9DA36EDA3463BD0C151678610F0FCA0D8B52D90EA7F13E642589E2C18D54
      [1] (1 elem)
        BIT STRING (520 bit) 0000010000100001001111010101001001011000101111000110110001101001110000…

If you compare the two you can break the hex down into the same tree structure as the ASN.1:


30 81 87
   02 01 00
   30 13
      06 07 2A8648CE3D0201
      06 08 2A8648CE3D030107
   04 6D
      30 6B
         02 01 01
         04 20 898C9DA36EDA3463 BD0C151678610F0F
                   CA0D8B52D90EA7F1 3E642589E2C18D54
         A1 44
            03 42 00
                  04 213D5258BC6C69C3 E2139675EA3928A4 09FCFFEF39ACC8E0 C82A24AE78C37EDE
                     98FD89C0E00E74C9 97BB0A716CA9E0DC A673DBB9B3FA7296 2255C9DEBCD218CA

And if you'd like to see a JSON representation of the same thing, I built an asn1 parser demo and code that will do just that:

{
  "type": "0x30", "lengthSize": 1, "length": 135,
  "children": [
    {
      "type": "0x02", "lengthSize": 0, "length": 1,
      "value": "0x00"
    },
    {
      "type": "0x30", "lengthSize": 0, "length": 19,
      "children": [
        {
          "type": "0x06", "lengthSize": 0, "length": 7,
          "value": "0x2a8648ce3d0201"
        },
        {
          "type": "0x06", "lengthSize": 0, "length": 8,
          "value": "0x2a8648ce3d030107"
        }
      ]
    },
    {
      "type": "0x04", "lengthSize": 0, "length": 109,
      "children": [
        {
          "type": "0x30", "lengthSize": 0, "length": 107,
          "children": [
            {
              "type": "0x02", "lengthSize": 0, "length": 1,
              "value": "0x01"
            },
            {
              "type": "0x04", "lengthSize": 0, "length": 32,
              "value": "0x898c9da36eda3463bd0c151678610f0fca0d8b52d90ea7f13e642589e2c18d54"
            },
            {
              "type": "0xa1", "lengthSize": 0, "length": 68,
              "children": [
                {
                  "type": "0x03", "lengthSize": 0, "length": 66,
                  "value": "0x04213d5258bc6c69c3e2139675ea3928a409fcffef39acc8e0c82a24ae78c37ede98fd89c0e00e74c997bb0a716ca9e0dca673dbb9b3fa72962255c9debcd218ca"
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

How to parse / build ASN.1

Strictly speaking, you can't parse ASN.1 - because it's a hypothetical (abstract) syntax. But for all intents and purposes, "DER", "PEM", and "ASN.1" are interchangeable, so I'm just going to talk about DER.

(head to the Abstract Syntax Notation One article over at Wikipedia if you're interested in the theoretical notation)

That aside, if you want to work with PEM / DER / ASN.1, it's almost certain that you'll have to use or write a parser or packer (whichever your need), if nothing more than for the matter of cascading lengths.

If it weren't for that, you could just pick the schemas that you need to work with and hard code them.

Just Three Parts

Type

Type is always just one byte.

Types include primitive values (Boolean, Integer, Real, UTF8String, etc) as well as composite values (Sequence, Set), and meta-data (Object ID, somewhat similar to key in a key/value pair).

I haven't been able to find a list of all types and what there encodings are, but Microsoft has some good docs that list a few, and I find another site that lists a few more.

Length

Lengths are either a single byte (for small numbers, under 128), multiple bytes (for larger numbers over 128), or "indefinite".

If the number is above 128, the first byte is the number of bytes of the length (minus the first bit).

0x00 to 0x7F (0 - 127): this is the byte length of the value
- 0x02 would mean the length is 2 bytes
0x80 to 0xFF: this is the length of the length
- Example 0x8180 means the 1-byte length describes a 128-byte value
  - 0x81 & 0x7F = 0x01
  - 0x80 = 128
- 0x820101 would mean the length is 257 bytes
  - 0x80 & 0x7F = 0x02
  - 0x0101 = 257 bytes
0x80 exactly: the length is "indefinite"
- I think this means read to end-of-file?

And just to state the obvious: lengths cascade. Adjusting the length of any inner value affects the lengths of all outer values.

And although you might think "a 2048-bit key will always be 2048-bits, right?", you'd be wrong because there's a 50% change that you'll get a 2047-bit key - and hence a 0.4% chance that you'll get a 2040-bit key - a full byte less, plus the padding issue for any key using the high-order (2048th, 2040th, or 2032nd) bit.

Value

In JSON the values are often self-explantory, or at least guessable in context.

It's very clear what { "firstName": "Mike" } means, and easy to guess that { "first": "Mike", "last": "Wazowski" } means.

It becomes a little less clear as to what { "first": "Mike", "last": "Jon" } or [ "Mike", "Jon" ] might mean. Perhaps it's a scoreboard, a list of classmates, or maybe just an odd last name.

In the case of DER and ASN.1, however, the data doesn't carry any meaningful information at all. Instead of object keys you get, at best, object ids, so you have to know the schema of the data in order to make almost any meaning from it (though it is a bit better than looking at serialized binary structs - at least you know what type the data is likely to be).

Four tricky bits

Embedded Types

Certain values are used sometimes as primitives but other times as composites. I've seen this mostly with Bit String and Octet String.

If you think about how typed languages work, this makes sense. You can completely parse an outer schema with arbitrary data embeded inside of a primitive binary type and, once you know what that type is, parse the binary type a second time.

In order to write an arbitrary parser without being schema-aware you have two choices:

never parse primitive-ish values on your first pass (leave it to application logic)
attempt to recursively parse some primitive values and rollback on failure (pretty easy to detect)
- this method could produce falso positives, in theory

In code, those options look something like this:

func parse(bytes) {
  if not isKnownCompositeType(bytes[0]) {
    return getValue(bytes)
  }
  return parse(bytes.slice(0, getFullLength(bytes)))
}

func parse(bytes) {
  if isKnownCompositeType(bytes[0]) {
    return parse(bytes.slice(0, getFullLength(bytes)))
  }
  if isKnownPrimitiveType(bytes[0]) {
    return getValue(bytes)
  }

  try {
    return parse(bytes.slice(0, getFullLength(bytes)))
  } catch {
    return getValue(bytes)
  }
}

Length of Length

This isn't too tricky. Here's what was explained above, but in psuedo code

type = bytes[0]

len = bytes[1]
lenlen = 0x7f & len
if lenlen {
  len = int( bytes.slice(2, lenlen) )
}

value = bytes.slice(2 + lenlen, 2 + lenlen + len)

Integer Padding

A number can be positive or negative.

In most languages you have the ability to specify a size and sign of a number:

uint16
int32
float64

If the number is signed, then the high-order bit (the first bit of the most significant byte), such as the bit that would otherwise signify the billionth's place, determines whether the value is negative or positive.

When dealing with BigInts, however, the size is arbitrary and so the "high-order bit" is simply the first bit of the first byte - even if that particular int happens to be 3 bytes long (or 37 bytes long).

To account for this, ASN.1 Integers are padded with 0x00 if the high order bit is set. Hence a "2048-bit" (256-byte) number may actually use 257 bytes in ASN.1.

In code that looks like this:

# parsing
if 0x00 == bytes[0] {
  bytes = bytes.slice(1)
}

# packing
if 0x80 & bytes[0] {
  bytes = bytes.prepend(0)
}

Bit String Padding

For some reason that I don't quite understand, ASN.1 specifies how to handle a string of bits, not constrained to octets (bytes). Perhaps they wanted to account for CPUs that operate on nibbles?

For a reason that I understand even less, many x509 schemas use this type! (as well as also using the Octet String type, which seems the only sensible type to use for this)

This is essentially an "untyped type" (arbitrary bits), a prime suspect for the embedded types I mentioned earlier.

DER is byte-aligned (like most things), which means that you must always use 8 bits at a time, even if you only need 3 bits to describe some particular data value.

Since the Bit String type is not byte-aligned (only useful in a theoretical world where you could send 3/8 of a byte across the wire, as far as I can tell), it uses a pad byte to tell which bits of the first byte to ignore.

In practice, that pad is always '0x00', so the code would just look like this:

# parser
if 0x03 == bytes[0] {
  bytes = bytes.slice(getFullLength(bytes) + 1)
}

# packer
if 0x03 == bytes[0] {
  bytes = bytes.prepend(0)
}

And I was going to show you what the theoretical code would look like, but it A) doesn't make any sense (because I'd have to invent and then explain psuedo-code that uses bits instead of bytes) and B) would be long and complicated.

Resources

Your first stop should be to download Hex Fiend (macOS) or DHEX (curses-based), generate some der files with openssl, and just checking out what things look like, as I described in CSR, My Old Friend.

Next, I'd highly recommend using https://lapo.it/asn1js/, which appears to have full x509 schema support, to parse your PEMs to see exactly what they look like.

Then check my very own asn1-parser.js demo to see what the JSON structure for such a PEM might look like.

If you decide to start writing your own simplistic parser or packer, I recommend digging into either of these (they're only about ~100 lines long each):

Good luck. Feel free to hit me up if you have questions, or would like to hire me for a project.

By AJ ONeal

Did I make your day?

Buy me a coffee

(you can learn about the bigger picture I'm working towards on my patreon page )

ASN.1 for Dummies