Toshi's Treasure (toshitreasure)

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-24 | Status: Solved Techniques: sss_last_submitter_cheat, lagrange_coefficient_control, linear_secret_in_own_share, secret_recovery

Summary

Task: a 5-of-6 Shamir Secret Sharing combiner over GF(2^521-1) that reveals the reconstructed private key after you submit your share. Solution: Lagrange interpolation is LINEAR in our submitted y6, so secret(y6) = sec0 + L6·y6 with L6=5 the Lagrange coefficient at x=0 for x=6 (x in {2,3,4,5,6}). Submit y6=0 to learn sec0, then craft y6=(target-sec0)·L6^{-1} to make the combiner output any chosen value (the cheat); finally submit the REAL secret sec0 + 5·(our genuine share y) as the privkey to unlock and get the flag. Lesson: use verifiable secret sharing.

Toshi's Treasure (toshitreasure) — cryptohack (Misc, 150 pts)

Description

A 5-of-6 Shamir Secret Sharing scheme over the 13th Mersenne prime p = 2^521 − 1 guards a wallet private key. You hold one share. After all shares are submitted, the combiner reveals the reconstructed private key. Connect at socket.cryptohack.org 13384.

Files: our genuine share (share_...txt, point (x6, y6_real)), and a $1k wallet private key (hyper_privkey_...txt) we are tempted to steal.

Analysis

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Shamir reconstruction is Lagrange interpolation at x=0:

secret = Σ_{i} L_i · y_i  (mod p),   L_i = Π_{j≠i} (0 - x_j)/(x_i - x_j)

The other four shares are fixed; only our point (x6=6, y6) is attacker-controlled. The secret is therefore linear in our submitted y6:

secret(y6) = sec0 + L6 · y6   (mod p)

where sec0 is the contribution of the four fixed shares and L6 is the Lagrange coefficient at x=0 for x=6 given the support x ∈ {2,3,4,5,6}:

L6 = Π_{j∈{2,3,4,5}} (0 - x_j)/(6 - x_j)
   = ((-2)(-3)(-4)(-5)) / ((4)(3)(2)(1))
   = 120 / 24 = 5

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Because the combiner reveals the result after submission, this is the classic "last submitter controls the secret" attack — there is no verifiable secret sharing (VSS) to detect a tampered share.

Solution

1. Learn sec0. Submit y6 = 0; the revealed secret is exactly sec0.
2. Cheat to any target. To force the combined secret to equal the $1k wallet key target, solve target = sec0 + 5·y6 for the forged share: y6 = (target − sec0)·5^{-1} (mod p). Submitting this makes the combiner output target.
3. Unlock the real treasure. The genuine secret is sec0 + 5·y6_real, computed from our honest share. Submit that as the privkey to unlock and receive the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
P = 2**521 - 1
target = int("8b09cfc4696b91a1cc43372ac66ca36556a41499b495f28cc7ab193e32eadd30", 16)  # $1k privkey
myx, myy = my_share   # our genuine point (6, y6_real)

sec0, _ = submit(0)                          # y6=0 -> reveals sec0
L6 = 5                                        # Lagrange coeff at x=0 for x=6, support {2,3,4,5,6}
y6 = ((target - sec0) * pow(L6, -1, P)) % P   # forge share so combined == target (the cheat)
forged, _ = submit(y6)                        # combiner now outputs `target`
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

real = (sec0 + L6 * myy) % P                  # the TRUE secret from our honest share
send({"privkey": hex(real)})                  # unlock -> flag

The forged submission demonstrates we can make the reconstruction equal any value of our choosing; the honest reconstruction (sec0 + 5·y6_real) is the real private key that unlocks the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍