Adler32

Adler-32 ist ein einfacher, von Mark Adler entwickelter Prüfsummenalgorithmus. Er wird unter anderem von der zlib-Bibliothek benutzt, um (zufällige Übertragungs-)Fehler im komprimierten Datenstrom zu erkennen. In RFC 1950 wird der Algorithmus genau beschrieben.

Der Adler-32-Algorithmus ist einfacher und lässt sich schneller berechnen als die bekannte Zyklische Redundanzprüfung (cyclic redundancy check), bietet aber auch weniger Sicherheit beim Erkennen von zufälligen Bitfehlern.

Algorithmus

Der Algorithmus berechnet zwei Summen s1 und s2. s1 ist die Summe aller Datenbytes und wird am Anfang des Algorithmus auf 1 initialisiert, s2 ist die Summe aller s1-Werte. Beide Summen werden modulo 65.521 (die größte Primzahl < 2¹⁶) berechnet.

Obwohl der Algorithmus sehr einfach ist, sei hier eine Beispielimplementierung in C angegeben:

  /* Beispielcode zur Berechnung der Adler-32-Prüfsumme */
 
  uint32_t adler32(const void *buf, size_t buflength) {
 
     const uint8_t *buffer = (const uint8_t*)buf;
 
     uint32_t s1 = 1;
     uint32_t s2 = 0;
 
     for (size_t n = 0; n < buflength; n++) {
        s1 = (s1 + buffer[n]) % 65521;
        s2 = (s2 + s1) % 65521;
     }
 
     return (s2 << 16) | s1;
  }

Anmerkung Beispielimplementierung

Diese Beispielimplementierung ist nicht auf Geschwindigkeit, sondern auf Klarheit und Lesbarkeit hin optimiert. So muss etwa die recht langsame Modulo-Operation nicht bei jedem Datenbyte durchgeführt werden, sondern nur, wenn ein Überlauf der Variablen s1 oder s2 droht. Bei einer Bitbreite von 32 Bit (was bei der Verwendung von int nicht gewährleistet ist, daher oben uint32_t gemäß C99) genügt eine Durchführung der Modulo-Operation alle 5552 Bytes. Bei 64 Bit (uint64_t) breiten s1 und s2 würde sogar die Durchführung der Modulo-Operation alle 380.368.439 Bytes genügen, wodurch aber keine merkliche Geschwindigkeitsverbesserung erzielt werden kann. Näheres siehe Restklassenring.

Die hohe Anzahl der Sprünge verringert bei Prozessoren mit Pipeline die effektive Ausnutzung der quasi parallelen Ausführung einzelner Befehle. Es empfiehlt sich daher die einzelnen Daten in maximal 5552 Byte große Teilblöcke zu zerlegen, nach denen erst eine Modulo-Operation ausgeführt wird. Diese Blöcke sollten wiederum in 16 Byte große Untereinheiten zerlegt werden, die in einem Schleifendurchlauf zusammengerechnet werden. Durch dieses sogenannte Loop-Unrolling lässt sich in etwa 25–30 % Geschwindigkeitszuwachs auf modernen Prozessoren bei genügend großen Daten erzeugen.

Schwächen von Adler-32

Ein optimaler Prüfsummenalgorithmus erzeugt eine Prüfsumme, die möglichst gleichverteilt über ihren Wertebereich ist. Dies ist bei Adler-32 für kurze Datenfolgen (< 128 Byte) nicht gegeben, da der Wert für s1 nicht überläuft.

Durch die einfache arithmetische Struktur von Adler-32 kommt es zudem zu vielen Kollisionen, insbesondere auch bei ähnlichen Eingabewerten. Wird beispielsweise Byte n der Eingabe um k erhöht, Byte n+1 um 2×k erniedrigt und Byte n+2 um k erhöht, bleiben sowohl s1 (die Summe aller Bytes), als auch s2 (die Summe aller Zwischenwerte von s1) unverändert. Dieses gilt für beliebige Positionen n in der Eingabe, und alle positiven oder negativen Werte von k, soweit die betrachteten Bytes nicht überlaufen. Im Ergebnis kann die 32-Bit-Prüfsumme Adler-32 noch nicht einmal eine 24-Bit-Eingabe zuverlässig absichern.

Lediglich einfache und doppelte Bitfehler werden zuverlässig erkannt, und zwar durch die Summen s1 beziehungsweise s2. Treten jedoch Bursts von drei oder mehr Bitfehlern auf, wie im obigen Beispiel, ist eine sichere Erkennung nicht gewährleistet.

Aus diesem Grunde wurde unter anderem in der Implementierung des Stream Control Transmission Protocols der verwendete Prüfsummenalgorithmus Adler-32 durch CRC-32 ersetzt, da hier recht oft nur kurze Datenströme benutzt werden und die Schwäche von Adler-32 zutage tritt.

Auch ist es verhältnismäßig leicht, durch beabsichtigte Modifikation einen Datenstrom mit gleicher Prüfsumme zu erzeugen. Deshalb kann Adler-32 die Integrität der Daten nicht garantieren. Wenn eine solche Sicherheit gefordert ist, müssen kryptografische Hash-Funktionen wie beispielsweise SHA zum Einsatz kommen.