Back to writeups
FlagYardcryptoMediumsolved

verifiable delay

12 Jul 2026 · by 0xIDA

Solvers

verifiable delay

Author: 0xIDA
Platform: FlagYard · Category: crypto · Difficulty: Medium

Solvers

Summary

Wesolowski-style VDF over an RSA modulus. The server computes y = g^(2^(2^256)) mod n with the trapdoor phi(n) and asks for a different claim h plus a Fiat–Shamir Wesolowski proof for a 40-bit hash-to-prime challenge l. Forging with the group inverse (h = -y, pi = -proof) works for every odd prime l.

Challenge Description

it's just verifiable delay.

TCP service (internalPort 5000). Handout chal.py (strictest variant):

  • Generate 1024-bit strong primes p,q, n=pq, g=3
  • result = pow(g, pow(2, 1<<256, phi), n)
  • Read claim h with 1 < h < n-1 and h != result
  • l = genRandomPrime(n, g, h) — first 40-bit prime from SHA256(n||g||h||idx)
  • Print honest Wesolowski proof proof = g^{floor(2^(2^256)/l)}
  • Read pi with 1 < pi < n-1 and pi != proof
  • Accept if h == pi^l * g^r mod n where r = 2^(2^256) mod l

Reconnaissance

# files (4 chal.py variants; live image uses strict bounds)
# chal1: no range checks
# chal2/3: 0 <= h,pi < n
# chal4 (live): 1 < h,pi < n-1

# instance
mcp_flagyard_start_instance(lab_id=8, challenge_id=fde63f5b-...)
# → tcp.flagyard.com:22260

Live probe rejected h=0 with assert 1 < h < n - 1.

Vulnerability Analysis

Honest values satisfy:

result ≡ proof^l * g^r  (mod n)

Need a different pair (h, pi). Because l is an odd prime (all 40-bit primes except 2),

(-proof)^l * g^r ≡ (-1)^l * proof^l * g^r ≡ -result  (mod n)

So the forged claim/proof:

h  = n - result   # ≡ -result
pi = n - proof    # ≡ -proof

satisfies the verifier, while range checks and != asserts hold (n odd ⇒ result != n-result).

Failure only if l = 2 (probability ~2^{-40}); reconnect in that case.

This is a Fiat–Shamir / proof-of-exponentiation soundness issue: the protocol does not bind the claim to a unique residue class representative that rejects the group inverse of a valid transcript.

Exploitation

#!/usr/bin/env python3
from pwn import *

r = remote("tcp.flagyard.com", 22260, timeout=60)
line1 = r.recvline(timeout=120).decode()
line2 = r.recvline(timeout=60).decode()
n = int(line1.split("modulus is ")[1].strip())
result = int(line2.split("== ")[1].strip())

h = n - result
r.sendline(str(h).encode())

line3 = r.recvline(timeout=60).decode()
line4 = r.recvline(timeout=60).decode()
l = int(line3.split("challenge is ")[1].strip())
proof = int(line4.split("proof is ")[1].strip())
assert l % 2 == 1

pi = n - proof
r.sendline(str(pi).encode())
print(r.recvall(timeout=30).decode())

Live output:

my challenge is 964305709021
the correct proof is 1128652...
proof success! here's your flag
FlagY{Wesolowski's_VDF_is_less_secure_in_Fiat-Shamir!}

Submit: mcp_flagyard_submit_flag → Success.

Flag

FlagY{Wesolowski's_VDF_is_less_secure_in_Fiat-Shamir!}

Live-submitted and accepted on Flagyard (2026-07-12).

Key Takeaways

  1. Wesolowski verification is multiplicative: any unit u with u^l = 1 yields another accepting proof; for odd l, u = -1 always works in (Z/nZ)* when -1 is allowed as a group element.
  2. Range checks that only forbid {0,1,n-1} still allow n-y and n-π.
  3. Server-side trapdoor evaluation of the true VDF output does not prevent forging another accepting transcript once one valid (y, π) is known.
  4. Loose variants of the same challenge (h=0,pi=0 or h=y+n, pi=π+n) are even easier — always check bounds.

Tools Used

  • Python 3, pwntools
  • Flagyard MCP (start/stop instance, submit)
  • PyCryptodome (local analysis of handout)

Timeline

  • Download 4 chal.py variants, identify Wesolowski VDF
  • Live probe → strict 1 < x < n-1 bounds
  • Inverse forgery → flag in one connection
  • Submit success