Impact
When the exponent is bigger than r, the group order of the pairing target group GT, the exponentiation à la GLV (ExpGLV) can sometimes give incorrect results compared to normal exponentiation (Exp).
The issue impacts all users using ExpGLV for exponentiations in GT. This does not impact Exp and ExpCyclotomic which are sound. Also note that GLV methods in G1 and G2 are sound and not impacted.
Patches
Fix has been implemented in pull request #451 and merged in commit ec6be1a to master branch.
The fix increased the bounds of the sub-scalars by 1. In fact, since #213, we use a fast scalar decomposition that tradeoffs divisions (needed in the Babai rounding) by right-shifts. We precompute b=2^m*v/d (m > log2(d)) and then at runtime compute scalar*b/2^m (v is a lattice vector and d the lattice determinant). This increases the bounds on sub-scalars by 1 which we check at runtime before increasing the loop size (we don't target constant-timeness). m is chosen to be a machine word twice big than log2(d) so that we rarely need to increase the loop size. Hence why the issue happens only sometimes if we omit to increase the bounds. This bounds increase was implemented in G1 and G2 but forgot in GT.
Workarounds
Updating to v0.12.1+. Alternatively, use Exp or ExpCyclotomic instead. We are not aware of any users using ExpGLV anyway.
References
Acknowledgement
The vulnerability was reported by Antonio Sanso @ EF.
Impact
When the exponent is bigger than
r, the group order of the pairing target groupGT, the exponentiation à la GLV (ExpGLV) can sometimes give incorrect results compared to normal exponentiation (Exp).The issue impacts all users using
ExpGLVfor exponentiations inGT. This does not impactExpandExpCyclotomicwhich are sound. Also note that GLV methods in G1 and G2 are sound and not impacted.Patches
Fix has been implemented in pull request #451 and merged in commit ec6be1a to master branch.
The fix increased the bounds of the sub-scalars by 1. In fact, since #213, we use a fast scalar decomposition that tradeoffs divisions (needed in the Babai rounding) by right-shifts. We precompute
b=2^m*v/d (m > log2(d))and then at runtime computescalar*b/2^m(vis a lattice vector anddthe lattice determinant). This increases the bounds on sub-scalars by 1 which we check at runtime before increasing the loop size (we don't target constant-timeness).mis chosen to be a machine word twice big thanlog2(d)so that we rarely need to increase the loop size. Hence why the issue happens only sometimes if we omit to increase the bounds. This bounds increase was implemented in G1 and G2 but forgot in GT.Workarounds
Updating to
v0.12.1+. Alternatively, useExporExpCyclotomicinstead. We are not aware of any users usingExpGLVanyway.References
Acknowledgement
The vulnerability was reported by Antonio Sanso @ EF.