XAES-256-GCM: AEAD mit erweitertem Nonce

 (words.filippo.io)
1 Punkte von GN⁺ 2024-06-30 | 1 Kommentare | Auf WhatsApp teilen
  • XAES-256-GCM ist eine neue AEAD-Spezifikation, die 256-Bit-Schlüssel und 192-Bit-Nonces verwendet, um das Nonce-Management in High-Level-Verschlüsselungs-APIs weniger riskant zu machen
  • Der große Nonce ermöglicht es, für jede Nachricht automatisch einen neuen Wert aus dem CSPRNG des Betriebssystems zu erzeugen; bei 2⁸⁰ Nachrichten wird ein Kollisionsrisiko in der Größenordnung von 2⁻³² angestrebt
  • Intern handelt es sich um eine Extended-Nonce-Konstruktion, die aus Eingabeschlüssel und großem Nonce einen abgeleiteten Schlüssel und einen 96-Bit-Nonce erzeugt und anschließend unverändert Standard-AES-256-GCM verwendet
  • Die Go-Referenzimplementierung kommt mit crypto/cipher und crypto/aes allein auf unter 100 Zeilen; von den drei AES-256-Aufrufen pro Nachricht lassen sich einige vorberechnen
  • Mit Fokus auf FIPS-140-Konformität und Bibliothekskompatibilität kann es zusammen mit XChaCha20Poly1305 und AES-GCM-SIV als Kandidat für eine nonce-lose AEAD-API dienen

AEAD mit großem Nonce für High-Level-APIs

  • XAES-256-GCM ist ein Algorithmus für Authenticated Encryption with Associated Data (AEAD) und verwendet einen 256-Bit-Schlüssel sowie einen 192-Bit-Nonce
  • Die Designziele lassen sich auf drei Punkte verdichten
    • Unterstützung für große Nonces, die auch bei einer praktisch nahezu unbegrenzten Zahl von Nachrichten sicher zufällig erzeugt werden können
    • vollständige und direkte FIPS-140-Konformität
    • einfache Implementierung auf Basis gängiger Kryptografie-Bibliotheken
  • Dank des großen Nonces lässt sich eine API bauen, die für jede Nachricht einen neuen Nonce aus dem CSPRNG des Betriebssystems liest, ohne dass Nutzer selbst Birthday-Bound-Berechnungen anstellen müssen
  • Da Konformität und Kompatibilität priorisiert werden, lässt es sich auch in Umgebungen einsetzen, in denen andere AEADs mit großem Nonce schwer nutzbar sind, aber AEAD benötigt wird

Extended-Nonce-Konstruktion mit unverändertem AES-256-GCM

  • XAES-256-GCM ist wie XChaCha20Poly1305 eine Extended-Nonce-Konstruktion, die auf einem bestehenden AEAD aufsetzt
  • Aus dem Eingabeschlüssel und dem 192-Bit-Nonce werden ein abgeleiteter Schlüssel und ein abgeleiteter Nonce für das interne AES-256-GCM berechnet
    • Eingabeschlüssel und Nonce sind jeweils K, N
    • Der abgeleitete AES-256-GCM-Schlüssel und -Nonce sind Kₓ, Nₓ
  • Mit Aufrufen von AES-256ₖ und dem vorderen Teil des Nonces wird Kₓ erzeugt; die hinteren 96 Bit des Eingabe-Nonces werden als Nₓ verwendet
  • Pro Nachricht sind drei Aufrufe von AES-256ₖ erforderlich
    • Einer davon kann für einen gegebenen Schlüssel vorberechnet werden
    • Die übrigen zwei Aufrufe können denselben Key Schedule wiederverwenden

Die Implementierung ist kurz und mit Standardbausteinen beschreibbar

  • Die Go-Referenzimplementierung bleibt inklusive Vorberechnungsoptimierung und des größten Teils des Boilerplates unter 100 Zeilen
  • Die Go-Implementierung nutzt nur crypto/cipher und crypto/aes aus der Standardbibliothek
  • XAES-256-GCM lässt sich auch mit der Standard-KDF aus NIST SP 800-108r1 und dem standardisierten NIST-AES-256-GCM-AEAD beschreiben
    • Die KDF ist eine counter-based KDF
    • Die PRF ist CMAC-AES256
    • Der Eingabeschlüssel ist Kin
    • Das Label ist das ASCII-Zeichen X, also 0x58
    • Der Kontext sind die ersten 96 Bit des Eingabe-Nonces
    • Die Counter-Größe beträgt 16 Bit
    • Das optionale Feld L wird weggelassen
    • Die Ausgabe ist ein abgeleiteter 256-Bit-Schlüssel
  • Der abgeleitete Schlüssel und die letzten 96 Bit des Eingabe-Nonces gehen in AES-256-GCM ein
  • Dank der Parameterwahl ist die Konstruktion nach Entfernen der KDF- und CMAC-Abstraktionen nur geringfügig langsamer und komplexer als einfache AES-256-Aufrufe auf einem Counter
  • Dieselben Parameter werden auch von der High-Level-OpenSSL-API unterstützt

Drittanbieter-Implementierungen und Testvektoren

  • Mit Stand der Bearbeitung vom 2024-06-29 wurden Drittanbieter-Implementierungen hinzugefügt
  • Die Web-Cryptography-API-Implementierung verwendet einen 256-Bit-AES-CBC-CryptoKey
  • Die Spezifikation enthält Testvektoren für die beiden wichtigsten Codepfade
    • MSB₁(L) = 0
    • MSB₁(L) = 1
  • Außerdem werden akkumulierte Testvektoren bereitgestellt, die 10.000 oder 1.000.000 zufällige Iterationen komprimieren

Verzicht auf /11 und Alternativen

  • In einer früheren Idee gab es den Namen XAES-256-GCM/11, in der finalen Spezifikation wurde /11 jedoch aufgegeben
  • /11 war eine Performance-Optimierung; da einer der Gründe für AES-GCM die FIPS-140-Konformität ist, würde eine Änderung der Rundenzahl diese Konformität aufheben
  • Wenn FIPS-140-Konformität nicht das Ziel ist, gibt es mehrere Alternativen
    • AES-GCM-SIV
    • moderne AEAD-Konstruktionen auf Basis des AES-Kerns
  • Der Abschnitt Alternatives der Spezifikation vergleicht die einzelnen Alternativen mit XAES-256-GCM

Einordnung in Go und nonce-lose AEAD-APIs

  • XAES-256-GCM zielt auf ein sicheres, langweiliges, konformitätsfähiges und interoperables AEAD ab
  • Der wichtigste Einsatzbereich ist die Art von High-Level-API, die man Go gern hinzufügen würde
  • XAES-256-GCM ergänzt XChaCha20Poly1305 und AES-GCM-SIV und wurde als Kandidat für die Implementierung einer hypothetischen nonce-losen AEAD-API entworfen
  • Da es nicht bevorzugt wird, eine Go-spezifische Konstruktion in die Go-Standardbibliothek aufzunehmen, ist die Meinung der Maintainer anderer Kryptografie-Bibliotheken gefragt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-06-30
Meinungen auf Hacker News

  • Das Design ist ziemlich clever: Da es CMAC-basiert ist, kann der Schlüssel mit AES-CBC abgeleitet werden, ohne Low-Level-Primitiven zu benötigen.
    Aus AES-CBC-Sicht kann man es so betrachten, dass man mit L = AES-CBC-256ₖ(iv = 0¹²⁸, plaintext = 0¹²⁸)[:16] beginnt, daraus K1 erzeugt, M1 und M2 verschlüsselt, um Kₓ zu erhalten, und dann Nₓ = N[12:] verwendet.
    Bei AES-CBC-256 kann man annehmen, dass nur der erste 128-Bit-Block des Chiffrats zurückgegeben und der Padding-Block verworfen wird; selbst wenn sich Padding nicht abschalten lässt, kostet das im Vergleich zu einer Low-Level-Implementierung nur drei zusätzliche AES-Aufrufe mit demselben Schlüssel, was nicht schlecht ist.
    Eine JS-Implementierung auf Basis der WebCrypto API, die diese Eigenschaft nutzt, gibt es unter https://github.com/dchest/xaes; sie nimmt direkt einen CryptoKey für AES-CBC entgegen und unterstützt auch CryptoKey-Eigenschaften wie das Speichern in IndexedDB mit extractable=false.

    • In diesem Bereich sieht das wohl wie Standardschreibweise aus, aber ehrlich gesagt mag ich kryptografische Notation nicht.
      In diesem Pseudocode scheint die Hälfte der Zahlen Bytes und die andere Hälfte Bits zu zählen, und wenn man den Algorithmus nicht schon kennt, ist kaum zu erkennen, was was ist.
      Zum Beispiel sieht N[:12] nach 12 Bytes aus, aber 0¹²⁸ sind 16 Bytes, und X ist das tatsächliche Zeichen 'X', also die Bitfolge 01011000, während L keine Bitfolge 01001100, sondern eine Variable ist.
      Mathematiker mögen eindeutige Notation offenbar nicht so sehr wie Leute aus der Informatik.
    • Unheimlich aussehende Konstanten wie 0¹²⁰10000111 sind Bitfolgen, die die Koeffizienten des lexikografisch ersten Polynoms unter den irreduziblen Polynomen vom Grad b mit minimaler Anzahl von Nicht-Null-Termen darstellen, wobei b die Blockgröße der von CMAC verwendeten zugrunde liegenden Blockchiffre ist.
      Da steckt keine geheime Absicht dahinter.
    • Ich bin kein Kryptografieexperte, aber zusammengefasst verstehe ich es so: Standard-AES-GCM AEAD bricht katastrophal, wenn dieselbe Nonce für zwei verschiedene Nachrichten verwendet wird[1], und die Nonce-Größe ist in vielen Fällen auch zu klein, um zufällige Nonces sicher zu verwenden.
      Diese Arbeit macht es einfach, dieses Problem zu umgehen, indem bei jedem AES-GCM-Aufruf nicht nur die Nonce, sondern auch der Schlüssel geändert wird.
      Außerdem verwendet sie nur „normales“ AES, das in der Regel verfügbar ist, wenn AES-GCM verfügbar ist, und vermeidet neue komplexe Konstruktionen, die noch Schwächen haben könnten.
      Der Overhead pro Nachricht besteht aus zwei kleinen Puffern, die mit „normalem“ AES ver- und entschlüsselt werden müssen, sowie einer längeren 192-Bit-Nonce.
      [1]: https://frereit.de/aes_gcm/

  • Das scheint die Falle von reinem AES-GCM zu beseitigen, bei der man bei zufälligen Nonces ungefähr alle 2^32 Nachrichten den Schlüssel wechseln muss.
    Eine Nonce-Kollision in AES-GCM ist katastrophal und ermöglicht einem Angreifer mindestens, beliebige Nachrichten zu signieren.
    Man muss nicht zwingend zufällige Nonces verwenden, aber sie werden normalerweise empfohlen; ziemlich clever ist, dass es mit zwei Bausteinen – einer zählerbasierten Key-Derivation-Function und reinem GCM – FIPS-konform gemacht wird.

    • Genauer gesagt macht dieser Ansatz zufällige Nonces überhaupt erst sicher.
      Bei Standard-AES-GCM reichen 96 Bit nicht aus, um zufällige Kollisionen zu vermeiden, daher sollte man deterministische Nonce-Erzeugung verwenden.
      Außerdem muss man nach 2^32 Blöcken die Nonce oder den Schlüssel ändern, egal wie die Nonce erzeugt wurde, weil der Counter überläuft und der nächste Block dieselbe Nonce+Counter-Kombination wie der erste Block verwendet.

  • Wirklich großartig. Ich wünschte, das hätte es gegeben, als ich vor ein paar Jahren zuletzt ein verschlüsseltes Dateisystem gebaut habe.
    Bei großen Dateisystem-Deployments sind Nonce-Kollisionen eine große Sorge.
    2^32 klingt viel, aber wenn man auf einem PB-Array mit 100k IOPS pro Sekunde schreibt und sich auf die Zufälligkeit eines Pseudozufallszahlengenerators verlässt, ist eine Kollision praktisch garantiert.

    • Der CAESAR-Wettbewerb[1] endete 2019, und dabei sind mehrere AEADs mit ausreichend großem Nonce-Raum herausgekommen.
      [1] https://en.m.wikipedia.org/wiki/CAESAR_Competition
    • Ich frage mich allerdings, warum Nonce-Kollisionen ein Problem sind.
      Bedeutet das nicht nur, dass zwei Blöcke denselben Verschlüsselungsschlüssel teilen?
      Wenn man den Klartext keines der beiden Blöcke kennt, sehe ich nicht, wie das die Sicherheit des Systems schwächt.

  • Ich fände es gut, wenn das für eine FIPS-konforme age-Variante zur Archivdateiverschlüsselung verwendet würde.
    Bei einer Bankenprüfung wurde age für diesen Zweck abgelehnt, weil es ChaCha verwendet; der X25519-Public-Key-Teil von age wurde als in Ordnung angesehen. Ich dachte, X25519 sei relativ kürzlich von NIST zugelassen worden.
    Ich habe keine Go-Erfahrung, aber nach der age-Spezifikation sieht es so aus, als ließe sich das direkt einbauen; wenn ich Zeit habe, könnte ich es versuchen.
    Als Name böte sich „cage“ an, im Sinne von „compliant actually good encryption“.
    1: https://github.com/FiloSottile/age

    • „compliant actually good encryption“ ist vielleicht ein Oxymoron.
    • Nachgesehen: Ed25519 scheint zugelassen zu sein (FIPS 186-5), X25519 aber offenbar noch nicht.
    • Zur Info: In der Go-Standardbibliothek gibt es noch keine XAES-Implementierung, nur die Referenzimplementierung von C2SP.
    • bge, bureaucratic good encryption

  • Als Nicht-Kryptograf frage ich mich, warum man eine 192-Bit-Nonce verwendet und nicht 256 Bit.
    In praktischen Anwendungen scheinen mir diese zusätzlichen Bits kaum als Kosten ins Gewicht zu fallen.

    • Es gibt keinen Platz für 256 Bit. 192 Bit setzen sich aus 96 Bit aus dem unteren Nonce-Raum und 96 Bit zusammen, die zusammen mit dem nötigen Präfix in einen 128-Bit-CMAC-Block passen.
      Man könnte die CMAC-Eingabe länger machen, aber dann müsste die AES-256-Blockfunktion öfter ausgeführt werden, und man bekäme es in der CMAC-Key-Derivation-Function mit lästigen Key-Control-Problemen zu tun.
      Das ist ähnlich wie der Grund, warum XChaCha20Poly1305 eine 192-Bit-Nonce verwendet; dass es mit anderen wichtigen Extended-Nonce-AEADs konsistent ist, ist ebenfalls ein kleiner Vorteil.

  • Es hieß „Kollisionsrisiko 2⁻³² bei 2⁸⁰ Nachrichten“ – entstehen nicht schon vorher Probleme dadurch, dass die AES-Blockgröße nur 128 Bit beträgt?

    • Falls du die Birthday Bound für Blöcke meinst (https://sweet32.info), die ist eine Grenze für die Anzahl der mit einem einzelnen Schlüssel verschlüsselten Blöcke.
      XAES leitet für jede Nachricht einen großen Schlüssel ab und erreicht damit das, was man oft als Garantie jenseits der Birthday Bound bezeichnet.
    • Nein.
      Ohne mehr Kontext dazu, warum du glaubst, dass das ein Problem wäre, ist es schwer, genauer zu antworten.

  • „Sicher, langweilig, konform und interoperabel.“
    Genau meine Lieblingsart von Technik.

  • Gut. Es ist tatsächlich erfreulich, eine NIST-basierte Konstruktion zu haben.
    Schade ist allerdings, dass man mehrere Vorteile der NIST-Key-Derivation-Function, etwa Labels und Kontext, aufgibt.
    Ich verstehe, dass das zur Minimierung der Zahl der AES-Aufrufe geopfert wurde, aber insbesondere bei Nachrichten, die länger als ein paar hundert Bytes sind, hätte ich eine starke kryptografische Trennung wohl höher priorisiert als ein paar eingesparte AES-Aufrufe.
    Schließlich werden zufällige GCM-Nonces länger als 96 Bit eindeutig häufig missverstanden und bieten stärkere Garantien als 96-Bit-Nonces[1].
    Wenn man natürlich pro Nachricht einen neuen Schlüssel ableiten kann, ist das eindeutig besser.
    [1] https://neilmadden.blog/2024/05/23/galois-counter-mode-and-r...