Temps Constant en Dart — Limitations de la VMTemps Constant en Dart — Limitations de la VM

Résumé

La sécurité de Kyber en mode IND-CCA2 dépend crucialement d'opérations qui s'exécutent en temps constant : le même nombre de cycles CPU indépendamment des valeurs des données secrètes. Dart, en tant que langage exécuté sur une VM avec compilation JIT et ramasse-miettes, n'offre pas de garanties de temps constant. Ce document analyse les limitations concrètes identifiées lors de l'implémentation de xkyber_crypto.

Que Signifie "Temps Constant" en Cryptographie ?

Une opération est constante dans le temps si sa durée ne dépend pas de valeurs secrètes. Par exemple :

// CONSTANTE : la boucle exécute toujours 'len' itérations
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 : chaque byte contribue également
    }
    return result;
}

// PAS CONSTANTE : early exit filtre la position du premier byte différent
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;  // le temps dépend de l'endroit où ça échoue
    }
    return true;
}

La version constante assure qu'un attaquant qui mesure le temps de comparaison ne puisse pas déduire combien de bytes coïncident.

Le Problème Structurel de Dart

1. Compilation JIT et Réordonnancement

Dart utilise la compilation Just-In-Time (JIT) pendant le développement et la compilation Ahead-Of-Time (AOT) pour la production. Dans les deux cas, le compilateur peut réordonner, fusionner ou supprimer des opérations que le programmeur supposait invariantes :

// Intention : accumuler XOR sans early exit
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;
}

Problèmes potentiels :

• Dart VM pourrait optimiser la boucle si elle détecte que r n'est pas utilisé jusqu'à la fin, mais il n'y a pas de garanties.
• Le compilateur AOT (gen_snapshot) peut appliquer des transformations qui brisent l'illusion de temps constant.
• Il n'existe pas d'attribut @ConstantTime ni de directive du compilateur pour préserver la sémantique temporelle.

2. Ramasse-Miettes (GC)

Dart a un GC générationnel avec barrières d'écriture (write barriers). Quand le code cryptographique écrit dans une liste, la VM peut exécuter du code supplémentaire non déterministe :

r.coeffs[8 * i + j] = aj - bj;  // écrit ? déclenche-t-il une write barrier ?

Chaque écriture peut activer le GC si le générateur jeune se remplit. Cela introduit des variations de temps de microsecondes ou millisecondes — des ordres de grandeur plus grands que les différences qu'une attaque de temporisation cherche à exploiter.

3. Vérification de Bornes dans les Listes

Chaque accès à List<int> en Dart vérifie que l'index est dans la plage :

a.coeffs[i] = barrettReduce(a.coeffs[i]);  // vérification de bornes à chaque accès

Bien que la vérification de bornes soit constante pour les index valides, la VM peut lancer des exceptions (lentes, non constantes) sur des index invalides. Pire encore : l'optimiseur peut élider les vérifications de bornes dans certaines boucles et pas dans d'autres, introduisant des différences visibles.

4. Division Entière et Module

La réduction de Montgomery nécessite :

int r = (a + t * KYBER_Q) ~/ 65536;  // division entière en Dart

En C, ~/ 65536 se compile comme un décalage à droite de 16 bits (>> 16), qui est constant dans le temps. En Dart, ~/ est une division entière que le JIT peut ou non optimiser selon la plateforme et la phase de compilation.

5. Random.secure() et Entropie

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

Random.secure() dépend de la plateforme sous-jacente. Dans les navigateurs web (Dart compiled to JavaScript), il utilise window.crypto.getRandomValues(), qui peut épuiser l'entropie du système et se bloquer. En Flutter natif, il utilise le générateur d'aléatoire du système d'exploitation. Il n'y a pas de contrôle sur le temps de réponse.

Points Critiques Identifiés

Comparaison avec des Langages qui Offrent des Garanties

Conclusion

La VM de Dart n'a pas été conçue pour la cryptographie à haute assurance. Il n'y a pas :

• Un type ConstantTimeList<T> qui évite la vérification de bornes
• Un attribut @PreserveControlFlow pour empêcher le JIT d'optimiser les boucles
• Une fonction native de comparaison constante vérifiée par la communauté

Toute implémentation de Kyber en Dart pur qui ne recourt pas à des extensions natives (FFI avec C/Rust) est vulnérable aux attaques de temporisation. La seule solution viable dans l'écosystème Dart/Flutter pour la cryptographie post-quantique est d'utiliser des bindings vers des bibliothèques natives comme liboqs ou l'implémentation de référence de pq-crystals via dart:ffi.

Le dépôt xkyber_crypto est archivé comme témoignage que la correction fonctionnelle ne suffit pas : la sécurité cryptographique nécessite un contrôle sur la machine que le langage ne fournit pas.