h4x0rpsch0rr

In the following we summarize our solutions for a reversing task that appeared last weekend during the PlaidCTF 2016.

This task is the perfect example that it is possible to obtain a secret from a compiled program even without having any clue about the internal mechanics of the code.

This challenge exposed a chosen-plaintext oracle for a quite complicated homebrew block cipher, which one should use to decrypt a given ciphertext. Remarkably, we were the only team to solve this challenge during the CTF.

Task description:

The creators of the AI we’re so desperately looking for used the remote server to encrypt their data. It seems that this service merely encrypts the data we’re sending to it. We managed to find a possibly valuable piece of encrypted data along with the server’s script. Could you take a look and see if anything can be done?

nc five-blocks.2016.volgactf.ru 8888

server ciphers data

Hints

1. What would you get if you’d encrypted four-block data of the form AABC, where A, B, C are 64-bit arbitrary blocks?
2. Are the rounds of the second block cipher completely dependent or independent of each other? Or is the truth somewhere in the middle?

In this task, one had to break an instance of the Goldreich-Goldwasser-Halevi lattice encryption scheme.

The task description reads:

I remember some of the AI engineers saying this was a very unusual cryptosystem. It was used to encrypt and transmit information of the enormous importance. Moreover, it seems there’s no need to share a key before the transmission.

We’ve found some kind of a key file, a ciphertext and the enciphering script itself. Is it possible to decrypt the data?

The script linked in the challenge description uses the following sage function to encrypt a message:

def encrypt(plain_block, W, delta=151):
    n = W.ncols()
    m = vector([ord(ch)  for ch in plain_block])
    r = random_vector(ZZ, n, x=-delta+1, y=delta)
    e = m * W + r
    return e

In that snippet, $W$ is a unimodular square integer matrix loaded from the key.public file. That is, encryption essentially consists of the operation

\[ e \;=\; m\cdot W + r \]

where $r$ is a small random error vector and the message $m$ is suitably interpreted as an integer vector.

Now what seems to be required to obtain $m\cdot W$ (hence $m$) from the disturbed vector $m\cdot W+r$ is solving the closest vector problem (CVP) in the lattice spanned by the columns of $W$. However, this seems to be, to the best of public knowledge, quite hard in general, hence naïvely throwing the given point into sage just heats your CPU for a long time.

After noticing this challenge was about elliptic curves, I could not resist having a try at it. The “description” consisted of the following data:

p = 16857450949524777441941817393974784044780411511252189319
A = 16857450949524777441941817393974784044780411507861094535
B = 77986137112576
E: y^2 = x^3 + Ax + B over GF(p)
P = (5732560139258194764535999929325388041568732716579308775, 14532336890195013837874850588152996214121327870156054248)
Q = (2609506039090139098835068603396546214836589143940493046, 8637771092812212464887027788957801177574860926032421582)
Q = secret * P
flag = secret

Hence the task is simply to compute the (discrete) logarithm of Q with base P on an elliptic curve E given by a Weierstraß equation \[ E\colon\quad y^2=x^3+Ax+B \text. \]

This painful task simulates an embedded toaster firmware that you have to pwn by using the random generator output. The used architecture is ARMv7.

This bulk-writeup briefly describes the solutions for the four simpler reverse engineering tasks of the 9447 CTF 2015.

In this challenge, we were given the source code of a server and client along with a network dump generated from letting those communicate. The description reads:

Some secret communication was captured, and we’re having trouble decrypting it. Can you help?

The protocol consists of a Diffie-Hellman-style key agreement, only the underlying operation seems to have been changed. Carefully reading the code shows that the computation is performed in the ring of $2\times 2$ matrices over a finite field using a Montgomery ladder algorithm, so we have to find a way to solve the Diffie-Hellman problem in these (in fact, we will even compute logarithms).

As most of you probably know by now, we held our first CTF last weekend and with it there was a lot to learn for us. Since most (or probably even all) of our readers here are CTF players and organizers themselves, we thought it would be a nice touch to compile everything into a blog post to give all of you the chance to laugh about our stupid mistakes and maybe even learn something new. :)

Selecting the date

We actually picked the date for our CTF quite carefully. We used ctftime.org to choose a more or less free weekend, and at the time we did that, neither Hack.lu, EKOPARTY nor WhiteHat Grand Prix had been announced there. We know all those are linked to conferences so I guess there would have been a way to know that would happen. If someone knows a better source for this kind of information, please let us know so we can choose a better date next time.

In this challenge from the first ever CTF competition organized by the H4x0rPsch0rr team, …

Your task is simple: ssh -i id_rsa -p 1122 ctf@1.ctf.link

Oh, and here’s the key, because we love you <3 :)

The (RSA) private key is…

-----BEGIN RSA PRIVATE KEY-----
MIMIECICAQACgggBANRFHE8WEB/STSEH+Coqqdw6sI3CyaLGNuH1A46qBC5JzXeX
Kg9KPSkbwydPj5HVZ+i2d9nDK5ifYv0mC7CCHAE2RuYqOwDJe3LKt0ZBHI11nomm
    [...roughly 11k more lines of base64...]
4ZcP2zJaIKd7LKH7b79gxtJyMJCHt+34AzdJqRGHwRef9FHp4j+VxtGdtycoUkvk
4oPCAd4tUhJuj35AlMWcXQHCYOH+opKBAgEBAgEBAgEAAgEAAgEA
-----END RSA PRIVATE KEY-----

…extraordinarily huge.

Extract some RTP data and find the flag in the lofty frequencies above some growling cats.

We analyze a small binary that asks to satisfy a seemingly unsolvable equation.

A delegation of the H4x0rPsch0rr team spent a weekend in the awesome city of Kraków and participated in the even more awesome CONFidence CTF organized by the DragonSector team (thanks for the invitation!). Out of the numerous challenges that were opened up during the CTF, no team was able to solve a reversing task called “Deobfuscate Me” which was worth 400 points.

After the competition task authors presented their sample solutions which, in case of this task, consisted of incrementally measuring differences in the execution traces of the challenge depending on the user input. However, we wanted to show that it was also possible to leverage symbolic execution in combination with a SMT solver to solve the challenge. Our (somewhat tedious) approach is described in this writeup.

The objective of this amazing challenge was solving the elliptic curve discrete logarithm problem using a twist attack on a Montgomery ladder.

To enable us to do so, the server essentially provides an oracle for the function $\mathbb E\to\mathbb E,\;g\mapsto g^f$, where $f$ is the private key and $\mathbb E$ is an elliptic curve (yep, I use multiplicative notation for elliptic curves — deal with it). According to the task description, the flag is $f$’s hexadecimal representation.

Let $p = 2^{160} + 7$, which is prime, and $A=40638$. The (Montgomery) curve in use is \[ \mathbb E\colon\quad y^2 = x^3 + Ax^2 + x \] over the finite field $\mathbb F_p=\mathbb Z/\langle p\rangle$. The organizers were kind enough to also supply the curve’s group order \[ \lvert\mathbb E\rvert = 1461501637330902918203684014253252914573215409208 \text, \] which is unfortunately safe as it factors into $2^3$ and some large prime, effectively avoiding small-subgroup attacks. Since we can only supply an $x$ coordinate (as opposed to both $x$ and $y$ coordinates), invalid point attacks as described in the linked paper are also unapplicable.

lets pretend that first CDN didnt happened! can you get a shell, there is a second flag in the root of the fs! It is up at http://54.88.83.98/ : 275

Sidenote: I highly recommend reading my other writeup to Andrew first, as they cover the same binary. I’ll assume that you’ve read it.

After getting the first flag, there wasn’t much left to analyze in the binary, besides the standard nginx functions. I’ve spent some time looking at minjs(), but did not come up with anything. But a quick look at minhtml() made it pretty obvious. Looking at the stack layout, we see a bunch of uninteresting stuff happen. But at the very top of the stack, there is a u_char ret[1024] allocated. This looks promising!

we have an EXPERIMENTAL CDN based on nginx. It can optimize html, javascript, leetify text and rehost images. It is up at http://54.88.83.98/ flag is in /flag.txt : 275

We were given nginx binary and a config file. The config file wasn’t really interesting, it just mapped everything to a custom action:

server {
    listen 8080;
    server_name localhost;

    location / { hello; }
}

Examining the unknown

Community College
I can’t follow what’s going on here. Can you? : 300

As always with CTF challanges, let’s run file on what we’re given:

file fredkin fredkin: ELF 32-bit LSB executable, MIPS, MIPS-II version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=2204905041c5ddc8a13ab816a6421daf0870b6a0, stripped

MIPS? Ooooh, well … Firing up IDA and loading the binary we’re greeted by a relatively complex main function calling several other functions (who’d have guessed this?). The following is the prologue:

This challenge was concerned with exploiting a timing oracle vulnerability, as was already disclosed in the task description:

The timing in this challenge is clearly not very realistic—but the methods you’ll use here can be extended to real-world implementations of modular exponentiation. Server at 52.1.245.61, port 1025. My solution takes a little while. Good luck.

Along with this, the server’s Python source code was provided.

From the code, one recognizes that the server repeatedly performs modular exponentiation of some attacker-chosen base $g$ to the power of a randomly generated secret $x\in\{1,\dots,\frac{p-1}2-1\}$ modulo a public, pre-chosen safe prime $p$; that is, $p=2q+1$ for another prime $q$.

As hinted in the challenge description, the square-and-multiply function provides a (pretty unrealistic) timing oracle: Whenever the accumulator contains the value $4$, the server sleeps for a second. Incidentally, the challenge’s main goal is to provide a number $g$ such that $g^x\equiv4\pmod p$, upon which the server prints the flag.

Additionally, a function called group_check enforces (by ensuring $g^{\frac{p-1}2}\equiv1\pmod p$) that the provided base $g$ is a square modulo $p$ (also known as “quadratic residue”, although the author deems this terminology rather unfortunate), that is, there is some $h\in\mathbb Z$ such that $h^2\equiv g\pmod p$. This means that all computation is performed in the subgroup of squares of $(\mathbb Z/p\mathbb Z)^\ast$, a group with some pretty nice properties — we’ll see a little more about this later.

Fun fact: It took one of our team members about 10 seconds to recognize the similarity to this sound while listening to the song. He was like “wait a second, PUT THAT ON AN OSCILLOSCOPE!”. We then proceeded to annoy everyone by playing the song in an infinite loop until the author finally got his hands on one.

Gathering Information

Find the key!
File: File
Server: huffy.2015.ghostintheshellcode.com:8143

This was the only “official” reversing challenge in the 2015 edition of the Ghost in the Shellcode CTF. It was made available several hours before the end of the competition and worth 300 juicy points.

Executing the binary and entering some random text yields a lot of output:

$ ./huffy
CWD: ~/CTF/2015_01_GitS/rev300_huffy
AAAA
Nibble  Frequency
------  ---------
0   0.100000
1   0.400000
2   0.000000
3   0.000000
4   0.400000
5   0.000000
6   0.000000
7   0.000000
8   0.000000
9   0.000000
a   0.100000
b   0.000000
c   0.000000
d   0.000000
e   0.000000
f   0.000000

Read 5 bytes
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.100000
Two lowest frequencies: 0.100000 and 0.100000
Two lowest frequencies: 0.200000 and 0.200000
Two lowest frequencies: 0.400000 and 0.400000
Two lowest frequencies: 0.400000 and 0.800000
Breaking!
0 --0-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
1 --0-- 0x804c3c0 
2 --0-- 0x804c258 --0-- 0x804c270 --0-- 0x804c288 --0-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
3 --1-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
4 --1-- 0x804c3a8 --1-- 0x804c3c0 
5 --1-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
6 --1-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
7 --1-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
8 --1-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
9 --1-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
a --1-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
b --1-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
c --1-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
d --1-- 0x804c288 --0-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
e --1-- 0x804c270 --0-- 0x804c288 --0-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
f --1-- 0x804c258 --0-- 0x804c270 --0-- 0x804c288 --0-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0 
Encoding input...
ASCII Encoded: 110110110110101010111
Binary Encoded:
�j
Executing encoded input...
[1]    10542 segmentation fault (core dumped)  ./huffy

Okay, let’s see what is going on here. It prints out the current working dir and asks for input. After being fed with data and pressing C-d to signal a EOF, the binary performs a frequency analysis on the nibbles of the input and prints out the result. Indeed, we find (including the “invisible” newline character)

This was a nice little crypto challenge related to AES key expansion. The description says

We implemented aes in hardware and saved a lot of memory. Feel free to use our online aes encryption service to secure your data.

Additionally, we were provided with a Python server script and an IP/port pair. The server provides the following options:

self.commands = {"help": (self.help, "show this help"),
                "setkey": (self.set_key, "Set AES key"),
                "getkey": (self.get_key, "Set AES key"),
                "encrypt": (self.encrypt, "Encrypt with AES"),
                "flag": (self.flag, "Encrypt flag"),
                }

Besides that, the script mainly consists of interface code to communicate with an AES hardware module, essentially passing the [gs]etkey and encrypt commands to the module and echoing back the results to the socket.

Of course, our attention immediately shifted to the flag command, which does

def flag(self, paran):
        self._set_key(os.urandom(16))
        self.println(self._encrypt(FLAG).encode("hex").strip())

This challenge required us to submit a single program that can be compiled and run as five different programming languages. The task presented us with

Just `cat flag`

$ python2 --version
Python 2.7.6
$ python3 --version
Python 3.4.0
$ gcc --version
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2
$ ruby --version
ruby 1.9.3p484 (2013-11-22 revision 43786) [x86_64-linux]
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.6.3

and a file upload field below.

This suggested we needed to write a program that prints the file flag to stdout in all of

• Python2;
• Python3;
• C;
• Ruby;
• Haskell

on a x86_64 machine running Linux.

This was another algebra-focused crypto challenge (we need more of those!). For this task, we were provided with a compiled Python client that communicates encryptedly with a server along with a packet dump of a conversation between an admin and the server.

Let’s first take a look at the actual public-key cryptosystem: Each party generates two different primes $p$ and $q$, from which the numbers $n=pq$, $\ell=(p-1)(q-1)$, and $m\;\equiv\;\ell^{-1}\mod n$ are derived. The public key is $n$. The private key consists of $\ell$ and $m$.

To encrypt a message $\mathit{plain}\in\lbrace0,\dots,n-1\rbrace$, the following steps are performed: 1. Find a random prime $r$ between $1$ and $n$. 2. Compute the ciphertext as $\mathit{cipher}=(n+1)^\mathit{plain}r^n\bmod n^2$.

(Note that $r$ is chosen as a prime to ensure that it is coprime to $n$, which implies $r^n\bmod n^2\neq 0$ and thus $\mathit{cipher}\neq 0$.)

The following property is essential for the solution:

For all $k\in\mathbb N$, \[ (n+1)^k\;\equiv\;\sum_{i=0}^k\binom kin^k\;\equiv\;nk+1\mod n^2 \text. \] In particular, this implies that $(n+1)^\mathit{plain}\;\equiv\;n\mathit{plain}+1\mod n^2$.

This challenge required solvers to perform a related message attack on RSA. The task description is as follows:

Two agents, Alex and Jane, have simultaneously known very secret message and transmitted it to Center. You know following:

1. They used RSA with this (see below) public key
2. They sent exactly the same messages except the signatures (name appended, eg. “[message]Alex”)

3. They did encryption this way:

   c, = pubKey.encrypt(str_to_num(message), 1) # using RSA from Crypto.PublicKey
   c = num_to_str(c).encode('hex')
   

4. And here are cryptograms you have intercepted:

“61be5676e0f8311dce5d991e841d180c95b9fc15576f2ada0bc619cfb991cddfc51c4dcc5ecd150d7176c835449b5ad085abec38898be02d2749485b68378a8742544ebb8d6dc45b58fb9bac4950426e3383fa31a933718447decc5545a7105dcdd381e82db6acb72f4e335e244242a8e0fbbb940edde3b9e1c329880803931c”

“9d3c9fad495938176c7c4546e9ec0d4277344ac118dc21ba4205a3451e1a7e36ad3f8c2a566b940275cb630c66d95b1f97614c3b55af8609495fc7b2d732fb58a0efdf0756dc917d5eeefc7ca5b4806158ab87f4f447139d1daf4845e18c8c7120392817314fec0f0c1f248eb31af153107bd9823797153e35cb7044b99f26b0”

Now tell me that secret message! (The answer for this task starts from ‘ructf_‘)

The service bank consisted of a binary and a redis key/value storage database.

After netcatting to the service, which was hostet on port 3270, we found out that there is an Admin account, which presumably contained our keys.

First, we tried to reverse engineer the binary but found out that this was clearly not intended:

asprintf(&ptr, "%s%s", a1, "please_dont_try_to_reverse_this_this_is_just_anti_reimplementation_stuff");

Clearly, this was a dead end so we focused on the redis server. The server configuration was rather standard, so we applied basic security measures and renamed potentially evil functions like EVAL, EVALSA and others.

Trying to figure out what was going on we opened up redis-cli and specified the unix domain socket wich was used for communication between the service and the database.

redis-cli -s /home/bank/tmp/redis.sock

Using the MONITOR debug command we quickly found out a few things:

• Each account has got (at least) 4 Keys:
  • USERNAME_log
  • USERNAME_registered
  • USERNAME_password
  • USERNAME_balance
• The passwords were store in clear text
• The password of the Admin-account was qwertys – it was the same on all hosts.

After having finished the randomness solver, I decided that sleeping several hours would probably a good idea. (We’re based in Germany, where the CTF started at local time 11 pm.) When I got up again, several new reversing challenges had been published, amongst them elbisrever (it took me several hours to realize that the name is a pun btw …)

Now the standard procedure for any unknown file:

$> file randy
elbisrever: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, BuildID[sha1]=0xa07c38b37cd6059f1eccd431d7382494bd7b5d17, stripped

Hm … statically linked might result into problems, as we won’t recognize library functions. Let’s see what IDA has to say:

The randy binary should be the next target of interest. As it has no file name extension, we assume that it’s an executable binary for Linux. A quick lookup confirms this:

$> file randy
randy: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=0x0bb2fcccb38b0191ba3512735541461e5ffb468a, not stripped

So let’s once more give in to the temptation and just run it:

$> ./randy
Password: pass
:(

Okay. It asks for a password and then quits on my (obviously) wrong input. Let’s ask IDA to show what is going on inside. The boring part is done by the tool:

The binary named space game was the first of the challenges that drew my attention simply due to its file extension .nds - which is the standard file extension for Nintendo DS ROM images.

That having said, space game seemed to be a good candidate for the first blood candidate. Remembering that my actual background for reversing was originally from hacking both, Nintendo GBA and Nintendo DS systems for many years, I decided that it shouldn’t be to difficult for me to defeat it. :-)

In order to play the game, you need a suited Emulator, preferably one with a debugger included. My candidate of choice therefore was Martin Korth’s excellent (commercial) no\$gba debugger. Loading the binary in no\$gba and pressing several random keys we are presented with the following screen: