Constant Time in Dart — VM LimitationsConstant Time in Dart — VM Limitations

Summary

The security of Kyber in IND-CCA2 mode critically depends on operations executing in constant time: the same number of CPU cycles regardless of the values of secret data. Dart, as a language running on a VM with JIT compilation and garbage collection, does not offer constant-time guarantees. This document analyzes the specific limitations identified during the implementation of xkyber_crypto.

What Does "Constant Time" Mean in Cryptography?

An operation is constant-time if its duration does not depend on secret values. For example:

// CONSTANT: the loop always executes 'len' iterations
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: each byte contributes equally
    }
    return result;
}

// NOT CONSTANT: early exit leaks the position of the first differing byte
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;  // time depends on where it fails
    }
    return true;
}

The constant version ensures that an attacker measuring comparison time cannot deduce how many bytes match.

Dart's Structural Problem

1. JIT Compilation and Reordering

Dart uses Just-In-Time (JIT) compilation during development and Ahead-Of-Time (AOT) compilation for production. In both cases, the compiler may reorder, merge, or eliminate operations that the programmer assumed were invariant:

// Intention: accumulate XOR without 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;
}

Potential problems:

• The Dart VM could optimize the loop if it detects that r is not used until the end, but there are no guarantees.
• The AOT compiler (gen_snapshot) can apply transformations that break the illusion of constant time.
• There is no @ConstantTime attribute or compiler directive to preserve timing semantics.

2. Garbage Collection (GC)

Dart has a generational GC with write barriers. When cryptographic code writes to a list, the VM may execute additional non-deterministic code:

r.coeffs[8 * i + j] = aj - bj;  // writes? triggers a write barrier?

Each write can activate the GC if the young generation fills up. This introduces timing variations of microseconds or milliseconds — orders of magnitude larger than the differences a timing attack seeks to exploit.

3. Bounds Checking on Lists

Every access to List<int> in Dart verifies that the index is within range:

a.coeffs[i] = barrettReduce(a.coeffs[i]);  // bounds check on every access

Although bounds checking is constant for valid indices, the VM may throw exceptions (slow, non-constant) on invalid indices. Worse: the optimizer may elide bounds checks in some loops but not others, introducing visible differences.

4. Integer Division and Modulo

Montgomery reduction requires:

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

In C, ~/ 65536 compiles to a right shift of 16 bits (>> 16), which is constant-time. In Dart, ~/ is an integer division that the JIT may or may not optimize depending on the platform and compilation phase.

5. Random.secure() and Entropy

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

Random.secure() depends on the underlying platform. In web browsers (Dart compiled to JavaScript), it uses window.crypto.getRandomValues(), which can exhaust system entropy and block. In native Flutter, it uses the operating system's randomness generator. There is no control over response time.

Identified Critical Points

Comparison with Languages That Do Offer Guarantees

Conclusion

The Dart VM was not designed for high-assurance cryptography. There is no:

• A ConstantTimeList<T> type that avoids bounds checking
• A @PreserveControlFlow attribute to prevent the JIT from optimizing loops
• A native constant-time comparison function verified by the community

Any pure-Dart implementation of Kyber that does not resort to native extensions (FFI with C/Rust) is vulnerable to timing attacks. The only viable solution in the Dart/Flutter ecosystem for post-quantum cryptography is to use bindings to native libraries such as liboqs or the pq-crystals reference implementation via dart:ffi.

The xkyber_crypto repository is archived as a testament that functional correctness is not sufficient: cryptographic security requires control over the machine that the language does not provide.