Ein Jahresrückblick auf die Entwicklung eines ASN.1-Compilers in D

• Ein Entwickler teilt die technischen und mentalen Erfahrungen, die er bei der direkten Implementierung eines ASN.1-Compilers (dasn1) in der Programmiersprache D gemacht hat
• Das Projekt zielt auf die Implementierung von x.509-Zertifikaten und TLS 1.3 ab und unterstützt die komplexe Verarbeitung der DER-Kodierung von ASN.1
• Der Beitrag behandelt ausführlich die strukturelle Sperrigkeit von ASN.1, die Schwierigkeit der Implementierung der Spezifikationen x.680 bis x.683 sowie den Einsatz von Metaprogrammierung in D
• Er erklärt konkret, wie Funktionen von D wie static import, mixin template, typeof() und alias this bei Codegenerierung sowie beim Entwurf von AST und IR hilfreich waren
• Der Beitrag beschreibt ASN.1 als „schmerzhaft, aber äußerst lehrreich“ und schildert offen die praktischen Schwierigkeiten und die Erfüllung beim Bau eines Compilers

---

Projektüberblick und Motivation

• Der Autor entwickelt derzeit ein asynchrones I/O-Framework auf D-Basis namens Juptune und musste für die TLS-Implementierung die ASN.1-DER-Kodierung selbst verarbeiten
  • Um die Struktur von x.509-Zertifikaten in TLS zu parsen, musste er die komplexe Darstellungsweise von Daten in ASN.1 verstehen
• Das Projekt begann als persönliche Herausforderung zum Lernen und aus Spaß und ist inzwischen so weit, dass einige Zertifikate erfolgreich geparst werden können
• ASN.1 ist ein alter Standard aus den 1990er-Jahren, wird aber weiterhin in modernen Systemen wie TLS, SNMP und LDAP verwendet
• Der Autor merkt an: „ASN.1 wird in der Welt breit genutzt, aber die meisten Entwickler wissen nicht einmal, dass es existiert“

Was ist ASN.1?

• ASN.1 (Abstract Syntax Notation One) ist eine Sprache zur Definition und Kodierung von Datenstrukturen, gewissermaßen ein „Vorfahre von Protobuf“
• Der Standard besteht aus Notation (x.680 bis x.683) und Kodierungsregeln (BER, CER, DER, PER, XER, JER usw.)
  • BER: grundlegendes TLV-Format, unterstützt unendliche Länge
  • CER: eingeschränkte Form von BER, verwendet immer unendliche Länge
  • DER: deterministische Teilmenge von BER, wird standardmäßig in der Kryptografie verwendet
  • PER/OER: komprimierte Kodierung auf Bit-Ebene
  • XER/JER: XML- bzw. JSON-basierte Kodierung
• Die Vielzahl der Kodierungsarten macht das Ganze komplex, bietet aber hohe Flexibilität und Erweiterbarkeit

Die Komplexität der ASN.1-Notation

• Der grundlegende ASN.1-Standard ist x.680; die Erweiterungsspezifikationen x.681 bis x.683 sind in einem äußerst schwer zugänglichen akademischen Stil verfasst
• Eine Implementierung ist auch nur mit x.680 möglich, aber die vielen Regeln für semantische Umformungen und Syntaxvarianten machen sie schwierig
• x.681 definiert das Information Object Class System und unterstützt eine eigene Initialisierungssyntax
  • Beispiel: CALLED &name [WHO IS &age YEARS OLD]
• x.682 definiert Table Constraint, x.683 parametrisierte Typen
  • Ein Konzept ähnlich zu Generics in D, bei dem sowohl Typen als auch Werte als Parameter übergeben werden können

Interessante Funktionen von ASN.1

• Constraint-System: Beim Definieren eines Typs lassen sich Wertebereiche oder Größen direkt angeben
  • Beispiel: UInt8 ::= INTEGER (0..255)
  • Unterstützt Operatoren wie SIZE, UNION(|) und INTERSECTION(^)
• Versionsverwaltungssystem: Über OBJECT IDENTIFIER lassen sich Modulversionen klar unterscheiden
  • Beispiel: id-pkix1-implicit(19) vs id-mod-pkix1-implicit-02(59)
  • Dadurch ist eine eindeutige Modulidentifikation ohne Namenskonflikte möglich

Warum D für Codegenerierung geeignet ist

• static import in D vermeidet Namenskonflikte und erlaubt es, ASN.1-Typnamen unverändert beizubehalten
• Die Funktion zur modullokalen Auflösung (.Type1) begrenzt die Symbolsuchen klar
• Mit typeof() können Typen automatisch abgeleitet werden, sodass sie bei der Codegenerierung nicht manuell verwaltet werden müssen
• Die Unterstützung für trailing commas vereinfacht die Codegenerierung
• Dank der Kombination von Compile-Time-Konstanten ist Zeichenkettenzusammenbau auch in @nogc-Funktionen möglich

Implementierungsbeispiele mit D-Funktionen

AST-Knoten auf Basis von Mixin-Templates

• Mithilfe von mixin template in D werden AST-Knoten für ASN.1 definiert
  • Jeder Knotentyp (List, Container, OneOf) wird als Template wiederverwendet
  • Statt komplexer Vererbung wird dies durch Codekopie zur Compile-Zeit vereinfacht

Template-basierte API und Compile-Time-Validierung

• Der Knoten Container enthält mehrere Unterknoten und führt Typvalidierung zur Compile-Zeit durch
  • Sicherer Zugriff ist in der Form node.getNode!Asn1TagDefaultNode möglich
• Der Knoten OneOf speichert einen von mehreren Typen und unterstützt Pattern Matching mit der Funktion match
  • Da Handler für alle Typen definiert werden müssen, ist Compile-Time-Sicherheit gewährleistet

Nutzung des experimentellen Pakets für Speicherverwaltung in D

• Mit std.experimental.allocator wird Objekterzeugung und -freigabe in einer @nogc-Umgebung umgesetzt
  • Über Kombinationen wie Region und StatsCollector wird ein benutzerdefinierter Allocator aufgebaut
  • Das Paket befindet sich allerdings seit zehn Jahren weiterhin im experimentellen Status

Funktion alias this

• Mit alias this wird umgesetzt, dass sich ein Wrapper-Struct wie ein internes Feld verhält
  • Beispiel: knappes Casting in der Form cast(Asn1ValueReferenceIr)item

version(unittest)

• Mit dem Schlüsselwort version(unittest) werden nur für Tests gedachte Funktionen definiert, die nicht in den eigentlichen Build aufgenommen werden

Test-Harness mit Templates + with()

• Gemeinsame Testlogik wird templatisiert, und mit der Anweisung with() lässt sich kompakter Testcode schreiben
  • Aufrufe sind dann als T() statt Harness.T() möglich

Wichtige Schwierigkeiten während der Implementierung

Value Sequence Syntax

• Mehrere Formen von Wertesyntax, die mit {} beginnen, sind je nach Kontext mehrdeutig
  • In Parser-Kommentaren taucht sogar die Formulierung auf: „Das macht keinen Spaß“
• Da Syntaxanalyse und semantische Analyse getrennt wurden, stieg die Schwierigkeit der Verarbeitung zusätzlich

Unklarheiten in der Spezifikation

• Es gibt nicht ausdrücklich dokumentierte Verhaltensweisen, etwa Regeln dafür, wann Tags unter bestimmten Bedingungen als EXPLICIT behandelt werden müssen
• Auch die Methode zur Modulversionsverwaltung ist nicht eindeutig definiert

Constraints müssen dreifach implementiert werden

1. für die Syntaxprüfung
2. für die Prüfung der Wertegültigkeit
3. für die Generierung von Runtime-Code

• Vor allem bei UNION und INTERSECTION ist auch die Zusammenstellung von Fehlermeldungen komplex

Die Illusion unveränderlicher IR-Knoten

• Nach der Umwandlung von AST zu IR schien zunächst keine weitere Änderung nötig zu sein,
  doch bei semantischen Transformationen wie AUTOMATIC TAGS mussten Daten dennoch verändert werden

Die allumfassende Komplexität von ASN.1

• x.509 ist relativ einfach, weil es nur ältere Syntax verwendet, aber moderne Spezifikationen erfordern die Implementierung von x.681 bis x.683
  • Deshalb wird ASN.1 außerhalb akademischer und kommerzieller Spezialbereiche kaum genutzt

Das Problem mit ANY DEFINED BY

• ANY DEFINED BY ist eine Struktur, bei der sich der Typ abhängig vom Wert eines anderen Felds ändert
  • dasn1 implementiert dies nicht direkt, sondern ersetzt es durch das benutzerdefinierte Intrinsic Dasn1-Any
  • Bei der tatsächlichen Dekodierung ist daher manuelle Verarbeitung nötig

Informationsüberlastung

• Durch das gleichzeitige Bearbeiten mehrerer Projekte wie ASN.1, x.68x, x.690 und Juptune war es schwierig, den Kontext der Codebasis im Blick zu behalten

Die Realität beim Bau eines Compilers

• Tausende Knoten-Visitoren, repetitiver Code und Implementierungen mit nur feinen Unterschieden bedeuten langweilige und harte Arbeit
• Gleichzeitig bringt jeder Schritt große Erfolgserlebnisse und Lernfortschritte
• Rückblickend sagt der Autor: „Niemand wird es benutzen, aber ich habe echte Compiler-Erfahrung gewonnen“
• Zum Schluss beendet er den Beitrag mit dem Scherz: „Lasst lieber die Finger von ASN.1, es verändert euer Leben“

Fazit

• Obwohl dasn1 auch nach einem Jahr Arbeit noch unvollständig ist,
  war das Projekt ein Anlass, das Potenzial der Programmiersprache D und die Komplexität von ASN.1 tief zu verstehen
• Der Beitrag endet humorvoll mit dem Traum, eines Tages „ASN.1-Compiler + TLS-1.3-Implementierungserfahrung“ in den Lebenslauf schreiben zu können, und blickt dabei auf das Wachstum des Entwicklers und die Realität der Branche zurück

[GN⁺]

Hacker-News-Kommentare

• Kurz gesagt wollte ich über ASN.1, die Sprache D und Compiler im Allgemeinen sprechen.
  Ich habe aber kein konsistentes Format gefunden und deshalb die zusammenhängenden Gedanken in einem Blogbeitrag gebündelt.
  Er ist nicht besonders ausgereift, aber das Thema lässt sich schwer kurz abhandeln, also bitte ich um Nachsicht.

  • Das Schnittmengenbeispiel (intersection example) scheint nicht wie beabsichtigt zu funktionieren.
    Mathematisch betrachtet gilt {0} ∪ ({2} ∩ {4,5,6,7,8}) = {0}, also ist am Ende nur ein einzelner Wert zulässig.
  • Sobald man D erwähnt, ruft man gewissermaßen Walter Bright herbei.
    Ich persönlich mag D wirklich sehr, aber realistisch gesehen werden Go und Rust deutlich häufiger verwendet.
  • Ich habe auch schon mit ASN.1-Daten gearbeitet, besonders im Zusammenhang mit Zertifikaten, und das war schmerzhaft.
    Mit dem Leid des Autors fühle ich daher sehr mit.
  • Ich habe den Beitrag mit großem Vergnügen gelesen.
    Ich liebe D, habe es aber seit Langem nicht mehr benutzt.
    Da ich früher selbst Parser und Protokoll-Implementierungen geschrieben habe, fand ich ihn umso interessanter.
  • Ein Blog ist am Ende der eigene Raum, also hoffentlich macht der Autor auf seine Weise weiter.

• „OMG ASN.1“ – was für ein herrliches Thema.
  Ich erinnere mich noch an die Zeit, als das Internet wuchs und die IETF Protokolle weiterentwickelte.
  Unternehmen interessierten sich damals nicht für das Internet; die Entwicklung wurde von der Wissenschaft und der IETF getragen.
  Als Unternehmen dann merkten, dass damit Geld zu verdienen war, begannen die Protocol Wars.
  ASN.1 ist ein Produkt dieses Krieges und ein Beispiel für den Zusammenprall von Unternehmenskultur und akademischer Kultur.
  Unternehmen kann man mit einer „Rezeptkultur“, die Wissenschaft mit einer „Funktionskultur“ vergleichen.
  Dieser Unterschied im Denken sagt auch etwas über die heutige AI-Entwicklungskultur aus.

  • Ich war einmal überrascht, als ich beim Film Father of the Bride plötzlich von X.25-Netzwerken hörte.
    Der Gedanke, dass wir statt des Internets vielleicht bei einem Adresssystem wie „CN=wikipedia, OU=org, C=US“ gelandet wären, ist ziemlich verstörend.
  • Ich dachte sofort, „OMG ASN.1“ sollte der Name meiner nächsten Band werden.
  • Ein Teil der Darstellung stimmt, aber die Hauptakteure als „Unternehmen“ zu bezeichnen, ist etwas ungenau.
    Tatsächlich standen ITU und ISO im Zentrum.
    Später, Ende der 1990er, gab es noch einen weiteren „Protokollkrieg“, und diesmal verlor die IETF.
  • Dieser Krieg war auch Teil der frühen Kommerzialisierung des Internets (en-shittification).
    ISO strebte nach Perfektion und wurde dadurch langsam, während die IETF mit einer Haltung von „wir reparieren es später“ schnell voranging.
    Das führte wiederum dazu, dass sich Protokolle verfestigten.
    Außerdem waren ASN.1-Implementierungen für C in den 1990ern oft miserabel.
  • Entscheidend ist, dass die Unternehmensperspektive letztlich eine Mainframe-Perspektive war.

• Es gibt ein türkisches Sprichwort: „Das ist nichts, was ein Mensch benutzen sollte!“
  Ich würde diesen Satz gern zum Motto einer Designphilosophie machen.
  Und wie in Game of Thrones mit dem Satz „Wer das Urteil fällt, soll auch selbst das Schwert führen“
  gilt auch hier: Wer die Spezifikation schreibt, sollte den Parser selbst implementieren.
  Wenn zu einer Spezifikation immer auch ein funktionierender Parser und Tests eingereicht werden müssten, bevor sie genehmigt wird, wäre die Qualität vermutlich viel besser.

• Ich mag die Sprache D wirklich sehr.
  Ich implementiere gerade nur mit Raylib einen Texteditor im Vim-Stil.
  Die Stärken von D sind aus meiner Sicht:

  • Man kann überall Unit-Tests schreiben.
  • Mit version(unittest)-Blöcken lässt sich testbezogener Code leicht verwalten.
  • Sprachfeatures wie enum, union, assert und Vertragprogrammierung sind hervorragend.
    Wenn ich in der Dokumentation nachsah oder ChatGPT fragte, fand ich immer eine elegante Lösung.
  • D ist für mich eine bitter-süße Sprache.
    Vom Sprachdesign her ist sie fast perfekt, aber mit Werkzeugen und einem Ökosystem auf Rust- oder Go-Niveau wäre sie viel erfolgreicher geworden.
  • Die Features von D sind gut, aber die Sprache wirkt zunehmend noisy.
    In der Standardbibliothek Phobos gibt es zu viele kleine Unannehmlichkeiten, sodass ich sie schließlich aufgegeben habe.
    An Phobos V3 wird zwar gearbeitet, aber wegen des kleinen Teams bin ich zugleich hoffnungsvoll und besorgt.

• „Habe ich je behauptet, ASN.1 sei komplex?“
  Sowohl das Schema als auch das Datenformat sind komplex, aber vieles davon ist Komplexität, die man ignorieren kann.
  Ich benutze die ASN.1-Schemanotation nicht, sondern habe direkt eine DER-Implementierung in C geschrieben.
  DER ist meiner Meinung nach die einzige Standardkodierung, die wirklich brauchbar ist.
  Ich habe außerdem eigene Kodierungsformate wie DSER, SDSER und TER entwickelt.
  Konstrukte wie ANY DEFINED BY nutze ich weiterhin sinnvoll,
  und für effizientere Kodierung habe ich sogar eine nicht standardisierte Funktion namens OBJECT IDENTIFIER RELATIVE TO ergänzt.

• Ich habe ebenfalls einmal einen ASN.1-Compiler gebaut.
  Ich habe nur Teile von X.681 bis X.683 implementiert, konnte damit aber ein vollständiges Zertifikat mit einem einzigen Codec-Aufruf rekursiv dekodieren.
  ASN.1 ist nicht bloß eine einfache Grammatik, sondern ein mächtiges Typsystem.
  Es wird unterschätzt, ist aber wirklich großartige Technik.

• Ich habe früher einmal einen ASN.1-Compiler für Swift gebaut.
  Im Projekt ASN1Codable habe ich Heimdals libasn1 verwendet,
  um ASN.1 in einen JSON-AST umzuwandeln und so das Parsing zu vereinfachen.

  • Im README von libasn1 spürt man einen subtilen Widerwillen gegenüber ASN.1.
    „Lasst es uns in JSON umwandeln“ klingt letztlich wie der Ausruf eines verletzten Entwicklers 😄

• Seltsamerweise fühlt sich die Arbeit mit ASN.1 angenehm an.
  Irgendwann möchte ich selbst einen ASN.1-Compiler für Rust schreiben.
  Die aktuellen Rust-Implementierungen basieren meist auf derive-Makros oder manueller Verkettung, was ich schade finde.

• Im Allgemeinen lassen sich bei der Implementierung eines Standards 80 % der Funktionen in 20 % der Zeit fertigstellen,
  aber die restlichen 20 % von ASN.1 könnten ein ganzes Leben dauern.

• Ich habe früher den ASN.1-Parser in der Netscape-Codebasis erweitert, um PKCS#12 zu unterstützen.
  Danach kannte ich den RSA-Standard und die ASN.1-Definitionen tiefer, als mir lieb war,
  aber der Ausdauer und dem leichten Masochismus des Blogautors zolle ich Respekt.

  • Mit so einer Erfahrung gibt es bestimmt jede Menge Anekdoten aus der Entwicklung wie aus einem Krieg.