Wednesday, March 29, 2017
PHDays CTF Quals Tasks Analysis
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.
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 CTFs tasks are usually based on vulnerabilities that can exist in real life. Whats 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 contests 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. Lets get into the details of some of them.
Analysis
PHDays CTF Quals is a task-based CTF contest, which means that teams should solve tasks and win points. Tasks can be classified into:
Lets 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:
Theres 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, well get:
789ccb8ccf482c498d2f4d06c2f444002a9f05b7
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 zlibs 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:
i_hate_ucucuga
So this is the flag that participants should have sent to the contests 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:
The extended Euclidean algorithm implementation in Python is at help:
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. Lets 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 its 512*512), and its too large for factorization as well.
Lets 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,
Therefore:
d’i = invmod(ei, pi-1)
Calculation of the algebraic supplement is performed by the following function in Python:
We will also need a function that converts the number to a string and displays the text from the last symbol ‘’ to the end of the string:
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 ecc.py and task.py, containing the scheme of key verification, implemented elliptic curve cryptography. It is known, that connecting to port 5555 via the address 195.133.87.171, one can establish a connection with some server:
nc 195.133.87.171 5555
password: secch4l*
It is reasonable to start with analyzing the given files. One can even try to run them.
I didnt 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:
So, here is the function main from task.py:
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 CTFs tasks are usually based on vulnerabilities that can exist in real life. Whats 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 contests 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. Lets get into the details of some of them.
Analysis
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).
Lets start from the latest.
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:
Theres 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, well get:
789ccb8ccf482c498d2f4d06c2f444002a9f05b7
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 zlibs 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:
i_hate_ucucuga
So this is the flag that participants should have sent to the contests 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) — Eulers phi function, the positive integers less than or equal to n that are relatively prime to n.
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. Lets 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 its 512*512), and its too large for factorization as well.
Lets 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,
Therefore:
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 ‘’ to the end of the string:
def showX(v): print ("%0256X" % v).decode("hex").split()[-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 ecc.py and task.py, containing the scheme of key verification, implemented elliptic curve cryptography. It is known, that connecting to port 5555 via the address 195.133.87.171, one can establish a connection with some server:
password: secch4l*
It is reasonable to start with analyzing the given files. One can even try to run them.
I didnt 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 task.py:
def main(): print "Auth:“ auth = raw_input() if hashlib.sha1(auth).hexdigest() != "375d5c01ca1b8c3863024d10aac7713472eb5033": #Available link for download
