Write-up for ZK Hack V3 - Shadow Puzzle

SOLUTION.md

Shadow Puzzle

Problem Summary

The Shadow puzzle involves exploiting a vulnerability in a zero-knowledge circuit to create a valid proof. The problem revolves around the storage structure of the "identifier," which is verified using sha256 and a substring check.

The registration process is described as follows:

1. Users sign up with their existing public keys (PK) on http://JWT.pk.
2. The platform samples a secret value called a "pepper" and computes an identifier of the form {pk}_{pepper}.
3. The SHA-256 hash of the identifier is added to a whitelist.

The challenge is to prove that the provided identifier meets the constraints of the circuit while bypassing private key access. Specifically, Alice found a way to register using Bob's public key to create a valid proof.

Key Observations

1. BoundedVec and Padding:
   • The BoundedVec used for the identifier allows for zero-padded storage up to 128 slots.
   • The len field determines the effective length of the identifier. Any unused slots are ignored in the hash computation.
2. Substring Vulnerability:
   • The circuit performs a substring check to ensure the pub_key is present in the identifier. This check is lenient and can be bypassed if the key exists anywhere in the storage.
3. SHA-256 Hash:
   • The circuit hashes the identifier (within its effective length) and compares it to the public whitelist. This provides an opportunity to manipulate the storage to meet the constraints.

Solution Walkthrough

Exploiting the Vulnerability:

1. By carefully constructing the identifier, we can bypass the substring and hash constraints simultaneously.
2. We exploit the fact that the unused storage slots in BoundedVec can hold arbitrary data.
3. The final crafted identifier includes:
   • Alice's public key (provided during registration).
   • Alice's pepper (obtained from http://JWT.pk).
   • Bob's public key appended to the storage to satisfy the substring check.

Steps to Solve

1. Understand the Circuit Logic:
   • Printed the storage and digest outputs in the circuit to verify what was being computed.
2. Manipulate Prover.toml:
   • Adjusted the len field to reflect the effective length (Alice's public key + Alice's pepper + Bob's public key).
   • Appended Bob's public key to the storage field to bypass the substring check.
3. Verify the Proof:
   • Used the bb prove and bb verify commands to ensure the proof was valid against the whitelist.

Final Prover.toml

# BEGIN DON'T CHANGE THIS SECTION

pub_key = [157, 133, 167, 136, 43, 161, 75, 166, 33, 14, 35, 106, 238, 18, 60, 56, 93, 209, 205, 52, 247, 110, 174, 192, 20, 58, 70, 42, 215, 98, 195, 150]
whitelist = [
    [235, 220, 189, 130, 58, 65, 55, 20, 75, 101, 34, 52, 87, 237, 210, 230, 97, 44, 199, 54, 139, 184, 61, 103, 40, 41, 177, 255, 90, 133, 243, 162],
    [104, 166, 62, 181, 1, 228, 244, 115, 180, 141, 231, 245, 235, 232, 254, 20, 44, 223, 11, 8, 122, 250, 202, 224, 78, 198, 165, 211, 249, 86, 201, 161],
    [131, 135, 86, 204, 58, 1, 220, 226, 90, 219, 112, 36, 1, 32, 243, 102, 219, 56, 119, 222, 191, 237, 192, 62, 176, 73, 50, 160, 23, 243, 250, 21],
    [14, 246, 194, 80, 125, 192, 12, 37, 168, 229, 132, 71, 41, 218, 184, 95, 126, 140, 231, 73, 188, 67, 87, 30, 31, 2, 72, 186, 89, 254, 138, 174],
    [197, 93, 46, 57, 214, 23, 120, 199, 214, 34, 1, 202, 41, 227, 230, 122, 177, 5, 179, 4, 197, 95, 230, 61, 152, 120, 106, 49, 96, 175, 169, 154],
    [32, 197, 4, 79, 137, 124, 121, 121, 120, 190, 124, 73, 155, 106, 147, 81, 49, 138, 184, 149, 43, 22, 108, 75, 134, 0, 97, 84, 145, 114, 198, 230],
    [60, 38, 50, 20, 10, 157, 111, 208, 222, 231, 6, 226, 147, 32, 50, 158, 54, 253, 120, 103, 17, 99, 147, 1, 14, 52, 229, 120, 229, 115, 252, 197],
    [185, 43, 209, 227, 198, 215, 98, 164, 22, 119, 133, 252, 151, 141, 83, 27, 200, 38, 148, 139, 71, 213, 35, 250, 108, 23, 172, 249, 62, 248, 222, 152],
    [190, 80, 189, 89, 178, 25, 7, 226, 190, 11, 159, 71, 247, 207, 103, 179, 22, 156, 195, 99, 232, 20, 61, 170, 214, 81, 246, 35, 211, 184, 77, 152],
    [190, 109, 123, 228, 174, 32, 60, 171, 12, 164, 196, 218, 12, 200, 191, 101, 28, 15, 130, 203, 4, 165, 3, 157, 68, 159, 122, 209, 184, 103, 215, 149]
]

# END DON'T CHANGE THIS SECTION

# BEGIN HACK
[identifier]
len = "65" # Effective length of the identifier: Alice's PK (32) + Alice's pepper (32) + separator (1 byte for len tracking)
storage = [
    # Alice's public key (commented out in the original main.nr file).
    155, 143, 27, 66, 87, 125, 33, 110, 57, 153, 93, 228, 167, 76, 120, 220,
    178, 200, 187, 35, 211, 175, 104, 63, 140, 208, 36, 184, 88, 1, 203, 62,
    # Alice's pepper (commented out in the original main.nr file).
    95, 213, 231, 76, 105, 105, 96, 199, 183, 106, 26, 29, 7, 28, 234, 145,
    69, 48, 9, 254, 205, 79, 21, 90, 13, 39, 172, 114, 59, 131, 15, 78, 118,
    # Bob's public key is appended to pass the substring check.
    157, 133, 167, 136, 43, 161, 75, 166, 33, 14, 35, 106, 238, 18, 60, 56,
    93, 209, 205, 52, 247, 110, 174, 192, 20, 58, 70, 42, 215, 98, 195, 150,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
]
# END HACK

Lessons Learned

1. BoundedVec Behavior: Understanding how unused slots in a BoundedVec are handled was critical.
2. Circuit Constraints: Analyzing the substring and hash constraints helped identify weaknesses.
3. Debugging Techniques: Printing intermediate circuit values (e.g., storage, digest) was invaluable in diagnosing the problem.

This solution demonstrates the importance of careful constraint definition in zero-knowledge circuits to prevent exploitation.