Kyber Implementation in Dart — xkyber_cryptoKyber Implementation in Dart — xkyber_crypto

Summary

Documentation of the implementation of Kyber (ML-KEM-512) in Dart/Flutter carried out during the algorithm learning phase. The repository xkyber_crypto implements the full IND-CCA2 scheme following the FIPS 203 specification, including NTT, Compress/Decompress, CBD, and the FO transform.

Archived in November 2025 after concluding that secure management of post-quantum cryptography in Dart is unfeasible without constant-time guarantees at the VM level.

Implementation Structure

lib/
├── params.dart           # Scheme parameters (KYBER_K, N, Q, η, etc.)
├── fq.dart               # Arithmetic operations modulo Q
├── reduce.dart           # Barrett and Montgomery reduction
├── ntt.dart              # Forward and inverse NTT with precomputed zetas
├── poly.dart             # Polynomials: serialization, compression, CBD, uniform
├── polyvec.dart          # Polynomial vectors
├── gen_matrix.dart       # Generation of matrix A for the Module-LWE problem
├── indcpa.dart           # Underlying IND-CPA scheme
├── kem.dart              # FO transform: IND-CCA2 KEM
├── shake.dart            # SHAKE128 (Keccak) from scratch
├── verify.dart           # Constant-time comparison and cmov
├── constant_time_comparison.dart  # Constant-time comparison wrapper
├── randombytes.dart      # Entropy generation (Random.secure)
├── noise_generator.dart  # Deterministic noise (not used in the main KEM)
├── kyber_kem.dart        # Public encapsulation/decapsulation API
├── kyber_keypair.dart    # Key pair generation
└── xkyber_symmetric.dart # AES-GCM symmetric encryption with the shared key

Code Extractions

Scheme Parameters (params.dart)

The implementation uses 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;

Key and ciphertext sizes are derived from these parameters:

const int KYBER_PUBLICKEYBYTES = 800;   // compressed pk + seed
const int KYBER_SECRETKEYBYTES = 1632;   // full sk
const int KYBER_CIPHERTEXTBYTES = 768;   // full ct

Each polynomial of 256 coefficients is encoded in 12 bits per coefficient (384 bytes), and the compressed version uses 3 bits (128 bytes).

Reductions: Barrett and Montgomery (reduce.dart)

Kyber requires efficient modular reductions. The implementation includes both methods:

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

Contrast with FIPS 203: The specification defines montgomeryReduce as a constant-time operation. In Dart, ~/ 65536 is an integer division that the Dart VM could optimize to a bit shift, but there is no guarantee. The JIT compiler may reorder operations and break constant time.

NTT (ntt.dart)

NTT is the computational core of Kyber. Iterative in-place implementation with 128 precomputed 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 with Montgomery reduction
      }
    }
  }
}

The zetas are the 256-th primitive root of unity in the field modulo 3329, precomputed as values in Montgomery domain:

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

Contrast with FIPS 203: Access to zetasOficial[k] with k++ per iteration is sequential and predictable. However, the C reference implementation uses pointers and direct memory access. In Dart, access to List<int> involves bounds checking and possible GC write barriers that the VM introduces without programmer control.

Polynomials: Compress/Decompress (poly.dart)

Compress reduces from 12 bits to 3 bits per coefficient:

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 inverts the operation:

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

CBD — Centered Binomial Distribution (poly.dart)

Noise is generated using the centered binomial distribution with η=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;
    }
  }
}

Contrast with FIPS 203: CBD involves a loop with bit shifting. The Dart VM does not guarantee that the for loop executes without GC interruptions, without JIT reordering, or without branch misprediction in the processor.

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

Contrast with FIPS 203: The FO transform is the most critical point for timing attacks. The comparison verify(c, cprime) must be constant-time. However, the Dart VM does not guarantee that the r |= a[i] ^ b[i] loop compiles without data-dependent branching.

SHAKE128 from Scratch (shake.dart)

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

Contrast with FIPS 203: Performance in Dart is significantly lower than in optimized C. In benchmarks, the Dart implementation can be 10-50x slower than the C reference.

Differences from the Reference Implementation (pq-crystals/C)

Conclusion

The implementation is functionally correct: all test vectors pass, encapsulation and decapsulation produce matching shared secrets. However, functional correctness does not imply cryptographic security in the presence of an attacker capable of measuring execution times, cache accesses, or power consumption.

The repository's archive reflects the conclusion that, in the current Dart/Flutter ecosystem, it is not possible to guarantee the constant-time properties that Kyber requires to be secure in a real adversarial environment.