has-writeup/aaaa/attitude-adjustment

Attitude Adjustment

Category: Astronomy, Astrophysics, Astrometry, Astrodynamics, AAAA Points (final): 69 points Solves: 62

Our star tracker has collected a set of boresight reference vectors, and identified which stars in the catalog they correspond to. Compare the included catalog and the identified boresight vectors to determine what our current attitude is.

Note: The catalog format is unit vector (X,Y,Z) in a celestial reference frame and the magnitude (relative brightness)

Given files: attitude-papa21503yankee.tar.bz2

Write-up

by erin (barzamin).

For this problem, we have two sets of N vectors which are paired; all points in the first set are just those in the second set up to rotation; we want to find the rotation which maps the first set onto the other one. Since we already know which point in the observation set maps to which vector in the catalog set, we can use the Kabsch algorithm to find the rotation matrix (note that this is called an orthogonal Procrustes problem). I'd only vaguely heard of the Kabsch algorithm before, and in the context of bioinformatics, so I didn't immediately identify it as a good path to the solution. Instead, I just googled "align two sets of vectors", for which it's the third result.

Since nobody has time to implement computational geometry during a ctf, I grabbed an existing Kabsch implementation. For some reason, I didn't notice that scipy.spatial has a Kabsch implementation built in, so I used some random external project, rmsd.

First, load the star catalog:

catalog = {}
with open('./attitude-papa21503yankee/test.txt') as f:
    i = 0
    for line in f:
        [x, y, z, m] = [float(s.strip()) for s in line.split(',')]
        catalog[i] = {'v': np.array([x,y,z]), 'm':m}
        i += 1

Set up some helpers for parsing the output of the challenge server and solving an orientation:

def parse_stars(stardata):
    stars = {}
    for line in stardata.strip().split('\n'):
        line = line.strip()
        star_id = int(line.split(':')[0].strip())
        direction = np.array([float(x) for x in line.split(':')[1].split(',\t')])
        stars[star_id] = direction
    return stars

def solve_orientation(stars, catalog):
    P = np.vstack(list(stars.values()))
    Q = np.vstack([catalog[i]['v'] for i in stars.keys()])
    print("rmsd: {}".format(calculate_rmsd.kabsch_rmsd(P,Q)))
    rotation_mtx = calculate_rmsd.kabsch(P, Q)
    rotation = Rotation.from_matrix(np.linalg.inv(rotation_mtx))
    return rotation

Note that I threw in an inversion of the rotation matrix; this is because I should've been aligning from the catalog to the current star locations. Switching P to be the catalog and Q to be stars would've done the same thing.

Then we just grabbed each challenge from the computer, aligned the sets, and spat the orientation of the satellite back at the server:

TICKET = 'THE_TICKET'
r = tubes.remote.remote('attitude.satellitesabove.me', 5012)
r.send(TICKET+'\n')
time.sleep(0.5)
for _ in range(20):
    r.recvuntil(b'--------------------------------------------------\n', drop=True)
    stars = parse_stars(r.recv().decode())
    rotation = solve_orientation(stars, catalog)
    r.send(','.join([str(x) for x in rotation.as_quat()]) + '\n')
    time.sleep(0.1)
print(r.clean())

The flag should get printed out on stdout by the final line.

Full code

Resources and other writeups

• https://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem
• https://en.wikipedia.org/wiki/Kabsch_algorithm
• https://github.com/charnley/rmsd/tree/master