Category: Reversing Points: 200 Solves: 29 Description:
Find valid credentials for the registration server keycheck running on
challs.campctf.ccc.ac 10114
Running this program, we get:
$ ./keycheck
Enter username: User
Enter key: Password
Registration data invalid.
As the title suggests, the goal is to find a username and key that will allow successful registration. Running strings on the binary doesn't tell us too much, but does show a reference to python2. Let's ease our way into this problem by using ltrace to show what libraries and system calls are performed.
$ ltrace -C -n 5 -s 2048 -S ./keycheck
SYS_brk(0) = 0x2454000
SYS_access("/etc/ld.so.nohwcap", 00) = -2
SYS_mmap(0, 8192, 3, 34) = 0x7f7dc4004000
SYS_access("/etc/ld.so.preload", 04) = -2
SYS_open("/etc/ld.so.cache", 524288, 01) = 3
SYS_fstat(3, 0x7ffe3a8ab060) = 0
SYS_mmap(0, 0x212a8, 1, 2) = 0x7f7dc3fe2000
SYS_close(3) = 0
SYS_access("/etc/ld.so.nohwcap", 00) = -2
SYS_open("/lib/x86_64-linux-gnu/libc.so.6", 524288, 030400100610) = 3
SYS_read(3, "\177ELF\002\001\001\003", 832) = 832
SYS_fstat(3, 0x7ffe3a8ab0a0) = 0
SYS_mmap(0, 0x3c9f00, 5, 2050) = 0x7f7dc3a19000
SYS_mprotect(0x7f7dc3bd9000, 2097152, 0) = 0
SYS_mmap(0x7f7dc3dd9000, 0x6000, 3, 2066) = 0x7f7dc3dd9000
SYS_mmap(0x7f7dc3ddf000, 0x3f00, 3, 50) = 0x7f7dc3ddf000
SYS_close(3) = 0
SYS_mmap(0, 4096, 3, 34) = 0x7f7dc3fe1000
SYS_mmap(0, 4096, 3, 34) = 0x7f7dc3fe0000
SYS_mmap(0, 4096, 3, 34) = 0x7f7dc3fdf000
SYS_arch_prctl(4098, 0x7f7dc3fe0700, 0x7f7dc3fdf010, 34) = 0
SYS_mprotect(0x7f7dc3dd9000, 16384, 1) = 0
SYS_mprotect(0x7f7dc4006000, 4096, 1) = 0
SYS_munmap(0x7f7dc3fe2000, 135848) = 0
__libc_start_main(0x400820, 1, 0x7ffe3a8ab9e8, 0x400a00 <unfinished ...>
setvbuf(0x7f7dc3dde740, 0, 2, 0) = 0
printf("Enter username: " <unfinished ...>
SYS_write(1, "Enter username: ", 16Enter username: ) = 16
<... printf resumed> ) = 16
getline(0x7ffe3a8ab8d8, 0x7ffe3a8ab8c8, 0x7f7dc3ddd980, -1 <unfinished ...>
SYS_brk(0) = 0x2454000
SYS_brk(0x2475000) = 0x2475000
SYS_fstat(0, 0x7ffe3a8ab730) = 0
SYS_mmap(0, 4096, 3, 34) = 0x7f7dc4003000
SYS_read(0Username
, "Username\n", 1024) = 9
<... getline resumed> ) = 9
printf("Enter key: " <unfinished ...>
SYS_write(1, "Enter key: ", 11Enter key: ) = 11
<... printf resumed> ) = 11
getline(0x7ffe3a8ab8d0, 0x7ffe3a8ab8c0, 0x7f7dc3ddd980, -1 <unfinished ...>
SYS_read(0Password
, "Password\n", 1024) = 9
<... getline resumed> ) = 9
pipe(0x7ffe3a8ab8e4 <unfinished ...>
SYS_pipe(0x7ffe3a8ab8e4, 0x7f7dc3ddf980, 9, 245) = 0
<... pipe resumed> ) = 0
fork( <unfinished ...>
SYS_clone(0x1200011, 0, 0, 0x7f7dc3fe09d0) = 3310
<... fork resumed> ) = 3310
close(3 <unfinished ...>
SYS_close(3) = 0
<... close resumed> ) = 0
write(4, "#!/usr/bin/python\n\nimport argparse\nimport hashlib\nimport sys\nfrom Crypto.PublicKey import RSA\n\ntry:\n FLAG = open("flag.txt").read().strip()\nexcept:\n FLAG = "CAMP15_DUMMY_FLAG"\n\n\npubkey = """-----BEGIN PUBLIC KEY-----\nMCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRALSMJB2tLS9JUsjztc0Q1vkCAwEAAQ==\n-----END PUBLIC KEY-----\n"""\n\n\ndef bad_reg_data():\n print "Registration data invalid."\n sys.exit(-1)\n\ndef main(reg_user, reg_key):\n try:\n reg_key = reg_key.decode("base64")\n except:\n bad_reg_data()\n\n ist_md5 = hashlib.md5(reg_user).hexdigest()[0:23] + "0"\n pubrsa = RSA.importKey(pubkey)\n\n try:\n soll_md5 = pubrsa.encrypt(reg_key, None)[0]\n soll_md5 = soll_md5.encode("hex")[0:23] + "0"\n except:\n bad_reg_data()\n\n if soll_md5 == ist_md5:\n print "Registration completed successfully."\n print "Here is your flag: {0}".format(FLAG)\n else:\n bad_reg_data()\n\nif __name__ == "__main__":\n parser = argparse.ArgumentParser()\n parser.add_argument("user")\n parser.add_argument("key")\n args = parser.parse_args()\n\n main(args.user, args.key)\n", 1118 <unfinished ...>
SYS_write(4, "#!/usr/bin/python\n\nimport argparse\nimport hashlib\nimport sys\nfrom Crypto.PublicKey import RSA\n\ntry:\n FLAG = open("flag.txt").read().strip()\nexcept:\n FLAG = "CAMP15_DUMMY_FLAG"\n\n\npubkey = """-----BEGIN PUBLIC KEY-----\nMCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRALSMJB2tLS9JUsjztc0Q1vkCAwEAAQ==\n-----END PUBLIC KEY-----\n"""\n\n\ndef bad_reg_data():\n print "Registration data invalid."\n sys.exit(-1)\n\ndef main(reg_user, reg_key):\n try:\n reg_key = reg_key.decode("base64")\n except:\n bad_reg_data()\n\n ist_md5 = hashlib.md5(reg_user).hexdigest()[0:23] + "0"\n pubrsa = RSA.importKey(pubkey)\n\n try:\n soll_md5 = pubrsa.encrypt(reg_key, None)[0]\n soll_md5 = soll_md5.encode("hex")[0:23] + "0"\n except:\n bad_reg_data()\n\n if soll_md5 == ist_md5:\n print "Registration completed successfully."\n print "Here is your flag: {0}".format(FLAG)\n else:\n bad_reg_data()\n\nif __name__ == "__main__":\n parser = argparse.ArgumentParser()\n parser.add_argument("user")\n parser.add_argument("key")\n args = parser.parse_args()\n\n main(args.user, args.key)\n", 1118) = 1118
<... write resumed> ) = 1118
close(4 <unfinished ...>
SYS_close(4) = 0
<... close resumed> ) = 0
waitpid(3310, 0, 0 <unfinished ...>
SYS_wait4(3310, 0, 0, 0Registration data invalid.
) = 3310
--- SIGCHLD (Child exited) ---
<... waitpid resumed> ) = 3310
SYS_exit_group(0 <no return ...>
+++ exited (status 0) +++
As you can see, the binary appears to unpack a python script, write it to disk, then execute it. To clean things up, here's the script:
#!/usr/bin/python
import argparse
import hashlib
import sys
from Crypto.PublicKey import RSA
try:
FLAG = open("flag.txt").read().strip()
except:
FLAG = "CAMP15_DUMMY_FLAG"
pubkey = """-----BEGIN PUBLIC KEY-----
MCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRALSMJB2tLS9JUsjztc0Q1vkCAwEAAQ==
-----END PUBLIC KEY-----
"""
def bad_reg_data():
print "Registration data invalid."
sys.exit(-1)
def main(reg_user, reg_key):
try:
reg_key = reg_key.decode("base64")
except:
bad_reg_data()
ist_md5 = hashlib.md5(reg_user).hexdigest()[0:23] + "0"
pubrsa = RSA.importKey(pubkey)
try:
soll_md5 = pubrsa.encrypt(reg_key, None)[0]
soll_md5 = soll_md5.encode("hex")[0:23] + "0"
except:
bad_reg_data()
if soll_md5 == ist_md5:
print "Registration completed successfully."
print "Here is your flag: {0}".format(FLAG)
else:
bad_reg_data()
if __name__ == "__main__":
parser = argparse.ArgumentParser()
parser.add_argument("user")
parser.add_argument("key")
args = parser.parse_args()
main(args.user, args.key)
It takes in two arguments (user and key) and performs two different computations on them. The user variable gets hashed with md5 and truncated at 24 bytes. The key variable gets base64 decoded, and then encrypted using the RSA public key that is located inside the script. It also get hex encoded and truncated at 24 bytes. Finally, the two values are compared and if match, you get the key.
Interestingly, there are a couple ways to go about this challenge:
MD5 Preimage Collision
You could try to find a preimage collision of md5 based on known and deterministic output of the RSA encryption. Because md5 has been a well known problem for a while, programs like HashCat may help speed things up. You also might be able to find a preimage in an md5 database online somewhere. The problem here is you're directly fighting what md5 is supposed to be doing, which among other things is providing preimage collision resistance.
Birthday Attack
The ever loved birthday attack. The birthday attack is so-named because of the surprising number of times you will find someone with the same birthday as someone else in the class. The concept will also work in this situation as we don't need to match a given hash/rsa combination, rather just find any match. An example of how this would work is:
#!/usr/bin/python2
import argparse
import hashlib
import sys
import string
import random
from Crypto.PublicKey import RSA
pubkey = """-----BEGIN PUBLIC KEY-----
MCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRALSMJB2tLS9JUsjztc0Q1vkCAwEAAQ==
-----END PUBLIC KEY-----
"""
pubrsa = RSA.importKey(pubkey)
def randomString(N):
return ''.join(random.choice(string.printable) for _ in range(N))
def makeHash(user):
return hashlib.md5(user).hexdigest()[0:23] + "0"
def makeSoll(key):
soll_md5 = pubrsa.encrypt(key, None)[0]
return soll_md5.encode("hex")[0:23] + "0"
userHash = []
user = []
keyRSA = []
key = []
while True:
# Generate two random strings
user.append(randomString(10))
key.append(randomString(10))
# Generate output
userHash.append(makeHash(user[-1]))
keyRSA.append(makeSoll(key[-1]))
collision = [x for x in userHash if x in keyRSA]
if len(collision) > 0:
print("It's my birthday!\n\tUser: {0}\n\tKey: {1}".format(user[userHash.index(collision[0])],key[keyRSA.index(collision[0])].encode("base64")))
break
There are numerous ways to speed up the above code. It's possible you'll get lucky, but due to the search space it's still pretty unlikely you'll stumble upon the answer.
Reverse RSA Key
Reversing the RSA key is the solution I ended up going with. In most cases, reversing the key would be computationally infeasible, as is the purpose of public key encryption. That said, lets look at the size of this key:
>>> from Crypto.PublicKey import RSA
>>> pubkey = """-----BEGIN PUBLIC KEY-----
... MCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRALSMJB2tLS9JUsjztc0Q1vkCAwEAAQ==
... -----END PUBLIC KEY-----
... """
>>>
>>> pubrsa = RSA.importKey(pubkey)
>>> pubrsa
<_RSAobj @0x7faa36d6b998 n(128),e>
As you can see, this key is only 128 bits in size. The bare minimum most crypto applications will even allow is 512 while most users are being pushed to 2048 or higher. This means cracking this RSA key should certainly be feasible. You can attempt to factorize it yourself, the success of which will likely have to do with your home computing power (or luck if you try a random algorithm). However, it turns out that there already exists a site dedicated to storing number factorizations.
You can grab the actual n value using pycrypto as follows:
>>> pubrsa.n
239988693319437709029258245775352190713L
Now that we know the value, we can simply plug it into the site and we get out the p and q values (15448096144646045267, 15535163108278055939). From here, we can create the private key used to work backwards from our known hash. Creating this key is something that isn't terribly well documented, and also usually asks for manual steps that can and should be automated. To ease that problem, I've created a simple script that will take in a p,q and optionally e value, and output the private key in pem format. Also, due to the nature of how private key pem/der files work, that file can be used for the public key as well.
https://github.com/Owlz/CTF/blob/master/helpers/generate_rsa_private_key.py
$ ./generate_rsa_private_key.py -h
usage: generate_rsa_private_key.py [-h] p q [e]
Create private RSA key from primes. Export in PEM format.
positional arguments:
p First RSA Prime
q Second RSA Prime
e Optional: Public Exponent (Default: 65537)
optional arguments:
-h, --help show this help message and exit
$ ./generate_rsa_private_key.py 15448096144646045267 15535163108278055939
-----BEGIN RSA PRIVATE KEY-----
MGICAQACEQC0jCQdrS0vSVLI87XNENb5AgMBAAECECz2bZQaaZNJs0hRV3QLe6UCCQDWYqmYlbV+
UwIJANeX/InEqrQDAghodaiHdaL6iwIJAIANiDQUGggdAghwem/NWYULog==
-----END RSA PRIVATE KEY-----
Now we simply load up that new key, select a user name we would like a key for, and create the key.
>>> privkey = """-----BEGIN RSA PRIVATE KEY-----
... MGICAQACEQC0jCQdrS0vSVLI87XNENb5AgMBAAECECz2bZQaaZNJs0hRV3QLe6UCCQDWYqmYlbV+
... UwIJANeX/InEqrQDAghodaiHdaL6iwIJAIANiDQUGggdAghwem/NWYULog==
... -----END RSA PRIVATE KEY-----
... """
>>> privrsa = RSA.importKey(privkey)
>>> import hashlib
>>> privrsa.decrypt(hashlib.md5("User").digest()).encode("base64")
'hVLJDW7J1w3FCA6Cc9CBqQ==\n'
Time to grab the flag:
$ nc challs.campctf.ccc.ac 10114
Enter username: User
Enter key: hVLJDW7J1w3FCA6Cc9CBqQ==
Registration completed successfully.
Here is your flag: CAMP15_dc71d59e50c5fc4cd7604db75da16de8
Flag: CAMP15_dc71d59e50c5fc4cd7604db75da16de8