Die Bibliothek libXfont kümmert sich um die Darstellung der verschiedenen Schriftarten unter X11 und um das Verarbeiten der Index-Dateien (“fonts.dir”, “fonts.alias”, “fonts.scale”). Sie ist integraler Bestandteil des X-Servers und des X-Font-Servers “xfs”. Clients selbst verwenden die Bibliothek gewöhnlich nicht, sondern bedienen sich der Bibliothek libXft zum Zugriff auf Schriftarten. Eine Schwachstelle in den Routinen zum Verarbeiten LZW-komprimierten Dateien in libXfont hat zur Folge, dass ein entfernter Angreifer Befehle mit den Rechten des X-Servers ausführen kann.
LZW-(Lempel-Ziv-Welch)-Kompression ist sehr verbreitet und kommt bei zahlreichen Programmen zum Einsatz. Auch die Bibliothek libXfont macht von ihr Gebrauch, um Speicher für die verschiedenen Schriften zu sparen. Das LZW-Komprimierungsverfahren basiert auf einem Wörterbuch, in dem die häufigsten Zeichenketten des zu komprimierenden Strings abgelegt werden.
Das Verfahren ist dabei so konstruiert, dass das Wörterbuch nicht explizit gespeichert werden muss, sondern beim Dekodieren direkt aus der komprimierten Datei rekonstruiert werden kann. Das Wörterbuch hat zudem die Eigenschaft, dass jede darin befindlich Zeichenkette der Länge n mit einem Teilmuster der Länge n-1 beginnt, welches sich schon in dem Wörterbuch befindet. Somit lässt sich das gesamte Wörterbuch effizient in einer Präfix-Suffix-Aufspaltung kodieren. Dabei enthält das Suffix das letzte Zeichen des zu speichernden Musters und das Präfix den Code für die n-1 ersten Zeichen.
Am besten lässt sich das Verfahren anhand eines einfachen Beispiels erklären.
LZW-Encoder
Ein LZW-Encoder durchläuft die folgenden Schritte, um eine bestimmte Eingabe zu kodieren:
- Initialisiere Wörterbuch mit allen benötigten Zeichen (Strings der Länge 1)
- Finde den längsten String S im Wörterbuch, der mit der aktuellen Eingabe übereinstimmt
- Schreibe den Wörterbuch-Code C von S in die Ausgabe und entferne S von der Eingabe
- Füge S+nächstes Zeichen der Eingabe unter nächstem freien Code C+1 in das Wörterbuch ein
- wiederhole 2, bis die Eingabe leer ist
Das folgende Beispiel erläutert die Komprimierung, wobei die Daten nur aus den Zeichen A, B, C bestehen und der zu kodierende String so aussieht:
ABCABCAAABC
Da nur drei Buchstaben vorkommen, wird das Wörterbuch in Schritt 1 wie folgt initialisiert:
Wörterbuch | Präfix | Suffix 1:A 0 A 2:B 0 B 3:C 0 C
Da es für Einzelzeichen noch kein Präfix gibt wird dieses auf 0 gesetzt, und das Suffix nimmt den Zeichenwert an. Mit dieser Kodierung würde der Eingabestring unkomprimiert also wie folgt aussehen:
1|2|3|1|2|3|1|1|1|2|3
Normalerweise wird das Wörterbuch mit den ersten 256 Zeichen (8 Bit) initialisiert, und nicht nur mit drei wie in diesem einfachen Beispiel. Nachdem Schritt 1 erledigt ist, ist der nächste freie Wörterbuch-Code 4, da die ersten drei Einträge nun belegt sind.
Im Folgenden ist dargestellt, wie der Encoder den Eingabestring nun zeichenweise durchläuft und dabei sowohl die Ausgabe als auch das Wörterbuch generiert:
Eingabe | Ausgabe | Wörterbuch | Präfix | Suffix A 1 4: AB 1 B B 2 5: BC 2 C C 3 6: CA 3 A AB 4 7: ABC 4 C CA 6 8: CAA 6 A A 1 9: AA 1 A ABC 7
Die am Ende so entstandene komprimierte Ausgabe ist also:
1|2|3|4|6|1|7
Das Beispiel zeigt, dass die Eingabe immer so weit eingelesen wird, bis der entsprechende String S nicht mehr im bis dahin generierten Wörterbuch zu finden ist.
Da anfangs nur A, B, C im Wörterbuch stehen, werden die ersten drei Zeichen gelesen und ihr Code direkt ausgegeben. Dabei wird immer parallel das Wörterbuch
mit dem aktuellen Zeichen und dem Folgezeichen aufgebaut (Schritt 4), so dass beim Einlesen des zweiten A auch das B noch gelesen werden kann, weil für AB
im Wörterbuch zu diesem Zeitpunkt schon der Code 4 angelegt wurde. Genauso wird die letzte ABC-Zeichenkette komplett eingelesen und in der Ausgabe durch den
Wörterbuch-Code 7 repräsentiert.
LZW-Decoder
Der Trick bei dem Dekomprimieren ist es, das Wörterbuch sukzessive während der Dekompression wieder aufzubauen. Ohne diesen Trick müsste der Algorithmus das gesamte Wörterbuch jedesmal in die komprimierte Datei schreiben, was Speicherplatz kostet. Beim Dekodieren werden die Eingabecodes eingelesen und der entsprechende String des soweit initialisierten Wörterbuchs ausgegeben. Im gleichen Schritt wird auch ein neuer Eintrag für das Wörterbuch generiert, so dass der Aufbau des Wörterbuchs und das Dekodieren der Eingabedaten parallel erfolgen.
Zunächst wird wieder das Wörterbuch so initialisiert wie es der Encoder auch machte:
Wörterbuch | Präfix | Suffix 1:A 0 A 2:B 0 B 3:C 0 C
Nun muss der komprimierte Datenstrom zeichenweise abgelaufen werden:
Eingabe | Ausgabe | Wörterbuch | Präfix | Suffix 1 A 2 B 4: AB 1 B 3 C 5: BC 2 C 4 AB 6: CA 3 A 6 CA 7: ABC 4 C 1 A 8: CAA 6 A 7 ABC 9: AA 1 A
Der Decoder rekonstruiert somit den String ABCABCAABC, was genau der Eingabe entspricht. Damit ist der ursprüngliche String rekonstruiert, und parallel wurde auch das korrekte Wörterbuch wieder aufgebaut.
Beim Aufbau des Wörterbuchs geht der Decoder wie folgt vor: Beim Einlesen des ersten Codes 1 ist bekannt, dass der Encoder diesen Code ausgab, weil er der maximale String im Wörterbuch war (Schritte 2 und 3 des Encoders). Gleichzeitig hat der Encoder zu diesem Zeitpunkt einen neuen Eintrag im Wörterbuch angelegt, der aus dem bisher eingelesenen String plus dem nächsten Zeichen besteht. Deshalb kann der Decoder schließen, dass der nächste hinzuzufügende Wörterbuch-Eintrag “A+das nächste Zeichen” sein muss. Dieses nächste Zeichen erfährt er im nächsten Leseschritt: Code 2, also B. Somit schreibt er für Code 4 den String AB in das Wörterbuch.
Die Eingabeklasse “KwKwK”
Im obigen Beispiel war der nächste eingelesene Code der komprimierten Datei immer schon im Wörterbuch vorhanden. Doch es gibt eine bestimmte Klasse von Eingabedaten, die eine Situation erzeugen, bei der der nächste einzulesende Code noch nicht im Wörterbuch steht. Alle Eingabestrings der Klasse KwKwK, bei denen K ein einzelnes Zeichen und w ein Wort ist, erzeugen genau diese Situation. Tatsächlich lässt sich zeigen, dass nur diese Datenklasse diese Situation erzeugt. In diesem Fall muss der Decoder sich ein wenig mehr anstrengen, um die Daten und das Wörterbuch korrekt zu rekonstruieren, wobei er folgender Logik folgt:
- Der Decoder sieht Code C1 und dann C2, wobei er C1 kennt, C2 aber noch nicht
- C1 kann S1 zugeordnet werden, und C2 ist ein unbekannter String S2
- C2 muss aber direkt nach C1 hinzugefügt worden sein
- Das heißt, der Encoder hat C2 zu dem Wörterbuch hinzugefügt für S2=S1+x, wobei x ein dem Decoder unbekannte Zeichen ist
- Das unbekannte Zeichen muss aber das erste Zeichen von S2 sein, da dieses ja jetzt in Ausgabe steht
- Da aber S2=S1+x, ist das erste Zeichen von S2 auch das erste Zeichen von S1
- Demnach muss also x=S1[0] sein
- Also kodiert C2 den String S2=S1+S1[0]
- Der Decoder fügt somit C2:S2 in sein Wörterbuch ein und schreibt S2 in die Ausgabe.
Der Decoder greift zu diesem Verfahren, sobald er der KwKwK-Situation begegnet, die sich darin äußert, dass der zu dekodierende Code noch unbekannt ist. Dann durchläuft er die Schritte 1 bis 8 und fährt fort. Da der unbekannte Code C2 maximal um eins größer sein kann als der letzte angelegte Wörterbuch-Code, tritt diese Situation nur dann auf, wenn C2=C_max+1, wobei C_max der größte derzeit im Wörterbuch befindliche Code ist.
Auch die libXfont-Bibliothek muss sich im Falle LZW-kodierter Daten um diese Situation kümmern. Das beschriebene LZW-Dekomprimierungsverfahren ist in der libXfont-Bibliothek in der Datei “decompress.c” implementiert. Zentraler Bestandteil der Verarbeitung LZW-komprimierte Dateien ist die Struktur “CompressedFile”:
typedef struct _compressedFILE { BufFilePtr file; char_type *stackp; code_int oldcode; char_type finchar; int block_compress; int maxbits; code_int maxcode, maxmaxcode; code_int free_ent; int clear_flg; int n_bits; /* bit buffer */ int offset, size; char_type buf[BITS]; char_type de_stack[STACK_SIZE]; char_type *tab_suffix; unsigned short *tab_prefix;
} CompressedFile;
“tab_prefix” und “tab_suffix” werden genauso wie “oldcode” und “finchar” für den Aufbau des Wörterbuchs verwendet, wobei “tab_prefix” und “tab_suffix” wie oben beschrieben die Präfix- und Suffix-Anteile des Wörterbuchs speichern. Die ersten 256 Einträge des Wörterbuchs werden in der Funktion “BufFilePushCompressed()” mit den ersten 256-Zeichen gesetzt:
for ( code = 255; code >= 0; code-- ) { file->tab_prefix[code] = 0; file->tab_suffix[code] = (char_type) code;
}
Dabei ist die Variable “file” ein Zeiger auf eine zuvor allozierte “CompressedFile”-Struktur. Da dies die ersten Einträge des Wörterbuchs sind, wird nur das Suffix gesetzt, genauso wie im einfachen ABC-Beispiel oben. Das eigentliche Dekodieren der Datei und der gleichzeitige Aufbau des Wörterbuchs finden in der Funktion “BufCompressedFill()” statt. Und dort findet sich auch eine Abfrage zum Behandeln des etwas komplizierteren KwKwK-Falles:
incode = code;
/* * Special case for KwKwK string. */
if ( code >= file->free_ent ) { *stackp++ = finchar; code = oldcode;
}
...
/* * Remember previous code. */
oldcode = incode;
Der Eintrag “file->free_ent” verweist immer auf den nächsten freien Code im Wörterbuch, das heißt der letzte Eintrag befindet sich zu diesem Zeitpunkt an der Stelle file->free_ent-1. Den letzten Code speichert “oldcode”, wobei “incode” den aktuellen Code zwischenspeichert. Das Problem an diesem Programmfragment ist, dass der Fall “code > file->free_ent” nicht abgefangen wird. Wie oben dargestellt kann der Code maximal um eins größer sein als der letzte Wörterbucheintrag. “code > file->free_ent” signalisiert also, dass etwas schiefgelaufen ist, und die Dekompression besser abgebrochen werden sollte.
Sicherheitsrisiken
Ohne einen Abbruch entstehen zwei mögliche Sicherheitsrisiken aufgrund falscher Code-Werte. Zunächst kann ein Angreifer eine Font-Datei mit einem LZW-Stream generieren, der dazu führt, dass die libXfont-Bibliothek in eine Endlosschleife gerät und damit den X-Server einfriert:
/* * Generate output characters in reverse order */
while ( code >= 256 )
{ *stackp++ = file->tab_suffix[code]; code = file->tab_prefix[code];
}
Je nachdem, wie der Angreifer die Codes im präparierten LZW-Stream anordnet, ist es hier möglich, die Variable “code” immer oberhalb von 256 zu halten, sodass die Schleife nie terminiert.
Von dieser Schleife geht aber noch eine zweite Gefahr aus, da der Zeiger “stackp” via Zeiger-Arithmetik konstant um den Suffix-Anteil des Wörterbucheintrags erweitert wird. Dieser Zeiger wird anfangs jedoch auf “file->stackp = file->de_stack” gesetzt, und “de_stack” ist mit fixer Größe als “char_type de_stack[STACK_SIZE]” in der Struktur “CompressedFile” definiert. Dadurch entsteht zusätzlich ein Heap Buffer Overflow, der von einem Angreifer ausgenutzt werden kann, um Befehle mit den Rechten des X-Servers auszuführen. Der X-Server läuft typischerweise mit recht hoher Berechtigung, sodass hier ein ernstes Problem entsteht.
Es gibt mehrere Möglichkeiten, diese Schwachstelle im Programmcode zu korrigieren. Beispielsweise könnte das Dekodieren abgebrochen werden, falls “code > file->free_ent” eintritt.
Ein anderer Patch bestünde darin, in der “while()”-Schleife die Variable “stackp” zu überwachen,und abzubrechen falls, diese über die “STACK_SIZE”-Grenze von “de_stack” anwächst. Diese zweite Lösung wurde vor einer Woche in den libXfont-Quelltext eingefügt:
while ( code >= 256 )
{ if (stackp - de_stack >= STACK_SIZE - 1) return BUFFILEEOF; *stackp++ = file->tab_suffix[code]; code = file->tab_prefix[code];
}
Mit dieser Korrektur sind die angesprochenen Attacken nicht mehr möglich, denn sowohl der Overflow als auch die Endlosschleife werden durch die “If()”-Bedingung abgefangen.
Version 1.4.4 von libXfont enthält diesen Patch und ist somit nicht mehr anfällig für diese Sicherheitslücke. Ältere Versionen sind von diesem Problem allerdings betroffen.
