kiloparsec/CONCEALED-PROTOCOL-TIMING.md

# Concealed protocol timing assessment

Recorded 2026-10-22. This evaluates the current Elligator call graph, measures its implementation, and tests the proposed wall-clock roundup policy. It is not a demonstration of a private-key recovery attack or a proof that no side channel exists.

## 1. Correcting the original concern

The implementation is variable-time, but the original warning did not adequately distinguish public-input variation from secret-dependent leakage.

- The server calls `decode()` on the representative received in HELO. All bignum inputs in this path are public wire data. The long-lived server scalar enters libsodium's DH operation after that mapping; it does not enter the bignum implementation.
- The client uses libsodium to generate an ephemeral point, then bignum to convert/map its public coordinates. The successful Montgomery coordinate is recoverable from the transmitted representative. The low three torsion-selection bits are cleared by ordinary X25519 and do not contribute to its secret scalar.
- The client retries with independent random candidates when the inverse mapping fails. Discarded candidates are not reused. Elligator's [key-exchange reference](https://elligator.org/key-exchange) explicitly permits this variable retry count for properly random ephemeral keys.
- Client preparation precedes the first HELO. Measuring it remotely requires an independent connection-start reference. Server mapping affects the response path and is directly measurable in principle, but its inputs are public.

Consequently, these measurements must not be described as evidence that our server's private key leaks through bignum arithmetic. Current dataflow does not establish such a leak. This conclusion is based primarily on which values the arithmetic consumes, not on a low statistical score. Future changes that put secret scalars or secret-dependent hidden coordinates into this arithmetic require a new assessment.

## 2. Measurement method and scope

Host: Intel Core Ultra 9 275HX, 24 logical processors, Linux 7.1.8-legion-audio x86_64. JVM: OpenJDK 21.0.12. Kotlin 2.4.0. The original Native measurements below use the Linux x64 **debug test binary**. Subsequent optimized release results and JVM allocation profiling are recorded in the [snapshot qualification report](CONCEALED-PROTOCOL-QUALIFICATION.md#6-optimized-native-measurements).

The Elligator probe uses 64 warm-up rounds and 256 measured samples per class. Class order is shuffled each round with a fixed seed. The eight torsion cases share the same clamped scalar within each round; only the three low bits differ. Received representatives include random public inputs, a zero boundary case, and paired encodings differing only in ignored high bits. Inverse-map cases compare reference inputs that are representable or rejected. Generation uses fresh synthetic randomness; a separate equivalent loop records rejection counts. No key bytes are logged.

The JVM handshake probe performs all four actual cryptographic flights with fresh ephemeral keys and fixed synthetic identities, including the prefix parsing used by the connection. It excludes socket IO, application hooks, admission/queue waits and artificial delays. Its first sample is **not** a process-cold benchmark: earlier tests can have initialized classes. Padding is disabled to isolate cryptographic work.

Monotonic clocks measure elapsed time. Mean, median, p95, p99, maximum and exploratory Welch t statistics are retained with raw samples. Measurements are a single host run, without CPU isolation, a controlled thermal/frequency profile or adversarial co-resident load. GC/JIT, scheduler activity, autocorrelation and multiple comparisons prevent interpreting these numbers as a constant-time certificate.

## 3. Measured results

All times below are milliseconds; 256 measurements per listed group.

| Runtime | Operation | Median | p99 | Maximum |
| --- | --- | ---: | ---: | ---: |
| JVM | Decode random public representative | 2.790 | 4.197 | 5.872 |
| JVM | Encode representable public coordinate | 5.262 | 8.030 | 10.574 |
| JVM | Reject unrepresentable public coordinate | 2.503 | 3.808 | 5.925 |
| JVM | Generate fresh Elligator key pair | 7.603 | 27.407 | 34.354 |
| Native debug | Decode random public representative | 77.316 | 79.015 | 89.529 |
| Native debug | Encode representable public coordinate | 147.269 | 149.589 | 181.251 |
| Native debug | Reject unrepresentable public coordinate | 70.917 | 72.753 | 107.829 |
| Native debug | Generate fresh Elligator key pair | 154.524 | 537.195 | 766.529 |
| JVM | Client HELO preparation | 5.138 | 22.171 | 29.364 |
| JVM | Server prefix authentication | 2.494 | 4.775 | 5.087 |
| JVM | Server HELO response construction | 2.680 | 4.846 | 5.335 |
| JVM | All four crypto flights, without IO | 11.063 | 27.966 | 35.193 |

The eight matched torsion classes had median special-public-key times of **0.335–0.342 ms on JVM** and **6.105–6.198 ms on Native debug**. Exploratory maximum absolute Welch t against torsion class zero was 0.99 and 2.02 respectively. Those small scores are not evidence of constant-time execution; the accepted/rejected public-input encoding branches are deliberately distinguishable (t approximately 57 on JVM and 371 on Native).

The separate instrumented generation loop observed **1–12 candidates on JVM** and **1–13 on Native debug** in 256 runs each. This explains expected rejection-related tails. Its largest observed Native debug generation time was 1.075 seconds; this is a separate sample set from the actual-generator row above.

The revised handshake probe's first-in-probe sample took **198.175 ms**. It was not a controlled process-cold experiment, and startup/JIT/initialization effects were not separately attributed. The remaining warm samples are shown in the table. Neither 50 ms nor the observed warm maximum is a guaranteed execution bound.

Server prefix parsing and subsequent complete-HELO construction currently perform separate public Elligator mappings. Their costs therefore both belong in the actual response path. These measurements do not include the newly added failed-authentication decoy; that cost is measured separately in section 7.

## 4. Exact roundup-plus-jitter experiment

The tested policy is the user's actual proposal, rather than simply adding noise to the current time:

```text
release = ceil(completion / 50 ms) * 50 ms + J
J is uniformly selected from {0, 1, ..., 10} whole milliseconds
```

A deterministic test enumerates all 50,000 microsecond start phases and all eleven jitter choices. For 2 ms versus 3 ms computations, the mean target release still differs by exactly **1 ms**. Subtracting the same mean start time gives the same elapsed-latency difference. Jitter broadens the distributions but does not remove that mean difference under this phase model.

A boundary example is simpler: start at grid phase 47.5 ms. A 2 ms calculation completes at 49.5 ms and releases in 50–60 ms; a 3 ms calculation completes at 50.5 ms and releases in 100–110 ms. These supports are disjoint even after whole-millisecond jitter. Controlling or learning the relevant phase is an additional attacker capability; the example establishes a limitation of the mitigation, not an attack against our handshake.

An operation-start deadline selected **before** calculation, such as `start + 50 ms + J`, gives the same target distribution for both calculations while they fit the budget. Work exceeding the deadline, correlated scheduler delays, and local cache/CPU-contention observations remain outside that guarantee. Rounding the elapsed operation duration into 50 ms buckets also works only while the compared durations stay in the same bucket.

The coroutine experiment uses synthetic 2/3 ms CPU work, 100 samples per class per policy, randomized order and independently randomized grid phase before each sample. It uses a fixed **monotonic** grid, equivalent to a fixed wall-clock grid up to its origin for this experiment, without adjustments of the system wall clock. Jitter is an integer number of milliseconds. Cancellable delays round the remaining wait up to milliseconds and recheck the deadline; scheduler overshoot is measured rather than assumed absent. This is a scheduling experiment, separately labelled from the real Elligator measurements.

| Synthetic CPU work | Unshaped mean | Completion-grid mean | Start-selected deadline mean |
| --- | ---: | ---: | ---: |
| 2 ms | 2.006 ms | 32.465 ms | 54.527 ms |
| 3 ms | 3.006 ms | 34.590 ms | 55.061 ms |

No compute-budget overruns occurred in these synthetic 2/3 ms runs. The 100-sample live comparisons after shaping had absolute Welch t near 1.00 (completion grid) and 1.18 (start deadline), compared with approximately 2574 unshaped. This illustrates how much harder a single small sample set becomes to distinguish. It does **not** invalidate the exact boundary model or establish equal distributions: sampled phases/jitter and scheduler overshoot differ between classes. The exact model, rather than the noisy observed mean gap, establishes the residual grid-boundary effect.

## 5. Interpretation and next decisions

1. **Variable execution time is confirmed.** Different public inputs and accepted/rejected inverse-map branches have different costs. That fact alone is not a private-key disclosure.
2. **No demonstrated secret leak has been found in the current bignum dataflow.** The timing warning should be narrowed accordingly. This does not independently audit libsodium, platform bindings, the custom handshake or co-resident side channels.
3. **Grid roundup is remote timing shaping, not full erasure.** It can make individual timings much less informative. Bucket crossings remain, and independent random extra work, including random bignum divisions, does not supply a general elimination guarantee. Research also demonstrates that concurrent response ordering can expose timing differences despite network noise: [Van Goethem et al., USENIX Security 2020](https://www.usenix.org/conference/usenixsecurity20/presentation/van-goethem).
4. **Do not infer a universal 50 ms budget from this host.** Native debug timings, cold startup, device speed and load differ. Any production deadline policy needs configurable bounds, consistent externally observable success/failure handling, explicit overruns, cancellation and admission limits. Waiting must occur outside the cryptographic semaphore. A global release grid can itself introduce a periodic traffic pattern; this has not been tested as a network fingerprint here.
5. **No clock-padding or random-division policy was added.** Following the subsequent user request, one bounded decoy decryption was added to the HELO authentication-failure path; section 7 records its exact behavior and cost. It is not an authentication upgrade or a general timing-concealment guarantee. An independent protocol review and the remaining fuzz/platform qualification are still required.

## 6. Reproduction and artifacts

Ordinary test runs do not execute the expensive sampling loops. Enable them explicitly:

```sh
KILOPARSEC_TIMING_PROBE=1 KILOPARSEC_TIMING_SAMPLES=256 \
KILOPARSEC_TIMING_WARMUP=64 \
./gradlew '-Dorg.gradle.jvmargs=-Xmx2g -XX:MaxMetaspaceSize=1g' \
  jvmTest --tests '*Timing*' linuxX64Test --tests '*ElligatorTiming*' --console=plain
```

`KILOPARSEC_SHAPING_SAMPLES` controls the live synthetic sample count per class/policy (default 100). Fresh randomness in actual generation, CPU state and scheduling mean that repeating the command will not reproduce identical timings. A repeated invocation with unchanged source may be considered up-to-date by Gradle; add `--rerun-tasks` when a fresh sampling run is intended. That also reruns compilation prerequisites.

Local ignored artifacts under `build/concealed-timing/` contain `jvm.csv`, `linuxX64.csv`, `handshake-jvm.csv`, `shaping-samples.csv`, `shaping-summary.txt` and host/run metadata. The tables above preserve the relevant summary in versionable documentation; raw samples remain local build output.

## 7. Requested server-side decoy decryption

Each `ConcealedServerIdentity` now owns a separate random 32-byte throwaway scalar seed. When the real HELO envelope authentication throws `UnauthenticatedFlight`, the wrapper copies the seed, flips 1–8 distinct effective X25519 scalar bits (positions 3 through 253), and performs **one** additional envelope-decryption attempt with that copy. The temporary copy and mutation entropy are cleared afterward. The persistent seed and the real server key are unchanged; concurrent attempts use independent copies.

The dummy outcome is discarded even if it succeeds. It cannot create a response, invoke identity hooks, advance real handshake state or turn a failed authentication into success. Expected dummy authentication/parsing failures preserve the original failure. Cancellation, unexpected runtime failures and fatal errors propagate. Bad lengths, low-order peer inputs and admission rejection do not trigger an envelope-authentication decoy. Client ACK/session-record failures are not part of this HELO-specific mechanism.

Both prefix and full-envelope failure paths run inside the existing server crypto admission limit. There is no recursive retry, added coroutine delay, random division loop or added unauthenticated response. The local server option `ConcealedOptions.Handshake.decoyOnHelloAuthenticationFailure` defaults to `true`; set it to `false` to omit the extra attempt. It is not negotiated and does not change the wire format.

A separate JVM probe measured 64 samples per class after 16 warmups, randomized across the same eight synthetic HELOs. It exercises the actual identity/admission wrapper and real envelope authentication, without network IO:

| Case | Median disabled | Median enabled | Mean added work |
| --- | ---: | ---: | ---: |
| Valid header | 2.488 ms | 2.481 ms | -0.034 ms |
| Bad header authentication | 2.501 ms | 4.981 ms | 2.435 ms |
| Bad body authentication | 2.584 ms | 5.109 ms | 2.646 ms |

This approximately doubles failed-HELO CPU work on the measured JVM, while successful authentication adds no dummy work. X25519 is designed to be constant-time and the repeated Elligator decode consumes the same public representative; changing the dummy scalar therefore does not itself imply broad random timing variation. No Intel microarchitectural attack reproduction was performed, and effectiveness against the user's previously observed attacks has not been established by these tests.

Five new unit tests cover exact invocation bounds, successful dummy-result discard, expected versus unexpected exceptions, effective-bit mutation and erasure, concurrent copy independence, both actual failure stages, and preservation of real keys and a later valid handshake. Existing connection regression tests cover UDP injected noise and readiness behavior. The five new tests plus six connection tests passed on **JVM, Kotlin/JS and Linux Native (11 each)** after the production change; Android release and Wasm compilation also passed. The actual-path JVM failure timing probe passed separately.

The additional opt-in probe is `HelloFailureTimingProbeTest`; output is `build/concealed-timing/helo-failure-jvm.csv`. Run with `KILOPARSEC_TIMING_PROBE=1`; `KILOPARSEC_FAILURE_TIMING_SAMPLES` controls samples per class (default 64). The earlier `*Timing*` JVM filter includes it on subsequent fresh runs.