Tiempo Constante en Dart — Limitaciones de la VMTiempo Constante en Dart — Limitaciones de la VM

Resumen

La seguridad de Kyber en modo IND-CCA2 depende críticamente de operaciones que se ejecuten en tiempo constante: el mismo número de ciclos de CPU independientemente de los valores de los datos secretos. Dart, como lenguaje ejecutado sobre una VM con compilación JIT y recolección de basura, no ofrece garantías de tiempo constante. Este documento analiza las limitaciones concretas identificadas durante la implementación de xkyber_crypto.

¿Qué Significa "Tiempo Constante" en Criptografía?

Una operación es constante en tiempo si su duración no depende de valores secretos. Por ejemplo:

// CONSTANTE: el bucle siempre ejecuta 'len' iteraciones
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: cada byte contribuye igual
    }
    return result;
}

// NO CONSTANTE: early exit filtra la posición del primer byte diferente
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;  // el tiempo depende de dónde falla
    }
    return true;
}

La versión constante asegura que un atacante que mida el tiempo de comparación no pueda deducir cuántos bytes coinciden.

El Problema Estructural de Dart

1. Compilación JIT y Reordenación

Dart usa compilación Just-In-Time (JIT) durante el desarrollo y compilación Ahead-Of-Time (AOT) para producción. En ambos casos, el compilador puede reordenar, fusionar o eliminar operaciones que el programador asumía como invariantes:

// Intención: acumular XOR sin 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;
}

Problemas potenciales:

• Dart VM podría optimizar el bucle si detecta que r no se usa hasta el final, pero no hay garantías.
• El compilador AOT (gen_snapshot) puede aplicar transformaciones que rompan la ilusión de tiempo constante.
• No existe un atributo @ConstantTime ni una directiva del compilador para preservar la semántica temporal.

2. Recolección de Basura (GC)

Dart tiene un GC generacional con barreras de escritura (write barriers). Cuando el código criptográfico escribe en una lista, la VM puede ejecutar código adicional no determinista:

r.coeffs[8 * i + j] = aj - bj;  // ¿escribe? ¿dispara una write barrier?

Cada escritura puede activar el GC si el generador joven se llena. Esto introduce variaciones de tiempo de microsegundos o milisegundos —órdenes de magnitud mayores que las diferencias que un ataque de timing busca explotar.

3. Bounds Checking en Listas

Cada acceso a List<int> en Dart verifica que el índice esté dentro del rango:

a.coeffs[i] = barrettReduce(a.coeffs[i]);  // bounds check en cada acceso

Aunque el bounds checking es constante para índices válidos, la VM puede lanzar excepciones (lentas, no constantes) en índices inválidos. Peor aún: el optimizador puede elidir bounds checks en unos bucles y no en otros, introduciendo diferencias visibles.

4. División Entera y Módulo

La reducción de Montgomery requiere:

int r = (a + t * KYBER_Q) ~/ 65536;  // división entera en Dart

En C, ~/ 65536 se compila como un desplazamiento a la derecha de 16 bits (>> 16), que es constante en tiempo. En Dart, ~/ es una división entera que la JIT puede o no optimizar según la plataforma y la fase de compilación.

5. Random.secure() y Entropía

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

Random.secure() depende de la plataforma subyacente. En navegadores web (Dart compiled to JavaScript), usa window.crypto.getRandomValues(), que puede agotar la entropía del sistema y bloquearse. En Flutter nativo, usa el generador de aleatoriedad del sistema operativo. No hay control sobre el tiempo de respuesta.

Puntos Críticos Identificados

Comparación con Lenguajes que Sí Ofrecen Garantías

Conclusión

La VM de Dart no fue diseñada para criptografía de alto aseguramiento. No hay:

• Un tipo ConstantTimeList<T> que evite bounds checking
• Un atributo @PreserveControlFlow para evitar que el JIT optimice bucles
• Una función nativa de comparación constante verificada por la comunidad

Cualquier implementación de Kyber en Dart puro que no recurra a extensiones nativas (FFI con C/Rust) es vulnerable a ataques de temporización. La única solución viable en el ecosistema Dart/Flutter para criptografía post-cuántica es usar bindings a bibliotecas nativas como liboqs o la implementación de referencia de pq-crystals a través de dart:ffi.

El repositorio xkyber_crypto está archivado como testimonio de que la corrección funcional no es suficiente: la seguridad criptográfica requiere control sobre la máquina que el lenguaje no proporciona.