Implementierung von Kyber in Dart — xkyber_cryptoImplementierung von Kyber in Dart — xkyber_crypto

Zusammenfassung

Dokumentation der Implementierung von Kyber (ML-KEM-512) in Dart/Flutter, die während der Lernphase des Algorithmus erstellt wurde. Das Repository xkyber_crypto implementiert das vollständige IND-CCA2-Schema gemäß der Spezifikation FIPS 203, einschließlich NTT, Compress/Decompress, CBD und FO-Transform.

Archiviert im November 2025 nach dem Schluss, dass die sichere Verwaltung von Post-Quanten-Kryptographie in Dart ohne zeitkonstante Garantien auf VM-Ebene nicht durchführbar ist.

Struktur der Implementierung

lib/
├── params.dart           # Parameter des Schemas (KYBER_K, N, Q, η, etc.)
├── fq.dart               # Arithmetische Operationen modulo Q
├── reduce.dart           # Barrett- und Montgomery-Reduktion
├── ntt.dart              # Direkte und inverse NTT mit vorberechneten Zetas
├── poly.dart             # Polynome: Serialisierung, Kompression, CBD, Uniform
├── polyvec.dart          # Vektoren von Polynomen
├── gen_matrix.dart       # Generierung der Matrix A des Module-LWE-Problems
├── indcpa.dart           # Zugrundeliegendes IND-CPA-Schema
├── kem.dart              # FO-Transform: IND-CCA2 KEM
├── shake.dart            # SHAKE128 (Keccak) von Grund auf
├── verify.dart           # Zeitkonstanter Vergleich und cmov
├── constant_time_comparison.dart  # Wrapper für zeitkonstanten Vergleich
├── randombytes.dart      # Entropieerzeugung (Random.secure)
├── noise_generator.dart  # Deterministisches Rauschen (nicht im Haupt-KEM verwendet)
├── kyber_kem.dart        # Öffentliche API für Einkapselung/Entkapselung
├── kyber_keypair.dart    # Erzeugung von Schlüsselpaaren
└── xkyber_symmetric.dart # Symmetrische AES-GCM-Verschlüsselung mit dem gemeinsamen Schlüssel

Codeauszüge

Parameter des Schemas (params.dart)

Die Implementierung verwendet ML-KEM-512 (NIST-Stufe 1, k=2):

const int KYBER_K = 2;
const int KYBER_N = 256;
const int KYBER_Q = 3329;
const int KYBER_ETA = 2;

Die Größen von Schlüsseln und Ciphertexts leiten sich von diesen Parametern ab:

const int KYBER_PUBLICKEYBYTES = 800;   // pk komprimiert + Seed
const int KYBER_SECRETKEYBYTES = 1632;   // vollständiger sk
const int KYBER_CIPHERTEXTBYTES = 768;   // vollständiger ct

Jedes Polynom mit 256 Koeffizienten wird mit 12 Bits pro Koeffizient (384 Bytes) codiert, und die komprimierte Version verwendet 3 Bits (128 Bytes).

Reduktionen: Barrett und Montgomery (reduce.dart)

Kyber erfordert effiziente modulare Reduktionen. Die Implementierung enthält beide Methoden:

int barrettReduce(int a) {
  const int v = 20159;  // floor((1<<26 + KYBER_Q/2) / KYBER_Q)
  int t = ((a * v) >> 26);
  int r = a - t * KYBER_Q;
  return r;
}

int montgomeryReduce(int a) {
  int t = (a * KYBER_QINV) % 65536;  // R = 2^16
  int r = (a + t * KYBER_Q) ~/ 65536;
  if (r >= KYBER_Q) { r -= KYBER_Q; }
  return r;
}

Kontrast mit FIPS 203: Die Spezifikation definiert montgomeryReduce als zeitkonstante Operation. In Dart ist ~/ 65536 eine ganzzahlige Division, die die Dart-VM möglicherweise zu einer Bitverschiebung optimieren könnte, aber es gibt keine Garantie. Der JIT-Compiler kann die Operationen umordnen und die Zeitkonstanz brechen.

NTT (ntt.dart)

NTT ist das rechnerische Herz von Kyber. Iterative In-Place-Implementierung mit 128 vorberechneten Zetas:

void _nttInPlace(List<int> poly) {
  int len, start, j, k;
  int t, zeta;
  k = 1;
  for (len = 128; len >= 2; len >>= 1) {
    for (start = 0; start < 256; start = j + len) {
      zeta = zetasOficial[k];
      k++;
      for (j = start; j < start + len; j++) {
        // ... Butterfly mit Montgomery-Reduktion
      }
    }
  }
}

Die Zetas sind die primitive 256. Einheitswurzel im Feld modulo 3329, vorberechnet als Werte im Montgomery-Bereich:

final List<int> zetasOficial = <int>[
  2285, 340, 1017, 1352, 203, 1441, 2048, 360, ...
];

Kontrast mit FIPS 203: Der Zugriff auf zetasOficial[k] mit k++ pro Iteration ist sequentiell und vorhersagbar. Allerdings verwendet die C-Referenzimplementierung Zeiger und direkten Speicherzugriff. In Dart beinhaltet der Zugriff auf List<int> Bounds-Checking und mögliche GC-Write-Barrieren, die die VM ohne Programmiererkontrolle einführt.

Polynome: Compress/Decompress (poly.dart)

Compress reduziert von 12 Bits auf 3 Bits pro Koeffizient:

Uint8List polycompress(Poly a) {
  for (int i = 0; i < KYBER_N; i += 8) {
    int t0 = (((t.coeffs[i] << 3) + (KYBER_Q >> 1)) ~/ KYBER_Q) & 0x7;
  }
}

Decompress kehrt die Operation um:

a.coeffs[i + 0] = (d0 * KYBER_Q + 4) >> 3;

CBD — Centered Binomial Distribution (poly.dart)

Das Rauschen wird durch die zentrierte Binomialverteilung mit η=2 erzeugt:

void cbd(Poly r, Uint8List buf) {
  for (int i = 0; i < KYBER_N ~/ 8; i++) {
    int t = buf[2 * i] | (buf[2 * i + 1] << 8);
    for (int j = 0; j < 8; j++) {
      int aj = (t >> j) & 1;
      int bj = (t >> (j + 8)) & 1;
      r.coeffs[8 * i + j] = aj - bj;
    }
  }
}

Kontrast mit FIPS 203: CBD beinhaltet eine Schleife mit Bitverschiebungen. Die Dart-VM garantiert nicht, dass die for-Schleife ohne GC-Unterbrechungen, ohne JIT-Umordnung, ohne Branch-Misprediction im Prozessor ausgeführt wird.

FO-Transform: IND-CCA2 KEM (kem.dart)

int cryptokemdec(Uint8List ss, Uint8List c, Uint8List sk) {
  indcpaenc(cprime, mprime, pk, coinsPrime);
  int fail = verify(c, cprime) ? 0 : 1;
  if (fail == 0) {
    ssInput.setRange(0, KYBER_SYMBYTES, kprime);
  } else {
    ssInput.setRange(0, KYBER_SYMBYTES, z);
  }
}

Kontrast mit FIPS 203: Der FO-Transform ist der kritischste Punkt für Timing-Angriffe. Der Vergleich verify(c, cprime) muss zeitkonstant sein. Allerdings garantiert die Dart-VM nicht, dass die Schleife r |= a[i] ^ b[i] ohne datenabhängige Verzweigungen kompiliert wird.

SHAKE128 von Grund auf (shake.dart)

void _keccakf() {
  for (int round = 0; round < 24; round++) {
    // Theta, Rho, Pi, Chi, Iota
  }
}

Kontrast mit FIPS 203: Die Leistung in Dart ist deutlich geringer als in optimiertem C. In Benchmarks kann die Dart-Implementierung 10-50× langsamer sein als die C-Referenz.

Unterschiede zur Referenzimplementierung (pq-crystals/C)

Schlussfolgerung

Die Implementierung ist funktional korrekt: Alle Testvektoren bestehen, die Einkapselung und Entkapselung erzeugen übereinstimmende gemeinsame Geheimnisse. Allerdings impliziert funktionale Korrektheit keine kryptographische Sicherheit in Gegenwart eines Angreifers, der in der Lage ist, Ausführungszeiten, Cache-Zugriffe oder Energieverbrauch zu messen.

Die Archivierung des Repositorys spiegelt den Schluss wider, dass es im aktuellen Dart/Flutter-Ökosystem nicht möglich ist, die zeitkonstanten Eigenschaften zu garantieren, die Kyber benötigt, um in einer echten adversariellen Umgebung sicher zu sein.