This was a great CTF and we hacked some stuff. Here’s how.

This challenge consisted of breaking a **subset- product problem**.
Only two teams managed to solve the task during the CTF: we came in second after MSLC, who also got first blood on all other crypto tasks.

The full source code of the task is rather short:

```
from Cryptodome.Util.number import bytes_to_long, getPrime
import random
import hashlib
sr = random.SystemRandom()
p = getPrime(120)
num = [sr.randint(1,p-1) for i in range(90)]
secret = sr.randint(0, 2**90)
r = 1
for i in range(90):
if (secret >> i) & 1:
r *= num[i]
r %= p
flag = open("flag.txt","rb").read()
h = hashlib.sha256(str(secret).encode('utf-8')).digest()
print(p)
print(num)
print(r)
print(bytes_to_long(h)^bytes_to_long(flag))
```

So, we are given a product $r$ of a subset of known integers $x_1,…,x_n$, modulo a prime $p$, and the goal is to figure out what that subset was.

This task was about the additive transfer attack on elliptic curves, which seemed very interesting, but unfortunately no math was needed to solve it.

Here’s the only relevant part of the task script (written in `sage`

):

```
def input_int(msg):
s = input(msg)
return int(s)
```

Knowing that sage only recently switched to Python3 and the server might still
be running an older version,
we tried exploiting one of Python**2**’s
most dangerous footguns,
namely the *extremely* inappropriately named `input()`

function.
As the name suggests, this function reads some input — *and then eval()s it*. (WTF?!)

Writeup for PlaidCTF 2020’s “Bonzi Scheme” task, a.k.a. *How to hack hex with hyx: A totally serious guide*.

Full release of our research paper on executing a “preimage attack” on the MD5 function.

This challenge was a simple
(multi-threaded)
C++ web server (source)
featuring HTTP basic authentication for files in the `/secret/`

directory, which includes `flag.html`

.
Solvers had to circumvent the password check
(or figure out a way to get code execution
that I haven’t discovered yet `:-)`

).

This task asked for a forgery in a homebrew RSA-like signature scheme over a number field.
Sadly, it seems that everyone who solved it during the CTF circumvented the most interesting bits of the intended solution by applying more brute force (poor souls `:-)`

), so I will discuss my own solution here just in case anyone cares.

This challenge was a classical nonsensical shellcoding problem:
To solve it,
one had to *find* a **linear congruential generator** (LCG)
whose output is *printable*
x86_64 shellcode starting with the string `hxp<3`

.

It seems that some teams made assumptions on the (randomized) register values in their shellcode and simply kept retrying their payload $2^{16}$ times, but there was actually at least one deterministic one-shot solution which I’ll show here.

This challenge consisted of a ~~hard~~software security module
providing RSA signatures in PHP, together with a simple web
frontend written in Go that executes shell commands if they
are correctly signed (together with the client’s IP address).
However, (un)fortunately, the server would only sign
the command `ls -l`

, so one had to forge a signature.

This challenge fits into the category of babyheap challenges which are small heap puzzles with arbitrary limitations. Here a small pad was implemented which can hold eight notes at a time but after reading a note it was destroyed. The vulnerability was a classical use after free (UAF) in `rewrite`

that did not check whether a note was valid or not. This bug however could only be triggered once.

If Compiler Explorer is too bloated for you, you can always rely on our excellent compiler bot to tell you whether you screwed up while coding your latest exploit.

And since we never actually run your code, there’s no way for you to hack it!

Download: compilerbot-f64128acb63c6bbe.tar.xz (10.9 KiB)

Connection:`nc 88.198.154.157 8011`

Time for an Emu War.

Pl0x upload your coolest ROMs, here is mine :>.

Download: Emu War-35eccd2af489ec05.tar.xz (495.9 KiB)

Connection:`http://78.47.138.71:65000/`

The

otherother JavaScript engine.Download: vvvv-cc9085ea51e239dc.tar.xz (11.3 KiB)

Connection:`nc 88.198.156.11 13336`

In this CTF, we destroyed both LC↯BC and PPP. lol.

This was a great CTF and we hacked some stuff. Here’s how.

- CTF: https://ctftime.org/event/851/
- Category: misc
- Points: 203

Given was `PlayCAP.pcapng`

and `app.html`

. First checking the PCAP, we see that an USB connection is captured there. In the `Response DEVICE`

, the vendor `Nintendo Co., Ltd`

is shown. Later the device name is sent as string: `Pro Controller`

.

This is one more challenge from the “heap exploitation puzzle franchise”. Like many times before you can almost directly interact with the heap. Typical for 0CTF, allocations were tracked on a mmapped page at an entirely random address. Together with the address, the size of the allocation is stored as well. There can be at most 16 allocations at a time. You can update, view and delete these allocations, and as long as you are within the 16-allocation limit, you can also create new allocations.

In this challenge there are two vulnerabilities. First, allocations are created with malloc and not immediately initialized, so that when viewed directly after allocation, you recieve the old content. Second, when updating you can only provide bytes up to the size you specified when allocating the chunk, but a null byte is always added. This results in the infamous null byte overflow.

Unless you’ve lived under a rock for the past months, you’ve probably already heard the ~~good~~ news that hxp will organize their famous and celebrated* CTF during 36C3 this year.

*

This CTF featured the best barszcz ever!— Redford, p4*

The only thing I can complain about is the lack of pierogi.— valis, justCatTheFish_*

If hxp ever organizes C3CTF, I will cut my hair!— nsr, teamless, also known as Gynvael*

a big group of hxp players from Germany, which makes me sad— msm, Dragon Sector

Yet another cryptanalysis challenge to test your differential-linear skills.

This challenge comes with an implementation of (almost) textbook DES, and a server that allows us to encrypt arbitrary plaintexts with that cipher (in ECB mode, i.e. each 64-bit block independently) using a key that is randomly generated per connection.

There is a time limit set for 20 minutes. To obtain the flag, we need to find the key used by the server for our connection, and submit it to the server.

Unlike some other CTFs [1, 2], this time DES actually means DES without any weird modifications — but there are only 8 rounds instead of the standard 16.

People always say that ROP is Turing complete, show me by implementing the Floyd-Warshall algorithm.

The description already says exactly what is going to happen here: We are provided with a program that

- prints the address of
`malloc`

to give us access to the libc (libc6 2.27-3, Ubuntu x64), - reads a ROP chain from the input,
- generates random fully-connected graphs,
- and verifies that the ROP chain actually performs the Floyd-Warshall algorithm.

This challenge is yet another one of the “heap puzzle” kind. The interactions with the server usually are quite obvious however arbitrary restrictions are enforced. This task is no exception to that. Before going over the challenge and the solution, I quickly wanted to thank the author of this challenge for its well thought out design. All reads performed by the program took a predictable number of bytes from the input stream, so that synchronization could be skipped in some parts of the exploit. This massively speed up the time needed to perform all the necessary actions, as the script had not to wait for the quite large round-trip time too often.

When connecting to the given URL, we are provided with the following output:

```
Imagick is a awesome library for hackers to break `disable_functions`.
So I installed php-imagick in the server, opened a `backdoor` for you.
Let's try to execute `/readflag` to get the flag.
Open basedir: /var/www/html:/tmp/b6b320612bead18b3b67932f139fed1f
Hint: eval($_POST["backdoor"]);
```

This challenge asked us to break an instance of the Matsumoto–Imai multivariate public-key encryption scheme. Clearly the first thing to look at is a **linearization attack**:
The first step is generating about $(N+1)^2$ plaintext-ciphertext pairs $(x_i,y_i)$, which is of course possible using the public key by encrypting random plaintexts. One then looks for *linearization equations* of the form
\[
a_{ij}x_iy_j + b_ix_i + c_ix_i + d = 0
\]
that *all* those pairs satisfy; this consists of solving a big linear system with $(N+1)^2$ unknowns $a_{ij},b_i,c_j,d$. The construction of the nonlinear maps used in the MI scheme ensures that there exist $N$ such equations in almost all cases. Finally, one can take those linearization equations, plug in a specific ciphertext $y_1,\dots,y_N$, and solve for the plaintext $x_1,\dots,x_N$.

This crackme-style reversing task consisted of an x86_64 binary whose main operations are:

- Build a table
`data`

of 128-bit constants. - Check that the input matches
`flag\{[0-9a-f]{32}\}`

. - Hex-decode the inner part of the flag to obtain a byte string
`x`

. - Initialize a 128-bit integer variable
`v`

with the value -1 (all bits set). - For each byte
`c`

in`"flag{" + x + "}"`

:- Compute
`v := data[(v&0xff) ^ c] ^ (v >> 8)`

.

- Compute
- Check that
`v`

in little-endian representation equals`x`

.

This challenge consisted of finding a collision for Keccak with a very small capacity parameter.

The only really relevant part of the task’s source code is:

```
return CompactFIPS202.Keccak(1552, 48, bytearray(msg), 0x06, 32)
```

When given two distinct `msg`

s such that this call returns the same hash value, the server will hand out the flag.

This challenge asked us to recover the initial state of three linear-feedback shift registers (each of size 48), given the output of a nonlinear `combine()`

function applied to the three individual output streams:

```
def combine(x1,x2,x3):
return (x1*x2)^(x2*x3)^(x1*x3)
```

This challenge is about a variant of RSA encryption where the integers are replaced by a polynomial ring over $\mathbb F_2$.

Recall that RSA works in a ring $\mathbb Z/n$ where $n=pq$ is a product of two large random primes. To break RSA, it is sufficient to compute the size $\varphi(n)$ of the unit group $(\mathbb Z/n)^\ast$ since this allows one to compute $e$th roots in that group. The owner of the private key can compute $\varphi(n)$ as $(p-1)(q-1)$; without knowing $p$ and $q$ this problem is assumed to be hard.

In this challenge, $\mathbb Z$ is replaced by $\mathbb F_2[x]$ and $n$ is replaced by a big polynomial $f\in\mathbb F_2[x]$ of degree $2049$.

This task consisted of exploiting a program whose main purpose seems to be to read some input and compare it to the flag. To perform this operation, the program uses multiple threads and does some other suspicious things, but I didn’t use these for solving it (and in fact, the author confirms that the following solution was unintended).

Most of the code is irrelevant, except for the following snippet of the reconstructed C code that does the actual comparison:

```
for (i = 0; i < len_flag; ++i) {
if (globals->input[i] != flag[i]) {
myprintf(globals->input);
myprintf(" is not right.\n");
return 0;
}
}
myprintf(":)\n");
```

In this challenge, the task was to break out of a
Ruby sandbox
using `seccomp`

and Ruby’s “safe” mode to read the flag file.

I have almost no clue about Ruby, hence I went the low-level route.

Every player knows the one problem of both online and on-site CTFs. You really enjoy (or hate) hacking awesome challenges. But once the CTF is over most of the online services, web challenges, downloads and descriptions are gone forever.

We tried to offer a static archive of our past CTFs. Sadly, we can’t keep the challenge services running forever and only the challenges’ description and downloads are available. This is a big problem when you want to test your write-up against the original execution environment or generally want to teach anyone about past CTFs.

So, we decided to dig through our archives and repack all challenges of the hxp CTF 2017 into one self-contained virtual machine:

This “baby” task consisted of exploiting the following short C program without being given the compiled binary:

```
/* includes omitted */
char asdf[1024];
int main()
{
long long index = 0;
alarm(5);
read(0, &index, 1024);
read(0, asdf+index, 8);
read(0, &index, 1024);
}
```

In this task, we’re given a core dump of an `x86-64`

ELF file that has crashed due to a `SIGSEGV`

. Our job is to investigate on the reason of the `SIGSEGV`

and reconstruct the actual program flow calculating a flag.
The reason of the segfault is quite obvious, as `gdb`

tells us:

```
RAX 0x555555554e9a ◂— inc dword ptr [rax]
RBX 0x555555554e9d ◂— leave
RCX 0x7fffffffec70 ◂— 0x6c69665f73696874 ('this_fil')
RDX 0x7fffffffec94 ◂— 0xdc7ab200791dc20e
RDI 0x7fffffffec70 ◂— 0x6c69665f73696874 ('this_fil')
RSI 0x7fffffffec90 ◂— 0x791dc20eefa46567
R8 0x7ffff7fd7740 ◂— 0x7ffff7fd7740
R9 0x13
R10 0x7ffff7fd7740 ◂— 0x7ffff7fd7740
R11 0x246
R12 0x5555555549d0 ◂— xor ebp, ebp
R13 0x7fffffffed90 ◂— 0x5
R14 0x0
R15 0x0
RBP 0x7fffffffecb0 —▸ 0x5555555552d0 ◂— push r15
RSP 0x7fffffffec38 —▸ 0x5555555552aa ◂— mov eax, 0
RIP 0x555555554e9a ◂— inc dword ptr [rax]
[────────────────────────DISASM───────────────────────────]
► 0x555555554e9a inc dword ptr [rax]
```

Currently, `rax`

points to non-writable memory within the program’s executable segment causing the `inc`

instruction to fail. Clearly, the execution flow should not end up here.

We’re given a binary called `mario`

which (stereotypically) simulates a pizza bakery in Italian English.

A first investigation shows that Mario is not happy with our pizza:

In this challenge, we were given a binary `preview`

, which prints the first seven lines of any file if (and only if) the file contains more than six lines. Of course the flag file contains a single line only.

The binary itself consists of two stages: the first stage (an ELF file) will “decrypt” the second stage, which is another ELF file contained in the data section, load this program as well as the runtime linker (rtld) to random addresses, and jump into the loader. The loader loads the remaining shared libraries and executes the second program normally.

In this challenge, one had to write x86 shellcode using musical notes, i.e.,
the shellcode had to be a sequence of the ASCII strings
`An`

, `A#n`

, `Bn`

, `Cn`

, `C#n`

, `Dn`

, `D#n`

, `En`

, `Fn`

, `F#n`

, `Gn`

, `G#n`

,
where `n`

is between `0`

and `9`

. (And one had to send these notes to
the server encoded as frequencies, which was easy to revert.)
The registers were initialized as: `eax=ebx=ecx=edx=0`

and `edi=esi=esp`

.
Some constant strings were put on the stack prior to running our code.
The shellcode was loaded and executed at `0x60606000`

.

We assembled a `read(0, 0x60606260, a_few)`

syscall to read more (regular)
shellcode using **self-modifying code** as follows.

The challenge consisted of a Python service which encodes a user-supplied message in a user-supplied image using a native Python library. Due to missing (wrong) length checks, the binary allowed for buffer overflows on the stack as well as on the heap.

Check if you have a flag that has been compromised in a data breach

Connection:

100 Basepoints + 100 Bonuspoints * min(1,

^{3}⁄_{39}Solves) = 107 Points

This writeup explains the haveibeenpwning challenge of the recent hxp CTF 2017.

The challenge presents a web site that allows to check if our flags have been compromised.

extract the flag! Download:

83ff3b21362b514c20861c94fb3f68aed3e11ebf81c80f5e1f6ecfcc4ca8ed64.tar.xz

The challenge consisted of extracting a flag from a .pcapng-stream, captured while scanning a sheet of paper via USB.

web_of_ages consisted of six levels, all with one sort of injection exploit.

- Level 1: SQL injection
- Level 2: Blind SQL injection
- Level 3: XPath injection
- Level 4: Object injection
- Level 5: Insert injection
- Level 6: Command injection

This level had basically no filter and a normal “print” statement, so all you needed to do was to select the username and password from the database. The username was especially easy, just circumvent the check with `{"user":"???", "' OR 1=1 -- "}`

, the result was `admin`

. To get the password we used UNION: `{"user":"admin", "password":"' AND 0=1 UNION (SELECT password, password, password FROM auth WHERE username = '{}') -- "}`

.

Warning: flag format for this challenge: HXP{…}

Now please inspect. Download:

4dd967a4fa319ae9049d4f7e3e7b5fc225e6467aa7c0bffac69335a0ad41c508.tar.xz

250 Basepoints + 100 Bonuspoints * min(1,

^{3}⁄_{0}Solves) = 350 Points

The idea of this challenge was to distribute a pcap that contained different layers of encrypted content to show that their *typical mode of operation* is insecure.

When opening the pcap in your favorite packet analyzer (for example Wireshark) you will find a lot of DNS traffic. With Iodine you are able to tunnel your data through a restricted network that otherwise requires a login within a captive portal. Usually these networks filter traffic like HTTP or SSH but allow passing of DNS traffic.

Iodine traffic is not encrypted, authentication is implemented by checking an MD5 hash in the beginning of the protocol. The **Upstream data** is typically encoded with a custom version of **base128** and the **downstream** is typically raw when used with a DNS record of type **NULL**.

This was the highest-rated crypto challenge in our recent hxp CTF 2017.

In a nutshell, the task is to find a collision in a weak instantiation
of the
Charles-Goren-Lauter hash function
on a **supersingular isogeny graph**.

The idea of that hash function is: Given an exponentially large graph,
we can construct a hash function using graph walking
by choosing the edge taken at each step according to the next input bit.
Once all bits are consumed, some identifier of the end node is returned.
Assuming that the underlying graph is “random”, this yields a
collision-resistant hash function.

(For example: collisions give rise to nontrivial cycles by concatenating the two different paths with the same end node;
finding a preimage would amount to finding a path between the start node and the target node. Since the graph is exponentially large, obtaining either of these objects by brute force is infeasible.)

However, in our instantiation, the underlying graph has some efficiently computable structure that can be used to find collisions much faster than by brute force.

This writeup explains how we solved a reversing task called `moon`

during the
Google CTF last weekend. In summary, the task implements a password check
*using OpenGL shaders*.

The organizers threw “yet another crypto problem” (yacp) at us. It’s a 32bit ELF binary that implements a simple encryption / hashing service. In the following we describe our (most likely overly complicated) three-stage exploit that would get us the flag just one hour after the competition ended. The writeup is intentionally written in a rather detailed way, so skip right to the bottom if you’re only interested in the high-level summary of what we did.

*wheel of robots* was one of the pwn challenges in the Insomnihack main event with medium difficulty.
You could choose from 6 robots to add to the ‘wheel of robots’. Some robots have an adjustable attribute
which determined the maximum size their name could take.

- Tinny Tim
- Bender (intelligence)
- Robot Devil (cruelty)
- Chain Smoker
- Billionaire Bot
- Destructor (powerful)

You could change the name of robots you already added to the wheel of robots, or delete them.
Once you added 3 robots to the wheel, you could spin it. One of the three robots was then
selected and an action executed depending on the robot. For most robots, the name was printed
as well.
Internally, the robots had each a flag and a pointer in the `BSS`

. The flag was set when a
robot got selected, and cleared when it was deleted. The pointer pointed to the name which was
allocated on the heap.

This challenge required us to design a quantum circuit which detects on a two-qubit system whether a measurement is taking place or not, while making sure a certain state never gets measured. As per the challenge description, this can be used to detect an eavesdropper without them noticing.

We’re given an Android `.apk`

file, and asked to steal information from the
exfiltrators. After figuring out the encoding scheme used to communicate with
the server, we extract the secret flag from the server via an SQL injection.

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`

Hints

- What would you get if you’d encrypted four-block data of the form AABC, where A, B, C are 64-bit arbitrary blocks?
- 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. :)

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`

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 *fun* 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,\;P\mapsto [f]P$, where $f$ is the private key and $\mathbb E$ is an elliptic curve. 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; }
}
```

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.

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:

- They used RSA with this
(see below)public key- They sent exactly the same messages except the signatures (name appended, eg. “[message]Alex”)
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')`

And here are cryptograms you have intercepted:

`“61be5676e0f8311d`

ce5d991e841d180c 95b9fc15576f2ada 0bc619cfb991cddf c51c4dcc5ecd150d 7176c835449b5ad0 85abec38898be02d 2749485b68378a87 42544ebb8d6dc45b 58fb9bac4950426e 3383fa31a9337184 47decc5545a7105d cdd381e82db6acb7 2f4e335e244242a8 e0fbbb940edde3b9 e1c329880803931c”

`“9d3c9fad49593817`

6c7c4546e9ec0d42 77344ac118dc21ba 4205a3451e1a7e36 ad3f8c2a566b9402 75cb630c66d95b1f 97614c3b55af8609 495fc7b2d732fb58 a0efdf0756dc917d 5eeefc7ca5b48061 58ab87f4f447139d 1daf4845e18c8c71 20392817314fec0f 0c1f248eb31af153 107bd9823797153e 35cb7044b99f26b0” 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: