Timing side channel in ECDH.

[bleichenbacher-daniel]

There is a significant timing side channel in the computation of ECDH.

Analysis

The analysis was done under node using version 0.2.0 of ecc-jsbn.
Curves that were analyzed are secp224r1 and secp256r1.

The analysis of the library was performed on actual measurements.
A large number of tests (50'000 per curve) was performed to minimize the
probability of false positives.

This analysis takes all measurements, selects a fraction (1/2, 1/4, ...) of the
results with the fastest timings and then uses some characteristic of the
private key or the value k used to compute ECDSA signatures to
divide the results into multiple sets. A Chi-squared test is then performed
to determine if the distribution of the size of the obtained sets is
different from the expected distribution.

I.e., the tests confirmed that there is a correlation between the timing
and the most significant bits of the private key, the bit-length of the private key
and the least significant bits of the private key.

Timing differences

The timing difference between measurements with private keys having 4 leading
0-bits and other private keys is about 250 $\mu s$ for secp224r1 and about 400 $\mu s$
for secp256r1. This is a rather large difference.

Measurements

The timing measurements were taken for the method deriveSharedSecret. I.e.,

    const privateKey = new ECKey(curve);
    const start = process.hrtime.bigint();
    let shared = priv.deriveSharedSecret(publicKey);
    const time = process.hrtime.bigint() - start;

Potential causes

At this point no analysis of the source code has been performed.