DO NOT FORK THE REPOSITORY, AS IT WILL MAKE YOUR SOLUTION PUBLIC. INSTEAD, CLONE IT AND ADD A NEW REMOTE TO A PRIVATE REPOSITORY, OR SUBMIT A GIST
Install Noir v0.37.0.
curl -L noirup.dev | bash
noirup --version 0.37.0
Install the compatible version of the bb CLI for the Barretenberg proving backend.
curl -L bbup.dev | bash
bbup --version 0.61.0
Generate the witness:
nargo execute
Generate the proof:
bb prove -b ./target/puzzle3.json -w ./target/puzzle3.gz -o ./target/proof
Verify the proof:
bb verify -p ./target/proof
Compile:
nargo compile
Generate the verification key:
bb write_vk -b ./target/puzzle3.json -o ./target/vk
______ _ __ _ _ _
|___ /| | / / | | | | | |
/ / | |/ / | |_| | __ _ ___| | __
/ / | \ | _ |/ _` |/ __| |/ /
./ /___| |\ \ | | | | (_| | (__| <
\_____/\_| \_/ \_| |_/\__,_|\___|_|\_\
A cutting-edge crypto company unveiled http://JWT.pk, a revolutionary identity
infrastructure platform designed to simplify private key management. By allowing
users to register seamlessly with existing keys, the service promised to redefine convenience and
security in the digital world. It allows users to send amounts up to $100 without having access to their
private keys.
The registration process goes as follows: Users sign up with their existing
public keys (pk) http://JWT.pk then samples a secret value called “pepper” and computes an identifier
of the form: “{pk}_{pepper}”. SHA256 of the identifier is then added to the set of registered identifiers.
Users can later authenticate a transaction by simply providing a proof
of knowledge of the whitelisted identifier formed by the (pk, pepper) pair without needing to use
their private key at any step of the process.
Alice found out that Bob registered to http://JWT.pk with a
public key “BOB_pk”. She then registered using “ALICE_pk” and
obtained “ALICE_pepper” from http://JWT.pk.
Bob woke up one morning to see his account drained. How did Alice do it?
The main.nr file only contains the main function, which is the constraints (circuit) that are in it. We are not allowed to modify this file.
fn main(identifier: BoundedVec<u8, 128>, pub_key: pub [u8; 32], whitelist: pub [[u8; 32]; 10]) {
// the identifier hashes to a digest that is in the public whitelist
let digest = std::hash::sha256_var(identifier.storage(), identifier.len() as u64);
let mut present = false;
for i in 0..whitelist.len() {
if whitelist[i] == digest {
present = true;
}
}
assert(present);
// the specified public key is in the identifier
let id_haystack: StringBody128 = StringBody::new(identifier.storage(), 128);
let pk_needle: SubString32 = SubString::new(pub_key, 32);
let (result, _): (bool, u32) = id_haystack.substring_match(pk_needle);
assert(result);
}Basically, 2 conditions are checked here:
- Identifier is among registered identifiers, which means that its hash is in the whitelist.
- The public key is included in the identifier.
In the comment, we are also provided Alice's public key and pepper.
The Prover.toml contains both instance and witness (public and private data). The instance includes the whitelist and the public key of Bob. We are left with the witness, which is just a 128-byte identifier. Our task is to try to forge an identifier to bypass the above constraints.
If we were Bob, it's straightforward. Just provide Bob's public key and pepper with the form: "{pk}_{pepper}". But we don't know Bob's pepper. On the other hand, passing each constraint alone is not difficult.
For the former, just provide our (Alice's) key and pepper and since we are whilelisted, this will pass. And for the latter, if Bob's public key is provided inside the identifier, this constraint can pass. How to satisfy both?
By observing a little bit, we can see that besides the identifier storage itself, we are allowed to provide another field, which is len. And there is an “asymmetry" between how two constraints consider the identifier. While the whilelist check with our provided len, the public key inclusion check considers a fixed length of 128.
Now, everything seems clear, Alice's "{pk}_{pepper}" only takes 65 bytes. And by limiting the len at 65, we can put Bob's public key anywhere in the remaining part, which makes us bypass the latter constraint.
Here is the implementation, note that 95 is "_".
[identifier]
len = "65"
# storage = alice_pk + [95] + alice_pepper + [0] * 31 + pub_key
storage = [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, 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, 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, 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]
# END HACK