PACTF, as hosted by the Phillip’s Academy, was a three-round capture-the-flag that took place from April 10th to May 1st. This competition was unique in that it featured a week-long competition window allowing contestants to select their own forty-eight hour time frame. The rounds covered a variety of subject matters and offered challenges from the beginner to downright difficult levels.

We are the Forest Park Bruins, a team of five high school students and aspiring computer scientists from Woodbridge, Virginia:

• Brandon Walker, your’s truly
• Hamza Mir
• Mathew Cinnamon
• Michelle Miller
• Joseph Bokossa

These write-ups will attempt to provide context and strategies for the competition’s problem set. Due to the inopportune timing of the competition however not all solves are documented. Nevertheless, code snippets beginning with $ were run on zsh on Ubuntu 14.04 while snippets beginning with >>> were ran in Python 3.5.

Round 1: Confounding Crypto

This first round covered many different aspects of cryptography, from ancient encoding to modern day ciphers and a lot in between. Thirteen questions were available totaling 585 points; four teams were able to complete all but one of them.

Julius (10 points)

Problem: ’Ojin’ nx ozxy ‘Rtsp’ ns WTY13, nxs’y ny? Bfny, st, ymfy’x ‘Egfc’. Fqxt, ymj kqfl nx ozxy_f_bfwrzu{lIAUuYRT}

Hint: Et tu, Brute?

In good tradition of the many other CTFs before it, PACTF starts us off with the sine qua non of cryptography: the Caesar cipher.

While Caesar’s cipher is oft applied with a shift of 13 characters in what is known as “ROT13”, a function that is effectively its own inverse, this problem leaves finding $$k$$ as an exercise. With only 25 possibilities to verify, it becomes trivial to crack our ciphertext. A few lines of Python later and we have a decrypter in hand:

>>> s = "’Ojin’ nx ozxy ‘Rtsp’ ns WTY13, nxs’y ny? Bfny, st, ymfy’x
‘Egfc’. Fqxt, ymj kqfl nx ozxy_f_bfwrzu{lIAUuYRT}"

>>> uppercase = range(ord('A'), ord('Z')+1)
>>> lowercase = range(ord('a'), ord('z')+1)

>>> def decrypt(s, k):
    out = ""

    for c in s:
        if ord(c) in uppercase:
            out += chr(uppercase[(ord(c)-ord('A')+k)%26])
        elif ord(c) in lowercase:
            out += chr(lowercase[(ord(c)-ord('a')+k)%26])
        else:
            out += c

    return out

>>> for k in range(1, 27):
    print(n, decrypt(s, k))
...
20 ’Idch’ hr itrs ‘Lnmj’ hm QNS13, hrm’s hs? Vzhs, mn, sgzs’r ‘Yazw’.
    Zkrn, sgd ekzf hr itrs_z_vzqlto{fCUOoSLN}
21 ’Jedi’ is just ‘Monk’ in ROT13, isn’t it? Wait, no, that’s ‘Zbax’.
    Also, the flag is just_a_warmup{gDVPpTMO}
22 ’Kfej’ jt kvtu ‘Npol’ jo SPU13, jto’u ju? Xbju, op, uibu’t ‘Acby’.
    Bmtp, uif gmbh jt kvtu_b_xbsnvq{hEWQqUNP}
...

With this, we find that $$k=21$$ and that our flag is just_a_warmup{gDVPpTMO}.

Stegono-saurus (15 points)

Problem: RAWR! No, just kidding. Let’s get down and read some great sociology. A fascinating read in sociology.

Hint: Wait!! Is that a mistake there?

Steganography, a word which shares its root stegos (“covering”) with the armored dinosaur, is a technique of disguising data within an otherwise innocuous medium. As opposed to any plain form of encryption, steganography yields security through obscurity.

A common vehicle of digital steganography are images, as large amounts of data can be encoded without creating any visual cues. Such methods can vary from hiding data in the least significant bits of colors to carefully manipulating a JPEG’s discrete cosine transformation parameters. When given text however, variations are much trickier to conceal. One trick, once again relying on visual deceit, is to replace ASCII characters with Unicode false cognates or to similarly hide control characters or whitespace out of sight. Another approach however, as this problem presents, is to simply inundate any adversaries with an overwhelming amount of data, e.g. the text of a poorly scanned novel.

That last part is actually pretty important here: the text itself, even before any steganographers get their hands on it, is at places disfigured. A quick Google search finds us the original text for further inspection.

A diff then reveals that a series of characters have been slightly altered in our version of the document. (Note: if diff prints out the entire document, it is likely the file line-endings are of different formats. The steg.txt file provided by the competition uses Unix line-endings.)

$ diff -dU0 real.txt steg.txt
--- real.txt    2016-04-24 11:50:52.035013300 -0400
+++ steg.txt    2016-04-24 11:39:53.556189400 -0400
@@ -294 +294 @@
-feeling that through revolution, victory could be wrested from
+feeling that Through revolution, victory could be wrested from
@@ -305 +305 @@
-maze of old errors and illusions and having found at last the key
+maze of old errors and illusions and Having found at last the key
@@ -360 +360 @@
-One of these movements was that towards 'synthesis' in the
+One of thEse movements was that towards 'synthesis' in the
...

$ wdiff -3 real.txt steg.txt

======================================================================
[-through-] {+Through+}
======================================================================
[-having-] {+Having+}
======================================================================
[-these-] {+thEse+}
======================================================================
....

These individual character changes can be pieced together to find our flag: THEFLAGISSTEGISC00L.

Intercepted ZIP (20 points)

Problem: We intercepted a ZIP file that looks important.

Hint: You may need to crack the password. But try to make the guesses educated, okay?

We have a regular old ZIP file, only our flag is protected in it by a symmetric encryption algorithm. Let’s take a look at it:

$ unzip -v intercepted.zip
Archive:  intercepted.zip
YOU ROCK
 Length   Method    Size  Cmpr    Date    Time   CRC-32   Name
--------  ------  ------- ---- ---------- ----- --------  ----
      25  Defl:N       27  -8% 08-23-2015 22:40 9bd829b5  flag.txt
--------          -------  ---                            -------
      25               27  -8%                            1 file

“YOU ROCK”? Well thanks, ZIP file! You know what doesn’t rock though? Storing passwords in plaintext. In 2009, the social network development company RockYou experienced a massive backlash after a data breach exposed the private information of over 32 million users, including an unprecedented number of raw passwords. Good news for the hacker, bad news for the hackee.

This password list can be found all over the internet and even directly downloaded in a handy format. Likewise, there are a plethora of tools for utilizing these files. Let’s hack up a quick script to sort this out.

>>> import zipfile
>>> zip_file = zipfile.ZipFile('intercepted.zip')
>>> with open('rockyou.txt', 'r') as password_list:
        for line in password_list.readlines():
            try:
                password = line.strip('\n')
                zip_file.extractall(pwd=password)
                print(password)
                break
            except:
                pass
soylamejor

A few seconds later, we find out the password was soylamejor.

$ unzip -P soylamejor intercepted.zip
Archive:  intercepted.zip
YOU ROCK
  inflating: flag.txt
$ cat flag.txt
Sazi3K4BwNU0pjRujeFYNxjNY%

Note that the trailing % indicates that the flag file did not have a line ending – the flag itself is only Sazi3K4BwNU0pjRujeFYNxjNY. Of course a traditional brute force would have worked as well, but why waste your time when a password list has already been made?

Dropped the file! (30 points)

Problem: Ah! Noo! I dropped my file!! It’s all scrambled now! Can you help me fix it? I left something in there for you! whoops!

Hint: Is this corrupted, damn!

For what it’s worth, this competition was put together on OS X. As a result, many Apple-specific concepts will come up; fret not Linux/Windows brethren, as every problem can be completed without any worries of finding a friend with a MacBook. In this problem we are presented with a DMG, or Apple disk image, allegedly corrupted, and we are tasked with recovering data from inside of it. It might prove useful to try out a few DMG recovery solutions, but try not to get too ahead of yourself.

DMG files can optionally be compressed; the file header in our case is obscured so the best we can get so far is to hope that the contained files were left uncompressed. The file can now either be scanned against a list of known file signatures, or less scientifically by one’s own eyes.

$ xxd "Dropped a file.dmg" | less

Its generally safe to skip the first few hundred bytes. Files may also be aligned and therefore have padding bytes in between – keep on the lookout for any peculiar patterns. A ways down the file we spot this, followed by some intriguing XML:

00002030: 253d 1663 74af c8f3 4845 5245 3842 5053  %=.ct...HERE8BPS

A quick search tells us we’ve struck an Adobe Photoshop file starting at 0000203c (apparently 8B is an abbreviation of Adobe?). We can extract this PSD and find an very faint image, which after some contrast adjustments reads:

Our flag is aPhotoSopFileInwhite?ThisIsHardlyFair.

Surfing Keys (40 points)

Problem: An agent in a tough spot managed to get to a terminal and quickly type in the password to RoboCorp’s new website, but alas! It wasn’t his computer, and the message seems jumbled up:

qwfpgjurtypkyybrsvypaespyyir

Hint: Look down. To your fingers. Look closely, and see the infinite number of possibilities for your keys, and find the right one.

Keyboard layouts can come in all different sorts of flavors. While most keyboards taste like QWERTY, a few radical alternatives exist and thrive in enthusiast communities. These layouts typically offer things like ergonomics or efficiency gains at the expense of having to relearn one’s muscle memory patterns. Two of the most popular choices are Dvorak and Colemak.

Immediately it should be clear from the top row what’s going on: the agent typed the message on a Colemak keyboard assuming that it was QWERTY. Decoding the message is as easy as mapping the Colemak key to the same position on the QWERTY layout.

>>> qwerty = 'qwertyuiopasdfghjkl;zxcvbnm'
>>> colemak = 'qwfpgjluy;arstdhneiozxcvbkm'
>>> ''.join(qwerty[colemak.index(c)] for c in 'qwfpgjurtypkyybrsvypaespyyir')
'qwertyisfornoobsdvorakdrools'

Too Much Resistance (40 points)

Problem: Black, blue, red, white!!! AHHHH! TOO MANY COLORS!

Hint: What could they possibly mean?

Electrical resistance is defined as a measure of the difficulty electrical current experiences traveling through a conductor. Given a choice, current will always travel the past of least resistance. Whereas an ideal wire will have little to no resistance, a resistor is specially made to have a certain value defined in the unit Ohms ($$ \Omega $$). To make identifying through-hole, axial-lead resistors easier, a common color mnemonic described by IEC 60062 is used.

Typically, resistors will have four or five color bands describing the two significant figures, a multiplier, and a percent tolerance. Looking at our file, we only see three colors per line however. Maybe a better description would have been “too few colors!”. Nevertheless, we can continue on assuming that all three colors refer to digits themselves. Every single row sums to be within the 0x61 - 0x7a range, suggesting that they are each likely encoding individual characters. Let’s see what it’s trying to tell us!

>>> inp = """Brown Brown Brown
Brown Black Yellow
Brown Black White
Brown Brown Brown
Brown Black Yellow
Brown Black White
Brown Brown Brown
Brown Black Yellow
Brown Black White
Brown Brown Blue
Brown Black Yellow
Black White Violet
Brown Brown Blue
Brown Brown White
Black White Violet
Brown Brown Green
Black White Violet
Brown Black Red
Brown Brown Violet
Brown Brown Black
Brown Brown Black
Brown Red Brown
Brown Brown Brown
Brown Brown Black
Brown Black Brown""".split('\n')

>>> COLOR_VALUES = ['Black', 'Brown', 'Red', 'Orange', 'Yellow', 'Green', 'Blue', 'Violet', 'Grey', 'White']

>>> for line in inp:
    colors = line.split(' ')

    value = COLOR_VALUES.index(colors[0]) * 100
    value += COLOR_VALUES.index(colors[1]) * 10
    value += COLOR_VALUES.index(colors[2])

    print(chr(value), end='')
ohmohmohmthatwasafunnyone

You are a square. (45 points)

Problem: It is a simple fact. If you want to solve this one, you gotta think like a square.

Hint: Be the square, invert your square!

In terms of cryptography, there are a few ideas centered around creating squares, such as the four-square cipher or the related Playfair cipher. While these are good ideas worth investigating, one will eventually hit a dead end and wonder exactly what is supposed to be inverted. The problem is actually much simpler, provided an understanding of basic matrix operations.

A square matrix refers to a matrix, that is, well, square. It has just as many rows as it does columns. Not to be confused with the reciprocal of a matrix, a matrix $$m$$ can be “inverted” by transposing it. The transpose of a matrix $$m^\intercal$$ can be found by reflecting it over its main diagonal which would for instance make a $$2 \times 3$$ matrix into a $$3\times 2 $$ matrix but in our case leaves our square the same shape.

$$ \left ( \begin{array}{ccccc} A & B & C & D & E \\F & G & H & I & J \\ K & L & M & N & O \\ P & Q & R & S & T \\ U & V & W & X & Y\end{array} \right )^{\intercal} = \left ( \begin{array}{ccccc} A & F & K & P & U \\ B & G & L & Q & V \\ C & H & M & R & W \\ D & I & N & S & X \\ E & J & O & T & Y\end{array} \right ) $$

Conveniently enough this can be achieved by Python’s built-in zip function.

>>> m = [list(row) for row in 'abcde fghij klmno pqrst uvwxy'.split(' ')]
>>> mt = list(zip(*m))

To decode the original message, we just calculate the position of the letter in the original matrix $$ m $$ and use its new value in $$ m^\intercal $$.

$$ L=m_{3,2} \rightarrow m^\intercal_{3,2}=H $$

>>> ''.join(mt[int((ord(c)-65)/5)][(ord(c)-65)%5].upper() if c.isalpha() else c for c in 'BHAG QS GEUSS YWE\'NU RPX A SIEANU! TDSWGDDS')
'flag is guess you're ndt a square! xpsogpps'

Correcting the letter casing, we get the flag to be XPSOGPPS (contrary to what it is telling us).

Blaise de Infiltration (50 points)

Problem: Psst! It’s the monkey. I managed to steal some data from EvilCorp, but I had to book it before they caught me, so I didn’t have time to break it… At any rate, I’ve left the file for you da-message, so you should take a look at it when you get the chance. They mentioned it being some kind of french cipher from the 1500s, but then they were also talking about some turkish snack food in World of Warcraft, or something… Beats me.

Hint: What’s the opposite of a Variant Beaufort?

The flag is monkeyseemonkeydo.

Lost Keys (50 points)

Problem: Hey, I’m Cameron Wong. I had a flag ready for you, but it seems that it’s locked away somewhere, and I’ve lost my keys… What I do have, though, is a door, maybe you can try getting into that?

Hint: If your first instinct was to google my name and/or my username, you’re barking up the wrong tree! I’m way more narcissistic than that! Also, I hate typing spaces in keys, that’s just annoying.

The flag is ireallyhatereconproblems.

Got Bits (55 points)

Problem: Ha-ha! I’ve encrypted it! With RSA! There’s no way you can get it now! daSecret.

Hint: 512? Hope you started this problem early…

There are no tricks up anyone’s sleeves for this problem: the objective is plainly to factor the 154 digit prime modulo. Given the time frame, this is a rather ridiculous request and we were only able to honor it after hours of intense computing.

Not-So-Random Randomness (60 points)

Problem: I’ve strengthened my RSA now! Now you got noo chance! encrypted.txt

Hint: With this ‘completely’ random seed from my old debian. This 2048-bit RSA key is unbreakable.

Ironically and despite appearances, this problem is easier to solve than “Got Bits”. While RSA is usually only vulnerable to those with lots of resources at hand, small implementation mistakes have time and time again led to massive exploit vectors.

The flag is D0n't_Always_TRusT_DaT_D3bian.

Phillips Decryption Service (70 points)

Problem: Welcome to the PA decryption service! You can decrypt any message that was encrypted using this key! Don’t bother trying to decrypt out flag, though, there’s no way you could ever get that! Oh, if you’re wondering, the server source can be found here

nc 198.211.110.148 59292

Hint: I wonder if we could just math out a way to get the original message?

The flag is flag{0opZ_i_g00fd}.

Unbreakable (80 points)

Problem: This encryption is unbreakable! Good luck getting this one!

2c511e041c15171c461018060c44110e17481e1f0e0651101c04060b531a0d58542410411651070406511e070d02501e17114505130658101d0012185305020600580b0e0405011444

25010e52171e0f014b5013100511460b070d530c001f540751091d121b034b54041746111900184851113c57052f030a50223910584909301a14171c091f07040c1d020c1408081f0c

Hint: Don’t drag your feet, welcome to my crib! Don’t throw out your

keys, just use them over and over again!

Unfortunately, this problem was literally unbreakable:

Unbreakable in its current state is unsolvable. We’re sorry about the inconvenience. We are discussing whether to fix it or remove it.

Allegedly there is a way to solve this, but we decided not to spend our time on discarded points.

Point-Slope Encryption (100 points)

Problem: We uncovered these weird numbers from Dr. Miles’ secret folder, but we don’t know what to do with it! Can you help us? We also found this script and this data in the same place, if it helps.

Hint: That ‘s’ function seems like it does something familiar…

So we’re given a list of two dimensional coordinates, a linear differential equation with initial condition, and a Python script for generating aforementioned coordinate pairs. Given that the encrypt method operates only on the current character and some mysterious function secret_func, it appears to be feasible to merely generate all possible ciphertexts and perform matching from there. Foremost, we’ll need to piece together secret_func.

The first step is to solve our DE. This requires integrating the left hand side of the equation using partial fractions and solving for the obtuse initial condition which conveniently produces a constant of 0. Another technique, and a much easier one at that, is to use Wolfram|Alpha.

$${f(x)}=-40.425355545341{({log(3{cos(\frac x2)}-2{sin(\frac x2)})}-{log(3{sin(\frac x2)}+2{cos(\frac x2)})})}$$

With that, we now can produce coordinate pairs for every ASCII value and map them against those provided to us. By the fact that our secret_func does not use the exact same values as the original, we have to account for precision errors by ignoring the trailing decimal.

>>> st = """(-440.17925980651745, -45994.43065337396)
(-141.40690087018172, -14311.319428148769)
(29.962721534647773, 3861.455411554571)
(42.12458508316416, 5151.151944679189)
(29.34494303123509, 3795.9435111034722)
(48.43313581170133, 5820.137908152502)
(138.26067085775853, 15345.837655224792)
(-141.40690087018172, -14311.319428148769)
(16.944686532756496, 2480.966760036832)
(-75.8477042277014, -7359.139091069058)
(38.29410602194571, 4744.951402652675)
(43.26979944557393, 5272.595421412209)
(-75.8477042277014, -7359.139091069058)
(-440.17925980651745, -45994.43065337396)
(29.243680708805417, 3785.2052171197656)
(26.800991531589407, 3526.1719077269113)
(-466.7651719451952, -48813.71559095174)""".split('\n')
>>> import math
>>> def encrypt(f, x0, x1):
    y0 = f(x0)      
    y1 = f(x1)
    s0 = s(f, x0)
    s1 = s(f, x1)
    if s0 == s1: return "NULL"
    x = (y1-y0 + s0*x0 - s1*x1)/(s0-s1)
    return (x, s1*(x-x1) + y1)
>>> def s(f, x, precision=3):
    h = 10**(-precision)
    return (f(x+h) - f(x)) / h
>>> def secret_func(x):
    return -40.425355545341 * (math.log(abs(3 * math.cos(x/2)-2 * math.sin(x/2))) - math.log(abs(3 * math.sin(x/2)+2 * math.cos(x/2))))
>>> for x in range(ord(' '), ord('~')):
    e = encrypt(secret_func, -9/4 * math.pi, x)
    for i in range(0, len(st)):
        if st[i].startswith(str(e)[:5]):
            st[i] = chr(x)
>>> print(''.join(st))
flag{c4lC_1z_fuN}

The Gamble / Decider. (100 points total)

Problem: You can solve this. You will lose 20 points. But a much more valuable problem will be unlocked.

Hint: The flag is not the flag. At least it seems that way.

There is not much to be said about this – the flag is indeed not the flag and the only reward, if you want to call it that, is access to “Decider.”

Problem: Decider. Tie-Breaker - all u get is that and this

Hint: No help for this one.

This problem and its gatekeeper were removed from Round 1 on the grounds of being infeasible to solve.

After some investigation, we’ve decided that some issues with the problem “Decider” That ‘s’ function seems like it does something familiar…That ‘s’ function seems like it does something familiar…have rendered it unfeasible to solve for the majority of competitors. As some team’s timers have ended, the problem will be retracted entirely in the interest of fairness (there were zero solves for the problem). We will be refunding points to those who took “The Gamble” shortly.

According to Camdar, the problem may have been later on repurposed as a “round 3.5,” or final tie-breaker. This was not done however. Nevertheless, we present an attempt at a solution:

On first glance, we are given an out file and what appears to be some kind of cipher text. While out is a very generic extension, it is worth noting that the GNU C compiler gcc’s default output file is a.out, which conveniently is the name of our file. We can confirm our suspicion by verifying the file’s magic number:

$ od -t x1 -N 16 a.out
0000000 cf fa ed fe 07 00 00 01 03 00 00 80 02 00 00 00
0000020

The first four bytes are CF FA ED FE. We can check this against a file signature database to find that we are looking at a Mach-O binary, and specifically one generated by a little-endian 64-bit machine. The associated constant in Apple’s official source is MH_CIGAM_64 (note the backwards spelling of magic, this indicates the reverse byte order, or endianness). Looking at a reference for a Mach-O file’s header, we see that following our magic, there should be a cputype member of type cpu_type_t (defined as an int). According to the output above, this number is 07 00 00 01 or rather 0x01000007 which is equal to the constant CPU_TYPE_X86_64. This last step was rather redundant, but we now know for certain that we are looking at a 64-bit OS X Mach-O binary.

At this point, we may be interested in what the file does. This isn’t necessary but gives us an idea of what we’re dealing with. Keeping in mind that one should never run an unknown binary on their system, we execute it in a virtual machine.

$ ./a.out
PYRMSPXMSSXMPYTMSQXMPYQMSPPMSSTMSSPMSPRMPXSMSSQMPYYMPVSMSSRMSPPMPXXMSPXMSPRMPXTMPVSMSQQMSQTMPVYMSQQM

The program does not appear to accept any arguments nor does it poll for user input. Also, the output appears to be constrained between M and X, giving us a range of 11 characters. We may infer from this alone that the underlying data might consist of all ten digits plus one delimiter. Most importantly, the output is the same form as the provided ciphertext, telling us that we may need to reverse the algorithm and devise an inverse of it.

This kind of pattern is highly suggestive of an operation such as XOR. We can test out our hypothesis by trying to find a single-byte XOR key that produces a letter from M to X with 0 to 9 and a delimiter:

>>> hex(ord('M') ^ ord('0'))
'0x7d'
>>> [chr(ord(c) ^ 0x7d) for c in 'PYRMSPXMSS']
['-', '$', '/', '0', '.', '-', '%', '0', '.', '.']

Well, that didn’t work. If we recall our ASCII table however, the typical delimiters, punctuation et. al., precede the digits and alphabet. What happens if we assume M to be one of these?

>>> keys = [ord('M') ^ x for x in range(ord(' '), ord('0'))]
>>> for key in keys:
        print(''.join(chr(ord(c) ^ key) for c in 'PYRMSPXMSS'))
=4? >=5 >>
<5>!?<4!??
?6="<?7"<<
>7<#=>6#==
90;$:91$::
81:%;80%;;
;29&8;3&88
:38'9:2'99
5<7(65=(66
4=6)74<)77
7>5*47?*44
6?4+56>+55
183,219,22
092-308-33
3:1.03;.00
2;0/12:/11

Two lines are particularly interesting, 183,219,22... and 092-308-33..., produced by the keys 0x61 and 0x62 respectively. We may have just found something noteworthy, but we cannot continue with it alone. It’s unavoidable now to proceed with either static or dynamic analysis of the binary, giving us a sneak peak of the next round to come.

There are dozens of ways of going about deciphering the program’s flow. This is not meant to serve as an in-depth overview but rather one simple approach. In the interest of gratis software, we will utilize the very capable Online Disassembler.

First things first, we load our file and see it automatically recognized as a “Mach-O 64-bit x8664 executable”. This write-up will continue using the AT&T mnemonic style, though Intel style may be more familiar to many Windows hackers. Checking the Sections tab, we see that .text begins at the virtual address 100000cc0 which is the main entry point function. Seeking to this function, we see the dense jungle of movs and assorted other operations we will have to navigate.

Skimming through the method we see a few things: a) there are an unproportionate number of mov operations, b) a few standard library string functions are being called, and c) a string is being loaded from memory:

.text:00000ce3      488d053e220000  lea 0x223e(%rip),%rax

This seven-byte opcode is loading the bytes at 0x223e + 0x0ce3 + 0x07 or .cstring:00002f28 into register rax: ReverseThisAlgorithmWithTheGivenStringToGetTheFlag. Great! We have the input and output, now we just need the blackbox in between. At this point it might be best to either find a decompiler or to debug the program at runtime. Instead, we will look for what we already know: the string is somehow being manipulated and finally XORed.

.text:0000172f      83f261          xor $0x61,%edx

Going further up the program, we can find calls to std::basic_string::append and std::operator+<char>. The latter appears to join one string with the suffix ‘,’ while the former joins these combined strings into one sequential conglomerate.

Let’s apply what we know so far to a snippet of the program’s output.

Output      PYRMSPXMSSXMPYTMSQXMPYQMSPPMSSTM
To hex      5059524d5350584d5353584d5059544d5351584d5059514d5350504d5353544d
XOR 0x61    3138332c3231392c3232392c3138352c3230392c3138302c3231312c3232352c
To ASCII    183,219,229,185,209,180,211,225,

But what do these numbers mean? Let’s look at the input again

Input       ReverseThisAlgorithmWithTheGivenStringToGetTheFlag
To dec      82 101 118 101 114 115 101 84 104 105 115 65 108 103 111 114 105 116 104 109 87 105 116 104 84 104 101 71 105 118 101 110 83 116 114 105 110 103 84 111 71 101 116 84 104 101 70 108 97 103

What do we get if we add the first two numbers? 183. What about the second pair? 219. Here’s the algorithm, short and sweet:

def encrypt(msg):
    # split string every two characters
    pairs = [msg[i:i+2] for i in range(0, len(msg), 2)]
    # sum ASCII values of each pair
    sums = [sum(ord(c) for c in p) for p in pairs]
    # concatenate sums together
    text = ','.join(str(s) for s in sums + [''])
    # XOR text by 0x61
    return ''.join(chr(ord(c) ^ 0x61) for c in text)

Now, how about decryption? It turns out its no where near as easy: while getting the sum of two numbers produces one possible number, doing the opposite gives us a large set of possibilities – this algorithm is many-to-one. How large really is “large”, though? Let’s quantify it:

>>> def test(a):
        l = []
        for i in range(ord(' '), ord('~')):
            for j in range(ord(' '), ord('~')):
                    if i + j == a:
                            l.append(chr(i) + chr(j))
        return l
>>> s = "188,220,188,188,188,221,201,184,225,169,172,201,158,112,180,157,175,174,176,189,160,213,191,231,195,153,166,164,140,147,102".split(',')
>>> s = [int(x) for x in s]
>>> combos = 1
>>> for x in s:
        combos *= len(test(x))
13344623296403406796219952304992695708417996800000000000L

This is what the competition staff were getting at when they said it was “unfeasible [sic]”. Just because its hard doesn’t mean its impossible though.

Round 2: Bamboozling Binaries

This round delves into a variety of topics, including regular expressions, dynamic analysis, and return-oriented programming. At some point during the round, several of these questions were modified; the solutions as presented should reflect those of the latest revision.

Guessing Game (15 points)

Problem: The evil villains have hidden their flag behind a machine that will only spit it back out if you can guess a random number, how devious! However, their programmer wasn’t quite sure how to make absolutely sure that things were random, so there’s a hole in their program! Can you exploit it?

nc 104.236.216.251 64753

Hint: What happens if the same person plays multiple times?

Computers are inherently deterministic. That is, given one input, they will continually produce the same output (neglecting external stimulation). When trying to create numbers that are supposed to be random, this presents a significant problem. Two solutions are available, one less secure than the other: seed an algorithm using 1) some other deterministic value such as a timestamp or a user-entered string, or using 2) an external, truly random factor provided by a TPM or equivalent. This problem involves the former.

A look at RandomGame.java reveals that a random number generator java.util.Random is being used with a custom seed. This custom seed is in turn created by two passes through customHash, a wrapper around String.hashCode.

Random rng = new Random(customHash("" + customHash(name)));
...
int number = rng.nextInt(51);
...
private static int customHash(String s) {
    // TODO: Write long and complicated hashing algorithm
    return s.hashCode();
}

Using something like a Java REPL, we can quickly determine what number the server will use for a given name:

java> ("" + "brandon".hashCode()).hashCode()
java.lang.Integer res0 = -786342638
java> (new Random(-786342638)).nextInt()
java.lang.Integer res1 = 22

$ echo -en 'brandon\n22\n' | nc 104.236.216.251 64753
What is your name? Guess my number (between 0 and 50): Wow, you got it!
Your flag is:
PA{m1Nd_j00r_sE3Dz}

Of course, since the program tells you the number it was looking for after an incorrect guess, getting the flag could have been as easy as playing twice with the same name.

Regex 1: Classy Punctuation (15 points)

Problem: Joe wants to know: He can be a bit dramatic with his punctuation, but does he ever repeat it 23 times? Help him write a regex that matches 23 characters each of which is ‘’.’’, ‘’!’’ or ‘’?’’?

Hint: Learn about regular expressions at RegexOne.

One of the accepted flags is ([.|!|?]{23}).

RabbitJS (30 points)

Problem: All but the 1, [, ], and = keys broke on JavaScript Mage Joey’s keyboard. That didn’t stop him from trying to tell the world what he had learnt, though.

Hint: Sometimes, it’s best to leave a viewpoint function unevaluated.

The flag is flag{carroll_knew_it}.

Magic (40 points)

Problem: Wanna see a magic trick?

Hint: I wonder if you could get into memory and see the magic?

The original flag was pa{cHECk_uR_vAr5} and the new flag is pactf{eax_more_like_easy}.

Foolish Filesystem (50 points)

Problem: You found an interesting program on the floor… wonder what it is?

Hint: What is a directory? A miserable little pile of hidden files!

This problem can be easily solved by disassembling the binary or even just doing some trial and error with the inputs. It is also trivial to skip past any of the text-based adventure fun, but I’m not sure why you would ever want to do that.

$ gdb adventure
(gdb) info functions
...
0x000000000040085d  give_flag
0x0000000000400986  process
0x0000000000400c3c  main
...
(gdb) disas give_flag
Dump of assembler code for function give_flag:
    0x000000000040085d <+0>:     push   %rbp
    0x000000000040085e <+1>:     mov    %rsp,%rbp
    0x0000000000400861 <+4>:     sub    $0x50,%rsp
    0x0000000000400865 <+8>:     mov    %fs:0x28,%rax
    0x000000000040086e <+17>:    mov    %rax,-0x8(%rbp)
    0x0000000000400872 <+21>:    xor    %eax,%eax
    0x0000000000400874 <+23>:    movl   $0x6e5d5b6a,-0x40(%rbp)
    0x000000000040087b <+30>:    movb   $0x0,-0x3c(%rbp)
    0x000000000040087f <+34>:    movl   $0x0,-0x50(%rbp)
...

So there’s a function blatantly called give_flag, and a quick skim reveals no access of any data above rbp (indicating no parameters). It must be our lucky day!

(gdb) break main
Breakpoint 1 at 0x400c40
(gdb) call give_flag()
pactf{H1d3_uR_s3kr1tz}
...

Neato! Even though this felt like a nice shortcut, it turns out running the program would have been faster…

$ ./adventure
You find yourself in a strange filesystem.

Not knowing where you are, or who did this to you, you are left
with one recourse - to find the flag and escape!

After some experimentation, you seem to be in some kind of shell.
Maybe the standard navigation commands will help you?
>>> ls -a
You find something glinting in the dark.

total 1
-rw-r--r-- 1 ??? ??? 4096 ??? ?? ??:?? .sekrit
>>> cat .sekrit
That's it! The flag!
pactf{H1d3_uR_s3kr1tz}

The original flag to this problem was pactf{i_lUv_D0tf1l3z}.

Regex 2: Don’t Look Back (50 points)

Problem: You have been tasked with taking over FlexCorp’s web 3.0 project as the previous lead developer just went into retirement. As you shield your eyes from the unmaintable horror, you see a little regex scrawled against his desk with a little inscription reading “how to parse Web 3.0 data.” Presumably, he was talking about the large, shared CSV file in which everyone at FlexCorp had to log which tools they used on company grounds.

You know that his first name begins with an C and his last name ends with an N.

Here’s the CSV file, and here’s the regex:

^(?:.*?,){29}(?:c\w+n),(?:.*?,){35}(.*?),.*$

Can you find the name of the tool?

Hint: We weren’t kidding about the file being large. You’ll want to have a regex a bit cleverer than the veteran’s for this… Backtrack a bit to learn about character classes.

The original flag was clement_hudson and the new flag is zalgo_is_tony_the_pony.

Sliding Letter Game (50 points)

Problem: nc 198.211.110.148 64753

It’s the letter matching game! You just need to change the characters of a string so it matches a password! The source is here.

Hint: What happens if you make a number that’s really big?

The original flag was Abrac4dabr4h0cuspocu5youv3done1t and the new flag is flag{w4tch_y0ur_l1mi7z}.

Huge Numbers (60 points)

Problem: How many 10,000-digit numbers (without leading zeros) exist such that no three adjacent digits have a sum greater than 9? The flag is the first > 15 digits.

Hint: How many digits do you have to keep track of at once?

If this looks like a Project Euler problem, well you’re not far off.

How many 20 digit numbers $$n$$ (without any leading zero) exist such that no three consecutive digits of $$n$$ have a sum greater than 9?

For the sake of the competition, it might be wise to simply come upon someone else’s publicized solution and change that $$20$$ to $$10000$$. However this problem can be easily described as one of dynamic programming.

The number of numbers $$d$$ beginning with digits $$a$$ and $$b$$ followed by $$r$$ more digits can be expressed as $d(a,b,r)$. For any three digit number, that is where $$r=1$$, $$d(a,b,1)=9-a-b+1$$. Any additional digits can then be expressed as the recursive sum of all subsets: $$d(a,b,r)=\sum_{c=0}^{9-a-b} d(b,c,r-1)$$.

$$d(a,b,r)=\begin{cases}9-a-b+1 & r=1\\ \sum_{c=0}^{9-a-b} d(b,c,r-1) & r > 1 \end{cases}$$

Implementing the original Project Euler problem naively through this approach is no problem, but going anywhere near 10000 digits will cause massive tail call issues. One technique for this is then to keep all calculations in a working list and instead posing the solution as an iterative one:

m = 10000

# prepare first three digits
d = [[9-a-b for b in range(9-a+1)] for a in range(9+1)]

# iterate over the next 9997 digits
for _ in range(m-3):
    d = [[sum(
             d[c][a] for c in range(9-a-b+1))
             for b in range(9-a+1)]
         for a in range(9+1)]

# sum each of the working sums
s = sum(sum(x) for x in d)
print(str(s)[:15])

It will take a few seconds but we are returned our desired flag: 128706110652472. If you were curious, the original number was a whopping 7239 digits long.

Whitespace (60 points)

Problem: I’ve found this java program on someone’s computer that looks fishy.

Hint: I wonder, is that really Java?

Esoteric languages are a fun distraction in a world full of boring old paradigms and syntax rules. Some allow for program flow manipulation in two dimensions, some strive to be a bit too minimalistic, and others are designed to be impossible to understand. One such language is aptly called Whitespace, and as you might be led to believe, consists entirely of whitespace characters.

First things first, we should run the program as it appears before we dive in over our heads.

$ javac whitespace.java
$ java whitespace
nope

Well then, let’s investigate this hunch of ours. The Whitespace spec isn’t all too hard to implement, but for simplicity’s sake a Javascript version already exists. Hey, who am I kidding; let’s do this The Hard Way™.

$ sed 's/[^ \t]//g;s/ /S/g;s/\t/T/g' whitespace.java
SSSTSTSTSS
T
SSSSSTTSTSSS
T
SSSSSTTSSTST
T
SSSSSSTSSSSS
T
SSSSSTTSSTTS
T
SSSSSTTSTTSS
...

Keep in mind that line feeds are only preserved for readability purposes. Breaks do not necessarily represent the end of an instruction.

We see that the first “instruction modification parameter” is space, indicating a stack operation. Because our line doesn’t end immediately, we know the next sequence is a number: 001010100, or 84. Next, we see tab line feed. This is an input/output operation. The next two tokens are space space, meaning print out whatever character ordinal we just pushed. This pattern repeats on for a while.

push(84)     # S SSTSTSTSS L
print(pop()) # TL SS
push(104)    # S SSTTSSTST L
print(pop()) # TL SS
push(101)    # S SSSTSSSSS L
print(pop()) # TL SS
push(32)     # S SSTTSSTTS L
print(pop()) # TL SS
...

$ # Get rid of useless characters, replace spaces and tabs with 0s and 1s,
  # and remove every other line
  sed 's/[^ \t]//g;s/ /0/g;s/\t/1/g;n;d' whitespace.java |
  # Keep only the last 8 bits (the character)
  grep -o '.\{8\}$' |
  # Convert the binary strings to integers
  xargs -I '{}' echo 'ibase=2;obase=A; {}' | bc |
  # Convert the integers to their corresponding ASCII characters
  # (I didn't know how to do this in bash...)
  python -c 'import sys;print("".join(chr(int(c)) for c in sys.stdin.readlines()))'
The flag is: two_programs_in_one

Was that really necessary? No. Did I learn a thing or two about sed trying to write that though? Yes.

Sorcery (70 points)

Problem: What is this magic? My file is here, but where are my hardcoded strings?

Hint: And as Dorthy was told, “Follow the yello brick pointers.” (We recommend using this online tool! It’s pretty nice.)

The flag is pactf{1_dun_ducked_up!}.

Coalmine (80 points)

Problem: nc 104.236.216.251 59292

Keep digging! We’re running out of oxygen! Check the source here

Hint: How could we figure out what the canary value is?

The flag is ctf_1z_mY_0xyGen.

Regex 3: Oh, The Power! (90 points)

Problem: By now you are acquainted with the powers of regex, but can you make a regex match only the powers of 5? Only a string of 5^n repeating ‘x’s should pass.

You have all of 30 characters.

Hint: Take away 4/5ths of a power of 5, and you have: a power of 5.

One of the accepted flags is (x|x{5}|x{25}|x{125}|x{625}). This exploits the fact that the engine only evaluated the first five elements of the sequence. A less cheeky solution is of course much harder to digest: ^(?:(x+)\1{3}(?=\1\$))*x$.

Jump (100 points)

Problem: Don’t fall off….

Hint: I wonder where I’ve seen this before?

Well well well, what do we have here?

Yup, it’s a GameBoy Advanced game, a strange ROM hack at that. According to the file, it is called SSB_ADVANCE. This in hand, we can locate the origin of this file from it’s decade old posting on GBADEV. Neglecting the possibility that Camdar went by thegamegreak0134 and has spent the last ten years putting together this competition, we can seek diff for more information.

The first difference, of two bytes, occurs at 0000'0430. The second difference is much more substantial and located at the very end of the file, 0001'2e70. Remembering that the GBA utilized a ARMv4T processor, we can load up the ROM in a disassembler and get cracking.

At 0000'0430, it appears that a BL 0x072C instruction has been replaced by a jump to the appended codecave: BL 0x00012EE0. Following it, we find the following subroutine:

00012EE0                 LDR     R2, =0x2000000
00012EE4                 LDR     R1, =0x8012E8C
00012EE8                 LDRB    R0, [R2]
00012EEC                 MOV     R0, R0,LSL#2
00012EF0                 LDR     R1, [R1,R0]
00012EF4                 LDRB    R0, [R1]
00012EF8                 STRB    R0, [R2,#1]
00012EFC                 LDRB    R0, [R2]
00012F00                 ADD     R0, R0, #1
00012F04                 CMP     R0, #0x14
00012F08                 BLT     loc_12F10
00012F0C                 MOV     R0, #0
00012F10                 STRB    R0, [R2]
00012F14                 LDR     R0, =0x800072C
00012F18                 BX      R0

At the start of every tick of the game (starting at 0000'0430), this little detour will load a particular byte from the ROM and place it into the GBA’s working RAM located at 0200'0001, preceded by the index of the byte. The locations of the 20 bytes to be loaded are kept directly before the above function.

00012E8C                 DCD 0x800018C  ; p
00012E90                 DCD 0x8000770  ; a
00012E94                 DCD 0x800137A  ; c
00012E98                 DCD 0x800076C  ; t
00012E9C                 DCD 0x800E649  ; f
00012EA0                 DCD 0x800F08F  ; {
00012EA4                 DCD 0x800E649  ; f
00012EA8                 DCD 0x8004020  ; 4
00012EAC                 DCD 0x8004068  ; L
00012EB0                 DCD 0x800393D  ; c
00012EB4                 DCD 0x8003975  ; 0
00012EB8                 DCD 0x8003B48  ; n
00012EBC                 DCD 0x8003EDC  ; _
00012EC0                 DCD 0x8003FB0  ; P 
00012EC4                 DCD 0x800434E  ; U
00012EC8                 DCD 0x80045FA  ; n
00012ECC                 DCD 0x800F1DD  ; C
00012ED0                 DCD 0x8012754  ; H
00012ED4                 DCD 0x8012508  ; !
00012ED8                 DCD 0x8012E89  ; \0
00012EDC                 DCD 0          ; \0

This second to last byte is supposed to be 0x8012E88, or }. Regardless, the flag as loaded into the WRAM is pactf{f4Lc0n_PUnCH!}.

Round 3: Wicked Web

This final round was more of a mixed bag, with some problems belonging more to miscellany than the world wide web.

First Task (10 points)

Problem: What is this?

Hint: If you don’t know what it is, then Google would be your best friend.

The solution here is to literally Google reverse image search the provided picture to learn that it is of the Sutro Tower.

Sutro Tower is a 977 ft (298 m) three-pronged TV and radio antenna tower in San Francisco, CA. Rising from a hill between Twin Peaks and Mount Sutro near Clarendon Heights, it is a prominent feature of the city skyline and a landmark for city residents and visitors.

— Sutro Tower, Wikipedia

Ess Kyuu Ell (20 points)

Problem: We let Phil in accounting take this one. We had higher hopes for him…

Hint: There are a few ways to solve this one. Get creative! You’ll need to use some SQL injection. Good luck!

The flag is phil_should_stick_to_banking.

What Does It Say? (20 points)

Problem: What does it say? Special note of thanks to the great people at what?

Hint: How can you figure out what the site says?

Using any respectable browser to access this website should result in flat-out denial without any option for recourse. An invalid certificate should however be no match for a more controllable tool like wget.

$ wget -qO- revoked.grc.com | grep "special note of thanks"
<p class="classy_grey" style="padding:0.5em 1em; color:#000; font-size:8pt;">A special note of thanks to the great people at <a href="http://digicert.com"><b>Digicert</b></a>, GRC's carefully chosen and, we believe, the best certificate authority, who were gracious enough to work with us to create a special pre-revoked security certificate. Perhaps the first time this has ever been done!</p>

Our flag is then Digicert, nothing more, nothing less.

Bears and Bulls (30 points)

Problem: FlexCorp likes to dabble in the stock market. They have managed to keep their investments off the books, but, vain as they are, they couldn’t help but track how popular their investments were being, tracking this in a CSV file titled interest.csv, created in January 2004 and apparently accessed monthly. Can you figure out their investments (separating them with an underscore if necessary)?

Hint: Google is your best friend.

Mystery Man (40 points)

Problem: I’m Tony Tan, and I often get weird emails. But I don’t like the feels of this one, and I need to know who sent it.

Hint: I want the sender’s first name, middle initial, and last name. Don’t email him though, because I don’t want him finding out about this.

The flag is Jerome L. Waters.

Lurking In Plain Sight (50 points)

Problem: The flag is lurking in plain sight.

Hint: Nope!

The flag is i_found_a_header!.

SQL: The Sequel (50 points)

Problem: Dr. Miles looked at our stuff and decided to teach us a lesson. Unfortunately, he was kind of in a rush and decided that the builtin PHP string escapes should be enough. Is he right?

Hint: A quote is a quote, as PHP gloats!

Wikipedia Knew (60 points)

Problem: Once upon a time, Wikipedia knew what THE FLAG is.

Hint: I wish we could travel back in time.

The flag is cNi76bV2IVERlh97hP.

The Big Picture (70 points)

Problem: My friend often tells me that I am missing the big picture.

Hint: No hint.

Unauthorized Access (70 points)

Problem: Get us authorized.

Hint: Can you change who you are?

A Fierce Attacker (80 points)

Problem: Intelligence states that the flag is located on a server with the domain ‘pactf2.tk’ on a secret sub-domain. Can you find the correct sub-domain?

Hint: Take a guess. Or find someone fierce instead.

Let’s scout the domain first:

$ dig +nocmd pactf2.tk any +noall +answer
pactf2.tk.              150     IN      A       104.27.143.85
pactf2.tk.              150     IN      A       104.27.142.85
pactf2.tk.              126     IN      NS      pat.ns.cloudflare.com.
pactf2.tk.              126     IN      NS      gabe.ns.cloudflare.com.
pactf2.tk.              3426    IN      HINFO   "Please stop asking for ANY" "See draft-ietf-dnsop-refuse-any"

Its not like anyone was expecting the second highest question to be that easy, but its worth checking just to be sure. The domain’s name servers point to CloudFlare and there are no subdomain CNAME records in sight. This means that the subdomain is instead being handled at the server level and that our only recourse is brute force.

[fierce][82] is an archaic Perl tool that was at least at one point an essential tool for any pentester’s arsenal. The idea is to resolve an entire wordlist’s worth of subdomains and hope that a few of them are hits. Many scripts have superseded fierce over the years and performing a simple check is as easy as using [an internet service][83]. It takes five seconds in particular for this web service to resolve three A records for pactf2.tk:

pactf2.tk       A    104.27.142.85
vpn.pactf2.tk   A    104.27.142.85
www.pactf2.tk   A    104.27.142.85

The Flag:

CJY0n9d1cZHkuEkEsF2U5sf1Aqh0TQ

Heartbroken (100 points)

Problem: I need to intercept someone’s secure connection to this website. Can you help me steal the RSA private key for the server cerificate? Submit the Base64 encoded SHA256 hash of the server’s RSA private key.

Hint: If you got the private key, you’ll need to convert it to DER format, hash it with SHA256, and then make sure the hash is in Base64. The end result should somewhat look like lv8t74hplkz79CIsCsBzDiaTfJF1skxv0rLhkV5Gw2A=.

openssl rsa -in private.key -outform der | openssl dgst -sha256 -binary | openssl enc -base64