Vaidehi: The Sealed Covenant

Category: Cryptography (Schnorr / MuSig nonce reuse) Target: https://pinaka-m05-cyber-xo-x.vercel.app Flag: PINAKA{one_session_one_nonce_the_council_seal_undone}

1. The setup

The Council of Mithila is a 3-of-3 MuSig-style multisignature scheme over secp256k1. Three council public keys X_1, X_2, X_3 aggregate into a single key:

L      = H("L", X_1, X_2, X_3)
a_i    = H("coef", L, X_i)
X      = Σ a_i · X_i

Each covenant revision is sealed by a Schnorr signature (R, s). Verification for (doc_id, revision, body) is the standard equation:

s·G == R + e·X        (mod curve)
e    = H("e", R, X, doc_id, revision, body)

A signature is produced by an honest sealer holding the aggregate secret x (where X = x·G) and a per-session nonce scalar k (where R = k·G):

s = k + e·x   (mod n)

The registry publishes two genuine seals for revisions 1 and 2, and refuses to seal revision 7 unless a valid seal for exactly that (doc_id, revision, body) is presented.

2. The flaw: session nonce reuse

params.json states the fatal design decision:

The council opens ONE signing session per document, identified by doc_id. The session's pre-committed aggregate nonce R is fixed for the document and reused for each revision sealed within it.

The challenge correctly binds the full message, including the revision number, so e_1 ≠ e_2. But the nonce k behind R is identical for both signatures. The two published seals confirm it:

revision 1: R = (785909...88552, 863997...06131),  s_1 = 272417...46630
revision 2: R = (785909...88552, 863997...06131),  s_2 = 435593...14050

Two Schnorr signatures that share a nonce but differ in challenge form a linear system:

s_1 = k + e_1·x
s_2 = k + e_2·x

Subtracting gives s_1 − s_2 = (e_1 − e_2)·x, so the aggregate private key falls out directly:

x = (s_1 − s_2) · (e_1 − e_2)^(-1)   (mod n)

The signature scheme itself is sound; the session policy leaks the key because it reuses the one secret a Schnorr signer must never reuse.

3. Extracting the key

Using the supplied challenge() / verify_seal() protocol (reimplemented in pure Python in solve.py so no external py_ecc install is required):

1. Reconstruct the aggregate key X from the council keys and confirm it matches params.aggregate_key.
2. Verify both genuine seals locally (sanity check on the encoding).
3. Compute e_1 and e_2 against the shared R and X.
4. Recover:

x = 0x00c16457aab32c149183f58325331af35fd9d66e624fbd43f81c479851272a35

The corresponding nonce scalar is recovered from either seal with k = s_i − e_i·x:

k = 0x21f3e503d8c1e418f00d181bb7205349c38ceac9053d4428b99c764d5a59256b

As a check, x·G == X, confirming the extracted scalar is the true aggregate key.

4. Forging revision 7

With x and k known, any message can be signed. To stay faithful to the corrupted session (and avoid needing to re-commit to a new R), we reuse the published R and compute a fresh challenge for the forbidden revision:

e_7 = challenge(R, X, doc_id, 7, body_7)
s_7 = k + e_7·x   (mod n)
    = s_1 + (e_7 − e_1)·x   (mod n)

The resulting seal verifies against the same verify_seal used by the registry:

{
  "doc_id": "mithila-betrothal-covenant",
  "revision": 7,
  "body": "Revision 7: Mithila cedes Vaidehi and her dominion to the demon-king; the kingdom's sovereignty passes to Lanka.",
  "seal": {
    "R": [
      78590942717428059269889991809638578455145461928612893688259669499439350188552,
      86399799529526984061083292644132654262624075746664350706617581532843906706131
    ],
    "s": 94047503437372943715288006595592556461899117252581377777093910299313937128897
  }
}

5. Submission

POST /covenant/seal
Content-Type: application/json

Response:

{
  "result": "accepted",
  "revision": 7,
  "doc_id": "mithila-betrothal-covenant",
  "proclamation": "The sealed covenant the council refused now bears a valid seal.",
  "flag": "PINAKA{one_session_one_nonce_the_council_seal_undone}"
}

6. Root cause and remediation

Root cause: The protocol derives one aggregate nonce R per document session and reuses it across revisions. Because the challenge includes the revision, the message changes while the nonce stays fixed — the textbook nonce-reuse key-recovery condition.

Remediation:

• Derive a fresh, unpredictable nonce for every signed message, e.g. RFC 6979 deterministic nonces bound to the full message, or a fresh random k.
• Never reuse R across distinct challenges. A "session" may share state (participants, keys), but must never share the nonce.
• If a nonce might have been reused, treat the aggregate key as compromised and rotate it.
• Bind the nonce commitment to the exact message (e.g. commit to a per-message R), rather than to a document session.

7. Files

Reproduce with:

python3 solve.py

The script prints the extracted aggregate key, the forged seal, and writes submission.json.