Ein Message Authentication Code (MAC) dient dazu, Gewissheit über den Ursprung von Daten oder Nachrichten zu erhalten und ihre Integrität zu überprüfen.[1] MAC-Algorithmen erfordern zwei Eingabeparameter, erstens die zu schützenden Daten und zweitens einen geheimen Schlüssel, und berechnen aus beidem eine Prüfsumme, den Message Authentication Code.[1]
Funktionsweise
Die Integrität einer zu übertragenden Nachricht lässt sich mittels MACs wie folgt prüfen:[2] Zunächst vereinbaren Sender und Empfänger einen geheimen Schlüssel. Der Sender berechnet für diesen Schlüssel und seine Nachricht einen MAC und sendet dann die Nachricht sowie den MAC an den Empfänger. Dieser berechnet den MAC zu der empfangenen Nachricht und dem Schlüssel und vergleicht den berechneten MAC mit dem empfangenen. Die Übereinstimmung beider Werte interpretiert der Empfänger als erfolgreichen Integritätstest: Die Nachricht wurde von einer Partei abgeschickt, die den geheimen Schlüssel kennt, und sie wurde während der Übertragung nicht verändert.
Ein MAC geht wie folgt über die Verwendung einer kryptographischen Hashfunktion hinaus:[3] Wenn eine Nachricht nur mit ihrem Hashwert als MAC übertragen würde, wäre dies nicht sicher, da die Hashfunktion öffentlich bekannt ist. Ein Angreifer könnte die Nachricht modifizieren und einen neuen Hashwert für die neue Nachricht berechnen und diesen übertragen. Falls allerdings Sender und Empfänger ein Geheimnis teilen, kann dies in die Hashberechnung einfließen, so dass ein Angreifer nach Modifikation einer Nachricht nicht in der Lage ist, den passenden Hashwert zu berechnen.
Bestimmung des MAC
MACs basieren entweder auf Blockchiffren oder auf Hash-Funktionen oder sind speziell entwickelte MACs. Ein Verfahren zur Berechnung eines MAC auf Basis des DES und CBC ist als ANSI X9.9 standardisiert. Ein weiteres gebräuchliches Verfahren zur MAC-Berechnung, der HMAC, basiert auf kryptographischen Hash-Funktionen. Ein spezieller MAC ist der Message Authentication Algorithm (MAA), der 1983 als ein Standard für Banken entwickelt wurde.
Bezug zu digitalen Signaturen
Auch wenn die Manipulationssicherheit von Schlüsseltexten eine Verwandtschaft mit digitalen Signaturen nahelegt, bestehen Unterschiede der beiden Verfahren. MACs unterscheiden sich von digitalen Signaturen darin, dass die Überprüfung des MACs Kenntnis desselben geheimen Schlüssels erfordert, der zu seiner Berechnung genutzt wurde.[4] Daher kann jeder, der einen MAC überprüfen kann, diesen auch berechnen; entsprechend ist er in der Lage, eine Nachricht unbemerkt durch eine modifizierte mit passendem MAC auszutauschen.[4]
Im Gegensatz dazu werden digitale Signaturen im Rahmen asymmetrischer Kryptosysteme mit Hilfe eines privaten Schlüssels, der nur dem Absender bekannt ist, erstellt und mit Hilfe eines veröffentlichten Schlüssels überprüft.[4] So ist sichergestellt, dass der Unterschreiber im Besitz des privaten Schlüssels ist, und es sich so mit hoher Wahrscheinlichkeit um den vorgegebenen Autor der Nachricht handelt.
Informationstheoretisch sichere Verfahren
Beispiel
Ein Klartextbit (A oder B) soll mittels einer 1-Bit MAC authentisiert übertragen werden. Der Schlüssel ist zwei Bit lang.
Schlüssel | (A,0)* | (A,1)* | (B,0)* | (B,1)* |
---|---|---|---|---|
00 | A | B | ||
01 | A | B | ||
10 | A | B | ||
11 | A | B |
* (Text,MAC)
Die Nachricht AABB unter dem (zuvor vereinbarten) geheimen Schlüssel 11000110 wird dann als (A,1)(A,0)(B,1)(B,0) übertragen.
Sicherheitsanalyse
Angenommen ein Angreifer fängt das erste übertragene Paar aus obigem Beispiel ab und versucht, anstelle des A ein B zu übersenden. Damit die Änderung nicht bemerkt wird und er nicht auffällt, benötigt er den passenden MAC. Ihm ist aus der Übersicht bekannt, dass der entsprechende Schlüsselabschnitt 10 oder 11 lautet. Mit diesem Wissen ist es ihm aber nicht möglich, sich zwischen (B,0) und (B,1) zu entscheiden. Genau vor der gleichen Entscheidung steht er auch ohne Kenntnis des Schlüsselabschnitts, also der Frage MAC=0 oder MAC=1. Er rät also durchschnittlich in jedem zweiten Fall richtig.
Über diesen Sachverhalt kann man allgemein informationstheoretische Sicherheit definieren.
W(x|S) = W(x) (zur Notation siehe Bedingte Wahrscheinlichkeit)
In Worten: Unabhängig der a priori Kenntnis über den Klartext x erhält ein Angreifer durch Sehen des Schlüsseltextes S (hier: Klartext und MAC) oder von Teilen davon keine Information hinzu. Damit ist absolute Sicherheit nach Shannon gegeben.
Bei allen Betrachtungen wird natürlich vorausgesetzt, dass das beschriebene System korrekt funktioniert und auch so benutzt wird. Fällt dem Angreifer z. B. der geheime Schlüssel (oder -teile) in die Hand, so sind auch informationstheoretisch sichere Systeme zu brechen.
Eigenschaften
Die folgenden Eigenschaften beziehen sich auf den allgemeinen Fall. Im Speziellen gibt es abgeleitete effizientere Verfahren gleicher Qualität.
Die Fehlerwahrscheinlichkeit (am Beispiel: 0,5) bestimmt sich aus der Länge des pro Nachrichtenbit verwendeten MAC (am Beispiel: 1)
Da es immer einen passenden und damit zufällig zu erratenen MAC geben muss, kann auch durch die Verlängerung des MAC keine Wahrscheinlichkeit gleich Null garantiert werden. Durch den asymptotischen Zusammenhang nähert sich die Wahrscheinlichkeit aber schnell vernachlässigbaren Dimensionen.
Die nötige Schlüssellänge (am Beispiel: 2) bestimmt sich durch . Möchte man also eine Nachricht der Länge übertragen, sind Schlüsselbits (am Beispiel: 8) nötig.
Analog zum One-Time-Pad stellt sich hier ebenfalls die Frage, wie viele Schlüssel notwendig sind, um die gewünschte und eben beschriebene Sicherheit zu gewährleisten. Allgemein wird dieser Wert mit angegeben. Damit ist das obige Beispiel mit der angegebenen Dimensionierung (u. a. Größe von MAC und Schlüssel) optimal.
Literatur
- Charlie Kaufman, Radia Perlman, Mike Speciner: Network Security: Private Communication in a Public World, Prentice Hall PTR, Upper Saddle River, New Jersey, 2002, ISBN 0-13-046019-2.
- Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography, CRC Press, 2001, ISBN 0-8493-8523-7. Online