#ctftime

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

If you've never done assembly, start with the first section here. The other sections are lists of lists of problems, sorted into: high school CTFs, permanent CTFs, challenge repositories, and a few other topic-oriented puzzles. That makes the prior sentence a list-list-list, I'm pretty sure.

Assembly / reversing intros

If you're new to assembly, start with http://www.opensecuritytraining.info/IntroX86-64.html Scroll down to the slides. The first few will give enough assembly to read useful programs. At the "Linux tools" section, it will show you how to compile or disassemble open your own programs. Then finally it will show a bit about how to continue learning more assembly, and gives an example of CMU's binary bomb to start playing. It gives a solid introduction to enough

(If you'd like to start with the x86, not x64 version, you can take the equivalent slides at http://www.opensecuritytraining.info/IntroX86.html )

If you didn't like the above, but want to try reversing on your Windows machine a bit, you can go through the following two:

https://www.ethicalhacker.net/columns/heffner/intro-to-assembly-and-reverse-engineering

https://www.ethicalhacker.net/columns/heffner/intro-to-reverse-engineering-part-2

They also give a quick overview of assembly, and show how to use a disassembler (OllyDbg) on Windows. This doesn't cover any x86-64 (the more modern stuff), though, and is a much more cursoty treatment of assembly.

And finally https://github.com/michalmalik/linux-re-101 has a huge list of info that details most of what you want to know, ever, but is generally more useful as a reference than a tutorial.

High school level challenges

https://2013.picoctf.com/

https://picoctf.com/

http://hackyou.ctf.su/

Permanently online CTFs/Wargames

https://www.starfighters.io/ - Mostly binary analysis, some crypto

https://backdoor.sdslabs.co/ - Mix of different problem types

https://microcorruption.com/ - All binary analysis. Doesn't use a standard instruction set, but is good practice.

http://smashthestack.org/

Smash the Stack requires some elaboration: I mainly recommend (of those up right now) BLACKBOX for reversing/exploitation stuff ("Category 2"). There's also TUX for Linux stuff ("Category 1", not really CTF material), and AMATERIA for language-specific payloads ("Category 5").

http://overthewire.org/wargames/

OtW also has a few subcategories. Bandit/Leviathan/Natas/Krypton all fall under Linux ("Category 1", not CTF stuff). The others are all binary analysis.

Lists of challenges (greatly varying difficulty)

https://github.com/wapiflapi/exrs

http://security.cs.rpi.edu/courses/binexp-spring2015/lectures/2/challenges.zip

http://challenges.re/

http://crackmes.de/

http://www.reteam.org/crackmes.html

http://shell-storm.org/repo/CTF/ (Tons of old CTF problems gathered up here)

https://ctftime.org (Links to basically every CTF ever, with lots of writeups. Finding problems might take digging though)

Other resources

(These aren't actually related obviously but there's not enough for a post of their own yet)

https://projecteuler.net/ (some of this is pretty tricky math and will teach about useful algos/number theory things)

http://cryptopals.com/ (All crypto puzzles)

https://xss-game.appspot.com/ (All web puzzles)

This is a pretty common question for people who want to get into the CTF world (or hacking in general) but don't really know where to start. (If you don't even know what a CTF is, or don't understand how capture the flag relates to computer hacking, check out https://ctftime.org/ctf-wtf/ . We mostly do Jeopardy.) There are lots of books out there or video tutorials, but a disappointingly large number of them are either educating you on a very specific canned tool ("Become a Wireshark Wizard", "Metasploit for Fun and Profit"), and/or are devoid of working examples to practice on. And practice is really the crucial thing here. This is why I always recommend practice sites and old problems instead (and, for everyone I know who plays competitively, this is basically where they got a lot of their education). So the below should be a guide for where to get started.

The correct starting place will vary a lot depending on your current background, and what you want to explore. So, starting with the very basics:

0. Know some quick-to-write programming language. Well.

This can be anything reasonably flexible. Nowadays the standard starter language seems to be Python. I deserve some flak for it, but I do most of my CTF work in Java and Mathematica. (The latter is a closed platform, but if you're a college student you can probably get it free, and it's great for big integer actions or algorithmically oriented problems.) C is also fine and will help for more complicated things down the line, but is probably not the most efficient for many easy tasks.

The language doesn't matter so much as being able to quickly do simple tasks in it. As some examples, you should be able to easy

Read in a file, 4 bytes at a time, and print each of those as a 4-byte integer

Write a matrix multiplication function that works on arbitrary size matrices

Read in a page from a given URL, find all the URLs mentioned that end in ".png", and download those images to a directory

Solve the first 15 problems on Project Euler: https://projecteuler.net/archives

This doesn't mean you need to be able to do all of these right now. I can never remember the syntax for downloading a webpage right away. But you should be able to do each of those above 4 tasks in an hour or less, allowing yourself free access to Google and StackOverflow for anything short of a complete given solution.

If you're not currently at the stage of knowing such a programming language well, then your education is somewhat beyond the scope of this post for now. Take an intro CS course at your university, or look at the incredibly numerous tutorials on line. And again, Project Euler is a great way to start learning about simple little tasks like what you'll often need to do. In particular, you do not need to be familiar with any principles of design or git or anything like that to be a good cracker.

1. Learn basic Linux commands

Like it or not, the world's servers and professional programming environments all run on Linux. And everything interesting you do on Linux is done via the command line. (Not to mention that, usually when you're breaking into another server, you don't have any GUI.)

If you've never used a command line before, then http://ryanstutorials.net/linuxtutorial/ can you get you started with that. Once you understand the basic navigation, a nice place to get started playing around is http://overthewire.org/wargames/bandit/ . This will also give you a place to test if you don't have a personal installation of Linux handy.

If you want a copy of Linux on a machine of your own (and you probably will, very quickly!) your main options are either installing a virtual machine, dual-booting, or finding a shell server you can get a personal account on. The first one means installing it like a normal OS, the second one means running inside of your main OS. You can find plenty of tutorials on both of these online, and their advantages/disadvantages. The third option means finding a club or group that has a server you can get an account on. (Good options are your school's computer clubs, CS department, or maybe even your dorm.)

Beyond the Basics

Now've you got the rudiments, you have a few options for what to pursue. If you want to start "hacking" right away -- the most accessible challenges will be those that are just exploring messed up system configurations. These will teach you a good familiarty with Linux, but don't expect to see any challenges like this in any CTF. This is what http://overthewire.org/wargames/leviathan/ offers. Spend a bit of time on it if you want. But beyond that, you will need to learn more skills.

Sections 3 through 6 below don't have many example problems. The place I really recommend starting off with is picoCTF. You can go to https://2013.picoctf.com/compete#Title and I made a throwaway account for people reading this tutorial. The Team Name is TumblrTutorialThrowaway, and the password is the sum of all primes up to (and including) 31337. At the time of this posting, only the first few problems are unlocked, but quickly I expect to see them all open up. Go through and try to do lots of problems. They'll give you good introductions to applying the material mentioned below.

Beyond that set of problems, there are naturally other CTFs still up (newer picoCTFs, HSCTF on the easy end; and lots and lots of competitive ones). The hub for all CTFs is http://ctftime.org/ . Go there, pick a CTF at random (in general higher rating == harder problems), choose a problem with a category you like, and see if it still works. You can expect all problems to still work except for exploitation and web, which require running a server, and so might dead. These practice problems usually also have writeups, which are great if you have no idea where to start yet.

In no particular order, various skills (which correspond to different problem types) follow, and each of them has no prerequisites on the others unless states.

2.1 Learn C. Understand memory. Know the stack.

This is where you can start digging into classical "exploitation", often referred to as "pwning". You'll have to learn the C language (that is, not C++) well enough to do tasks like:

Read in a file, read in 4-byte integers, print them out in hexadecimal

Build and safely deallocate a linked list

Recursively navigate a directory structure

Understand what a void *, the difference between unsigned char and char, and what it means to "overflow a buffer".

Know what fork() or exec() are, give an example use of each

Know what a function pointer is, give an example use

Once you've got that you can try simple memory exploitation. Terms you'll want to look at "buffer overflow", "stack smashing"; understanding exactly how the stack is structured. Then you really get started. This is what http://overthewire.org/wargames/narnia/ (and other challenges on the site: Behemoth and Utumno) fall under. http://smashthestack.org/ also has a variety like this, but a lot of is much harder. An important feature here is that your challenges will have source code. This is not realistic for almost any competition environments.

2.2 Learn assembly. Learn to reverse engineer. Prereq: 2.1

This is probably still something you can get from a course at your university, to a small degree. However, that course will be oriented towards writing assembly, not reading it. There are many courses out there to give a tutorial on assembly reveng. You should learn how to use a dissassembler (such as objdump) and how to use it on simple programs you wrote yourself. You should learn how to use gdb for watching a program as it executes. Learn how to read registers and memory; how to set breakpoints. You can now try either exploitation problems that don't have source code (like more smash the stack, or OverTheWire's "Maze" category). There are also many problems where reverse engineering is the whole point of the problem. For this, check out a site like http://crackmes.de/ .

If you're getting more serious about this, you'll want a more dedicated disassembler. IDA is the de facto top disassembler. It also has plugins (HexRays) which let it give a good amount of C code. There other free alternatives (https://retdec.com/decompilation/) but they're generally less powerful. There are cracks online of IDA, but be careful, of course. It's also worth looking into decompilers for other bytecodes: Python, Java, and .NET decompilers are all good to have on hand for a CTF, especially entry-level ones.

2.3 Advanced exploitation and reversing Prereq: 2.2

There are many more topics in exploitation that are things you never really need to learn about otherwise. Check out terms like: * ROP (Return-Oriented Programming) * Format string exploitation * ALSR circumvention * Stack canary circumvention * Self-modifying code / homomorphic code (handle this with memory dumps) ... each of these can quickly turn up results online, with old problems to practice on.

3 Cryptography

Obviously this is a whole profession unto itself. But there are many great CTF problems that just require carefully thinking about some math. First thing is to get familiar with how cryptosystems work. Start with simple ones like AES. You don't need to know the exact internals of the "block function", but learn about AES-ECB vs. AES-CBC, for instances, and understand the difference. Then move onto understanding Diffie-Hellman and RSA. Try implementing RSA yourself (encryption and decryption).

Next is attacking them. These will be practical attacks that exploit a flat-out problem in the implementation -- not a fancy cryptanalysis attack like linear or differential cryptanalysis. So you don't need to worry about those. Instead, there are certain well-established attacks to be familiar with, such as

Padding oracles

Coppersmith's attack

Length extension attacks (for hash functions)

Attacks on Electronic Code Book mode encryption

Slider attacks

4 Web

Web problems are a classic groaner. They abound. So you can, for starters,

Learn some PHP, learn its most classic bugs. Learn to abuse them.

Learn SQL injection.

Learn XSS attacks .. these have many example problems online and tutorials, but are often viewed as too easy for CTFs. There are more advanced attacks, though, like

Command-injection attacks

Misconfigured file permissions (.htaccess, .htpasswd, directory listings)

Directory traversal attacks

PHP object injection attacks

Session hijacking

5 Language knowledge

There are some challenges that you just have to know about the specifics of a language well. The classic examples of these are "jails": a program uses an eval unwisely and you have to abuse it. For some examples with Python, you can try to picoCTF tutorial at https://2013.picoctf.com//problems/pyeval/stage1.html (increment the number in the URL for harder versions, up to stage 4). A more professional level challenge is at https://blog.inexplicity.de/plaidctf-2013-pyjail-writeup-part-i-breaking-the-sandbox.html . If you'd like to see an example in a different language, there's a PHP jail at http://blog.dornea.nu/2016/06/20/ringzer0-ctf-jail-escaping-php/ There are also jails in JavaScript, Ruby, Bash, or any language with an eval command.

Then there are deserialization problems (Java's ObjectInputStream, or Python's pickle system), which often require similar knowledge of the language. There are problems just about understanding really odd languages: Can you understand Brainfuck? What about Glass (https://esolangs.org/wiki/Glass)? Can you read obfuscated Erlang, or reverse engineer Haskell that was compiled down to ARM assembly?

6 Forensics and Miscellaneous

These are pretty open ended. A lot of this comes from knowing steganography (low-bit encoding, for instance), file carving, and file system structure (if I give you the middle half of an .iso, can you read it?). Some of it comes from network knowledge (can you use Wireshark?). A lot of it comes from knowing the internals of certain file structures (comments sections in JPEGs, PNGs, or MP3s; how a PNG compresses data). And a lot of it is random bullshit. Really the best option is to read some documentation on file structure, and try old problems: https://ctftime.org/tasks/?tags=misc&hidden-tags=misc

Confused?