Consensys Gnark Denial-of-Service Vulnerability in Scalar Multiplication via Fake-GLV Algorithm

A denial-of-service vulnerability has been identified in Consensys Gnark version 0.12.0, when computing scalar multiplication using the fake-GLV algorithm. The vulnerability arises because the algorithm can enter a very slowly converging loop for certain inputs, particularly scalars of the form 'order - k' where k is small. This issue can cause the prover to get stuck, potentially leading to a denial-of-service condition.

Impact

Exploitation of this vulnerability can cause the prover to become unresponsive, stuck in a loop that takes an excessively long time to converge, especially with certain scalar values.

Reproduction

The vulnerability can be reproduced by using the fake-GLV algorithm for scalar multiplication in Gnark version 0.12.0, with scalars that are small negative values or of the form 'order - k'. This can be done by adding a test case that uses such scalar values, which will trigger the denial-of-service condition by causing the computation to take an unacceptably long time.

Remediation

Users can update to Consensys Gnark version 0.13.0 or later, where this vulnerability has been patched. The update can be applied by changing the Gnark version in the project's go.mod file and then recompiling the project.