CMAC und Poly1305: MACs für Blockchiffren

Ein Message Authentication Code (MAC) nimmt einen Schlüssel und eine Nachricht entgegen und erzeugt daraus einen Tag. Der Tag bestätigt, dass die Nachricht nicht manipuliert wurde und von jemandem erzeugt wurde, der den Schlüssel besitzt.

HMAC verwendet eine Hashfunktion als Primitive. CMAC und Poly1305 verwenden dagegen Blockchiffren beziehungsweise Polynomarithmetik. Blockchiffren-MACs vermeiden die Abhängigkeit von einer Hashfunktion und lassen sich natürlich in AES-Hardware integrieren.

CMAC (Cipher-based MAC) ist im NIST SP 800-38B definiert. Die Nachricht wird bis zu einer Blockgrenze aufgefüllt, aus der Chiffre werden zwei Subkeys K1/K2 abgeleitet, diese werden in den letzten Block ein-XOR-verknüpft, und anschließend wird der CBC-Modus ausgeführt, ohne Zwischenchiffretexte zu speichern.

K1 = AES_K(0^128), um 1 Bit nach links verschoben und mit einer Konstante ein-XOR-verknüpft, wenn das MSB 1 war. K2 wird auf dieselbe Weise aus K1 durch Verschieben abgeleitet. Diese Subkeys binden den letzten unvollständigen Block sicher und verhindern Length Extension.

Poly1305 ist ein von Daniel Bernstein entwickelter One-Time-Authenticator. Dabei wird ein Polynom über der Primzahl 2^130-5 ausgewertet. Die Nachricht wird als Koeffizienten des Polynoms behandelt und ein einmaliges Schlüsselpaaar (r, s) verwendet.

Tag = (sum of (m_i * r^i) mod 2^130-5) + s mod 2^128. Der Schlüssel r wird auf 22 bestimmte Bits eingeschränkt, um Timing-Angriffe zu verhindern. s ist eine 16 Byte große einmalige Additionsmaske.

Poly1305 wird fast immer mit ChaCha20 kombiniert. ChaCha20 erzeugt das einmalige (r, s) aus dem Keystream der Stromchiffre. Dadurch ist das kombinierte AEAD-Verfahren nachweislich sicher und auf ARM-/Mobilprozessoren extrem schnell.

AES-GCM authentifiziert mithilfe von GHASH, einem polynomialen MAC über GF(2^128). AES-CMAC ist einfacher und wird in IEEE 802.11i (WPA2) sowie in TLS-1.2-Chiffrensammlungen verwendet. GCM bietet Verschlüsselung und Authentifizierung in einem Durchlauf.

Poly1305 erreicht auf ARM Cortex-A mit NEON-Intrinsics etwa 1 Zyklus pro Byte. AES-CMAC benötigt eine AES-Blockoperation pro 16-Byte-Block. Bei großen Datenmengen ist Poly1305 auf Hardware ohne AES-NI schneller als CMAC.

CMAC ist unter der Annahme, dass AES eine pseudorandom Permutation ist, unter einem Angriff mit frei wählbaren Nachrichten existentially unforgeable. Poly1305 ist bei einem wirklich zufälligen einmaligen Schlüssel informationstheoretisch sicher – die Wahrscheinlichkeit einer Fälschung beträgt höchstens 8*ceil(L/16)/2^106.

CMAC: WPA2, S/MIME, Integrität von Dateisystemen. Poly1305: TLS 1.3 über ChaCha20-Poly1305, WireGuard-VPN, Signal Protocol, Noise Protocol Framework. Beide Verfahren sind in modernen Hochsicherheitssystemen weit verbreitet.

Sie haben die CBC-basierte Konstruktion von CMAC und die Polynomarithmetik von Poly1305 kennengelernt. Beide sind MACs mit konstanter Laufzeit und hoher Sicherheit, die in Protokollen der Praxis eingesetzt werden. Als Nächstes: TLS/HTTPS und die Kombination all dieser Primitive.