UniVsThreats 26 Quals CTF - Celestial Body - Cryptography Writeup

Category: Cryptography

Flag: UVT{0rb1t4l_c0ngru3nc3_m4k35_pr3d1ct4ble_k3y5}

Challenge Description#

We’ve intercepted a highly classified deep-space transmission!

We know the date the transmission began, but not the exact moment. The spacecraft broadcasts a cryptographic fingerprint of the time alongside its non-consecutive telemetry windows and five snapshots of its internal state, sampled at irregular intervals to resist eavesdropping.

Each sector is authenticated by the spacecraft’s onboard Transmission Authentication Protocol. The signatures are included in the transmission log.

Can you decrypt the flag?

Analysis#

The first thing that mattered was the epoch_hash: only the day is known, but the script truncates sha256("HH:MM:SS") to 16 hex chars, so this is a tiny 86,400-search space. I brute-forced all times in the day immediately.

1
import hashlib
2
h="8b156702c993b9b5"
3
for hh in range(24):
4
    for mm in range(60):
5
        for ss in range(60):
6
            t=f"{hh:02d}:{mm:02d}:{ss:02d}"
7
            if hashlib.sha256(t.encode()).hexdigest()[:16]==h:
8
                print(t)
9
                raise SystemExit

1
04:12:55

With the exact timestamp recovered, I pulled the important constants from both files to make sure the math model matched the implementation: a 512-bit LCG modulus prime, five non-consecutive samples at steps [0,4,10,18,28], and each sample leaking only the upper 192 bits (UNKNOWN_BITS = 320).

1
rg -n "TRUNCATE_BITS|UNKNOWN_BITS|STEPS|epoch_hash|tap_sign|generate_telemetry" encrypt.py

1
9:TRUNCATE_BITS = 192
2
10:UNKNOWN_BITS  = PRIME_BITS - TRUNCATE_BITS
3
11:STEPS         = [0, 4, 10, 18, 28]
4
65:def generate_telemetry(a, b, p):
5
74:        outputs.append(state >> UNKNOWN_BITS)
6
120:    epoch_hash = hashlib.sha256(time_str.encode()).hexdigest()[:16]

1
rg -n "epoch_hash|^p =|t_[0-9]+|iv\s*=|ciphertext\s*=|sig_t" output.txt

1
2:epoch_hash          = 8b156702c993b9b5
2
3:p = 10035410270612815279389330410121900529620495869479898461384631211745452304638984576440553552006414411373806160282016417372459090604747980402493134112626213
3
5:  t_0 = 1129223615711367884405014640005288172041367198689786688285
4
6:  t_4 = 579514026315281536883405991880758556036404753274817543322
5
7:  t_10 = 1279648546218423539959079224022586160480305721841176089544
6
8:  t_18 = 1946366015289015629063708515503091199628321083313573104031
7
9:  t_28 = 3902208990133988884490762855871313599751888895643028675415
8
10:iv         = ba04a327ffd0c69205ff5dcb5f463d9c
9
11:ciphertext = 1879e4d0f174c9a6d2be99b6f632cc0f3ea89989e69dbd080761cb616b37d8eba37635de6c6475d741f69450c8259590
10
19:  sig_t00 = (r=289099664372750378797408625704893428920316669030, s=952632243424303327990876772909325222302098148060)
11
20:  sig_t04 = (r=289099664372750378797408625704893428920316669030, s=1272131170288215264283670079256435522443165444185)
12
21:  sig_t10 = (r=289099664372750378797408625704893428920316669030, s=934252686529025066385350090392561039201739148363)
13
22:  sig_t18 = (r=289099664372750378797408625704893428920316669030, s=727371275836726048686075601698051388854630211444)
14
23:  sig_t28 = (r=289099664372750378797408625704893428920316669030, s=886522231176385982733156462394271368291922808313)

The repeated DSA r value is a nonce-reuse smell, so I briefly considered recovering the TAP signing key first, but that would not directly yield the AES key because encryption depends on the LCG final state, not the signing secret.

cry

The clean path was recovering the hidden 320-bit suffix of state_0 from truncated outputs. After deriving a,b from the Halley coordinate seed at 04:12:55, I used the affine relation state_s = a^s*state_0 + b*(a^s-1)*(a-1)^(-1) mod p, rewrote each sample constraint as a bounded modular equation, then solved the hidden-number instance with an LLL-reduced CVP lattice (fpylll). That gives low(state_0), reconstructs exact states at steps 4/10/18/28, and then the script computes final_state, derives SHA-256 key material, and decrypts the CBC ciphertext.

1
import hashlib
2
from Crypto.Util.number import bytes_to_long,long_to_bytes
3
from skyfield.api import load
4
from skyfield.data import mpc
5
from skyfield.constants import GM_SUN_Pitjeva_2005_km3_s2 as GM_SUN
6
from fpylll import IntegerMatrix, LLL, CVP
7
from Crypto.Cipher import AES
8
from Crypto.Util.Padding import unpad
9

10
p=10035410270612815279389330410121900529620495869479898461384631211745452304638984576440553552006414411373806160282016417372459090604747980402493134112626213
11
tele={0:1129223615711367884405014640005288172041367198689786688285,4:579514026315281536883405991880758556036404753274817543322,10:1279648546218423539959079224022586160480305721841176089544,18:1946366015289015629063708515503091199628321083313573104031,28:3902208990133988884490762855871313599751888895643028675415}
12
M=1<<320
13
iv=bytes.fromhex("ba04a327ffd0c69205ff5dcb5f463d9c")
14
ct=bytes.fromhex("1879e4d0f174c9a6d2be99b6f632cc0f3ea89989e69dbd080761cb616b37d8eba37635de6c6475d741f69450c8259590")
15

16
h="8b156702c993b9b5"
17
found=None
18
for hh in range(24):
19
    for mm in range(60):
20
        for ss in range(60):
21
            t=f"{hh:02d}:{mm:02d}:{ss:02d}"
22
            if hashlib.sha256(t.encode()).hexdigest()[:16]==h:
23
                found=(hh,mm,ss); break
24
        if found: break
25
    if found: break
26
print("time",found)
27

28
with load.open("CometEls.txt") as f:
29
    comets=mpc.load_comets_dataframe(f)
30
comets=comets.set_index("designation",drop=False)
31
row=comets.loc["1P/Halley"]
32
ts=load.timescale(); t=ts.utc(2026,1,26,*found)
33
eph=load("de421.bsp"); sun=eph["sun"]
34
halley=sun+mpc.comet_orbit(row,ts,GM_SUN)
35
x,y,z=sun.at(t).observe(halley).position.au
36
coord=f"{x:.10f}_{y:.10f}_{z:.10f}"
37
a=bytes_to_long(hashlib.sha512((coord+"_A").encode()).digest())
38
b=bytes_to_long(hashlib.sha512((coord+"_B").encode()).digest())
39
print("coord",coord)
40

41
steps=[4,10,18,28]
42
A=[]; D=[]
43
for s in steps:
44
    As=pow(a,s,p)
45
    Bs=(b*(As-1)*pow(a-1,-1,p))%p
46
    Di=(As*tele[0]*M + Bs - tele[s]*M)%p
47
    A.append(As); D.append(Di)
48

49
B=IntegerMatrix(5,5)
50
B[0,0]=1
51
for i in range(4):
52
    B[0,i+1]=A[i]
53
for i in range(4):
54
    B[i+1,i+1]=p
55
LLL.reduction(B)
56
v=CVP.closest_vector(B,[0]+[-x for x in D])
57
l0=int(v[0])
58
print("l0_bits",l0.bit_length())
59

60
s0=tele[0]*M+l0
61
def adv(s,n):
62
    for _ in range(n):
63
        s=(a*s+b)%p
64
    return s
65
s28=adv(s0,28)
66
final_state=(a*s28+b)%p
67
key=hashlib.sha256(long_to_bytes(final_state)).digest()
68
pt=unpad(AES.new(key,AES.MODE_CBC,iv).decrypt(ct),16)
69
print(pt.decode())

1
time (4, 12, 55)
2
coord -19.4862860815_29.1000971321_1.8433470888
3
l0_bits 320
4
UVT{0rb1t4l_c0ngru3nc3_m4k35_pr3d1ct4ble_k3y5}

Once the lattice candidate satisfied all truncated telemetry equations and decrypted clean PKCS#7 output with the expected UVT{...} format, the solve was complete.

dance

Solution#

1
# !/usr/bin/env python3.12
2
import hashlib
3
from Crypto.Util.number import bytes_to_long, long_to_bytes
4
from skyfield.api import load
5
from skyfield.data import mpc
6
from skyfield.constants import GM_SUN_Pitjeva_2005_km3_s2 as GM_SUN
7
from fpylll import IntegerMatrix, LLL, CVP
8
from Crypto.Cipher import AES
9
from Crypto.Util.Padding import unpad
10

11
p = 10035410270612815279389330410121900529620495869479898461384631211745452304638984576440553552006414411373806160282016417372459090604747980402493134112626213
12
tele = {
13
    0: 1129223615711367884405014640005288172041367198689786688285,
14
    4: 579514026315281536883405991880758556036404753274817543322,
15
    10: 1279648546218423539959079224022586160480305721841176089544,
16
    18: 1946366015289015629063708515503091199628321083313573104031,
17
    28: 3902208990133988884490762855871313599751888895643028675415,
18
}
19
M = 1 << 320
20
iv = bytes.fromhex("ba04a327ffd0c69205ff5dcb5f463d9c")
21
ct = bytes.fromhex("1879e4d0f174c9a6d2be99b6f632cc0f3ea89989e69dbd080761cb616b37d8eba37635de6c6475d741f69450c8259590")
22

23
epoch_hash = "8b156702c993b9b5"
24

25
found = None
26
for hh in range(24):
27
    for mm in range(60):
28
        for ss in range(60):
29
            t = f"{hh:02d}:{mm:02d}:{ss:02d}"
30
            if hashlib.sha256(t.encode()).hexdigest()[:16] == epoch_hash:
31
                found = (hh, mm, ss)
32
                break
33
        if found:
34
            break
35
    if found:
36
        break
37

38
with load.open("CometEls.txt") as f:
39
    comets = mpc.load_comets_dataframe(f)
40

41
comets = comets.set_index("designation", drop=False)
42
row = comets.loc["1P/Halley"]
43
ts = load.timescale()
44
t = ts.utc(2026, 1, 26, *found)
45
eph = load("de421.bsp")
46
sun = eph["sun"]
47
halley = sun + mpc.comet_orbit(row, ts, GM_SUN)
48
x, y, z = sun.at(t).observe(halley).position.au
49

50
coord = f"{x:.10f}_{y:.10f}_{z:.10f}"
51
a = bytes_to_long(hashlib.sha512((coord + "_A").encode()).digest())
52
b = bytes_to_long(hashlib.sha512((coord + "_B").encode()).digest())
53

54
steps = [4, 10, 18, 28]
55
A = []
56
D = []
57
for s in steps:
58
    As = pow(a, s, p)
59
    Bs = (b * (As - 1) * pow(a - 1, -1, p)) % p
60
    Di = (As * tele[0] * M + Bs - tele[s] * M) % p
61
    A.append(As)
62
    D.append(Di)
63

64
B = IntegerMatrix(5, 5)
65
B[0, 0] = 1
66
for i in range(4):
67
    B[0, i + 1] = A[i]
68
for i in range(4):
69
    B[i + 1, i + 1] = p
70

71
LLL.reduction(B)
72
v = CVP.closest_vector(B, [0] + [-x for x in D])
73
l0 = int(v[0])
74

75
s0 = tele[0] * M + l0
76
assert 0 <= s0 < p
77

78
def advance(state, rounds):
79
    for _ in range(rounds):
80
        state = (a * state + b) % p
81
    return state
82

83
s28 = advance(s0, 28)
84
final_state = (a * s28 + b) % p
85

86
key = hashlib.sha256(long_to_bytes(final_state)).digest()
87
pt = unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(ct), 16)
88
print(pt.decode())

1
python3.12 solve.py

1
UVT{0rb1t4l_c0ngru3nc3_m4k35_pr3d1ct4ble_k3y5}