# verified-msg Writeup

## Summary

This challenge mixes a faulty elliptic-curve implementation with a small but very real memory-corruption bug.

The full solve has two phases:

1. Trigger a fault in the signer/verifier precomputation logic and recover the private key from faulty signatures.
2. Use the sign-path overflow to corrupt `precomp_ptr` and `callback`, then turn a verified admin message into `system(vstate.buffer)` and read the flag.

The final remote flag was:

```text
tkbctf{y34h_u_4r3_4dm1n!-2b99ef896e9ad1706e046d3500319f21df4abcc9914655934b5b477d7fb649dc}
```

## Files

- [chall.cpp](https://github.com/prathamgupta36/CTF-Writeups/blob/main/2026/tkbctf5_2026/pwn_crypto/verified-msg/_src/verified-msg/chall.cpp)
- [crypto.hpp](https://github.com/prathamgupta36/CTF-Writeups/blob/main/2026/tkbctf5_2026/pwn_crypto/verified-msg/_src/verified-msg/crypto.hpp)
- [solve.py](https://github.com/prathamgupta36/CTF-Writeups/blob/main/2026/tkbctf5_2026/pwn_crypto/verified-msg/solve.py)

## Service overview

The service keeps a global state:

```cpp
struct VerificationState {
  uint256 private_key;
  point_t public_key;
  unsigned char buffer[MAX_MSG];
  Precomp *precomp_ptr = &precomp;
  void (*callback)(void) = admin;
} vstate;
```

Relevant offsets in `vstate`:

- `buffer` at `0x68`
- `precomp_ptr` at `0x8068`
- `callback` at `0x8070`

The binary is PIE, so we first need a base leak. Conveniently, the `give me the gift` path prints the address of `admin`.

## Bug 1: faulty scalar multiplication

The first bug is in `Precomp::fast_scalar_mult()` and `pick()`:

```cpp
for (int i = 0; i < 16; i++) {
  int d = int(uint16_t(kk));
  kk >>= 16;
  if (d > 32767) {
    d -= 65536;
    kk += 1;
  }
  digits[i] = d;
}
...
size_t idx = size_t(abs(digit));
ensure(idx);
point_t pt = decompress(table[idx]);
```

If a 16-bit window becomes `0x8000`, then `d = -32768`. `abs(-32768)` is still `32768`, so `pick()` indexes one past the end of:

- `slot_state[32768]`
- `table[32768]`

That out-of-bounds access matters because `Precomp` is laid out as:

- `slot_state` at offset `0x0000`
- `base` at offset `0x1000`
- `table` at offset `0x1028`

So `slot_state[32768] = true` flips the first bit of `base.x` at offset `0x1000`.

## Triggering the fault

Verification computes:

```cpp
u1 = hash * s^-1 mod N
u2 = r * s^-1 mod N
u1_point = vstate.precomp_ptr->fast_scalar_mult(u1)
```

So we can choose a verifying signature that forces `u1 = 0x8000`.

For the empty message, let:

- `e = H("") mod N`
- `r = 1`
- `s = e * (0x8000)^-1 mod N`

Then `u1 = e * s^-1 = 0x8000`, so verification enters the bad `pick(-32768)` path and flips `precomp.base.x` from `Gx` to `Gx + 1`.

## Why the fault is useful

This is the important structural fact:

- the precomputation table is filled from the original base point `G`
- then the out-of-bounds bit flip changes only `precomp.base`

After that:

- the signer uses `decompress(precomp.base) = G'`
- the verifier still behaves as if it is using the old `G` table

So post-fault signatures are generated on a different base point `G'`, while the verifier remains on the original group.

That gives us faulty signatures we can mine for the private key, while still being able to forge normal verifier-accepted signatures after recovery.

## Recovering the private key

### The curve structure

`G' = decompress(Gx + 1, parity(Gy))` is still on the same curve, but its order is not `N`.

Its order is:

```text
ord(G') = N * h
h = 15174272033 = 63031 * 240743
```

That tiny cofactor is the whole weakness.

### What a faulty signature gives us

After the fault, signatures are:

```text
R = k G'
r = x(R)
s = k^-1 (e + r d) mod N
```

From `r = x(R)` we only know `R` up to sign, but that is enough:

1. Lift `r` to a point on the curve.
2. Multiply by `N`.
3. This projects onto the small torsion subgroup generated by `N G'`.
4. Solve a tiny discrete log there to recover `k mod h`, up to the expected global sign ambiguity.

So each faulty signature gives:

```text
k ≡ ±a_i (mod h)
```

### Turning that into `d`

Write:

```text
k_i = a_i + h t_i
```

Plug into the signature equation:

```text
s_i (a_i + h t_i) ≡ e_i + r_i d (mod N)
```

Rearranging gives a standard hidden-number style problem. With a handful of samples, the unknowns `t_i` are small enough that LLL + Babai is enough to recover `d`.

In practice:

- collect 8 faulty signatures
- compute the two residue candidates `±a_i`
- branch over the `2^8` sign choices
- run Babai on the reduced lattice
- validate candidates locally by recomputing `x(k G')`

That is what [solve.py](https://github.com/prathamgupta36/CTF-Writeups/blob/main/2026/tkbctf5_2026/pwn_crypto/verified-msg/solve.py) does.

## Phase 1 result: normal forgeries

Once `d` is recovered we can forge ordinary verifier-accepted signatures on the original base `G`.

That gives two useful actions:

1. Forge `give me the gift` and leak the address of `admin`.
2. Forge `i'm admin`, which only calls `admin()` and prints `you are admin!`.

That is not enough for the flag, so we still need the memory bug.

## Bug 2: sign-path overflow

In the sign path:

```cpp
memcpy(&vstate.buffer[len], &s, sizeof(s));
len += sizeof(s);
memcpy(&vstate.buffer[len], &r.x, sizeof(r.x));
len += sizeof(r.x);

write_bytes(vstate.buffer, min(len, MAX_MSG));
```

If `len` is near `0x8000`, the appended `s || r.x` overflows past `buffer`.

The useful case is:

```text
msg_len = 0x7fc2
```

Then:

- `s` fits entirely
- the last 2 bytes of `r.x` overwrite the low 2 bytes of `precomp_ptr`

So every overflow-sign attempt randomizes:

```text
precomp_ptr_low16 = top16(r.x)
```

Directly smashing `callback` is not enough, because verification dereferences `precomp_ptr` before calling `callback`. A broken pointer crashes first.

So the exploit must be staged.

## Turning `precomp_ptr` into an arbitrary 40-byte write

The key observation is that `Precomp::ensure(1)` does:

```cpp
table[1] = base;
slot_state[1] = true;
```

If we can make `precomp_ptr` point to a fake `Precomp` object, then a verify with:

- `u1 = 1`
- `r = 0`
- `s = H(msg)`

forces `ensure(1)`, and therefore copies 40 bytes from fake `base` to fake `table[1]`.

For a fake object at:

```text
P1 = precomp_ptr_abs - 0x1050 = pie_base + 0x10298
```

the fake `table[1]` starts exactly at `precomp_ptr`, so `table[1] = base` becomes a 40-byte controlled write over:

- `precomp_ptr`
- `callback`
- the following 24 bytes

## Why the first stage can be blind

The overflow-sign only controls the low 16 bits of `precomp_ptr`, so landing exactly on `P1` would be a `1/65536` event.

But we do not need the exact pointer.

If the randomized pointer is:

```text
P1 - s,  0 <= s <= 32
```

then the 40-byte `table[1] = base` write starts up to 32 bytes before `precomp_ptr` and still fully covers the 8-byte `precomp_ptr` slot.

That gives 33 useful states:

```text
Pr[hit in one overflow-sign] = 33 / 65536 ≈ 5.0e-4
```

So one blind loop is:

1. Do `sign(msg_len = 0x7fc2)` to randomize `precomp_ptr_low16`.
2. Send a universal stage-A verify message.
3. If the pointer happened to land in the useful window, stage A rewrites `precomp_ptr = P1`.

## The three-stage pwn chain

### Stage A: normalize `precomp_ptr`

Use a fake `Precomp` message that works for every useful shift in the `0..32` window.

Goal:

```text
precomp_ptr = P1
```

After this point we have an exact fake-object anchor.

### Stage B: install the final fake object

Now `precomp_ptr = P1`, so the 40-byte write is exact.

Write:

```text
precomp_ptr = buffer + 1
callback    = system@plt
```

The `buffer + 1` detail matters.

If we pointed `precomp_ptr` at `buffer`, then the next `ensure(1)` would set `slot_state[1] = true`, which writes bit 1 into the first byte of `buffer` and breaks the `"i'm admin"` prefix before the callback check.

Pointing at `buffer + 1` moves that one-bit write onto the apostrophe byte in:

```text
i'm admin';cat /flag*;#
```

That byte is already `0x27`, so the write is harmless and the prefix survives.

### Stage C: final forged admin verify

With `precomp_ptr = buffer + 1`, we build one last fake `Precomp` inside the message itself:

- fake `table[1].x = 0`
- fake parity byte = `0`

Then verify:

```text
r = 0
s = H(msg)
```

This makes:

```text
u1 = 1
u2 = 0
u1_point = fast_scalar_mult(1) = table[1] = point with x = 0
```

So the check passes with `r = 0`.

The message starts with the required admin prefix and then closes the shell quote:

```text
i'm admin';cat /flag*;#\0
```

At the callback site:

- verification already succeeded
- `memcmp(vstate.buffer, "i'm admin", 9) == 0`
- `callback == system`
- `rdi == vstate.buffer`

So the binary executes:

```c
system(vstate.buffer);
```

The shell first tries to run `im admin`, which fails harmlessly, then runs `cat /flag*`.

That is why the final output contains:

```text
sh: 1: im admin: not found
tkbctf{...}
```

## Local validation

The final exploit was validated locally first:

```bash
python3 solve.py --local
```

Local payload:

```text
i'm admin';echo PWNED;#
```

Expected output:

```text
verified!
sh: 1: im admin: not found
PWNED
```

## Remote execution notes

The crypto phase is deterministic and reliable.

The pwn phase is probabilistic:

- each blind loop succeeds with probability about `33 / 65536`
- the remote jail only allows about 300 seconds
- in practice, a single remote session does not get many pwn loops after the expensive fault + key-recovery stage

So the practical solve is to run several independent workers in parallel, each with a modest loop budget.

Example:

```bash
for i in $(seq 1 24); do
  PWN_MAX_LOOPS=120 /tmp/fpyenv/bin/python solve.py 35.194.108.145 10887 > /tmp/vmsg_$i.log 2>&1 &
done
wait
```

In my final run, one worker hit immediately after entering the pwn loop and printed the flag.

## Final exploit outline

1. Trigger the `-32768` precomp fault with a chosen verification.
2. Collect 8 faulty signatures from the corrupted signer.
3. Recover `d` using small-subgroup residue extraction plus lattice recovery.
4. Forge `give me the gift` and leak `admin`, hence the PIE base.
5. Repeatedly:
   - overflow-sign to randomize the low 2 bytes of `precomp_ptr`
   - run stage A to normalize `precomp_ptr = P1` if the random pointer landed in the useful window
   - run stage B to install `precomp_ptr = buffer + 1` and `callback = system`
   - run stage C to verify an admin-prefixed shell payload and execute `cat /flag*`
6. Read the flag.

## Flag

```text
tkbctf{y34h_u_4r3_4dm1n!-2b99ef896e9ad1706e046d3500319f21df4abcc9914655934b5b477d7fb649dc}
```