Hacker Battles: Parsing PHDays CTF and CTF Quals Jobs

Positive Hack Days CTF - international information protection competitions, which are held according to the gaming principle of Capture the Flag. Several teams during the allotted time defend their networks and attack strangers. The main task of the participants is to identify vulnerabilities in enemy systems and gain access to secret information (flags), while detecting and eliminating such vulnerabilities in their system.

In today's topic, we will present an analysis of some interesting tasks that the participants of the past competitions faced.

History and Geography

This year PHDays CTF will be held for the fourth time. The competition was held for the first time during the Positive Hack Days forum in 2011, then the PPP team members became the winners, the Russian team Leet More won the next year, and Eindbazen from the Netherlands became champions at PHDays III. Every year, teams from all over the world take part in PHDays CTF - from the USA to Japan.

This year, more than 600 teams have registered to participate in the qualifying competitions.

Quests and atmosphere

According to the established tradition, game tasks and infrastructure are prepared in accordance with the legend of the competition - a special storyline that turns a simple set of PHDays CTF tasks into an exciting competition that has a goal. For example, last year, participants saved the fictional world of D'Errorim from death. Upcoming competitions will continue this story .

Competition tasks are usually based on real prototypes: the vulnerabilities in CTF tasks and services can be found in various systems in real life. PHDays CTF competitions are also interesting for the original game mechanics, which make it possible to implement different and dissimilar strategies for playing the game (more on the PHDays website ).

Usually, the organizers prepare unusual tasks for teams that are not directly related to hacking. For example, during PHDays 2012, extra points could be earned by discovering bonus flags in a special garbage container, and during PHDays III the teams had to overcome the “ hack maze ” - the obstacle course with a laser field, tracking sensors, secret doors, a room with bugs and other interesting tests.

But the main points, of course, are earned solely in the course of solving various problems of information security. Let's take a look at some of them.

Parsing

The qualification stage of the competition (PHDays CTF Quals) refers to the type of task-based CTF, that is, teams must solve tasks and get points for them. Tasks may fall into one of the following categories:

• Forensic - computer forensic examination,
• Reverse (reverse engineering) - binary code analysis,
• Pwn - exploitation of vulnerabilities,
• Admin - administration skills,
• Network - knowledge of network infrastructure and protocols,
• Crypto - cryptography,
• Stegano - steganography,
• PPC (professional programming and coding) - olympiad programming,
• Web - search and use of web vulnerabilities,
• Misc - miscellaneous.

Let's start with the last category.

Unobvious quests

Participants in PHDays IV CTF Quals as part of one of the tasks needed to decrypt the message hidden in the mp3 file .

As a rule, if the condition of the problem mentions the extraction of a message hidden in a container, one of the ready-made solutions from the field of steganography is used. In this case, to find the answer, you usually need to select a program for decryption and run it with the correct keys. That is, the "key to success" in solving a specific task lies in the search for a suitable option, previously prescribed by the authors.

In our case, everything is somewhat different. If you open the proposed file in a text editor, it looks like this:

At the beginning of the file are metadata in ID3 format. First comes the TRCK (track number) tag, and then some pieces of 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

This information can be divided 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 of the RGB identifiers. These are usually numbers, but in one case NULL. It is easy to assume that this is an array of records, each of which contains up to three single-byte values. You can sort, combine, convert decimal codes to characters and print them in hexadecimal, for example, using 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 get:

789ccb8ccf482c498d2f4d06c2f444002a9f05b7

The hexadecimal sequence begins with bytes with codes 0x78 0x9C, and this tells us that the zlib data compression algorithm is used. If you use zlib in compression mode with default parameters, the output sequence will begin with these bytes.

With one call to the decompress function of the zlib library in Python, you can unpack the packed message:

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

And then the text will be displayed:

i_hate_ucucuga

It was this flag that had to be sent to the organizers of the competition.

Invalid Cryptography

This assignment belongs to the category Crypto. According to legend, a communication session was intercepted , and the teams need to decrypt the transmitted messages.

First of all, the process of exchanging keys and then transmitting encrypted data is clearly visible. It is necessary to understand on the basis of what cryptographic basis such communication can be built.

The task is called mars, we can assume that this means Modified RSA.

Each key consists of two parts, and the second part in both cases is 0x010001 == 65537 - a frequently used public exponent of RSA (e). So, in the communication session, there is first an exchange of public keys (n ₁ / e ₁ , n ₂ / e ₂ ), and then an exchange of messages encrypted on them (c1, c2).

If this is really something similar to RSA, then ci = pow (m _i , e _i , n _i ). It is required to find m ₁ and m ₂ .
pow - function of modular exponentiation, pow (val, exp, modulus) == val ^exp % modulus.

According to the RSA algorithm:

• m _i = pow (c _i , d _i , n _i ),
• d _i * e _i ≡ 1 mod φ (n _i ),
• n _i is the product of several primes,
• φ (n) is the Euler function, the number of natural numbers coprime to n and less than n.

In the task, n ₁ and n ₂ have a length of 1535 bits, that is, they cannot be factorized (decomposed into simple factors).

We will use the implementation of the extended Euclidean algorithm in Python:

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)

Find the GCD (the largest common factor) of the numbers n ₁ and n ₂ :

gcd = egcd(n1,n2)[0]

GCD (n ₁ , n ₂ ) has a length of 1024 bits. Find other divisors of the numbers n ₁ and n ₂ :

p1 = n1 / gcd
p2 = n2 / gcd

p ₁ and p ₂ are primes 512 bits long, gcd is a composite number 1024 bits long (most likely 512 * 512), and it is also too large for factorization ...

Consider the case when the desired messages m _i can be represented by numbers not exceeding p _i .

Let n _i = p _i * q * r, then for 0 <m _i <p _{i the} following expression will be valid:

pow (m _i , e _i , n _i )% p _i == pow (m _i , e _i , p _i )

Тогда экспонента для расшифрования d’_i должна удовлетворять следующему выражению:

e_i*d’_i ≡ 1 mod φ(p_i)

Значение d’_i может быть найдено путем вычисления алгебраического дополнения:

d’_i = invmod(e_i, φ(p_i))

Для простого p_i справедливо:

φ(p_i) == p_i-1,

Следовательно:

d’_i = invmod(e_i, p_i-1)

Вычисление алгебраического дополнения реализуется следующей функцией на 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")

You will also need a function that turns a number into a line and leaves only text from the last character '\ 0' to the end of the line:

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

Calculate di, perform decryption:

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

And we get the result:

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

Flag - string " its_n0t_ab0ut_p4dd1ng".

Ccc cryptographic assignment

Given: source.tar.gz archive containing the ecc.py and task.py files, which contain the key verification scheme implemented using elliptical cryptography. It is known that by connecting at address 195.133.87.171 to port 5555, you can establish a connection with some server:

nc 195.133.87.171 5555
password: secch4l*

Since the sources are given, it is worth starting with their analysis. You can even run them.
Since I did not have the libnum module, I had to write it myself. It is enough to implement in it the previously mentioned function of modular inversion and the extended Euclidean algorithm used by it:

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, the function mainfrom task.py:

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
    goflag()

A line is read, SHA-1 from which must be equal to the specified value ("secch4l *").
Then a random 8-byte prefix is ​​generated that is sent to the client. Bytes are encoded as a hex string. In response, the client must send a string no longer than 16 bytes, so that it starts with the specified prefix, and the first 3 bytes of the SHA-1 value from this string must be zero. If all the steps are successful, the goflag () function is called.

The following code fragment connects to the server, sends a password, receives a prefix, calculates and sends a response:

def readLn(sock):
  a = []
  while True:
    c = sock.recv(1)
    if '\n' == c: return "".join(a)
    a.append(c)
HOST = "195.133.87.171"
PORT = 5555
sock = 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, please
s = readLn(sock)		
print s			# Prefix is (hexed)  0b3997e62b9ffbf4
prefix = s.split()[-1].decode("hex")
for i in xrange(0x7FFFFFFF):
  s = "%s%X" % (prefix, i)
  if hashlib.sha1(s).digest()[:3] == '\0\0\0': break
sock.send(s + '\n')

После выполнения этого кода на стороне клиента сервер выполняет функцию goflag(), выводящей примерно следующий текст:

EC PASSWORD CHECK
R = 572115218124168948525078362547166172445820217705568707355669424304224832114
SHARED SECRET = R ^ PASSWORD
ENCRYPTED MESSAGE: 7a93846a011e0d0382e94f32d705239e6298169dcec20da5d6

Что же происходит в функции goflag из task.py:

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")

Asymmetric cryptography on elliptic curves is used. The P-256 curve recommended by NIST is selected. The implementation of operations on curve points does not contain obvious vulnerabilities.

We know the value of R, but without knowing the value of PASSWORD (which is read by the server from the password.txt file), we cannot calculate S. Knowing S would allow us to easily calculate the key. So maybe encryption is implemented with an error?

Function encryptfrom task.py:

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 preceded by a random 8-byte initialization vector iv, and encryption is performed as an XOR flag with a gamma generated as the output of two SHA-256 calculations. Without knowing the meaning of key, getting a gamma is unrealistic. But how is key obtained in the program?

The derive function from task.py:

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

It turns out that the value of point S (consisting of two coordinates - x and y) is used as input SHA-256. In fact, the value of str (int (x * 1024 / y)) is supplied to the hash input. Since x and y have close values ​​(these are large integers), the result of arithmetic operations should be close to 1024 (although it may exceed it by several times).

Thus, due to the particular implementation of the derive function, the key value can take on a very small number of states. You can simply sort through them all, try to decrypt the message on every key, and if it consists only of printed characters, we have achieved success.

import hashlib, ecc
enc = "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

Thus, the flag is the line "ecc_is_too_s3cure".

Reverse engineering. Shadelt900

Reverse engineering is another popular job category. In addition to CTF, the Best Reverser contest is included in the PHDays competition program.

The Shadelt900 assignment, like the previous three, was part of the PHDays IV CTF Quals program, held in January 2014. The teams had to decrypt an image called 'derrorim_enc.bmp'. It was known that the tool used to encrypt it was called Shadelt9000.exe, but the decryptor could not be found. Here is this image:



Upon closer inspection of the Shadelt9000.exe file, it becomes clear that the application uses OpenGL. There is also a copyright inflate 1.2.8 Copyright 1995-2013 Mark Adler, indicating that the program uses the popular zlib compression library.

If you look in the disassembler where the calls to the zlib functions come from, you can quickly find such a piece of code:



The 0x47F660 and 0x47F7B8 addresses contain data arrays packed by zlib. Unpack them:

from zlib import decompress as unZ
base = 0x47C000 - 0x7AE00 # data section base
ab=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 1.txt file contains a pixel shader:

#version 330
uniform 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 the 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 main information about the pixel shader is highlighted in red:



The current element of the processed texture (input file) is
in the variable t, and the current gamma element (generated in a pseudo-random way) is in the variable g.
In the variable s, we see some value used later for the cyclic shift of s.
The output value is actually calculated as

(rol(t,s) ^ g)

follows. If you run the program several times with the same input file, then for each element the value of g will change from start to start, and t and s will remain the same.

Find how the gamma is generated:

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

It can be seen that it depends on the current time.

From the original archive you can find out that the file derrorim_enc.bmp was created on 01.21.2014 at 18:37:52.
We get the value that the time () function would return at that moment:

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

0x52de8640

Now copy the file ShadeIt9000.exe to ShadeIt9000_f.exe and fix it.

At offset 00015557, the bytes must be

E8 A5 31 01 00

replaced with

B8 40 86 DE 52

This is equivalent to replacing

call _timewith mov eax,52de8640h.

Thus, we got the version of ShadeIt9000_f, which will always encrypt with the same gamut as it was at the time of encryption of the file of interest to us.
Now you need to prepare the values ​​that will help decrypt the image:

import os
bmp=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 00_enc.bmp file will contain the result of encrypting the picture, consisting of zero bytes. This will be gamma in its purest form.

The XX_enc.bmp file will contain the result of encrypting the picture, consisting of bytes with a value of 2. This will help us find out how many bits each byte was cyclically shifted.

Finally, by decrypting Shadelt9000:

def rol(v,i): return (((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))

we get: The



correct, but not the most effective way to solve the task was described above. There is a shorter way.

Immediately behind the vertex shader at the addresses 0x47F848 and 0x47F9A0 lies the packed zlib code of the pixel and vertex shader to perform the inverse transform. Perhaps he was accidentally forgotten by the task designer. Or maybe left intentionally.

The vertex shader codes for encryption and decryption are identical, so it makes no sense to touch them. And what happens if you replace the pixel shader?

Copy ShadeIt9000_f.exe to ShadeIt9000_d.exe and fix it:

00015775: 60 F6 ==> 48 F8

Then run ShadeIt9000_d.exe derrorim_enc.bmp. And we get the output of the decrypted file derrorim_enc_enc.bmp, which (with the exception of small artifacts) coincides with the one that we decrypted with a Python script.

That's all for today! Thank you all for your attention, we will be happy to answer questions in the comments.

We remind you that the final of the PHDays IV CTF will be held on May 21 and 22 during the Positive Hack Days forum. It will be possible to monitor the progress of the competition not only directly on the site, but also using mobile applications. Follow the news !

Read also:

• PHDays III CTF: An Inside Look (Part 1)
• PHDays III CTF: An Inside Look (Part 2)

We remind you that registration has already begun for participation in the online contests HashRunner and " Competitive Intelligence " on PHDays IV!

PS An archive of all PHDays CTF and CTF Quals assignments can be found on the PHDays website . So, if you have a desire to test yourself - go ahead!

PPS A detailed analysis of the tasks presented in the topic took place at a special webinar hosted by Dmitry Sklyarov. The webinar entry is available at: http://my.webinar.ru/record/290241/ .