The specs behind the specs – a deep-dive on ASN.1

Not OP, but one of the challenges is that definite-length encodings like DER have to be encoded in a non-intuitive way. Values must be encoded prior to lengths (because the length is unknown), and the values can be nested. Therefore you have to encode a message essentially backwards when using definite-length encodings. This can potentially require a great deal of memory and can increase latency because streaming the data is hard.

Indefinite lengths (BER has this option, CER requires it) can help avoid this problem, but then you lose the benefit of skipping elements (which you allude to in your next paragraph).

> Do you feel that the same doesn't apply to serialisation formats? How are the non-tlv binaries encoded then? Just implied offsets according to the schema? Can you then evolve the schema at all, or do you feel that both producer and consumer should have always access to the full schema, and flexiblity here is a non-feature?

You've hit the tradeoffs pretty well in the question, I think. The nice thing about TLV is that you can decode without a schema and potentially work with the contents: it's a relatively simple format to decode and validate even if it's not necessarily great for the encoder.

ASN.1 supports schema-informed packed encodings that place greater demands on both the encoder and decoder. The main advantage is that they greatly reduce message overhead, but it requires a lot of bit-twiddling for presence/absence, default values, and, in unaligned variants, everything else, too. It's impossible, generally, to decode everything without the schema. PER has rules that disambiguate the values (e.g., they have to be ordered in a particular way, so you know what's coming next), and this mitigates some of the problems of TLV-style encodings.

The tradeoffs are worth it when your pipes are small. 3GPP and LTE messages are largely encoded in PER. The people playing in that world usually have plenty of money to spend on commercial solutions and have bandwidth to roll their own, too. That's a bit different than smaller shops who are looking for convenient automated serialization formats.

First, some generic problems with TLV encodings:

  - they necessarily result in unnecessarily
    redundant encodings -- this is wasteful, bloat
  
  - that redundancy is of zero help to a compiler
  
  - that redundancy is a psychological crutch to
    any programmer writing hand-coded codecs, but
    this often has led to serious bugs
  
  - tag allocation has to be managed, and here
    again you really want a compiler to do it for
    you -- ASN.1 eventually added AUTOMATIC tags,
    but the damage of not having had those was
    done

  - streaming encoding is infeasible -- you have
    to know the definite lengths before you
    start encoding, so you lose
  
  - you either have to compute the length of the
    encoding of any value before you begin
    encoding it, or you have to encode "back to
    front" (and then possibly realloc as needed)
    or both

Bottom-line: TLV is an unnecessary crutch. Compilers simply don't need it. For proof by existence consider that Sun's rpcgen(1) existed in 1986, a mere two years after ASN.1's 1984 standard, and rpcgen(1) uses XDR syntax and encoding -- XDR is NOT a TLV encoding at all. But ASN.1 tooling -proprietary and open source- took much longer to catch up with XDR and IDL/NDR and other things. It's almost like TLV encodings made it harder to get to compilation because they were a crutch for hand-coding codecs. But even XDR is easy to hand-write codecs for!

BTW, XDR and NDR were basically the first flatbuffers-like encodings. Lustre RPC has an even more flatbuffers-like encoding, but it's hand-coded. There's just nothing new in this space, and there hasn't really been anything new in this space in many years.

> At least in file formats it to me seem they would be instrumental to have a extendible and flexible format, where you can skip unknown or uninteresting chunks (in say, PNG chunks, or IFF-based formats like OBJ, etc.).

TLV is NOT necessary for this sort of extensibility. You naturally end up with something like TLV when using non-TLV encodings with support for extensibility, though it's often more like LTV. Let's say you have a struct you want to make extensible in some non-TLV encoding you're designing... What would you do? Well, knowing ASN.1's PER/OER and knowing how we've dealt with this in XDR I would do this: add an octet string field to the end of every extensible struct! What would that octet string contain? The encoding of the extensions. What if you want to support different kinds of extensions in a mix-and-match way? Well, that's easy too: add a discriminated union or "typed hole" to the end of every extensible struct, with every choice taken having a Length prepended to it so you can skip it.

Extensibility is something that has been beat to death in the ASN.1 space, and it has all of these options:

- extensibility markers in SEQUENCE / SET types (i.e., "struct" types)

- extensibility markers in CHOICE types (i.e., discriminated union types)

- extensibility markers in INTEGER and BIT STRING constraints (i.e., enum types)

- rules for handling known and unknown extensions in each ER (encoding rules)

- typed holes.

A typed hole is just a glorified discriminated union with an "external" sort of discriminant and specification of the union arms' types. Basically, a typed hole is just a struct with two fields: a) a type identifier of some sort (an integer, a string, an OID, a relative OID, whatever), b) an octet string containing an encoding of the value of a type identified by (a).

ASN.1 has syntax and semantics for expressing what type IDs go with what types, and so you can actually have compilers that recursively and automatically decode/encode through typed holes.

> Do you feel that the same doesn't apply to serialisation formats? How are the non-tlv binaries encoded then? Just implied offsets according to the schema? Can you then evolve the schema at all, or do you feel that both producer and consumer should have always access to the full schema, and flexiblity here is a non-feature?

I address this above. This is all addressed in ASN.1 (and also XML because of XMLNS). Many very smart people who came before you and I saw to it that ASN.1 addressed all these issues definitively long ago.

My guess is that his complaint is that MACRO semantics are not well defined and are challenging to parse with conventional compilers. I've always wondered if they were inspired in some part by LISP, since you could in principle translate them fairly readily. ROSE and SNMP are still relatively commonly-used specifications that embed macro definitions, and most of the work I've seen done with them involves actually hard-coding the output (rather than actually parsing the MACROs).

You don't need ASN.1 MACROs for anything in Internet protocols, and you can do without more generally anyways.

The dozens of ASN.1 specs are absolutely hideous and entrenched in obsolete telecom jargon. If the sole goal Protobuf was to avoid having Google engineers be required to refer to the dozens of ASN.1 specs when disagreements or confusions arose, then it would have been 100% worth it for just that reason.

The 90s were rough on text encoding, but it seems pretty settled now.

Part of my curiosity stems from Apple using it as part of their bootable file-format: https://www.theiphonewiki.com/wiki/IMG4_File_Format

But as you say, I have to assume they're using it in a very constrained way.

PKIX actually leverages the weird encoding restriction to our benefit. It defines two kinds of names which things might have on the Internet (you can and should stop trying to name things which are actually on the Internet some other way), DnsNames and IpAddresses. IpAddresses, since they're either 32-bit or 128-bit arbitrary bit values, are just represented as either 32-bit or 128-bit arbitrary bit values. So you cannot express the erroneous IPv4 address 100.200.300.400 as an IpAddress, which means you can't trip up somebody's parser with that nonsense address. DnsNames use a deliberately sub-ASCII encoding from ASN.1 which can express all the legal DNS names (all A-labels and the ASCII dot . are permissible) but can't express lots of other goofy things including most Unicode. So a certificate issuer, even if they're completely incompetent, cannot write a valid DnsName that expresses some garbage IDN as Unicode. Hopefully they read the documentation and find out they need to use A-labels (Punycode) but if not they're prevented from emitting some ambiguous gibberish.

Even in forums where you'd once have expected pushback, "Just use UTF-8" is becoming more widespread. Microsoft for example, once upon a time you'd get at least some token resistance, today they're likely to agree "Just use UTF-8". So ASN.1 ends up no worse off for a half a dozen bad ways to write text you shouldn't use, compared to say XML, HTML, and so on.

Not to say the rest of the spec is notably better. If fully implemented, it requires supporting escape codes in strings to change character sets. I've never seen valid escape codes in real world data, but it probably exists.

As the original article shows, ASN.1 has lots of other challenges and complexity. Trying to write a code generator that supports all the complexity is no trivial task and the only open source one I've seen only generates C code. Protobuf has the advantage of having modern language support (including multiple type safe and memory safe languages).

Well, yes, because ASN.1 predates Unicode.

ASN.1 has always been as-well- or better-defined than its competition. The ITU-T specs for it are a thing of beauty not often equaled outside the ITU-T.

That said, for a long time the ASN.1 specs were non-free, and that hurt a lot. Also, the BER family of encoding rules stunted development of open source tooling for ASN.1.

Spent a bunch of time working with and adding to those libraries.

On this specific point: isn't this also the case for other high-performance serialisers? Google ProtoBufs, Apache Thrift, any protocol through Rust's SerDes...

Nope, nyet, bzzt. Proofs by counter-example:

- OpenLDAP has a printf/scanf-like approach to BER encoding

- Heimdal has an ASN.1 compiler that generates code, yes, but also alternatively generates bytecode that gets interpreted at run-time.

> The language semantics of ASN.1 don't really map to anything well, particularly around default fields and structures that can vary.

You are ill-informed. Proof by counter-example:

- there are ASN.1 encoding rules that produce natural XML (XER) and JSON (JER)

- "default fields" are supported (the relevant keyword is `DEFAULT`, naturally)

- "structures that can vary" -- if you mean unions, it's got that (the relevant keyword is `CHOICE`), and if you mean "extensions", it's got extensibility markers (that effectively are alike a CHOICE of an octet string of unknown stuff, or else the extensions known at module compile time.

ASN.1 today is as broad as it needed to evolve to be because its users needed it.

BER/DER/CER is binary S-expressions.

Interoperability with ASN.1 is very fragile at best.

In my experience, tooling is actually very good for most commonly-used languages, including C/C++, C#, Java, Python, and maybe even Go. And, of course, erlang. The real challenge is, I think, that you cannot find good free tooling, and the barrier to entry for Joe Developer is fairly high (in the thousands of dollars).

ASN.1 versioning in particular is a work of art.

Not so. Protocol buffers is just a TLV encoding, which is bad (see elsewhere in this thread) -- it's just a cut-down ASN.1 and variation on BER, so what.

ASN.1 can "well-version" everything just as well as anything else.

You can write more about these problems and it would have higher visibility.

Using IMPLICIT tagging yields encodings that dumpasn1(1)-like tools can't really give you much insight into.

Using EXPLICIT tagging yields bloat.

The answer is to use non-TLV encodings where possible and to use tools that can refer to the schema ("modules") to decode and pretty-print arbitrary things. dumpasn1(1) is just too simple.