Wednesday, May 7, 2014

PHDays CTF Quals: Tasks Analysis

Positive Hack Days CTF is an international information protection contest based on the CTF (capture the flag) principles. Several teams are to defend their own networks and attack the networks of the other teams for a specified period of time. The contestants need to detect vulnerabilities in other teams' systems and to obtain sensitive information (flags) while detecting and fixing vulnerabilities of their own systems.

Today we would like to analyze certain interesting tasks that were offered to participants of the past contests.

History and Geography

This year PHDays CTF takes place for the fourth time. The contest was launched during the Positive Hack Days forum in 2011. Back then, the team PPP from the US was the winner. The following year in 2012 Leet More from Russia took first place. In 2013 at PHDays III, Eindbazen from the Netherlands took the top prize. Teams from all over the world — from the USA to Japan — participate in PHDays CTF every year.

More than 600 teams from all over the world have registered to take part in this year’s PHDays CTF.

Tasks and the Atmosphere

Traditionally, tasks and infrastructure are prepared based on a legend of the contest, which would turn a set of tasks into a fascinating competition. Last year, PHDays CTF participants tried to save the fictional world D’Errorim. The upcoming contest will continue the plot.

PHDays CTF's tasks are usually based on vulnerabilities that can exist in real life. What's more, the contest is remarkable for its game mechanics that make it possible to implement various strategies during the game (for more details visit the PHDays website).

The contest's organizers often develop additional tasks that are not directly related to system hacking. For instance, during PHDays 2012, participants could earn extra points by finding flags in containers filled with scrap paper, while PHDays III teams needed to get over the Labyrinth with laser field and motion detectors, secret doors, a room with bugs and other obstacles.

However, main points could be earned by solving different tasks related to information security. Let's get into the details of some of them.


PHDays CTF Quals is a task-based CTF contest, which means that teams should solve tasks and win points. Tasks can be classified into:

  • Forensic (computer forensic science),
  • Reverse (binary code analysis),
  • Pwn (vulnerability exploitation),
  • Admin (admin skills),
  • Network (knowledge of network infrastructure and protocols),
  • Crypto (cryptography),
  • Stegano (steganography),
  • PPC (professional programming and coding),
  • Web (detecting and using web vulnerabilities),
  • Misc (miscellaneous).

Let's start from the latest.

Nonobvious Solution

PHDays IV CTF Quals had a task that implied decryption of a message hidden in an MP3 file.

As a rule, when you need to extract a hidden message from a container, you can use a steganography solution. To solve the task you can also select a decryption software and to run it using valid keys. In other words, usually the key to success lies in finding the solution that was set up by the developers.

But our case is different. When we open the given file in a text editor, it looks like this:

There's metadata in the ID3 format at the beginning. We can see the TRCK tag (track number) and some text.

RGB7   5,183, NULL RGB6   0,42,159 RGB5   194,244,68 RGB4   47,77,6 RGB3   44,73,141 RGB2   140,207,72 RGB1   120,156,203

We can divide the data into seven records (from RGB7 to RGB1):

RGB7   5,183, NULL
RGB6   0,42,159
RGB5   194,244,68
RGB4   47,77,6
RGB3   44,73,141
RGB2   140,207,72
RGB1   120,156,203

There are three values after each RGB identifier. The values are given in numbers except one case, when it is NULL. It is an array of records, each of them containing up to three single-byte values. We can sort out the records, combine them, turn decimals code into symbols and convert them to hexadecimal using, for example, the following program:

>>> a = [120,156,203, 140,207,72, 44,73,141, 47,77,6, 194,244,68, 0,42,159, 5,183]
>>> print "".join(map(chr, a)).encode("hex")

As a result, we'll get:


The hexadecimal sequence starts with 0x78 0x9С bytes, which tells us that the zlib data compression algorithm is used. When you use zlib for compression with default parameters, the output sequence starts with these bytes.

By calling zlib's decompress function in Python we can unpack the message.

>>> import zlib
>>> print zlib.decompress("".join(map(chr, a)))

At this point we can see the text:


So this is the flag that participants should have sent to the contest's organizers.

Improper Cryptography

This task belongs to the Crypto category. According to the legend, a communication session was intercepted, and participants needed to decrypt the transmitted messages.

First of all, we can see a key exchange process and transmission of encrypted data. We need to define the cryptographic basis on which the communication was built.

The task is called “mars”, which might mean Modified RSA. Each key consists of two parts, the second part being equal to 0x010001 == 65537. It is a frequently used RSA (e) exponent, which means that in the communication session public keys are exchanged first (n1/e1, n2/e2), then messages encrypted using these keys are exchanged (c1, c2).

If it really is something similar to RSA, then ci = pow(mi, ei, ni). We need to calculate m1 и m2.

pow is a modular exponentiation function, pow(val, еxp, modulus) == valexp % modulus.

According to the RSA algorithm:
  • mi = pow(ci, di, ni),
  • di*ei ≡ 1 mod φ(ni),
  • ni — a product of several prime numbers,
  • φ(n) — Euler's phi function, the positive integers less than or equal to n that are relatively prime to n.
In this task, the n1 and n2 length is 1535 bits, which means that factorization (decomposition into prime multipliers) cannot be applied.

The extended Euclidean algorithm implementation in Python is at help:

def egcd(a, b): # Extended Greatest Common Divisor    if a == 0: return (b, 0, 1)    else:        g, y, x = egcd (b % a, a)        return (g, x - (b // a) * y, y)

We need to define the greatest common divisor (GCD) n1 and n2:

gcd = egcd(n1,n2)[0]

The length of GCD(n1, n2) is 1024 bits. Let's find other divisors of  n1 and n2:

p1 = n1 / gcd
p2 = n2 / gcd

p1 and p2 — are prime numbers with the length of 512 bits, cd is a composite number with the length of 1024 bits (most likely it's 512*512), and it's too large for factorization as well.

Let's consider the case when the unknown messages mi can be represented in numbers that do not exceed pi.

Let ni = pi*q*r, then as 0 < mi < pi the following expression will be true:

pow(mi, ei, ni) % pi == pow(mi, ei, pi)

Then the exponent used to decrypt d’i should comply with the following expression:

ei*d’i ≡ 1 mod φ(pi

The value of  d’i can be obtained by the calculation of the algebraic supplement:

d’i = invmod(ei, φ(pi)) 

For a prime number pi it is true that: φ(pi) == pi-1,


 d’i = invmod(ei, pi-1)

Calculation of the algebraic supplement is performed by the following function in Python:

def invmod(a, m): # Modular inversion    g, x, y = egcd (a, m)    if g == 1: return x % m    raise Exception("modular inverse does not exist")

We will also need a function that converts the number to a string and displays the text from the last symbol ‘\0’ to the end of the string:

def showX(v):    print ("%0256X" % v).decode("hex").split('\0')[-1]

We calculate di, then perform decryption:

d1 = invmod(e, p1-1)
d2 = invmod(e, p2-1)
showX(pow(c1, d1, p1))
showX(pow(c2, d2, p2))

Getting the result:

REQUEST: GET_FLAG (SIGNATURE: 5e2d5e0323591b1c).
RESPONSE: its_n0t_ab0ut_p4dd1ng

The flag was  «its_n0t_ab0ut_p4dd1ng».

The SECC Task

The contestants are given: the archive source.tar.gz, with the files and, containing the scheme of key verification, implemented elliptic curve cryptography. It is known, that connecting to port 5555 via the address, one can establish a connection with some server:

nc 5555
password: secch4l*

It is reasonable to start with analyzing the given files. One can even try to run them.
I didn't have a libnum module, so I had to write it. For the module, implementing the above mentioned function of modular inversion and the extended Euclidean algorithm used by it would do:

def egcd(a, b): # Extended Greatest Common Divisor    if a == 0: return (b, 0, 1)    else:        g, y, x = egcd (b % a, a)        return (g, x - (b // a) * y, y)
def invmod(a, m): # Modular inversion    g, x, y = egcd (a % m, m)    if g != 1: raise Exception("modular inverse does not exist")    else: return x % m

So, here is the function main from

def main():    print "Auth:“    auth = raw_input()    if hashlib.sha1(auth).hexdigest() !=    "375d5c01ca1b8c3863024d10aac7713472eb5033":  # secch4l*        print "nope“        return    prefix = os.urandom(8)    print "Proof of work, please“    print "Prefix is (hexed) ", prefix.encode("hex")    test = raw_input().decode("hex")    if not test.startswith(prefix) or len(test) > 16:        print "nope“        return    h = hashlib.sha1(test).hexdigest()    if not h.startswith("000000"):        print "nope“        return

The string is read, the SHA-1value from which should equal the defined value ("secch4l*").
Then the function generates a random 8-byte prefix, sent to the client. The bytes are encoded as a hex string. In response, the client should send a string no longer than 16 bytes and starting with the defined prefix, also the first 3 bytes of the SHA-1 value from tis string should be null. With all the steps successfully completed, the function goflag() is called.

The next code fragment establishes server connection, sends the password, receives the prefix, calculates and sends the response:

def readLn(sock):  a = []  while True:    c = sock.recv(1)    if '\n' == c: return "".join(a)    a.append(c)
HOST = ""PORT = 5555sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)sock.connect((HOST, PORT))print readLn(sock) # Auth:sock.send("secch4l*\n")print readLn(sock) # Proof of work, pleases = readLn(sock) print s # Prefix is (hexed)  0b3997e62b9ffbf4prefix = s.split()[-1].decode("hex")for i in xrange(0x7FFFFFFF):  s = "%s%X" % (prefix, i)  if hashlib.sha1(s).digest()[:3] == '\0\0\0': breaksock.send(s + '\n')

After this code is executed on the client side, the server runs the function goflag(), which returns something like that:

R = 572115218124168948525078362547166172445820217705568707355669424304224832114
ENCRYPTED MESSAGE: 7a93846a011e0d0382e94f32d705239e6298169dcec20da5d6

So, what is happening in the goflag function of

def goflag():    print "EC PASSWORD CHECK"    r = random.randint(31337, 1 << 250)    R = p256.power(G, r)    print "R =", R    print "SHARED SECRET = R ^ PASSWORD"    S = p256.power(R, PASSWORD)    key = p256.derive(S)    cipher = encrypt(FLAG, key)    print "ENCRYPTED MESSAGE:", cipher.encode("hex")

Here asymmetric cryptography based on elliptic curves is used. The recommended by NIST curve P-256 is chosen. The implementation of the curve points operations contains no obvious vulnerabilities.

We have the R value, but without knowing the PASSWORD value (which is read by the server from password.txt) we cannot calculate S. The S value would let us easily obtain the key. Maybe, the encryption implementation is faulty?

Here is the encrypt function from

def encrypt(msg, key):    iv = os.urandom(8)    stream = hashlib.sha256(iv + key).digest()    stream = hashlib.sha256(stream + iv + key).digest()    cipher = iv + xor(msg, stream)    return cipher

The code shows that the encrypted message is proceded by a random 8-byte initialization vector (iv), and the encryption is performed via a XOR shift of the flag with the gamma, which is generated as an output of two SHA-256 calculations. Without the key it is unreal to obtain the gamma value. But how the program gets the key?

Here is the derive function from

def derive(self, p):
  return hashlib.sha256(str((p[0] << 10) / p[1])).digest()

So, the value of the S point (which is made of two coordinates — x and y) is used as the SHA-256 input. In fact, the value str(int(x*1024/y)) is input to the hash function. Since the values of x and y are close (they are large integer numbers), the result of the arithmetic operations should be close to 1024 (although the result may exceed it by several times).

So due to the specifics of derive implementation, the key value may have a limited number of states. One can just use brute force them, trying to decrypt the message for every key, and if the message contains only of graphic characters — we got the flag.

import hashlib, eccenc = "7a93846a011e0d0382e94f32d705239e6298169dcec20da5d6".decode("hex")iv = enc[:8]def decrypt(key):  stream = hashlib.sha256(iv + key).digest()  stream = hashlib.sha256(stream + iv + key).digest()  return ecc.xor(enc[8:], stream)
for i in xrange(0x7FFFFFFF):  s = decrypt(hashlib.sha256(str(i)).digest())  for c in bytearray(s):    if c < 32 or c >= 128: break  else:    print s # ecc_is_too_s3cure    break

So the "ecc_is_too_s3cure" string is the flag.

Reverse Engineering, or Shadelt900

Reversing is one more popular type of CTF tasks. Apart from CTF, the individual challenge called Best Reverser is also among PHDays contests.

The task Shadelt900, just as the three tasks described above, was the part of PHDays IV CTF Quals, which took place in January 2014. The teams had to decrypt the image file called "derrorim_enc.bmp". The name of the tool applied for encryption was given – Shadelt9000.exe, but no decryptor can be found. Here is the image:

A closer examination of Shadelt9000.exe shows that the application uses OpenGL. There is also the copyright sign: inflate 1.2.8 Copyright 1995-2013 Mark Adler, indicating that the tool uses the popular compression library zlib.

Looking via a disassembler where calls to zlib originate from, you can quite quickly find this code batch:

The addresses 0x47F660 and 0x47F7B8 contain data arrays, packed with zlib. Let's unpack them:

from zlib import decompress as unZbase = 0x47C000 - 0x7AE00 # data section baseab=open("ShadeIt9000.exe", "rb").read()open("1.txt", "w").write(unZ(ab[0x47F660-base:],-15))open("2.txt", "w").write(unZ(ab[0x47F7B8-base:],-15))

After unpacking, the file 1.txt appears to contain a pixel shader:

#version 330uniform sampler2D u_texture;uniform sampler2D u_gamma;varying vec4 texCoord0;varying vec3 v_param;uint func(vec3 co){    return uint(fract(sin(dot(co ,vec3(17.1684, 94.3498, 124.9547))) * 68431.4621) * 255.);}uvec3 rol(uvec3 value, int shift) {    return (value << shift) | (value >> (8 - shift));}const uvec3 m = uvec3(0xff);void main(){ uvec3 t = uvec3(texture2D(u_texture, vec2(texCoord0)).rgb * 0xff) & m; uvec3 g = uvec3(texture2D(u_gamma, vec2(texCoord0)).rgb * 0xff) & m; int s = int(mod(func(v_param), 8)); t = rol(t, s); vec3 c = vec3((t ^ g) & m) / 0xff; gl_FragColor = vec4(c, 1.);}

The 2.txt file contains a vertex shader:

attribute vec3 a_param;varying vec4 texCoord0;varying vec3 v_param;void main(void){ gl_Position = gl_ModelViewProjectionMatrix * gl_Vertex; texCoord0 = gl_MultiTexCoord0; v_param = a_param;}

The principal information about the pixel shader is in red color:

void main(){  uvec3 t = uvec3(texture2D(u_texture, vec2(texCoord0)).rgb * 0xff) & m;  uvec3 g = uvec3(texture2D(u_gamma, vec2(texCoord0)).rgb * 0xff) & m;  int s = int(mod(func(v_param), 8));  t = rol(t, s);  vec3 c = vec3((t ^ g) & m) / 0xff;  gl_FragColor = vec4(c, 1.);}

The t variable contains the current item of the processed texture (of the input file), and the g variable contains the current gamma item (randomly generated). The s variable contains a certain value, later used for the s cyclic shift. The output value is actually computed this way:

(rol(t,s) ^ g)

Running the program several times with the same input file shows that g changes for each item with every run, however t and s always remain the same.

Let's find how the gamma is generated:

unsigned char *pbGamma = malloc(cbGamma);srand(time(0));for (i = 0; i < cbGamma; i++) {  pbGamma[i] = rand();}

Here you can see that it depends on the current time.

The initial archive allows finding out that derrorim_enc.bmp was created on 01/21/2014 at 18:37:52.
We can obtain the value the time() function would return at that time:

>>> import time
>>> print hex(int(time.mktime((2014,1,21, 18,37,52, 0,0,0))))


Now let's copy ShadeIt9000.exe to ShadeIt9000_f.exe and modify it.

With the shift 00015557, the bytes

E8 A5 31 01 00

should be changed to

B8 40 86 DE 52

This equals changing

call _time


mov eax,52de8640h

So we got the version of ShadeIt9000_f which will always encode with the gamma that was used at the encryption moment of the file in question.

Now let's prepare the values which will help decoding the image:

import osbmp=open("derrorim_enc.bmp", "rb").read()hdr = bmp[:0x36]abData = bytearray(bmp[0x36:])cbBody = len(bmp) - len(hdr)open("00.bmp", "wb").write(hdr + '\0'*cbBody)open("XX.bmp", "wb").write(hdr + '\2'*cbBody)os.system("ShadeIt9000_f.exe 00.bmp")os.system("ShadeIt9000_f.exe XX.bmp")

The file 00_enc.bmp will have the result of image encoding, consisting of null bytes. This will be the very gamma per se.

The file XX_enc.bmp will have the result of image encoding, consisting of bytes with the value 2. This helps us find out by how many bits every byte was cyclically shifted.

Finally, let's decode Shadelt9000:

def rol(v,i): return (((v<<i) & 0xFF) | ((v>>(8-i)) & 0xFF))def ror(v,i): return (((v>>i) & 0xFF) | ((v<<(8-i)) & 0xFF))dRot = {rol(1,i):i for i in xrange(8)}bmp=open("derrorim_enc.bmp", "rb").read()hdr = bmp[:0x36]abData = bytearray(bmp[0x36:])abGamma = bytearray(open("00_enc.bmp", "rb").read()[0x36:])abRot = bytearray(open("XX_enc.bmp", "rb").read()[0x36:])for i,b in enumerate(abGamma): abRot[i] = dRot[abRot[i] ^ b]for i,b in enumerate(abGamma): abData[i] = ror(abData[i] ^ b, abRot[i])open("derrorim.bmp", "wb").write(hdr + str(abData))

Here is the result:

Above I described a valid but not the most efficient way to solve the task. There is a shorter path.

Right after the vertex shader, with the addresses 0x47F848 and 0x47F9A0 there is the zlib-packed code of the pixel and vertex shaders rady for reversing. Perhaps, the code was accidentally left there be the task developer. Or possibly the developer planted the code on purpose
The codes of the vertex shader are identical for encoding and decoding, so there is no sense in tackling them. What if to modify the pixel shader?

Let's copy ShadeIt9000_f.exe into ShadeIt9000_d.exe and change it:

00015775: 60 F6 ==> 48 F8

Then let's run ShadeIt9000_d.exe derrorim_enc.bmp. This allows obtaining the decoded file derrorim_enc_enc.bmp, which (except some small) is the same as the image we got via the Python scrypt.

That's all for today! Thank you for reading it, you are welcome to comment and ask questions!

P. S. The archive of PHDays CTF finals and quals tasks is available on the PHDays website.


  1. you’re unquestionably somebody that has something to say that individuals must to listen. Keep up the magnificent work. Continue moving the people! It is very helpful information for me. Because I am new in blogging and I require great instructional exercise like your post. I can recommend you the essay writing services for having a good opportunity to get support for your writing works.

  2. Very interesting blog. Alot of blogs I see these days don't really provide anything that I'm interested in, but I'm most definately interested in this one. Just thought that I would post and let you know.
    geometry dash| sniper games |happy wheels | happy wheels 2 |agario| my little pony games mickey mouse games mahjong |pacman

  3. Going Back to Basics Overcomplicating Estimating, Analysis and Deadlines don’t let that get you down because you can easily write a custom term paper in 3 hours if you would invest enough time, effort and patience towards

  4. Useful article!The coverage and in-depth is really supportive for gaining the insights. Thanks for sharing!