Nachrichten-Authentifizierungscode

In der Kryptographie bezeichnet der Message Authentication Code (MAC) einen erzeugten Prüfteil zur Authentifizierung einer gesendeten Nachricht und dient damit der Sicherung vor unbemerkter Manipulation der gesendeten Nachricht. Authentifizierungscodes sind informationstheoretisch sichere symmetrische Authentifizierungsverfahren und gewährleisten die Integrität und Authentizität elektronischer Daten und Nachrichten. Im Gegensatz zu Kryptosystemen verschlüsseln sie die Daten nicht.

Funktionsweise

Für ein symmetrisches Authentifizierungssystem wird ein zuvor an Sender und Empfänger ausgegebener geheimer Schlüssel benötigt. Der Sender erzeugt mittels eines geheimen Schlüssels und der zu übermittelnden Nachricht (Klartext) einen Prüfteil der Nachricht, den MAC. Übersendet werden Nachricht und MAC. Der Empfänger erstellt ebenfalls aus der erhaltenen Nachricht und dem geheimen Schlüssel den MAC und vergleicht diesen mit dem vom Sender verschickten. Stimmen beide überein, dann wurde die Nachricht wahrscheinlich nicht geändert. Die Genauigkeit der letzten Aussage kann durch Dimensionierung von Parametern selbst bestimmt werden.

Ein Angreifer kann die Nachricht zwar ändern, da er aber den geheimen Schlüssel nicht kennt, kann er keinen gültigen MAC für die veränderte Nachricht erstellen. Rät der Angreifer nicht zufällig richtig, dann lässt sich dadurch eine nachträgliche Änderung erkennen.

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.

Beispiel

Ein Klartextbit (A oder B) soll mittels einer 1-Bit MAC authentisiert übertragen werden. Der Schlüssel ist zwei Bit lang.

 (Text,MAC)
 Schlüssel  (A,0) (A,1) (B,0) (B,1)
     00       A           B
     01       A                 B
     10             A     B
     11             A           B

Die Nachricht AABB unter dem (zuvor vereinbarten) geheimen Schlüssel 11000110 wird dann als (A,1)(A,0)(B,1)(B,0) übertragen.

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 Erstellung und Verifikation des MACs mit demselben Schlüssel geschieht. Das bedeutet, dass der Sender und der Empfänger vorher einen geheimen Schlüssel ausgetauscht haben müssen. Aus diesem Grunde eignen sich MACs lediglich für symmetrische Verschlüsselungsverfahren. Da jeder, der einen MAC verifizieren kann, auch einen MAC erstellen kann, ist im Gegensatz zu digitalen Signaturen die Authentizität nicht gewährleistet.

Bei Signaturen wird durch die Asymmetrie 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.

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 $\varepsilon$ (am Beispiel: 0,5) bestimmt sich aus der Länge σ des pro Nachrichtenbit verwendeten MAC (am Beispiel: 1) $\varepsilon=2^{-\sigma}$

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 2σ. Möchte man also eine Nachricht der Länge l übertragen, sind l2σ Schlüsselbits (am Beispiel: 8) nötig.

Analog zum One-Time-Pad stellt sich hier ebenfalls die Frage, wieviele Schlüssel notwendig sind, um die gewünschte und eben beschriebene Sicherheit zu gewährleisten. Allgemein wird dieser Wert mit ε ^{− 2} angegeben. Damit ist das obige Beispiel mit der angegebenen Dimensionierung (u. a. Größe von MAC und Schlüssel) optimal.