Hi Nir,

Apologies for the delayed reply.

FixedPointCombMultiplier uses a comb-style multiplication with

precomputed multiples of the curve basepoint. It is constant-time in the

following ways:

1. Bits of the secret scalar are converted into table indices without

branching.

2. The actual table lookup is performed also without branching on the

index, and in a cache-safe way (all potential values at the given

position are loaded and masked together based on the index).

3. Each table entry is offset by a fixed amount so that the point at

infinity does not appear in the table. This requires a final

(unconditional) addition to fix-up the result.

However, there are caveats:

1. The API gives us the secret as a BigInteger, and it is converted to

fixed-size int[] using Nat.fromBigInteger. There will be an unavoidable

(small?) side-channel here for values that become shorter than the

maximum length across a 32-bit boundary.

2. We are still using point addition formulae that handle incidental

doublings and/or infinities with a branch. Given the values in the

lookup table and the constrained scalar, maybe this can only affect the

final loop iteration and/or the offset addition.

Regards,

Pete Dettman

On 25/5/20 3:45 pm, Drucker, Nir wrote:

> My question:

>

> -----------------

>

> I have an ECC P-256 private (secret) key (d) and I would like to

> generate the associated public key using BC. For that I am using

>

> ECParameterSpec P256_SPEC =

> ECNamedCurveTable.getParameterSpec(SECP256R1_CURVE);

>

> ECPoint ecPoint = new

> FixedPointCombMultiplier().*multiply*(P256_SPEC.getG(), d);

>

>

>

> Is the above “multiply” API runs in constant-time? i.e., does the

> underlying implementation include branches that depend on the secret “d”

> or access the memory in a way that depends on (d)?

>

> Does it act in this way on all platforms?

>

> Thanks,

>

> Nir Drucker.

>

> [1]

https://github.com/bcgit/bc-java/issues/383