Hack-a-Sat CTF Writeup: My 0x20 (aka ”Myspace”)
This is a writeup for the [Hack-a-Sat Quals](https://www.hackasat.com/ official website). (CTFTime)
When starting the problem, we're given a file with a list of coordinates and magnitudes, much like the previous problem "Spacebook". Here's a sample of the data:
... 0.12917758470082333, -0.2996856516398318, 0.9452521683720546, 549.118689999994 0.9470828032590738, 0.18779474775162674, -0.2603215252103395, 548.9928088571726 0.3236837032119143, -0.8780904407801409, 0.35240039455931266, 548.9327142902704 0.798881708067067, -0.21898034565040206, 0.5602103397248893, 548.9047957821459 -0.7525373837675844, 0.6060528002980617, 0.2576576978922172, 548.9041671760551 0.5549178539066054, 0.160929115618912, 0.8161911511170666, 548.8550712650854 ...
and so on, with 2500 lines. Like Spacebook, these are presumably the (x,y,z,magnitude) coordinates of all stars. We note that the (x,y,z) coordinates are are all unit vectors, and the magnitudes range from 550 to 50.
Next, we connect to the server, and after providing a ticket, we are given a list of "query" coordinates, and a prompt:
>> nc myspace.satellitesabove.me 5016 -0.005103, -0.000622, 0.999987, 22.368262 0.034002, -0.142792, 0.989169, 22.305011 -0.086138, -0.111392, 0.990036, 11.131303 0.056385, 0.014707, 0.998301, 10.988331 -0.042894, 0.159913, 0.986199, 10.649103 0.129499, -0.096808, 0.986843, 11.112766 0.040501, 0.008102, 0.999147, 10.688194 -0.168620, 0.029604, 0.985236, 10.479848 0.088160, -0.115219, 0.989420, 9.767099 -0.102337, -0.126756, 0.986641, 10.523903 -0.073148, 0.124094, 0.989571, 9.631445 -0.161086, 0.036724, 0.986257, 9.584012 -0.058411, -0.158301, 0.985662, 10.053369 0.028837, 0.008153, 0.999551, 9.017303 0.044306, 0.042326, 0.998121, 8.170405 -0.138748, 0.032492, 0.989794, 8.064267 -0.001273, 0.102120, 0.994771, 7.653594 -0.054005, -0.142963, 0.988254, 6.228814 Index Guesses (Comma Delimited):
Two key things to note:
The coordinates are all very nearly (0,0,1)
The magnitudes are much smaller than any in the reference database.
Like Spacebook, with think this a problem of [point set registration](https://en.wikipedia.org/wiki/Point_set_registration Wikipedia), identifying which stars in the query match up with which stars in the image. Our "camera" is facing in one direction and only sees a small section of the sky, which is why all the vectors are near (0,0,1). And, since the brightness is not normalized, we don't know what the magnitudes are supposed to correspond to.
In the real world, we would try to estimate the camera's calibration parameters (probably a linear model, for this problem?) and then try to fit. But I figured it would be easier for this problem, which probably had zero noise in the star locations, to just view this as an image recognition task.
The standard approach to image recongition is to compute invariant features that don't depend on your viewpoint. For us, there's really only one thing to do: compute the distances between stars.
This actually gives us a pretty simple algorithm right off the bat:
In the database, compute all 2500x2500 pairwise distances of stars.
Each star now has a set of 2499 distances; sort this list, and consider it the star's "signature".
In input data from the server, we have 20 stars. For each star i:
Compute its 19 distances to its neighbors, a "subsignature".
Check the subsignature for the closest match in the database, where the match error is the sum of differences from the observed distance to the closest distance in the database.
Match star i to the star in the database with the best match.
The whole solution is only 32 lines of python.
import numpy as np from numpy import genfromtxt starlocs = genfromtxt('test.txt', delimiter=',') #reference database nsat = np.shape(starlocs)[0] #number of challenge stars pdist = np.zeros((nsat,nsat)) #pairwise distances for i in range(nsat): for j in range(nsat): pdist[i,j] = np.linalg.norm(starlocs[i,0:3] - starlocs[j,0:3]) dists = np.zeros((nsat,nsat)) #sorted pairwise distances for i in range(nsat): dists[i,:] = pdist[i,:] dists[i,:] = np.sort(dists[i,:]) def dd(row, d2): #error between "signatures" err = 0 for i in d2: err += np.min(np.abs(row - i)) return err def bestrow(d2): #get the best match in the database errs = np.zeros(nsat) for i in range(nsat): errs[i] = dd(dists[i,:], d2) return (np.argmin(errs), np.min(errs)) ch = genfromtxt('chal.txt', delimiter=',') #copy-pasted the challenge from the server here. nch = np.shape(ch)[0] #number of challenge stars pd2 = np.zeros((nch,nch)) #pairwise distance of challenge stars for i in range(nch): for j in range(nch): pd2[i,j] = np.linalg.norm(ch[i,0:3] - ch[j,0:3]) ans = () for s in range(5): ans += (bestrow(pd2[s,:])[0],) #compute the best match for each print(ans) #and print
After the initial hurdle of computing the 6 million distances (~30 seconds, obviously could have been much faster), it takes just a couple seconds to solve any challenge. We only print out the first 5, because the server only required that we submit the indices of any 5. Running it the first time, the indices came out as (40, 185, 202, 601, 742), which was very confidence inspiring: they were already sorted (and thus, in correct order of magnitude!) A minute later we had the flag.
