How does ASN.1 encode an object identifier?

Question

I am having trouble understanding the basic concepts of ASN.1.

If a type is an OID, does the corresponding number get actually encoded in the binary data?

For instance in this definition:

id-ad-ocsp         OBJECT IDENTIFIER ::= { id-ad 1 }

Does the corresponding 1.3.6.1.5.5.7.48.1 get encoded in the binary exactly like this?

I am asking this because I am trying to understand a specific value I see in a DER file (a certificate), which is 04020500, and I am not sure how to interpret it.

Answer 1

Yes, the OID is encoded in the binary data. The OID 1.3.6.1.5.5.7.48.1 you mention becomes 2b 06 01 05 05 07 30 01 (the first two numbers are encoded in a single byte, all remaining numbers are encoded in a single bytes as well because they're all smaller than 128).

A nice description of OID encoding is found here.

But the best way to analyze your ASN.1 data is to paste in into an online decoder, e.g. http://lapo.it/asn1js/.

Answer 2

If all your digits are less than or equal to 127 then you are they can be represented with a single octet each. When you have larger numbers which are common, such as 1.2.840.113549.1.1.5 (sha1WithRsaEncryption), then use it uses Variable Length Decoding. These examples focus on decoding, but encoding is just the opposite.

1. First two 'digits' are represented with a single byte

You can decode by reading the first byte into an integer

if ($firstByte >= 80) {
    $nodeFirst = 2;
    $nodeSecond = $firstByte - 80;
}
else {
    $nodeFirst = $firstByte / 40;
    $nodeSecond = $firstByte % 40;
}

$oidText = "$nodeFirst.$nodeSecond"

Produces the values

1.2

2. Subsequent bytes are represented using Variable Length Quantity, also called base 128.

VLQ has two forms,

Short Form - If the octet starts with 0, then it is simply represented using the remaining 7 bits.

Long Form - If the octet starts with a 1 (most significant bit), combine the next 7 bits of that octet plus the 7 bits of each subsequent octet until you come across an octet with a 0 as the most significant bit (this marks the last octet).

The value 840 would be represented with the following two bytes,

10000110
01001000

Combine to 00001101001000 and read as int.

---

Great resource for BER encoding, http://luca.ntop.org/Teaching/Appunti/asn1.html

The first octet has value 40 * value1 + value2. (This is unambiguous, since value1 is limited to values 0, 1, and 2; value2 is limited to the range 0 to 39 when value1 is 0 or 1; and, according to X.208, n is always at least 2.)

The following octets, if any, encode value3, ..., valuen. Each value is encoded base 128, most significant digit first, with as few digits as possible, and the most significant bit of each octet except the last in the value's encoding set to "1." Example: The first octet of the BER encoding of RSA Data Security, Inc.'s object identifier is 40 * 1 + 2 = 42 = 2a16. The encoding of 840 = 6 * 128 + 4816 is 86 48 and the encoding of 113549 = 6 * 1282 + 7716 * 128 + d16 is 86 f7 0d. This leads to the following BER encoding:

06 06 2a 86 48 86 f7 0d

---

EDIT / DISCLAIMER: Fixed the first octet according to the comment below, but have not tested this. I'll leave this code snippet for now as a general reference, but it is not guaranteed to be correct and I do not recommend blindly copy and pasting it :). For >128 VLQ you would normally use bit-shifting to re-align the bits instead of a string of bits.

sub getOid {
    my $bytes = shift;

    #first 2 nodes are 'special';
    use integer;
    my $firstByte = shift @$bytes;
    my $number = unpack "C", $firstByte;

    my $nodeFirst;
    my $nodeSecond;

    if ($number >= 80) {
        $nodeFirst = 2;
        $nodeSecond = $number - 80;
    }
    else {
        $nodeFirst = $number / 40;
        $nodeSecond = $number % 40;
    }


    my @oidDigits = ($nodeFirst, $nodeSecond);

    while (@$bytes) {
        my $num = convertFromVLQ($bytes);
        push @oidDigits, $num;
    }

    return join '.', @oidDigits;
}

sub convertFromVLQ {
    my $bytes = shift;

    my $firstByte = shift @$bytes;
    my $bitString = unpack "B*", $firstByte;

    my $firstBit = substr $bitString, 0, 1;
    my $remainingBits = substr $bitString, 1, 7;

    my $remainingByte = pack "B*", '0' . $remainingBits;
    my $remainingInt = unpack "C", $remainingByte;

    if ($firstBit eq '0') {
        return $remainingInt;
    }
    else {
        my $bitBuilder = $remainingBits;

        my $nextFirstBit = "1";
        while ($nextFirstBit eq "1") {
            my $nextByte = shift @$bytes;
            my $nextBits = unpack "B*", $nextByte;

            $nextFirstBit = substr $nextBits, 0, 1;
            my $nextSevenBits = substr $nextBits, 1, 7;

            $bitBuilder .= $nextSevenBits;
        }

        my $MAX_BITS = 32;
        my $missingBits = $MAX_BITS - (length $bitBuilder);
        my $padding = 0 x $missingBits;
        $bitBuilder = $padding . $bitBuilder;

        my $finalByte = pack "B*", $bitBuilder;
        my $finalNumber = unpack "N", $finalByte;
        return $finalNumber;
    }

}

Answer 3

OID encoding for dummies :) :

• each OID component is encoded to one or more bytes (octets)
• OID encoding is just a concatenation of these OID component encodings
• first two components are encoded in a special way (see below)
• if OID component binary value has less than 7 bits, the encoding is just a single octet, holding the component value (note, most significant bit, leftmost, will always be 0)
• otherwise, if it has 8 and more bits, the value is "spread" into multiple octets - split the binary representation into 7 bit chunks (from right), left-pad the first one with zeroes if needed, and form octets from these septets by adding most significant (left) bit 1, except from the last chunk, which will have bit 0 there.
• first two components (X.Y) are encoded like it is a single component with a value 40*X + Y

This is a rewording of ITU-T recommendation X.690, chapter 8.19

Answer 4

This is a simplistic Python 3 implementation of the of above, resp. a string form of an object identifier into ASN.1 DER or BER form.

def encode_variable_length_quantity(v:int) -> list:
    # Break it up in groups of 7 bits starting from the lowest significant bit
    # For all the other groups of 7 bits than lowest one, set the MSB to 1
    m = 0x00
    output = []
    while v >= 0x80:
        output.insert(0, (v & 0x7f) | m)
        v = v >> 7
        m = 0x80
    output.insert(0, v | m)
    return output

def encode_oid_string(oid_str:str) -> tuple:
    a = [int(x) for x in oid_str.split('.')]
    oid = [a[0]*40 + a[1]] # First two items are coded by a1*40+a2
    # A rest is Variable-length_quantity
    for n in a[2:]:
        oid.extend(encode_variable_length_quantity(n))
    oid.insert(0, len(oid)) # Add a Length
    oid.insert(0, 0x06) # Add a Type (0x06 for Object Identifier)
    return tuple(oid)

if __name__ == '__main__':
    oid = encode_oid_string("1.2.840.10045.3.1.7")
    print(oid)