ASN - AS iN Hell

DISCLAIMER: This is not a jab on all the developers out there that are building ASN protocols. I empathize with you. It’s really more about how we’ve taken complexity of software for granted while we really ought to be working towards simplifying things.

I’m mostly writing this as I really need a place to jot down what little I know about ASN. Every time I revisit ASN time to time, I find myself pouring over 10,000 documents trying to remember the subtleties of BER, DER, PER encodings. First of all, ASN is nuts. Second of all it’s seriously retarded b0rken. Did I already mention, it’s nuts? I love the way Richard Feynman provides the absolutely simplest explanation for the most complex problem in hand. When you want talk about soap bubbles, talk about bubbles, not about an enchanting, hollow, spherical translucent thing that has a certain surface tension with rainbows on top for good measure. There’s another simple acronym for this: K.I.S.S.

Background

ASN is fundamentally a data modeling language with object and type constraints. Very similar in spirit to XML Schema, only many many orders of magnitude more complex. The language in which ASN is expressed is defined in a bunch of ITU specs that goes into all the gory details of the language. ASN defines simple types (called primitives) like Integer, Bit String, Octet String, IPAddress, etc. It also allows us to build more complex objects using Set, Sequence (called constructed types) and the likes. Unlike SOAP/XML, the ASN definition does not include function call arguments/return-value definitions. It mostly concerns itself with the PDU/Message formats. Also it doesn’t really specify the transport binding. Here’s an example from the LDAP rfc (rfc-2251):

BindRequest ::= [APPLICATION 0] SEQUENCE {
    version              INTEGER (1 .. 127),
    name                 LDAPDN,
    authentication       AuthenticationChoice
}

BindRequest is defined as SEQUENCE of a version, name and authentication where the latter two are complex types defined elsewhere.

So far so good. I think I’m starting to get this now.

50 ways to encode your lover

The complexity really starts kicking in when you start to serialize the data model into a bunch of bits on the wire. ASN encodes objects using TLV (type, length, value). The value of course, can be another set of TLV’s and ad infinitum. Each of the T’s, L’s and V’s have like a million ways of encoding depending on BER, DER and PER, not to mention implicit, explicit and automatic tags, phase of the moon and quantum fluctuations. First the T’s.

Type encoding

ASN types are broken down like this:

 76 5 43210
+--+-+-----+
|  | |     |
+--+-+-----+

The top 2-bits of the type are called the class and are defined as follows:

• Universal
• Application
• Context specific
• Private

The next bit indicates if the type as a whole is a primitive type or a collection type (SET, SEQUENCE, etc). Finally the bottom bits indicate the tag, which is the actual type of the type (heh?).

Not so fast: if the bottom 5-bits are all 1, then this is a multi-byte tag encoding, a.k.a. high-tag-number-form. What this means is you have to do base 128 arithmetic and a bunch of bit-shifting to figure when to stop parsing the T.

Length encoding

Wait, I have an idea. Let’s not just having a bunch of bytes to indicate the length. People will actually figure this thing out. Too scary. So, we are going to come up with all sorts of crazy ways to encode the lengths. Ultimately the length (bytes) indicates how big the V really is. Remember the V could be a complex TLV itself.

Lengths < 127

This I understand. It’s simple enough, high bit is set to zero and we have 7 bits that tells us how big the V is.

Lengths >= 127

Okay, this sort of makes sense too. In this case, the high bit is set and the lower 7-bits indicate how many bytes that follow describe the length. Yeah? In other words:

num_bytes_of_length = byte & 0×7f

and then you read that many bytes and do a bunch of bit shifts to get back the length.

I have no idea how long V is

This is also called indefinite encoding. So you essentially enclose V with 0×80 and [0×00, 0×00]. In other words, once you read 0×80, the next byte is the start of V. You keep reading until you hit two null’s. So what happens if the V itself has [0×00, 0×00]? I have no idea. Haven’t seen this one before.

Value encoding

Most of the value types are fairly straight-forward except OID (Object ID). Yeah, that’s the 3.1.3.37 you’ve seen with SNMP. First, OID encoding has something called prefix compression. It encodes the first two object id components into a single byte. Each of the other components are encoded using techniques described above; Base 128 arithmetic with bit shifts to recover each component. Don’t forget to handle 2’s complement for negative OID components. *sigh*.

Implicit and Explicit encodings

I’m starting to rofl now, ‘cos like I said, I thought I had figured this out after multiple encounters with ASN. Everything that we’ve talked about is about explicit encoding where things are [ahem] normal. Turns out this whole T encoding thing is still too easy for people. What if, no not hypothetically, we could make the T an index of the element relative to it’s parent in the ASN specification? This essentially means there’s no Integer, String, Sequence in the byte stream. There are only indexes. Let me see if I understand this:

    sequence {
        integer a
        boolean b
        string c
    }

With explicit encoding we will be serializing this to:

T_sequence L_sequence ( T_a L_a (a), T_b L_b (b) T_c L_c (c) )

With implicit encoding, we serialize this as follows:

Index_sequence L_sequence ( Index_a L_a (a), Index_b L_b (b) Index_c L_c (c) )

What this means is that sender and the recipient have to have the grammar in place to really make sense of these indices. Because the type of the object being transmitted is no longer part of the bits.

PER encoding

PER stands for Packed Encoding rules which really means, I’m still on dial-up, co’s I can’t afford broadband. This is when things get really interesting. So if you have an integer in the range of [x, y], then you encode this with least amount of bits that (value - x) takes. For example, an integer field in the ASN definition with a constraint of [1024, 1028] gets encoded as 3 bits (1028 - 1024 = 4 => 3 bits). I give up.

All of this brings me to the last issue:

Intrusion Detection

Most IPS’s used to do ASN parsing recursively, which essentially means you can create ASN bombs (recursive TLV’s) that cause a stack overflow in the IPS. With that out of the way, explicit encoding allows the IPS to narrow down the signature to match a particular element (using the T) to eliminate false positives. What if the encoding is implicit? This means the signature-based IPS has no way of knowing what to look for, unless it carries with it the full parser for the particular ASN-based protocol. Unlikely, since it’s going to drop the throughput from Gbits/s to Mbits/s.

You should know by now I’m nuts about ASN.