Bank of NNS

Challenge summary

A TCP(+TLS) service (“nc bank-of-nns-…chall.nnsc.tf 1337”) implements a toy bank. Withdrawals are authorized by a Kimchi (Mina’s PLONK-ish proof system, from o1-labs/proof-systems, pinned commit f6d958d) zero-knowledge proof that the requested amount is a valid “NNS” quantity. The service exposes:

SETTLE <amount> <base64 msgpack-encoded kimchi proof>
BALANCE
QUIT

Each connection reported the caller’s tracked BALANCE and the shared VAULT balance (initially 100000000000000000000000 NNS). A provided Rust crate (nns-prove) builds the circuit and proof for a chosen amount and would normally submit “settle ” over a plain TCP socket to a local instance.

The circuit (src/challenge.rs) is:

row 0: Generic "Public" gate      -> public input #0 = amount
row 1: Generic "Public" gate      -> public input #1 = 0
row 2: RangeCheck0 gate (standalone, "64-bit range check" mode)

gates.connect_64bit(1, 2);              // tie RangeCheck0 to the zero row
gates.connect_cell_pair((0, 0), (2, 0)); // tie amount to RangeCheck0's value column

Per Kimchi’s own documentation, a standalone RangeCheck0 gate can be turned into a pure 64-bit range check “by constraining witness cells 1-2 to zero” (columns vp0/vp1, the two highest 12-bit limbs of the normal 88-bit range check). connect_64bit(zero_row, start_row) is supposed to do exactly that.

Root cause

connect_64bit is implemented as three consecutive connect_cell_pair (transposition/cycle-splice) calls:

fn connect_64bit(&mut self, zero_row: usize, start_row: usize) {
    self.connect_cell_pair((start_row, 1), (start_row, 2));
    self.connect_cell_pair((start_row, 2), (zero_row, 0));
    self.connect_cell_pair((zero_row, 0), (start_row, 1));
}

Each connect_cell_pair swaps the two cells’ successor pointers in the permutation (“wire”) representation - the standard technique for splicing cycles. Tracing the three calls carefully (confirmed empirically by dumping CircuitGate::wires for the actual compiled circuit) shows the third call does not extend the 3-cycle as intended - it collapses back into:

(row2, col2) <-> (row1, col0)   [correctly forced to the public zero]
(row2, col1) -> (row2, col1)    [SELF-LOOP - no constraint at all!]

So column 1 of the RangeCheck0 gate (vp0, the limb with weight 2^76 in the gate’s internal “sum of limbs == value” equation) ends up with no copy constraint and no lookup constraint whatsoever. It is a fully free field element. Since:

value (public "amount") == sum_of_limbs
                         == col1 * 2^76 + col2 * 2^64 + ... (lower limbs)

and col2..col14 can simply be left at 0 (all individually satisfy their own small local range/crumb constraints at 0), the “amount” can be set to any element of the Pasta Fp field (~2^255), not just values below 2^64, by solving col1 = amount / 2^76 (mod p) - which is always solvable since 2^76 is invertible mod p. The “64-bit range check” is therefore completely unsound: it accepts a valid-looking “proof of funds” for literally any amount, positive, huge, whatever.

Exploit

1. Patched the provided nns-prove client to build a witness where every limb except column 1 is zero, and column 1 is solved for directly:

let two_pow_76 = Fp::from(2u64).pow([76u64]);
let inv = two_pow_76.inverse().unwrap();
row[1] = amount * inv;   // row[2] stays 0, forced by connect_64bit

This produces a proof that verifies successfully (both locally via kimchi::verifier::verify and on the live server) for an arbitrary amount, e.g. far beyond 2^64 or even u128::MAX.

2. Connected to the service and ran:

SETTLE 1267650600228229401496703205376000000 <forged proof>

The server does not perform any separate sanity check on withdrawal size once the (broken) ZK “proof of funds” verifies - it directly approved and dispensed the full amount, capping only at the remaining VAULT balance. VAULT dropped straight to 0 NNS and the service printed the flag in the BALANCE statement.

Lesson / root cause summary

Vec<CircuitGate>::connect_64bit from o1-labs/proof-systems (kimchi) builds its 3-way copy-constraint cycle in the wrong order for this call pattern, silently leaving one of the two “must be zero” limbs of a standalone RangeCheck0 gate completely unconstrained. Any circuit relying on this helper for a “64-bit range check” without independently re-verifying the wiring is unsound and lets a prover claim an arbitrary field element instead of a bounded 64-bit integer.

Tools used

• Rust/Cargo (patched the provided nns-prove crate)
• arkworks (ark-ff) for Fp field arithmetic (pow/inverse)
• openssl s_client for talking to the TLS “nc” service
• Cloned o1-labs/proof-systems at the pinned commit and dumped CircuitGate::wires via a #[test] to confirm the broken permutation cycle