Minerva vulnerability + patch

[Ján Jančár]

Hi all,
we have recently disclosed a vulnerability in ECDSA on binary field curves in
the SunEC library used in OpenJDK at:

https://minerva.crocs.fi.muni.cz

We have prepared a patch for this earlier, which was sent to Oracle along with
the report of the vulnerability. As the vulnerability is not fixed at this time,
I am resending the patch here.


*Vulnerability description*
Timing leak in ECDSA signature generation on binary field curves (ec2) in the
SunEC library (libsunec.so). The library essentially leaks the bit-length of the
secret nonce used in the scalar multiplication via the duration of scalar
multiplication.

This leak is present in all scalar multiplication on binary field curves in
SunEC, but can be abused in the case of ECDSA, where an attacker that is able to
measure the duration of signing of a few hundreds or thousands of known messages
can use a lattice attack based on the Hidden Number Problem [1] to reconstruct
the private key used, as demonstrated in [2].


*Issue*
The issue is in ec_GF2m_pt_mul_mont in ec2_mont.c which starts the Montgomery
ladder at the most significant set bit thus leaking bit-length by the duration
of the loop. This is necessary because the addition formulas used are incomplete
(they cannot handle the point at infinity correctly) and thus the computation of
the ladder cannot start past the end of the scalar at some fixed bit-length (of
the order of the curve for example). If it did, the variables (x1, z1) would
have to be initialized with the point at infinity, which is not even
representable in the coordinates that are used here.


*Affected*
Java 7 - Java 12 (current master) seems to all be affected, because
ec_GF2m_pt_mul_mont was not changed during that time and
ECDSA_SignDigestWithSeed calls it through this call chain:

ECDSA_SignDigestWithSeed
 -> ec_points_mul
   -> ECPoints_mul
     -> group->points_mul == ec_pts_mul_basic
       -> ECPoint_mul
         -> group->point_mul == ec_GF2m_pt_mul_mont

Notice also the pointless detour through the multi-scalar multiplication
functions which then short circuit to the single-scalar multiplication function
when only one input is provided.


*Mitigation*
One mitigation, that was presented in [2] and is used in quite a few libraries,
is to blind the bit-length of the secret nonce (and any secret scalar used in EC
point multiplication, so private key in ECDH, etc.) as follows:

  Instead of computing [k]G, with k being the nonce, compute
  k* = k + 2*n (if log_2(k + n) = log_2(n))
     = k + n (else)
  then compute [k*]G, which = [k]G, because n is the order of
  the subgroup. The log_2(k*) is then a fixed value, so nothing
  leaks.

This fixes the bit-length of k*, such that the distribution of
k = k* mod n remains unaffected (and so ECDSA is ok with regards to lattice
attacks on biased nonces) and [k*]G = [k]G so the mitigation is correct. Other
mitigations might include using complete addition formulas, which will allows
the ladder to start at any bit past the end of the scalar, thus it might be
fixed to the order bit-length.

The patch does the following to fix the issue:


 - ec.c:
   * Splits ec_points_mul to ec_point_mul and ec_points_mul, so
     that the single-scalar multiplication doesn't go through
     ECPoints_mul and the multi-scalar functions.
   * Cleans up some ifdef'ed code that really has no purpose to
     be there.
   * Adds the mitigation to the ECDSA sign function.

 - ecl_mult.c, ecl.h:
   * Introduces an argument to the ECPoint_mul and ECPoints_mul
     function that specifies whether to reduce the scalar modulo
     the order or not. This is necessary because the mitigation
     in ECDSA adjust the scalar to be bigger than the order. So
     reducing here would negate the effect. This argument is
     false (not reduce) only in the ECDSA sign call site.

 - ecp_jm.c:
   * Changes the orderBitSize bound in the ec_GFp_pt_mul_jm_wNAF
     function to take the maximum of the order bit size and the
     scalar bit size. For reduced scalars, this is constant and
     is equal to the order bit size. For scalars produced as a
     result of the above mitigation, this is larger than the
     order bit size, but still constant.

 - ecp_aff.c, ec2_aff.c:
   * Use the new parameter to the ECPoint_mul function in the
     pubkey validation functions.

After applying this patch, all tests passed on my end, I tested with:

make test TEST="sun/security/ec"

With this patch applied, one issue could still be present. Since the scalars
passed to the scalar multiplication function will not be reduced, there is a
possibility that the point at infinity is reached as an intermediate value
during computation.

Looking at the prime field code, there it should not be an issue, as the
formulas handle the case of a point at infinity by short circuiting and
returning the correct value. The timing difference by the short-circuit would be
minuscule in this case and mitigated by the currently applied timing measure.

Looking at the binary field case might pose a problem currently, as the formulas
are incomplete (which is actually the root cause of this whole vulnerability)
and do not short-circuit on the point at infinity. This point doesn't really
have a representation in the coordinates used, but could be represented and
detected as (0, 0), then the formulas could be made to handle this and
short-circuit to the correct result. It can be shown that for scalars of the
form k + n or k + 2n, with k in [1, n-1], the intermediate value of [n]G or
[2n]G is is only reached in Montgomery ladder for a few values so that this is
actually not an issue.


[1]: D. Boneh, R. Venkatesan: Hardness of computing the most significant bits of
secret keys in Diffie-Hellman and related schemes;
https://crypto.stanford.edu/~dabo/abstracts/dhmsb.html

[2]: B. B. Brumley, N. Tuveri: Remote Timing Attacks are Still Practical;
https://eprint.iacr.org/2011/232.pdf

Cheers,
Jan


-------------- next part --------------
A non-text attachment was scrubbed...
Name: kfix.diff
Type: text/x-patch
Size: 26320 bytes
Desc: not available
URL: <https://mail.openjdk.org/pipermail/security-dev/attachments/20191003/22352e0c/kfix.diff>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <https://mail.openjdk.org/pipermail/security-dev/attachments/20191003/22352e0c/signature.asc>