Adler-32
Adler-32 ist ein einfacher, von Mark Adler entwickelter Prüfsummenalgorithmus, der auf Fletcher’s Checksum basiert. 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 bestimmt eine 32-bit Integer-Zahl, die aus der Hintereinanderreihung zweier 16-bit Integer-Zahlen s1 und s2 gebildet wird. Der Parameter s1 wird mit 1 initialisiert und in jedem Schritt wird der Wert des nächsten zu prüfenden Bytes aufaddiert. Der Parameter s2 wird mit 0 initialisiert und in jedem Schritt wird der aktuelle Wert des Parameters s1 aufaddiert. Beide Summen werden modulo 65.521 (die größte Primzahl < 216) berechnet.
Beispielimplementierung in C:
/* Beispielcode zur Berechnung der Adler-32-Prüfsumme */
#include <stdint.h> // fuer uint8_t/uint32_t
#include <stddef.h> // fuer size_t
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 braucht etwa die recht langsame Modulo-Operation nicht bei jedem Datenbyte durchgeführt zu 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 Geschwindigkeitserhöhung 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 verkleinert 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.
Literatur
- Jonathan Stone, Checksums and the internet, S. 125ff, The Adler-32 checksum