11. Message Authentication Codes

Ein Message Authentication Code oder MAC ist eine Einweg-Hashfunktion, die einen Schlüssel enthält, mit nur diesem man den Hashwert verifizieren kann. Damit kann man Authentizität ohne Geheimhaltung erreichen.

Mit Hilfe von MACs können mehrere Benutzer ihre Dateien authentifizieren und einzelne Benutzer können mit MACs überprüfen, ob ihre Dateien verändert wurden, z. B. von Viren. Im Gegensatz zu Einweg-Hashfunktionen ist der Schlüssel des MACs zur Berechnung des Hashwertes nur dem Benutzer bekannt und der Hashwert kann nicht unbemerkt verändert werden.

Eine einfache Möglichkeit zur Umwandlung einer Einweg-Hashfunktion in einen MAC besteht darin, den Hashwert mit einem symmetrischen Algorithmus zu chiffrieren. Jeder MAC kann in eine Einweg-Hashfunktion umgewandelt werden, indem man den Schlüssel veröffentlicht.

11.1 CBC-MAC

Die einfachste Möglichkeit zur Konstruktion einer schlüsselabhängigen Einweg-Hashfunktion ist die Verschlüsselung einer Nachricht mit einem Blockalgorithmus im CBC- oder CFB-Modus. Der Hashwert ist der letzte verschlüsselte Block, der noch einmal verschlüsselt wird. Bei der Verwendung des Blockalgorithmus DES mit reduzierter Rundenzahl kann es mittels differentieller Kryptanalyse geknackt werden. Ein potentielles Sicherheitsproblem bei dieser Methode besteht darin, daß der Empfänger den Schlüssel kennen muß. Mit diesem Schlüssel kann er Nachrichten mit einem bestimmten vorgegebenen Hashwert generieren, indem er in der umgekehrten Richtung entschlüsselt.

11.2 Message Authenticator Algorithm (MAA)

Nicht besonders kompliziert produziert der MAA einen 32 Bit langen Hashwert und wurde vor langer Zeit für Mainframe-Computer mit schneller Multiplikationsanweisung entwickelt.

v = v<<<1

e = v w

x = ((((e + y) mod 2³²) v A ^ C)*(x M_i))mod2³²-1

y = ((((e + y)mod2³²) v B ^ D)*(y M_i))mod2³²-2

Diese Anweisungen werden für jeden Nachrichtenblock M_idurchlaufen. Der Hashwert besteht aus der XOR-Verknüpfung von x und y. Die Variablen v und e werden vom Schlüssel abgeleitet. A, B, C und D sind Konstanten. Dieser Algorithmus scheint weit verbreitet zu sein, gilt aber nicht unbedingt als sicher

11.3 Bidirektionaler MAC

Dieser MAC liefert einen Hashwert mit der doppelten Blocklänge des Blockalgorithmus. Zuerst berechnet man den CBC-MAC der Nachricht, anschließend den CBC-MAC aus den Blöcken in umgekehrter Reihenfolge der Nachricht. Der bidirektionale MAC besteht einfach aus der Konkatenierung dieser beiden Werte. Leider ist diese Konstruktion unsicher.

11.4 Juenemans Verfahren

Dieser MAC wird auch als quadratic congruential manipulation detection code (QCMDC) bezeichnet. Zuerst zerlegt man die Nachricht in Blöcke der Größe m Bit. Dann berechnet man:

H₀ = I_H , wobei I_H der geheime Schlüssel ist.

H_i = (H_i-1+M_i)² mod p, wobei p eine Primzahl kleiner 2m-1 ist.

Das Zeichen + steht für ganzzahlige Addition.

Jueneman empfiehlt m = 16 und p = 2³¹ - 1 und außerdem einen zusätzlichen Schlüssel H₁. Die eigentliche Nachricht beginnt dann bei H₂. Aufgrund einer Vielzahl von Angriffen des Geburtstagstyps, gibt es noch weitere Verbesserungsvorschläge, den QCMDC über Iterationen viermal berechnen (128 bit Hashwert). Weiter kann man ihn noch verbessern, indem man die vier Iterationen parallel durchführt und verbindet. Aber ebenso wie bei einer Verkleinerung der Nachrichtenblöcke wurde teilweise von Jueneman selbst gebrochen. Eine andere Variante ersetzt die Addition durch eine XOR-Verknüpfung und benutzt Nachrichtenblöcke, die wesentlich kleiner sind als p. H₀ wurde ebenfalls festgelegt, was eine schlüssellose Einweg-Hashfunktion liefert. Nach einem Angriff auf das Verfahren wurde es als Teil des Projekts European Open Shop Information-Tele-Trust verbessert, doch auch diese Verbesserung wurde gebrochen.

11.5 RIPE-MAC

Von Bart Preneel entwickelt und in das RIPE-Projekt aufgenommen benutzt er DES als Verschlüsselungsfunktion. Es gibt zwei Varianten des Verfahrens: RIPE-MAC1 benutzt einfache DES-Verschlüsselung pro 64 bit langen Nachrichtenblock, RIPE-MAC3 benutzt zwecks höherer Sicherheit Triple-DES. Der Algorithmus besteht aus drei Teilen. Zuerst wird die Nachricht auf ein Vielfaches von 64 bit vergrößert und dann in 64 bit lange Blöcke zerlegt. Eine schlüsselabhängige Kompressionsfunktion hasht diese Blöcke zu einem einzigen Block der Länge 64 bit. Der Vorgang wird von einem geheimen Schlüssel gesteuert. In diesem Schritt wird entweder DES oder Triple-DES verwendet. Die Ausgabe dieser Kompression durchläuft schließlich eine weitere DES-Chiffrierung mit einem Schlüssel, der aus dem zur Kompression benutzten Schlüssel abgeleitet wird.

11.6 IBC-Hash

Ein weiterer MAC, der in das RIPE-Projekt aufgenommen wurde. Der Algorithmus ist sehr interessant, weil er beweisbar sicher ist. Die Wahrscheinlichkeit eines erfolgreichen Angriffs läßt sich quantifizieren. Leider muß jede Nachricht mit einem anderen Schlüssel gehasht werden. Die durch Verändern der Parameter gewählte Sicherheitsstufe beeinflußt die maximale Länge einer Nachricht, die gehasht werden kann. Vergleichbare Einschränkungen gibt es bei keiner anderen vorgestellten Funktionen. Aufgrund dieser Besonderheiten empfiehlt der RIPE-Report, IBC-Hash nur für lange und selten übertragene Nachrichten einzusetzen.