Implementación de Kyber en Dart — xkyber_cryptoImplementación de Kyber en Dart — xkyber_crypto

Resumen

Documentación de la implementación de Kyber (ML-KEM-512) en Dart/Flutter realizada durante la fase de aprendizaje del algoritmo. El repositorio xkyber_crypto implementa el esquema IND-CCA2 completo siguiendo la especificación FIPS 203, incluyendo NTT, Compress/Decompress, CBD y el FO transform.

Archivado en noviembre de 2025 tras concluir que la gestión segura de criptografía post-cuántica en Dart es inviable sin garantías de tiempo constante a nivel de VM.

Estructura de la Implementación

lib/
├── params.dart           # Parámetros del esquema (KYBER_K, N, Q, η, etc.)
├── fq.dart               # Operaciones aritméticas modulo Q
├── reduce.dart           # Reducción de Barrett y Montgomery
├── ntt.dart              # NTT directo e inverso con zetas precomputados
├── poly.dart             # Polinomios: serialización, compresión, CBD, uniform
├── polyvec.dart          # Vectores de polinomios
├── gen_matrix.dart       # Generación de la matriz A del problema Module-LWE
├── indcpa.dart           # Esquema IND-CPA subyacente
├── kem.dart              # FO transform: IND-CCA2 KEM
├── shake.dart            # SHAKE128 (Keccak) desde cero
├── verify.dart           # Comparación en tiempo constante y cmov
├── constant_time_comparison.dart  # Wrapper de comparación constante
├── randombytes.dart      # Generación de entropía (Random.secure)
├── noise_generator.dart  # Ruido determinista (no usado en el KEM principal)
├── kyber_kem.dart        # API pública de encapsulación/desencapsulación
├── kyber_keypair.dart    # Generación de par de claves
└── xkyber_symmetric.dart # Cifrado simétrico AES-GCM con la clave compartida

Extracciones de Código

Parámetros del Esquema (params.dart)

La implementación usa ML-KEM-512 (NIST level 1, k=2):

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

Los tamaños de claves y ciphertext se derivan de estos parámetros:

const int KYBER_PUBLICKEYBYTES = 800;   // pk comprimido + semilla
const int KYBER_SECRETKEYBYTES = 1632;   // sk completo
const int KYBER_CIPHERTEXTBYTES = 768;   // ct completo

Cada polinomio de 256 coeficientes se codifica en 12 bits por coeficiente (384 bytes), y la versión comprimida usa 3 bits (128 bytes).

Reducciones: Barrett y Montgomery (reduce.dart)

Kyber requiere reducciones modulares eficientes. La implementación incluye ambos métodos:

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;
}

Contraste con FIPS 203: La especificación define montgomeryReduce como operación constante en tiempo. En Dart, ~/ 65536 es una división entera que la VM de Dart podría optimizar a desplazamiento de bits, pero no hay garantía. El compilador JIT puede reordenar las operaciones y romper el tiempo constante.

NTT (ntt.dart)

La NTT es el corazón computacional de Kyber. Implementación iterativa in-place con 128 zetas precomputados:

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 con Montgomery reduction
      }
    }
  }
}

Los zetas son la raíz primitiva 256-ésima de la unidad en el campo módulo 3329, precomputados como valores en dominio Montgomery:

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

Contraste con FIPS 203: El acceso a zetasOficial[k] con k++ por iteración es secuencial y predecible. Sin embargo, la implementación en C de referencia usa punteros y acceso directo a memoria. En Dart, el acceso a List<int> implica bounds checking y posible gc write barrier que la VM introduce sin control del programador.

Polinomios: Compress/Decompress (poly.dart)

Compress reduce de 12 bits a 3 bits por coeficiente:

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 invierte la operación:

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

CBD — Centered Binomial Distribution (poly.dart)

El ruido se genera mediante la distribución binomial centrada con η=2:

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;
    }
  }
}

Contraste con FIPS 203: CBD implica un bucle con desplazamiento de bits. Dart VM no garantiza que el bucle for se ejecute sin interrupciones del GC, sin reordenación por JIT, sin branch misprediction en el procesador.

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);
  }
}

Contraste con FIPS 203: El FO transform es el punto más crítico para ataques de timing. La comparación verify(c, cprime) debe ser constante en tiempo. Sin embargo, la VM de Dart no garantiza que el bucle r |= a[i] ^ b[i] se compile sin ramificaciones dependientes de datos.

SHAKE128 desde Cero (shake.dart)

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

Contraste con FIPS 203: El rendimiento en Dart es significativamente menor que en C optimizado. En benchmarks, la implementación Dart puede ser 10-50x más lenta que la referencia en C.

Diferencias con la Implementación de Referencia (pq-crystals/C)

Conclusión

La implementación es funcionalmente correcta: todos los vectores de test pasan, la encapsulación y desencapsulación producen secretos compartidos coincidentes. Sin embargo, la corrección funcional no implica seguridad criptográfica en presencia de un atacante capaz de medir tiempos de ejecución, accesos a caché o consumo de energía.

El archivo del repositorio refleja la conclusión de que, en el ecosistema Dart/Flutter actual, no es posible garantizar las propiedades de tiempo constante que Kyber requiere para ser seguro en un entorno adversarial real.