7
$\begingroup$

I saw that an RSA key, created by OpenSSL, contains the following HEX string:

2a 86 48 86 f7 0d 01 01 01

that HEX string gets interpreted as Object ID:

1.2.840.113549.1.1.1

It is obvious 01 01 01 is 1.1.1, but how does 2a 86 48 86 f7 0d get interpreted (parsed) as 1.2.840.113549?

$\endgroup$
  • $\begingroup$ Please do not reject the question as a dump of ciphertext with known plaintext asking for the decryption algorithm; it is actually about a convention commonly used in real-world cryptography, and elsewhere. $\endgroup$ – fgrieu Sep 12 '15 at 9:57
14
$\begingroup$

The question's bytestring 2a 86 48 86 f7 0d 01 01 01 is the Value field of an ASN.1 BER/DER TLV with type 6, which is the Object IDentifier for an RSA key (the Type and Length just before are coded as 06 09, and won't be further discussed).

In order to parse that Value bytestring, we first separate the bytes into blocks ending after each byte which high-order bit is clear (in other words: blocks end after a byte in range 00h to 7fh). Then we paste together the low-order 7 bits of the bytes (in big-endian/reading order); so that
_____2a|_____86_____48|_____86_____f7_____0d|_____01|_____01|_____01   becomes
0101010|00001101001000|000011011101110001101|0000001|0000001|0000001

We then interpret each block of bits as coding a non-negative integer in big-endian binary. The question's example now comes out as the six integers: 42 840 113549 1 1 1

There's a special case for the first integer: it was built as $z=40x+y$, with $x$ encoding the top-level authority that assigned $y$. Integer $x$ in always one of $0$ (for ccitt), $1$ (for iso) or $2$ (for joint-iso-ccitt), and if $x<2$ then $y<40$.
We thus replace the first integer $z$ by $x=\min(\lfloor z/40\rfloor,2)$ and $y=z-40x$.
Note: when $x=2$, $y$ can be arbitrarily large. Assigned $y$ include 40 (exercising the $\min$ rule), 48 (requiring coding $z$ over more than one byte), and 999 (with $y\ge2^8$), which might not be correctly handled by some existing software.

The question's example now comes out as the seven integers: 1 2 840 113549 1 1 1

One practice is to format these integers in decimal without leading 0 digit (with the exception of the integer zero represented as 0), separated by dots, as in
1.2.840.113549.1.1.1
or sometime enclosed in braces with separating spaces, as in
{1 2 840 113549 1 1 1}
or sometime (as shown by the OID Repository)
{iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)}
or in OID-IRI notation
/ISO/Member-Body/840/113549/1/1/1

The careful reader will notice that per the above conventions, different bytestrings can decode to the same OID; however the rule in crypto (for OIDs at least) is to stick to the unique DER encoding, such that (in the bitstring with the Value field of an OID) a byte 80h can only follow a byte which high-order bit is set (otherwise the 80h would encode leading zeroes of an integer, and must be suppressed).


Daniel Marschall's Study about OID encoding and size limitations was most useful in making the above (hopefully) correct; it also confirmed my intuition that OID decoding practices are chaotic. Microsoft has an explanation on OID format, which I found initially useful even though it turns out to be dangerously lacking.

The normative references for OID encoding are somewhere in IUT-T X.680 through X.695 Information Technology - Abstract Syntax Notation One (ASN.1) & ASN.1 encoding rules. They are also in its free ancestors IUT-T X.209:1988 Specification of Basic Encoding Rules for Abstract Syntax Notation One (ASN.1) in section 22 Encoding of an object identifier value, with definitions in IUT-T X.208:1988 Specification of Abstract Syntax Notation One (ASN.1) in section 28 Notation for the object identifier type and annexes B, C and D.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.