Timing side channel in scalar multiplication

[bleichenbacher-daniel]

There is a significant timing channel in the scalar multiplication.

Analysis

The analysis of the library was performed by measuring the time of scalar multiplications over secp256r1 and secp256k1.
To minimize the probability of false positives a large number of tests (200'000 per curve) were performed.

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 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.

This test confirmed that there is a correlation between the timing of ECDH operations and the most 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 300 $\mu s$.

Code

The following code snippet was used to collect individual measurements.

    let buffer = crypto.randomBytes(size);
    let n = BigInteger.fromBuffer(buffer);
    const start = process.hrtime.bigint();
    // uses addition subtraction chain.
    let pt = ecparams.G.multiply(n);
    const time = process.hrtime.bigint() - start;