ChronoGrind

Task description

Patience isn’t a virtue here, it’s the only exploit. The wearable sealed the coach’s message, and the only key is the one you earn. state.dat is stubborn but honest, it keeps notes on itself. No bugs, no leaks, no shortcuts, and no, your cores won’t save you. Bring a charger.

Approach

Deobfuscate state.dat

The hexdump shows runs of LLLL (0x4c) where zeros would be, so everything after the 4-byte CGD1 magic is XORed with 0x4c. After XOR the body is a TLV stream: 1-byte record id, 4-byte little-endian length, payload. Ids are hex-looking (0x11, 0x22, … 0x88).

Read the notes

Record 0x77 is plaintext and describes the entire derivation:

anchor = rec[11] (base241), seed = rec[22] (base241), cycles = rec[33] (decimal)
chk = rec[44] = sha256('anchor:seed:cycles' as decimal, colon-separated)[:8]
derivation: v = seed; repeat cycles times: v = v*v mod anchor
k = sha256(v as 256-byte big-endian)
msg container CGFX: magic 'CGFX'(4) ver(1) nonce(12) tag(16) ct(rest)
aead = chacha20-poly1305, key = k, nonce = nonce field

Parse the parameters

A quick parser XOR-decodes and extracts each record, then interprets the base-241 digits:

import hashlib, sys

x = open(sys.argv[1], 'rb').read()
recs = {}
i = 6
while i < len(x):
    rid = x[i]; ln = int.from_bytes(x[i+1:i+5], 'little')
    recs[rid] = x[i+5:i+5+ln]; i += 5 + ln

def b241(b, be=True):
    n = 0
    for d in (b if be else b[::-1]):
        assert d < 241, d
        n = n * 241 + d
    return n

cycles = int(recs[0x33])
chk = recs[0x44]
for be in (True, False):
    a = b241(recs[0x11], be); s = b241(recs[0x22], be)
    h = hashlib.sha256(f'{a}:{s}:{cycles}'.encode()).digest()[:8]
    print('be' if be else 'le', h.hex(), chk.hex(), h == chk,
          a.bit_length(), s.bit_length())
    if h == chk:
        open(sys.argv[2], 'w').write(f'{a}\n{s}\n{cycles}\n')

Records 0x11 and 0x22 are 259 base-241 digits each. Interpreting them big-endian gives a 2048-bit anchor and a 2045-bit seed, and the SHA-256 checksum in record 0x44 matches (little-endian does not). Cycles = 9,000,000,000. Record 0x55 is a taunt (“the anchor holds. keep grinding.”), 0x66 is a 2047-bit decoy that is neither the answer nor an early checkpoint, 0x01 is team=testrun.

Look for a shortcut (none found)

Knowing the factorization of the anchor would reduce the exponent modulo phi and finish instantly, so this was worth checking: the anchor is composite, has no factor below 2 million, is not a perfect power, Fermat finds no close factors, and 28 parallel ECM workers (sympy, B1 up to 250k, factors up to ~35 digits) found nothing. The hint record is not a usable checkpoint.

Grind

The chain runs with gmpy2’s powmod on exponents of 2^(2^20), checkpointing every 2^20 squarings:

import gmpy2, time, sys, os, hashlib
from gmpy2 import mpz, powmod

a, s, c = [int(l) for l in open(sys.argv[1]).read().split()]
ck = sys.argv[2]
a = mpz(a); v = mpz(s); done = 0
if os.path.exists(ck):
    done, vs = open(ck).read().split(); done = int(done); v = mpz(vs)
CH = 2**20; e = mpz(1) << CH
t0 = time.time(); start = done
while done < c:
    step = min(CH, c - done)
    v = powmod(v, (mpz(1) << step) if step != CH else e, a)
    done += step
    tmp = ck + '.tmp'
    open(tmp, 'w').write(f'{done}\n{v}\n')
    os.replace(tmp, ck)
    if (done // CH) % 50 == 0:
        el = time.time() - t0; rate = (done - start) / el
        print(f'{done} ({done/c*100:.2f}%) {rate/1e6:.3f} Msq/s '
              f'ETA {(c-done)/rate/60:.1f} min', flush=True)
print('DONE', v, flush=True)
k = hashlib.sha256(int(v).to_bytes(256, 'big')).hexdigest()
open(ck + '.final', 'w').write(f'{v}\n{k}\n')

Native C against GMP (grind.c, and a hand-rolled mpn-level Montgomery loop in mont.c) runs at the same ~0.86 µs per squaring, so the GMP assembly kernels are the floor on this CPU. Threads cannot help: each squaring depends on the previous one. Total time about 2 h 20 min.

Decrypt

The final step hashes the chain’s end value as a 256-byte big-endian integer, then runs ChaCha20-Poly1305 with the nonce from flag.enc:

import sys, hashlib
from Crypto.Cipher import ChaCha20_Poly1305

lines = open(sys.argv[1]).read().split()
v = int(lines[1]) if len(lines) > 1 and lines[0].isdigit() and len(lines[0]) < 20 else int(lines[0])
enc = open(sys.argv[2], 'rb').read()
assert enc[:4] == b'CGFX'
nonce, tag, ct = enc[5:17], enc[17:33], enc[33:]
k = hashlib.sha256(v.to_bytes(256, 'big')).digest()
print(ChaCha20_Poly1305.new(key=k, nonce=nonce).decrypt_and_verify(ct, tag).decode())

The tag verifies and the plaintext is the flag.

Lessons

• Running ECM on all cores alongside the grind cut the grind’s clock boost almost in half. On a desktop CPU, leave the sequential chain alone.
• The “under 60 minutes” figure assumes a faster single-thread core (roughly 0.4 µs per 2048-bit squaring on current Apple or Intel parts).