Konstante Zeit in Dart — Einschränkungen der VMKonstante Zeit in Dart — Einschränkungen der VM

Zusammenfassung

Die Sicherheit von Kyber im IND-CCA2-Modus hängt kritisch von Operationen ab, die in konstanter Zeit ausgeführt werden: die gleiche Anzahl von CPU-Zyklen, unabhängig von den Werten der geheimen Daten. Dart, als eine Sprache, die auf einer VM mit JIT-Kompilierung und Garbage Collection ausgeführt wird, bietet keine Garantien für konstante Zeit. Dieses Dokument analysiert die konkreten Einschränkungen, die während der Implementierung von xkyber_crypto identifiziert wurden.

Was bedeutet "Konstante Zeit" in der Kryptographie?

Eine Operation ist zeitkonstant, wenn ihre Dauer nicht von geheimen Werten abhängt. Zum Beispiel:

// KONSTANT: Die Schleife führt immer 'len' Iterationen aus
uint8_t ct_compare(const uint8_t *a, const uint8_t *b, size_t len) {
    uint8_t result = 0;
    for (size_t i = 0; i < len; i++) {
        result |= a[i] ^ b[i];  // XOR: jedes Byte trägt gleich bei
    }
    return result;
}

// NICHT KONSTANT: Early Exit gibt die Position des ersten unterschiedlichen Bytes preis
bool non_ct_compare(const uint8_t *a, const uint8_t *b, size_t len) {
    for (size_t i = 0; i < len; i++) {
        if (a[i] != b[i]) return false;  // die Zeit hängt davon ab, wo es fehlschlägt
    }
    return true;
}

Die konstante Version stellt sicher, dass ein Angreifer, der die Vergleichszeit misst, nicht ableiten kann, wie viele Bytes übereinstimmen.

Das strukturelle Problem von Dart

1. JIT-Kompilierung und Umordnung

Dart verwendet Just-In-Time (JIT)-Kompilierung während der Entwicklung und Ahead-Of-Time (AOT)-Kompilierung für die Produktion. In beiden Fällen kann der Compiler Operationen umordnen, zusammenführen oder eliminieren, die der Programmierer als invariant angenommen hatte:

// Absicht: XOR ohne Early Exit akkumulieren
bool verify(Uint8List a, Uint8List b) {
  if (a.length != b.length) return false;
  int r = 0;
  for (int i = 0; i < a.length; i++) {
    r |= a[i] ^ b[i];
  }
  return r == 0;
}

Potenzielle Probleme:

• Die Dart-VM könnte die Schleife optimieren, wenn sie erkennt, dass r bis zum Ende nicht verwendet wird, aber es gibt keine Garantien.
• Der AOT-Compiler (gen_snapshot) kann Transformationen anwenden, die die Illusion von Zeitkonstanz zerstören.
• Es gibt kein @ConstantTime-Attribut und keine Compiler-Direktive zur Bewahrung der zeitlichen Semantik.

2. Garbage Collection (GC)

Dart hat einen generationalen GC mit Write-Barrieren. Wenn der kryptographische Code in eine Liste schreibt, kann die VM nichtdeterministischen zusätzlichen Code ausführen:

r.coeffs[8 * i + j] = aj - bj;  // Schreiben? Auslösen einer Write-Barriere?

Jeder Schreibzugriff kann den GC auslösen, wenn die junge Generation voll ist. Dies führt zu Zeitvariationen im Mikrosekunden- oder Millisekundenbereich — Größenordnungen, die größer sind als die Unterschiede, die ein Timing-Angriff auszunutzen versucht.

3. Bounds-Checking in Listen

Jeder Zugriff auf List<int> in Dart überprüft, ob der Index innerhalb des Bereichs liegt:

a.coeffs[i] = barrettReduce(a.coeffs[i]);  // Bounds-Check bei jedem Zugriff

Obwohl das Bounds-Checking für gültige Indizes konstant ist, kann die VM bei ungültigen Indizes Ausnahmen auslösen (langsam, nicht konstant). Schlimmer noch: Der Optimierer kann Bounds-Checks in manchen Schleifen eliminieren und in anderen nicht, was sichtbare Unterschiede einführt.

4. Ganzzahldivision und Modulo

Die Montgomery-Reduktion erfordert:

int r = (a + t * KYBER_Q) ~/ 65536;  // ganzzahlige Division in Dart

In C wird ~/ 65536 als eine 16-Bit-Rechtsverschiebung (>> 16) kompiliert, die zeitkonstant ist. In Dart ist ~/ eine ganzzahlige Division, die der JIT je nach Plattform und Kompilierungsphase optimieren kann oder nicht.

5. Random.secure() und Entropie

final Random rnd = Random.secure();
return Uint8List.fromList(
    List<int>.generate(length, (_) => rnd.nextInt(256)));

Random.secure() hängt von der zugrundeliegenden Plattform ab. In Webbrowsern (Dart kompiliert zu JavaScript) verwendet es window.crypto.getRandomValues(), das die Systementropie erschöpfen und blockieren kann. In nativem Flutter verwendet es den Zufallsgenerator des Betriebssystems. Es gibt keine Kontrolle über die Antwortzeit.

Identifizierte kritische Punkte

Vergleich mit Sprachen, die Garantien bieten

Schlussfolgerung

Die Dart-VM wurde nicht für hochsichere Kryptographie entwickelt. Es gibt keine:

• Einen Typ ConstantTimeList<T>, der Bounds-Checking vermeidet
• Ein Attribut @PreserveControlFlow, um zu verhindern, dass der JIT Schleifen optimiert
• Eine native, von der Community verifizierte Funktion für konstanten Vergleich

Jede Implementierung von Kyber in reinem Dart, die nicht auf native Erweiterungen (FFI mit C/Rust) zurückgreift, ist anfällig für Timing-Angriffe. Die einzig praktikable Lösung im Dart/Flutter-Ökosystem für Post-Quanten-Kryptographie ist die Verwendung von Bindings an native Bibliotheken wie liboqs oder die Referenzimplementierung von pq-crystals über dart:ffi.

Das Repository xkyber_crypto ist als Zeugnis archiviert, dass funktionale Korrektheit nicht ausreicht: Kryptographische Sicherheit erfordert Kontrolle über die Maschine, die die Sprache nicht bietet.