ghsa-q3hw-3gm4-w5cr
Vulnerability from github
Description
The summary is that the proof of knowledge associated to a commitment is crucial to bind the commitment to the actual circuit variables that were supposed to be committed. However, the same σ is used for all proofs of knowledge for the commitments, which allows mixing between them, making it possible to fix the value of all but one commitment before choosing the circuit variable assignments.
In more detail:
To simplify notation, let us consider the case of two commitments, each to only a single variable. Let's say the basis elements for those commitments are K_0 and K_1. Then the proving key will contain K_0 and K_1, and also σ*K_0 and σ*K_1 for the proof of knowledge. The honest prover assigning a to the first circuit variable and b to the second will then produce commitments
D_0 = a*K_0
D_1 = b*K_1
Out of the two D's, a challenge r for the commitment folding will be generated. The folded commitment will then be
D_folded = D_0 + r*D_1 = a*K_0 + r*b*K_1
The honest prover will supply a fitting proof of knowledge
P = a*(σ*K_0) + r*b*(σ*K_1)
Now the verifier will only use all of this in two ways:
1. In the check of the Groth16 proof itself, where only the sum D_0 + D_1 is used.
2. In the proof of knowledge check, where it will be verified that P is indeed σ*(D_0 + r*D_1), with r calculated from D_0 and D_1 as before.
This has the following implications. In the following, a malicious prover's points will have an apostrophe appended, and we keep D_0 etc. for the legitimate values:
1. A malicious prover is only forced to provide D'_0 and D'_1 such that the sum is correct. So they can use arbitrary D'_0 as long as they set D'_1 = D_0 + D_1 - D'_0.
2. After choosing D'_0 and D'_1, the prover can always calculate r. Evaluating σ*(D'_0 + r*D'_1) is then possible as long as both D'_0 and D'_1 are linear combinations of basis elements for which σ times that basis element is known. In particular, this works as long as D'_0 and D'_1 are linear combinations of K_0 and K_1.
The upshot is that a malicious prover can choose arbitrary a' and b', and then set
D'_0 = a'*K_0 + b'*K_1
D'_1 = (a - a')*K_0 + (b - b')*K_1
Then they calculate r for this, and set
P = (a' + r*(a-a'))*(σ*K_0) + (b' + r*(b-b'))*(σ*K_1)
This will then be accepted as a valid proof. Yet the first commitment point can be chosen completely independently of a and b, so in particular the malicious prover can use a constant for this, so that they will know the in-circuit challenge that will be added to the public inputs before they have to choose the witness assignments. For most use cases of such challenges (for proving things with Fiat-Shamir, random linear combinations etc.) this causes a critical soundness problem.
The problem generalizes to more than two commitments and commitments to more than one circuit variable each; one can freely choose all but one commitment as arbitrary linear combinations of the basis elements for all commitments, and then must choose the one remaining commitment in such a way that the sum is correct.
The root cause of the issue is that the σ used for the proofs of knowledge is the same, allowing to mix between the basis elements, as one has σ times them available for all of them.
So the fix is to have a separate σ for each commitment. So in our example above, the proving key would have the basis elements K_0 and K_1, and for the proofs of knowledge now σ_0*K_0 and σ_1*K_1. Folding the commitments would not be possible in the same way now, so the verifier will have to do more pairings. The prover could still provide a folded proof of knowledge however. With
D_0 = a*K_0
D_1 = b*K_1
the proof of knowledge would be
P = a*(σ_0*K_0) + r*b*(σ_1*K_1)
For later, let us use notation for the unfolded proofs of knowledge
P_0 = a*(σ_0*K_0)
P_1 = b*(σ_1*K_1)
so that
P = P_0 + r*P_1
The verifying key would need G and σ_0*G and σ_1*G. To check the two unfolded proofs of knowledge would be the checks
e(P_0, G) = e(D_0, σ_0*G)
e(P_1, G) = e(D_1, σ_1*G)
As r is a challenge derived from D_0 and D_1, we may instead check
e(P_0, G) + r*e(P_1, G) = e(D_0, σ_0*G) + r*e(D_1, σ_1*G)
The left hand side is
e(P_0, G) + r*e(P_1, G) = e(P_0 + r*P_1, G) = e(P, G)
So the prover can just provide P and then the verifier checks
e(P, G) = e(D_0, σ_0*G) + r*e(D_1, σ_1*G)
Unfortunately, the right hand side can't be folded as before, as there isn't a side of the pairing that is kept constant between the pairings as before. So the verifier will need to have a pairing for each commitment on the right hand side.
Impact
It is a soundness issue - in case of multiple commitments used inside the circuit the prover is able to choose all but the last commitment. As we use the commitments for optimized non-native multiplication, lookup checks etc. as random challenges, then it could impact the soundness of the whole circuit.
However, using multiple commitments has been discouraged due to the additional cost to the verifier and it has not been supported in the recursive in-circuit Groth16 verifier and Solidity verifier. So we expect the impact of the issue be very small - only for the users who have implemented the native Groth16 verifier or are using it with multiple commitments. We do not have information of such users.
Patches
The issue has been patched in e7c66b000454f4d2a4ae48c005c34154d4cfc2a2
Workarounds
The recommendation has been to use only a single commitment and then derive in-circuit commitments as needed using std/multicommit package.
References
See the correspondence above.
{
"affected": [
{
"database_specific": {
"last_known_affected_version_range": "\u003c= 0.10.0"
},
"package": {
"ecosystem": "Go",
"name": "github.com/consensys/gnark"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "0.11.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2024-45039"
],
"database_specific": {
"cwe_ids": [
"CWE-200"
],
"github_reviewed": true,
"github_reviewed_at": "2024-09-06T19:53:20Z",
"nvd_published_at": "2024-09-06T13:15:04Z",
"severity": "MODERATE"
},
"details": "### Description\n\nThe summary is that the proof of knowledge associated to a commitment is crucial to bind the commitment to the actual circuit variables that were supposed to be committed. However, the same \u03c3 is used for all proofs of knowledge for the commitments, which allows mixing between them, making it possible to fix the value of all but one commitment before choosing the circuit variable assignments.\n\nIn more detail:\nTo simplify notation, let us consider the case of two commitments, each to only a single variable. Let\u0027s say the basis elements for those commitments are `K_0` and `K_1`. Then the proving key will contain `K_0` and `K_1`, and also `\u03c3*K_0` and `\u03c3*K_1` for the proof of knowledge. The honest prover assigning a to the first circuit variable and b to the second will then produce commitments\n`D_0 = a*K_0`\n`D_1 = b*K_1`\nOut of the two D\u0027s, a challenge r for the commitment folding will be generated. The folded commitment will then be\n`D_folded = D_0 + r*D_1 = a*K_0 + r*b*K_1`\nThe honest prover will supply a fitting proof of knowledge\n`P = a*(\u03c3*K_0) + r*b*(\u03c3*K_1)`\n\nNow the verifier will only use all of this in two ways:\n1. In the check of the Groth16 proof itself, where only the sum `D_0 + D_1` is used.\n2. In the proof of knowledge check, where it will be verified that P is indeed `\u03c3*(D_0 + r*D_1)`, with r calculated from `D_0` and `D_1` as before.\n\nThis has the following implications. In the following, a malicious prover\u0027s points will have an apostrophe appended, and we keep `D_0` etc. for the legitimate values:\n1. A malicious prover is only forced to provide `D\u0027_0` and `D\u0027_1` such that the sum is correct. So they can use arbitrary `D\u0027_0` as long as they set `D\u0027_1 = D_0 + D_1 - D\u0027_0`.\n2. After choosing `D\u0027_0` and `D\u0027_1`, the prover can always calculate r. Evaluating `\u03c3*(D\u0027_0 + r*D\u0027_1)` is then possible as long as both `D\u0027_0` and `D\u0027_1` are linear combinations of basis elements for which \u03c3 times that basis element is known. In particular, this works as long as `D\u0027_0` and `D\u0027_1` are linear combinations of `K_0` and `K_1`.\n\nThe upshot is that a malicious prover can choose arbitrary a\u0027 and b\u0027, and then set\n`D\u0027_0 = a\u0027*K_0 + b\u0027*K_1`\n`D\u0027_1 = (a - a\u0027)*K_0 + (b - b\u0027)*K_1`\nThen they calculate r for this, and set\n`P = (a\u0027 + r*(a-a\u0027))*(\u03c3*K_0) + (b\u0027 + r*(b-b\u0027))*(\u03c3*K_1)`\nThis will then be accepted as a valid proof. Yet the first commitment point can be chosen completely independently of a and b, so in particular the malicious prover can use a constant for this, so that they will know the in-circuit challenge that will be added to the public inputs before they have to choose the witness assignments. For most use cases of such challenges (for proving things with Fiat-Shamir, random linear combinations etc.) this causes a critical soundness problem.\n\nThe problem generalizes to more than two commitments and commitments to more than one circuit variable each; one can freely choose all but one commitment as arbitrary linear combinations of the basis elements for all commitments, and then must choose the one remaining commitment in such a way that the sum is correct.\n\nThe root cause of the issue is that the \u03c3 used for the proofs of knowledge is the same, allowing to mix between the basis elements, as one has \u03c3 times them available for all of them.\nSo the fix is to have a separate \u03c3 for each commitment. So in our example above, the proving key would have the basis elements `K_0` and `K_1`, and for the proofs of knowledge now `\u03c3_0*K_0` and `\u03c3_1*K_1`. Folding the commitments would not be possible in the same way now, so the verifier will have to do more pairings. The prover could still provide a folded proof of knowledge however. With\n`D_0 = a*K_0`\n`D_1 = b*K_1`\nthe proof of knowledge would be\n`P = a*(\u03c3_0*K_0) + r*b*(\u03c3_1*K_1)`\nFor later, let us use notation for the unfolded proofs of knowledge\n`P_0 = a*(\u03c3_0*K_0)`\n`P_1 = b*(\u03c3_1*K_1)`\nso that\n`P = P_0 + r*P_1`\n\nThe verifying key would need `G` and `\u03c3_0*G` and `\u03c3_1*G`. To check the two unfolded proofs of knowledge would be the checks\n`e(P_0, G) = e(D_0, \u03c3_0*G)`\n`e(P_1, G) = e(D_1, \u03c3_1*G)`\nAs r is a challenge derived from D_0 and D_1, we may instead check\n`e(P_0, G) + r*e(P_1, G) = e(D_0, \u03c3_0*G) + r*e(D_1, \u03c3_1*G)`\nThe left hand side is\n`e(P_0, G) + r*e(P_1, G) = e(P_0 + r*P_1, G) = e(P, G)`\nSo the prover can just provide P and then the verifier checks\n`e(P, G) = e(D_0, \u03c3_0*G) + r*e(D_1, \u03c3_1*G)`\nUnfortunately, the right hand side can\u0027t be folded as before, as there isn\u0027t a side of the pairing that is kept constant between the pairings as before. So the verifier will need to have a pairing for each commitment on the right hand side.\n\n### Impact\n\nIt is a soundness issue - in case of multiple commitments used inside the circuit the prover is able to choose all but the last commitment. As we use the commitments for optimized non-native multiplication, lookup checks etc. as random challenges, then it could impact the soundness of the whole circuit.\n\nHowever, using multiple commitments has been discouraged due to the additional cost to the verifier and it has not been supported in the recursive in-circuit Groth16 verifier and Solidity verifier. So we expect the impact of the issue be very small - only for the users who have implemented the native Groth16 verifier or are using it with multiple commitments. We do not have information of such users.\n\n### Patches\n\nThe issue has been patched in e7c66b000454f4d2a4ae48c005c34154d4cfc2a2\n\n### Workarounds\n\nThe recommendation has been to use only a single commitment and then derive in-circuit commitments as needed using [std/multicommit](https://pkg.go.dev/github.com/consensys/gnark/std/multicommit) package.\n\n### References\n\nSee the correspondence above.\n",
"id": "GHSA-q3hw-3gm4-w5cr",
"modified": "2024-11-20T19:26:02Z",
"published": "2024-09-06T19:53:20Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/Consensys/gnark/security/advisories/GHSA-q3hw-3gm4-w5cr"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2024-45039"
},
{
"type": "WEB",
"url": "https://github.com/Consensys/gnark/commit/e7c66b000454f4d2a4ae48c005c34154d4cfc2a2"
},
{
"type": "PACKAGE",
"url": "https://github.com/Consensys/gnark"
},
{
"type": "WEB",
"url": "https://pkg.go.dev/vuln/GO-2024-3122"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:L/AC:L/PR:N/UI:N/S:U/C:N/I:H/A:N",
"type": "CVSS_V3"
}
],
"summary": "gnark\u0027s Groth16 commitment extension unsound for more than one commitment"
}
Sightings
| Author | Source | Type | Date |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or seen somewhere by the user.
- Confirmed: The vulnerability is confirmed from an analyst perspective.
- Exploited: This vulnerability was exploited and seen by the user reporting the sighting.
- Patched: This vulnerability was successfully patched by the user reporting the sighting.
- Not exploited: This vulnerability was not exploited or seen by the user reporting the sighting.
- Not confirmed: The user expresses doubt about the veracity of the vulnerability.
- Not patched: This vulnerability was not successfully patched by the user reporting the sighting.