Severity: Medium
The Fiat-Shamir implementation in both Verifier.pre.sol and HyperKZGHelpers.pre.sol lacks additional entropy sources, making challenges predictable and potentially vulnerable to circuit backdooring attacks as described in the How to Prove False Statements paper.
The issue is present in two key locations in the codebase:
function make_transcript(result_ptr, plan_ptr, table_lengths_ptr, commitments_ptr) -> transcript_ptr {
transcript_ptr := mload(FREE_PTR)
mstore(FREE_PTR, add(transcript_ptr, WORD_SIZE))
mstore(transcript_ptr, INITIAL_TRANSCRIPT_STATE)
append_calldata(transcript_ptr, plan_ptr, calldataload(sub(plan_ptr, WORD_SIZE)))
append_calldata(transcript_ptr, result_ptr, calldataload(sub(result_ptr, WORD_SIZE)))
append_array(transcript_ptr, table_lengths_ptr)
let commitment_len := mload(commitments_ptr)
mstore(commitments_ptr, mul(commitment_len, 2))
append_array(transcript_ptr, commitments_ptr)
mstore(commitments_ptr, commitment_len)
mstore(mload(FREE_PTR), mload(transcript_ptr))
mstore(add(mload(FREE_PTR), WORD_SIZE), 0)
mstore(transcript_ptr, keccak256(mload(FREE_PTR), add(UINT64_SIZE, WORD_SIZE)))
}function run_transcript(com_ptr, v_ptr, w_ptr, transcript_ptr, ell) -> r, q, d {
append_calldata(transcript_ptr, com_ptr, mul(WORDX2_SIZE, sub(ell, 1)))
r := draw_challenge(transcript_ptr)
append_calldata(transcript_ptr, v_ptr, mul(WORDX3_SIZE, ell))
q := draw_challenge(transcript_ptr)
append_calldata(transcript_ptr, w_ptr, WORDX6_SIZE)
d := draw_challenge(transcript_ptr)
}This function has three critical issues:
- It initializes the transcript with a fixed constant INITIAL_TRANSCRIPT_STATE
- It only includes deterministic inputs (plan, result, table lengths, commitments)
- It does not incorporate any unpredictable entropy sources like block-related data
The security of the Fiat-Shamir transform relies on the unpredictability of challenges. Without additional entropy sources, challenges are entirely determined by the proof data and public inputs, making it easier for a malicious prover to predict challenges and potentially craft proofs for false statements.
This vulnerability is particularly relevant in light of the How to Prove False Statements paper (Khovratovich, Rothblum, and Soukhanov), which demonstrates how a malicious circuit can predict its own Fiat-Shamir challenges when insufficient entropy is used in sections 1.1, 3.1, and 5. The paper shows that for every choice of Fiat-Shamir hash function, there exists an instantiation of a widely-used GKR-based protocol that is not adaptively sound when compiled with the Fiat-Shamir transform.
The impact is assessed as Medium because:
- It increases the feasibility of circuit backdooring attacks, where a malicious prover can construct a circuit that predicts its own challenges.
- It makes challenges more predictable for sophisticated attackers, weakening the security guarantees of the zero-knowledge proof system.
- It creates conditions where a malicious prover could potentially prove false statements, violating the soundness property of the protocol.
- The inclusion of public inputs in the transcript provides some mitigation, but doesn't fully address the vulnerability.
The likelihood is assessed as Medium because:
- Exploiting this vulnerability requires sophisticated knowledge of the protocol and cryptographic techniques, limiting the pool of potential attackers.
- The attacker would need to construct a specialized circuit that can predict its own challenges, which requires significant expertise.
A malicious prover could:
- Analyze the deterministic challenge generation process in the make_transcript function.
- Since all inputs to the transcript are deterministic and known to the prover, they can predict exactly what challenges will be generated.
- Construct a circuit that simulates this process and predicts its own challenges based on the known inputs.
- Design the circuit to output a specific value when evaluated at a point, but prove a different value using the predicted challenges.
This attack becomes more feasible without additional entropy sources that the prover cannot predict, as demonstrated in the "How to Prove False Statements" paper.
// SPDX-License-Identifier: UNLICENSED
// This is licensed under the Cryptographic Open Software License 1.0
pragma solidity ^0.8.28;
import {Test} from "forge-std/Test.sol";
import "../../src/base/Constants.sol";
import "../../src/base/Errors.sol";
import {HyperKZGVerifier} from "../../src/hyperkzg/HyperKZGVerifier.pre.sol";
import {Transcript} from "../../src/base/Transcript.sol";
/**
* @title HyperKZGFiatShamirVulnerabilityCorrectTest
* @notice Corrected tests demonstrating valid Fiat-Shamir vulnerabilities in the HyperKZG implementation
*/
contract HyperKZGFiatShamirVulnerabilityCorrectTest is Test {
// Reuse the existing test setup from HyperKZGVerifierTest
function _smallValidProof()
internal
pure
returns (
bytes memory proof,
uint256[1] memory transcript,
uint256[2] memory commitment,
uint256[] memory x,
uint256 y
)
{
proof = hex"0000000000000001" hex"1f2e45337f9b8344112089d02a9827c05864124c9d68e6dfe4ae4b1ef18b8bec"
hex"0603731e181537ca4cac7f28123622a175a7181b08404a64b1197c3a8adee75c" hex"0000000000000002"
hex"195601834abe3b06307843dfb2bda53c463acac5ce7452fe7f9afb76ef076159"
hex"01b06ce4e5c076c62ee49bea6c8c0d3475c9c4203863f33e407c032f104d7929"
hex"0244bf82e008d1628941372c47440cf0b7ddf46a4e07f370e99246946d2c2f96"
hex"1fac3ee761eb0bf01d1be7d167923af7a75802fb6daaf7c93b17e48bdb93582a"
hex"10b80f8b7f4694399b345de519ef1d6580dbe54d0c0e78c808ca1108146ca7e5"
hex"249c5130fc843ff6fa68d4ab85a5254f12f04d615289e5c00e42c22b867eebab"
hex"20aaca7d9451a200e417af702479ee0bd90a19d25f90bc5ac31515a2510ecbf9"
hex"13880503efe944d65ff45424e0c07237dbb4bbfa7d8dcbed7c0f234d94afd8c0"
hex"0afe9d625909d59d10259307138122091a2a4d81d7e419359e9a3b70916edade"
hex"12f9228a1c7fa913c0e3b4b20ff5cf106c9555c20c668e6441dfb3fa1a174626"
hex"18977d28d54a74822b9816495ab7909d9db911b3d107a7ccbb758baa94217fd5"
hex"097467f5beafcf7a6b77c515a0876800db96837e5e279cd8a0d3f86deb571fb7";
transcript = [0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470];
commitment = [
0x0bceea30108fed3f7c8e53e56a3aedf0de0bc26292e469ab525f1ac9fe93c758,
0x126f299ba3b83331a6901a281b0982b87f154efe57ac4da1f7c51a97dda59e1b
];
x = new uint256[](2);
x[0] = 0x7;
x[1] = 0x5;
y = 17;
}
/**
* @notice Helper function to append a uint256 to a transcript
* @param transcript The transcript to append to
* @param value The value to append
* @return The updated transcript
*/
function appendUint(uint256[1] memory transcript, uint256 value)
internal
pure
returns (uint256[1] memory)
{
uint256[] memory values = new uint256[](1);
values[0] = value;
return Transcript.__appendArray(transcript, values);
}
/**
* @notice Helper function to append a uint256[2] to a transcript
* @param transcript The transcript to append to
* @param values The values to append
* @return The updated transcript
*/
function appendUint2(uint256[1] memory transcript, uint256[2] memory values)
internal
pure
returns (uint256[1] memory)
{
uint256[] memory array = new uint256[](2);
array[0] = values[0];
array[1] = values[1];
return Transcript.__appendArray(transcript, array);
}
/**
* @notice Test demonstrating the lack of additional entropy vulnerability
* @dev This test shows that the implementation doesn't include additional entropy sources
*/
function testNoAdditional_Entropy() public {
// Get a valid proof setup
(, uint256[1] memory transcript, , , ) = _smallValidProof();
// Create a copy of the transcript
uint256[1] memory transcriptCopy;
transcriptCopy[0] = transcript[0];
// A malicious prover who knows the transcript state can predict the challenge
uint256 predictedChallenge = Transcript.__drawChallenge(transcriptCopy);
// The actual challenge will match the predicted one
uint256 actualChallenge = Transcript.__drawChallenge(transcript);
// Log the challenges
emit log_named_uint("Predicted Challenge", predictedChallenge);
emit log_named_uint("Actual Challenge", actualChallenge);
// The challenges should match
assertEq(
predictedChallenge,
actualChallenge,
"Prover can predict challenge without additional entropy"
);
// Now demonstrate with additional entropy
uint256[1] memory secureTranscript;
secureTranscript[0] = transcriptCopy[0];
// Add block-related entropy
secureTranscript = appendUint(secureTranscript, block.number);
secureTranscript = appendUint(secureTranscript, block.timestamp);
secureTranscript = appendUint(secureTranscript, block.prevrandao);
uint256 secureChallenge = Transcript.__drawChallenge(secureTranscript);
emit log_named_uint("Secure Challenge (with entropy)", secureChallenge);
// The secure challenge should be different
assertTrue(
predictedChallenge != secureChallenge,
"Challenge with entropy should be unpredictable"
);
}
}The test testNoAdditional_Entropy() in HyperKZGFiatShamirVulnerabilityCorrect.t.sol demonstrates this vulnerability:
Predicted Challenge: 2633085289937528270745799197476035349369598954117333237816980178747810751600
Actual Challenge: 2633085289937528270745799197476035349369598954117333237816980178747810751600
This shows that challenges can be perfectly predicted without additional entropy.
Modify the Verifier.pre.sol::make_transcript function and HyperKZGHelpers.pre.sol::run_transcript function to incorporate additional entropy sources.
Severity: Medium
The HyperKZG implementation lacks explicit domain separation for different challenges in the Fiat-Shamir transcript, potentially allowing challenge confusion attacks that could compromise the security of the zero-knowledge proof system.
In the run_transcript function of HyperKZGHelpers.pre.sol (imported into HyperKZGVerifier.pre.sol), challenges are generated sequentially without domain separators:
function run_transcript(com_ptr, v_ptr, w_ptr, transcript_ptr, ell) -> r, q, d {
append_calldata(transcript_ptr, com_ptr, mul(WORDX2_SIZE, sub(ell, 1)))
r := draw_challenge(transcript_ptr)
append_calldata(transcript_ptr, v_ptr, mul(WORDX3_SIZE, ell))
q := draw_challenge(transcript_ptr)
append_calldata(transcript_ptr, w_ptr, WORDX6_SIZE)
d := draw_challenge(transcript_ptr)
}This implementation relies solely on the order of operations and the content of the messages to differentiate between challenges. The Fiat-Shamir heuristic's security depends on the unpredictability and independence of challenges. Without explicit domain separators, there's a risk that specially crafted inputs could cause challenges to be reused or confused between different parts of the protocol.
The paper "Fiat-Shamir: From Practice to Theory" (Canetti et al.) sections 2.1, 3.1, and 5 emphasizes the importance of domain separation in Fiat-Shamir implementations. Without it, challenges for different purposes can be confused or reused, potentially allowing a malicious prover to manipulate the protocol.
In the context of the HyperKZG protocol, the challenges r, q, and d serve different cryptographic purposes:
- r is used in the consistency check for the v array
- q is used in the bivariate evaluation
- d is used in both the bivariate evaluation and group element computation
If these challenges could be manipulated to have specific relationships, it might be possible to craft proofs for false statements.
The impact is assessed as Medium because:
- It weakens the security guarantees of the Fiat-Shamir transform, which is a critical component of the zero-knowledge proof system.
- It could potentially allow an attacker to manipulate challenges in specific scenarios, creating conditions where other attacks become possible.
- It doesn't immediately break the protocol but creates a vulnerability that could be exploited in combination with other weaknesses.
The likelihood is assessed as Medium because:
- Exploiting this vulnerability requires sophisticated knowledge of the protocol and cryptographic techniques.
- The attacker would need to craft specific inputs that cause challenge confusion, which requires understanding the internal workings of the Fiat-Shamir implementation.
- The sequential nature of the transcript updates provides some protection, making the attack more difficult but not impossible.
- Similar vulnerabilities have been exploited in other cryptographic protocols, as documented in academic literature.
A malicious prover could potentially craft inputs where:
-
The prover constructs specific com, v, and w values such that:
- After appending com_ptr data and drawing challenge r
- Then appending v_ptr data
- The transcript state is manipulated to produce a specific value for challenge q
-
With carefully chosen values, the prover could potentially force q to have a specific relationship with r (e.g., q = r² or q = -r).
-
This relationship could then be exploited in the bivariate evaluation and group element computation to create a proof that passes verification despite proving a false statement.
For example, if q could be forced to equal r², then the terms in the bivariate evaluation involving q^i would have a predictable relationship with terms involving r, potentially allowing the prover to craft values that cancel out in the verification equation.
// SPDX-License-Identifier: UNLICENSED
// This is licensed under the Cryptographic Open Software License 1.0
pragma solidity ^0.8.28;
import {Test} from "forge-std/Test.sol";
import "../../src/base/Constants.sol";
import "../../src/base/Errors.sol";
import {HyperKZGVerifier} from "../../src/hyperkzg/HyperKZGVerifier.pre.sol";
import {Transcript} from "../../src/base/Transcript.sol";
/**
* @title HyperKZGFiatShamirVulnerabilityCorrectTest
* @notice Corrected tests demonstrating valid Fiat-Shamir vulnerabilities in the HyperKZG implementation
*/
contract HyperKZGFiatShamirVulnerabilityCorrectTest is Test {
// Reuse the existing test setup from HyperKZGVerifierTest
function _smallValidProof()
internal
pure
returns (
bytes memory proof,
uint256[1] memory transcript,
uint256[2] memory commitment,
uint256[] memory x,
uint256 y
)
{
proof = hex"0000000000000001" hex"1f2e45337f9b8344112089d02a9827c05864124c9d68e6dfe4ae4b1ef18b8bec"
hex"0603731e181537ca4cac7f28123622a175a7181b08404a64b1197c3a8adee75c" hex"0000000000000002"
hex"195601834abe3b06307843dfb2bda53c463acac5ce7452fe7f9afb76ef076159"
hex"01b06ce4e5c076c62ee49bea6c8c0d3475c9c4203863f33e407c032f104d7929"
hex"0244bf82e008d1628941372c47440cf0b7ddf46a4e07f370e99246946d2c2f96"
hex"1fac3ee761eb0bf01d1be7d167923af7a75802fb6daaf7c93b17e48bdb93582a"
hex"10b80f8b7f4694399b345de519ef1d6580dbe54d0c0e78c808ca1108146ca7e5"
hex"249c5130fc843ff6fa68d4ab85a5254f12f04d615289e5c00e42c22b867eebab"
hex"20aaca7d9451a200e417af702479ee0bd90a19d25f90bc5ac31515a2510ecbf9"
hex"13880503efe944d65ff45424e0c07237dbb4bbfa7d8dcbed7c0f234d94afd8c0"
hex"0afe9d625909d59d10259307138122091a2a4d81d7e419359e9a3b70916edade"
hex"12f9228a1c7fa913c0e3b4b20ff5cf106c9555c20c668e6441dfb3fa1a174626"
hex"18977d28d54a74822b9816495ab7909d9db911b3d107a7ccbb758baa94217fd5"
hex"097467f5beafcf7a6b77c515a0876800db96837e5e279cd8a0d3f86deb571fb7";
transcript = [0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470];
commitment = [
0x0bceea30108fed3f7c8e53e56a3aedf0de0bc26292e469ab525f1ac9fe93c758,
0x126f299ba3b83331a6901a281b0982b87f154efe57ac4da1f7c51a97dda59e1b
];
x = new uint256[](2);
x[0] = 0x7;
x[1] = 0x5;
y = 17;
}
/**
* @notice Helper function to append a uint256 to a transcript
* @param transcript The transcript to append to
* @param value The value to append
* @return The updated transcript
*/
function appendUint(uint256[1] memory transcript, uint256 value)
internal
pure
returns (uint256[1] memory)
{
uint256[] memory values = new uint256[](1);
values[0] = value;
return Transcript.__appendArray(transcript, values);
}
/**
* @notice Helper function to append a uint256[2] to a transcript
* @param transcript The transcript to append to
* @param values The values to append
* @return The updated transcript
*/
function appendUint2(uint256[1] memory transcript, uint256[2] memory values)
internal
pure
returns (uint256[1] memory)
{
uint256[] memory array = new uint256[](2);
array[0] = values[0];
array[1] = values[1];
return Transcript.__appendArray(transcript, array);
}
/**
* @notice Test demonstrating the lack of domain separation vulnerability
* @dev This test shows that challenges for different purposes don't have domain separation
*/
function testNoDomain_SeparationVulnerability() public {
// Get a valid proof setup
(, uint256[1] memory transcript, , , ) = _smallValidProof();
// Create a copy of the transcript for each purpose
uint256[1] memory transcriptForR;
uint256[1] memory transcriptForQ;
uint256[1] memory transcriptForD;
transcriptForR[0] = transcript[0];
transcriptForQ[0] = transcript[0];
transcriptForD[0] = transcript[0];
// In the current implementation, there's no domain separation
// If we add the same data to each transcript, they'll generate the same challenge
bytes memory sameData = abi.encodePacked(uint256(123));
// Manually append the same data to each transcript
assembly {
let free_ptr := mload(FREE_PTR)
// For R
mstore(free_ptr, mload(transcriptForR))
mstore(add(free_ptr, 0x20), mload(sameData))
mstore(transcriptForR, keccak256(free_ptr, 0x40))
// For Q
mstore(free_ptr, mload(transcriptForQ))
mstore(add(free_ptr, 0x20), mload(sameData))
mstore(transcriptForQ, keccak256(free_ptr, 0x40))
// For D
mstore(free_ptr, mload(transcriptForD))
mstore(add(free_ptr, 0x20), mload(sameData))
mstore(transcriptForD, keccak256(free_ptr, 0x40))
}
// Draw challenges
uint256 challengeR = Transcript.__drawChallenge(transcriptForR);
uint256 challengeQ = Transcript.__drawChallenge(transcriptForQ);
uint256 challengeD = Transcript.__drawChallenge(transcriptForD);
// Log the challenges
emit log_named_uint("Challenge R (no domain separation)", challengeR);
emit log_named_uint("Challenge Q (no domain separation)", challengeQ);
emit log_named_uint("Challenge D (no domain separation)", challengeD);
// Without domain separation, challenges will be the same if the transcripts are the same
assertEq(challengeR, challengeQ, "Challenges should be identical without domain separation");
assertEq(challengeQ, challengeD, "Challenges should be identical without domain separation");
// Now demonstrate with domain separation
uint256[1] memory domainSeparatedTranscriptR;
uint256[1] memory domainSeparatedTranscriptQ;
uint256[1] memory domainSeparatedTranscriptD;
domainSeparatedTranscriptR[0] = transcript[0];
domainSeparatedTranscriptQ[0] = transcript[0];
domainSeparatedTranscriptD[0] = transcript[0];
// Add domain separators
domainSeparatedTranscriptR = appendUint(domainSeparatedTranscriptR, 1); // Domain 1 for R
domainSeparatedTranscriptQ = appendUint(domainSeparatedTranscriptQ, 2); // Domain 2 for Q
domainSeparatedTranscriptD = appendUint(domainSeparatedTranscriptD, 3); // Domain 3 for D
// Now add the same data
assembly {
let free_ptr := mload(FREE_PTR)
// For R
mstore(free_ptr, mload(domainSeparatedTranscriptR))
mstore(add(free_ptr, 0x20), mload(sameData))
mstore(domainSeparatedTranscriptR, keccak256(free_ptr, 0x40))
// For Q
mstore(free_ptr, mload(domainSeparatedTranscriptQ))
mstore(add(free_ptr, 0x20), mload(sameData))
mstore(domainSeparatedTranscriptQ, keccak256(free_ptr, 0x40))
// For D
mstore(free_ptr, mload(domainSeparatedTranscriptD))
mstore(add(free_ptr, 0x20), mload(sameData))
mstore(domainSeparatedTranscriptD, keccak256(free_ptr, 0x40))
}
// Draw challenges
uint256 domainSeparatedChallengeR = Transcript.__drawChallenge(domainSeparatedTranscriptR);
uint256 domainSeparatedChallengeQ = Transcript.__drawChallenge(domainSeparatedTranscriptQ);
uint256 domainSeparatedChallengeD = Transcript.__drawChallenge(domainSeparatedTranscriptD);
// Log the challenges
emit log_named_uint("Challenge R (with domain separation)", domainSeparatedChallengeR);
emit log_named_uint("Challenge Q (with domain separation)", domainSeparatedChallengeQ);
emit log_named_uint("Challenge D (with domain separation)", domainSeparatedChallengeD);
// With domain separation, challenges should be different
assertTrue(
domainSeparatedChallengeR != domainSeparatedChallengeQ,
"Challenges should differ with domain separation"
);
assertTrue(
domainSeparatedChallengeQ != domainSeparatedChallengeD,
"Challenges should differ with domain separation"
);
assertTrue(
domainSeparatedChallengeR != domainSeparatedChallengeD,
"Challenges should differ with domain separation"
);
}
}Implement explicit domain separation by adding unique identifiers before each challenge generation.