Missing prover binding in Fiat–Shamir enables cross-party replay

[HopeDevote]

Describe the bug

Proof::set_challenge(const octetStream&) derives the Fiat-Shamir challenge by hashing only the ciphertext bytes (unkeyed BLAKE2b-128, no label). The transcript omits the prover's party ID, any session/sub-session ID, the FHE public key, and a domain separator. In the sequential per-player proof loop of InputProducer::run, every party proves under the same global setup.pk and the verifier takes the statement from the untrusted stream itself. A corrupt party can forward an earlier party's proof verbatim as its own. The recomputed challenge matches, every verification equation holds, and the "proof" is accepted although the replaying party does not know the plaintext.

The vulnerable code:

// FHEOffline/Proof.cpp:36-42
void Proof::set_challenge(const octetStream& ciphertexts)
{
  octetStream hash = ciphertexts.hash();   // hash of the ciphertext stream ONLY
  PRNG G;
  assert(hash.get_length() >= SEED_SIZE);
  G.SetSeed(hash.get_data());
  set_challenge(G);
}

// Tools/octetStream.cpp:95-102 — unkeyed BLAKE2b-128, no label/party/session/pk
void octetStream::hash(octetStream& output) const
{
  output.resize(crypto_generichash_BYTES_MIN);          // = 16 bytes
  crypto_generichash(output.data, crypto_generichash_BYTES_MIN,
                     data, get_length(), NULL, 0);
  output.set_length(crypto_generichash_BYTES_MIN);
}

The challenge hash input contains nothing that varies per prover, per session, or per protocol: no prover index, no sid/ssid, no public key, no domain separator. Since the loop is sequential and the verifier accepts the statement ciphertexts from the proof stream, a corrupt party j2 > j1 can replay party j1's (ciphertexts, cleartexts) verbatim.

To Reproduce

The following test mimics on the wire exactly what a corrupt party is allowed to send under the malicious-security threat model. It adds a test hook to FHEOffline/Producer.cpp (only active when the TEST_REPLAY environment variable is set) that makes one party forward the previously received proof transcript instead of generating its own, plus a log line printing the transcript hash on every accepted proof:

--- a/FHEOffline/Producer.cpp
+++ b/FHEOffline/Producer.cpp
@@
         AddableVector<Ciphertext> C;
         vector<Plaintext_<FD>> m(personal_EC.proof.U, FieldD);
+        // test hook: replay an earlier party's transcript (env-gated)
+        static octetStream replay_ct, replay_pt;
+        bool test_replay = getenv("TEST_REPLAY")
+                           and P.my_num() == atoi(getenv("TEST_REPLAY"));
         if (j == P.my_num())
         {
+            if (test_replay and replay_ct.get_length() > 0)
+            {
+                ciphertexts = replay_ct;   // forward, do not generate
+                cleartexts  = replay_pt;
+                P.send_all(ciphertexts);
+                P.send_all(cleartexts);
+                C.resize(personal_EC.machine->sec, pk.get_params());
+                Verifier<FD>(personal_EC.proof, FieldD).NIZKPoK(C,
+                        ciphertexts, cleartexts, pk);
+            }
+            else
+            {
                 for (auto& x : m)
                     x.randomize(G);
                 personal_EC.generate_proof(C, m, ciphertexts, cleartexts);
                 P.send_all(ciphertexts);
                 P.send_all(cleartexts);
+            }
         }
         else
         {
             P.receive_player(j, ciphertexts);
             P.receive_player(j, cleartexts);
+            if (test_replay and replay_ct.get_length() == 0)
+                { replay_ct = ciphertexts; replay_pt = cleartexts; }
             C.resize(personal_EC.machine->sec, pk.get_params());
             Verifier<FD>(personal_EC.proof, FieldD).NIZKPoK(C, ciphertexts,
                     cleartexts, pk);
+            cerr << "[test] party " << P.my_num() << " accepted proof from party "
+                 << j << " with transcript hash " << ciphertexts.hash() << endl;
         }

Test program (Programs/Source/test_replay.mpc):

a = sint.get_input_from(0)
b = sint.get_input_from(1)
print_ln("sum=%s", (a + b).reveal())

Build and run (two parties, ChaiGear):

make -j2 chaigear-party.x
python3 compile.py test_replay
mkdir -p Player-Data
echo 100 > Player-Data/Input-P0-0
echo 300 > Player-Data/Input-P1-0

# party 0 (honest)
./chaigear-party.x -IF Player-Data/Input -N 2 -pn 19500 -h 127.0.0.1 0 test_replay &
sleep 6
# party 1 (forwards party 0's transcript as its own)
TEST_REPLAY=1 ./chaigear-party.x -IF Player-Data/Input -N 2 -pn 19500 -h 127.0.0.1 1 test_replay &
wait

Expected behavior

The verifier should reject a proof transcript that is byte-identical to another party's earlier proof in the same execution (and to any proof from a previous execution).

Error message

There is no error — that is the problem. Party 0 accepts the forwarded transcript, and the transcript hash of "party 1's proof" is identical to party 0's own proof:

party 1 log: [test] party 1 accepted proof from party 0 with transcript hash 27d2286e8ea058f2301d899bf11674e7
party 0 log: [test] party 0 accepted proof from party 1 with transcript hash 27d2286e8ea058f2301d899bf11674e7

MP-SPDZ version
master，v0.4.3
Additional context

This could potentially be fixed by binding the full context to the challenge, for example:

H("mpspdz-zkpopk" || sid || prover_id || pk_bytes || ciphertexts)

[mkskeller]

Thank you for raising this. You should find that 96ea79d fixes it.

[HopeDevote]

Thanks for the fix.