What are the security characteristics of the FixedPointCombMultiplier().multiply API

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

What are the security characteristics of the FixedPointCombMultiplier().multiply API

Drucker, Nir

Hello all,

 

I observed on [1] that “Early versions of BC didn't have side-channel attacks in mind, but we've gradually improved things over the years. Still, things aren't perfect; if you are concerned about a particular algorithm we could advise as to how protected it is. However, please ask these sort of questions on the mailing list in future”.

 

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

 

Reply | Threaded
Open this post in threaded view
|

Re: What are the security characteristics of the FixedPointCombMultiplier().multiply API

Peter Dettman-3
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