____ _ __ _ _ _ ____
/ __ \| | / _| | | (_) (_)/ __ \
| | | | |__ | |_ _ _ ___| |_ ___ _ __ _ __ _ _| | | |
| | | | '_ \| _| | | / __| __/ _ \| '_ \| |/ _` | | | | | |
| |__| | |_) | | | |_| \__ \ || (_) | |_) | | (_| |_| | |__| |
\____/|_.__/|_| \__,_|___/\__\___/| .__/|_|\__,_(_)_|\____/
| |
|_|
Ethereum foundation, Phantom.zone, and 0xPARC are launching a bounty program to test soundness of new approaches to program obfuscation. The first bounty is to break local mixing approach to program obfuscation.
10,000 USD
To win the bounty you must find a reversible circuit with <= 1014 gates which is funtionally equivalent to the obfuscted circuit we've provided here. We've provided an obfuscated circuit of a randomly sampled reversible circuit which is also an strong pseudo random permutation (SPRP). SPRP implies that the output permutation on any input bitstring is indistinguishable from a truly random permutation. The original reversible circuit has n=64 wires and 1014 gates. The task is to find the original "reversible circuit" only given the obfuscated circuit. The obfuscated circuit has n=64 wires and 237,224 gates. If you're able to find another circuit with <=1014 gates that is not the orignal circuit you still win the bounty because doing so breaks the assumption that original circuit is an SPRP.
Note: Generating input to output map of the permutation that obfuscted circuit computes is not "finding the original circuit". Hence, is not a valid submission.
To submit send the circuit JSON file of the circuit to bounty.obfustopia.io@gmail.com. To pay out the bounty it suffices to verify that your circuit is funtionally equivalent to our original/obfuscated circuit.
Following is an example circuit JSON file for reversible circuit n=4 and 1 gate:
{
"wire_count": 4,
"gate_count": 1,
"gates": [
[
0,
3,
2,
1
]
]
}
"wire_count" and "gate_count" are self explanatory. "gates" is array of base gates. Each gate is represented via an
array of 4 elements. The first element is control wire 0, second element is control wire 1, third is the target wire,
and the fourth element is the control function. There are 16 different control functions and their index can be found
here.
If circuit binary file already exists then its circuit JSON file can be generated using the following command:
cargo run --release -- 3 [circuit_bin_path] [circuit_json_path]
where
- circuit_bin_path: path to circuit's binary
- circuit_json_path: location to store input circuit's JSON file.
If you're new to program obfuscation via local mixing and reversible circuits this hackmd doc is a good place to start. Here after, we'll assume knowledge of program obfuscation via local mixing and reversible circuits.
We're interested in better understanding the security of local-mixing approach to program obfuscation. Random identity
generator (RIG) obfuscated circuits is the core construction required to obfuscate any arbitrary reversible circuit,
hence any arbitrary boolean function. RIG requires an obfuscator function, \(O_1\), that satifies property 1 of RIO and the
bounty tests the security of this function.
Algorithm to construct RIG samples a random SPRP reversible circuit \(C\) and outputs \(O_1(C) | O_1^{\dagger}(C)\) where
\(\dagger\) denotes inverse. For security, \(O_1\) must be output reversible circuits that are indistinguishable from random
reversible circuits that compute same permutation as the orignal circuit \(C\).
We implemented local mixing approach to \(O_1\), sampled random SPRP reversible circuit \(C\) based on 3-stage block cipher
decribed in Quantum statistical mechanics of encryption: reaching the speed limit of
classical block ciphers (check
this section of the provided hackmd) and ran \(O_1\) with strategy 1 for 235K iterations. Successful recovery of \(C\) or another
funtionally equivalent circuit with equivalent no. of gates in \(C\) will imply local mixing approach to \(O_1\) is not secure.
We implemented obfuscator function based on local mixing approach that satisfies property 1 of RIO (ie function \(O_1\))
available here
We obfuscated a random reversible SPRP circuit \(C\) with strategy 1 using the following command:
cargo run --release -- 1 logs.log out.bin original.bin 1
where `out.bin` is obfuscation job's binary and `orignal.bin` is original circuit C's binary.
Before running the command we modified default parameters for strategy 1 (`fn default_strategy1()`) to use n=64 and
total_steps=235,000.
The command sampled a random SPRP reversible circuit with n=64 (ie no. of wires) by calling
`Circuit::sample_multi_stage_cipher(n=64, rng)`. The sampled circuit is the original circuit \(C\). Multi-stage cipher is
based on
Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers
and is conjectured to be an SPRP.
After sampling \(C\) the command ran local mixing step with strategy 1 for total_steps=235,000 times. Once obfuscation job
finished, we converted both the original circuit and the obfuscated circuit to circuit JSON file with following
commands.
Convert original circuit C's binary to circuit JSON
cargo run --release -- 3 original.bin orignal.json
Isolate obfuscated circuit in obfuscation job's binary and convert to circuit JSON
cargo run --release -- 4 out.bin obfuscated.json
We've provided `obfuscated.json` file here.