Category: Cryptography, Steganography
You can download the Cryptography Challenge, along with all the challenges for the 2016 Greek Qualifier CTF of European Cybersecurity Challenge, in this link. More details on the Greek ECSC 2016 Qualifier CTF event can be found here.
Points: 80
Challenge designer: Gavrila
Description: > A matryoshka doll, also known as a Russian nesting doll, or Russian doll, refers to a set of wooden dolls of decreasing size placed one inside another. The name “matryoshka” (матрёшка), literally “little matron”, is a diminutive dorm of Russian female first name “Matryona” (Матрёна) or “Matriosha”. The first Russian nested doll set was made in 1890 by Vasily Zvyozdochkin from a design by Sergey Malyutin, who was a folk crafts painter at Abramtsevo.
Write-up
Phase 1
We are given a PNG image with the following text.
The image is referencing the XOR cipher.
The key is equal to the value of the Fibonacci function with input 2016.
def fibonacci(n):
a, b = 1, 1
for i in range(n-1):
a, b = b, a+b
return a
c = "56444e29da2ce23f0182943154ea69dcb5dc324cb596730ffc957729dd8f20271fa94a872c8b6c760490" \
"b7ae5b47cffae2218e206c98483e6e16ae3080cf123dbfb9d7ec347a974b5d2fe2f0cef1919a31f1721d" \
"28b3ba74a0715be354c79b86e03d328c87b69b8172f0827d054aec4b3b0ab7fad81bbefdb0de33d21a368" \
"c3191fb3f2f8b472e4b2788d32d3a658f208d28a358b462ced10f3636d9d6563e59a47fa3be4451f5c099" \
"903f180a80ae"
k = fibonacci(2016)
k = '%x' % k
print 'key: ', k
m = int(c,16) ^ int(k,16)
m ='%x' % m
print "Your message is: ", m.decode('hex')❯❯❯ python Phase1.py
key: 56444e29da2ce23f0182943154ea69dcb5dc324cb596730ffc957729dd8f20271fa94a872c8b6c760490b7ae5b47cffae2218e206c98483e6e16ae3080cf123dbfb9d7ec347a974b5d2fe2f0cef1919a31f1721d28b3ba74a0715be354c79b86e03d328c87b69b8172f0827d054aec4b3b0ab7fad81bbefdb0de75be7b51ac00b1d61f68e4674a2e42f8b65f1645eb45e858c62a9842aab46a4653abfa765a3cc10fc6cc687191a5fce05a6a24ae80
Your message is: Flag 1 - Go deeper, deeper, deeper, deeper, deeper...The 1st flag is: > Flag 1 – Go deeper, deeper, deeper, deeper, deeper…
Phase 2
In the PNG file we discover the following string:
❯❯❯ strings CryptoChallenge-BSidesAthens.png | grep -i xor ⏎
XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XOR ME XORSo, we proceed by XORing the file with the cryptographic key discovered in Phase 1.
key = "56444e29da2ce23f0182943154ea69dcb5dc324cb596730ffc957729dd8f20271" \
"fa94a872c8b6c760490b7ae5b47cffae2218e206c98483e6e16ae3080cf123dbfb" \
"9d7ec347a974b5d2fe2f0cef1919a31f1721d28b3ba74a0715be354c79b86e03d3" \
"28c87b69b8172f0827d054aec4b3b0ab7fad81bbefdb0de75be7b51ac00b1d61f" \
"68e4674a2e42f8b65f1645eb45e858c62a9842aab46a4653abfa765a3cc10fc6c" \
"c687191a5fce05a6a24ae80"
f = open("CryptoChallenge-BSidesAthens.png",'rb')
data = f.read()
f.close()
decoded = ""
key = key.decode('hex')
for i in range(0, len(data)):
decoded += chr(ord(data[i]) ^ ord(key[i % len(key)]))
f = open('data.out','wb')
f.write(decoded)
f.close()❯❯❯ python Phase2.py
❯❯❯ strings data.out | grep -i flag
Flag 3 - Not deep enough.txteR
Flag 3 - Not deep enough.txtPK
Flag 2 - Go even deeper.txt
Flag 2 - Go even deeper.txtThe 2nd flag is: > Flag 2 – Go even deeper
Phase 3
❯❯❯ for i in $(strings data.zip| grep deeper | grep zip | \
awk -F'.' '{print $1}' | sed -e 's/deeper//g' | sort -rnu); do \
[ -f deeper${i}.zip ] && unzip deeper${i}.zip; \
done❯❯❯ unzip DeepEnough.zip
Archive: DeepEnough.zip
extracting: BsidesAthens.zip.AES
inflating: Flag 3 - Not deep enough.txt
inflating: keyring.sec
inflating: message0.enc
inflating: message1.enc
inflating: message2.enc
inflating: secure-message.py
❯❯❯ cat "Flag 3 - Not deep enough.txt"
'''
It took some great skills to reach this point! Congratulations!
Your next challenge will require a bit more effort.
Your objective is to decrypt the archive "BsidesAthens.zip.AES".
The password is long and the algorithm used is AES,
so if you are thinking about brute force, well..., it might
take a very, very, very, very long time.
But there is still hope. The password has been shared "securely"
by the author with three of the organisers and luckily you have
access to all three messages.
You have access to the code used to create the messages.
Maybe you will find some creative way to recover the password.
Good luck, you are almost there! ;)
IMPORTANT NOTE: if you run the script you may erase the original
messages, so it might be a good idea to keep a back-up.
'''The 3rd flag is: > Flag 3 – Not deep enough
Phase 4
After checking the encryption code we can see that the encryption system used is RSA. The keyring stores the public key of three organisers and we can see that in all three cases the public coefficient is e = 3.
Since we have their public keys, the encrypted messages and a small public coefficient we can extract the message by using the Chinese Remainder Theorem
"""
Code provided by Gavrila
"""
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b%a, a)
return (g, x-(b//a)*y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
print("The selected value has no inverse.")
else:
return x % m
def CRT(n, a, lena):
p = i = prod = 1; sm = 0
for i in range(lena): prod *= n[i]
for i in range(lena):
p = prod // n[i]
sm += a[i] * modinv(p, n[i]) * p
return sm % prod
def invpow(x,n):
high = 1
while high ** n < x:
high *= 2
low = high/2
while low < high:
mid = (low + high) // 2 + 1
if low < mid and mid**n < x:
low = mid
elif high > mid and mid**n > x:
high = mid
else:
return mid
return mid + 1
pk1=0xb292089cde4f37b0736252371552546e02d39d9f0ad0ae39815d4104132f0b332b525024d8a743c9b675f21238e602a754ae416d76d7dd9b724f34f778e11f6fc9b54214cb4297d1053a48129175dd526ca506ef29b1b9e85d3273605c9ab94cec387ca80674706eda8e1c195f979b6aa020379bc4b6fe62a6d540ba377a11a9
pk2=0xd0ab2e0e7e7dd2f67611a116691c545004f5d701ad106f796f8e4c2d3a1adfdff9cd698d5199b70b5d760f079532b8d23a1a84ed2274c6a7645df2fd5c0f21ba28a3f5859716cc032af0d56087912a82c620a7431767d55768592e090904bf8fa566980b579fcb36431ef736a43086126eb509f8b9614db86540713eb7b494b5
pk3=0xd745072c2055ee0fd2b0a09d2a0251e317c2dafdfbb10c86aa6507d70d53b440ac08271e919a521a4861e0b0ce49a1d591f9bbe49d2d697305639bfbafb7f40adf09c7bf9a82ef5c3a447ea96abc42ba5760e08e3b50ef061bec83684cc4d13d3da9296c450369a577dc6656d38005edf55985ecd7805baaa393dbd885078653
m0=0x96bc126341297a2a2d1861cd649bde1cedc1b6e85223d6946c759da2a04b44d97b7ef01881063c7a1342ed26f5527456f5cf1208c3f7d088f519fa11a9c498b6448a0de709f23380664418773a18e4d37234ad740ae4468e188b0aede0bf586aff4e76695bff5619b2fb701fd417ce0909970de41b4b004317eeb6f7deadf9bc
m1=0x6e6a7fc2c3f398c55820fa3f160121cee6ceeb3f2bd43b7ef28056cd85b29305d313b40a7fd7d33e8646e6302cdfbf857692902c806ba08bd3f9cd1586a976999c74932e910ba496a1da4a0287743c52cbba4e9a59c6cc3d3d91465dd7337ffae6879cade77f907a60acb947173a503f63d5ff32af0c4378fab3bdf083c4c7c3
m2=0x51b03f33c34963f49af063b7022abdde38f69b06b5cc25556893088ee6f46fe5b9ad54d09a3a4ac94b64a3e0a98eda69de4f21e787dcf4e3e3249b1ac283dc43fc9584f97606ee0a43b0d213cc845e7adfcccf884a52c4f85361dc13d6b1492200b59f385c44cb1427d9c92a2f9b5b4c2c5874b4dfc3983b9bdcf1622d619480
n = [pk1, pk2, pk3]
c = [m0, m1, m2]
plainPow3 = CRT(n, c, 3)
p = invpow(plainPow3, 3)
if p*p*p == plainPow3:
key = "%x" % p
print "Key used is: ", key❯❯❯ python Phase4-a.py
Key used is: 791809cb7b659d323733b3583cf491d9151ce599e978d9895fa8c749a243e1daafea37aa69baff2e2e165a1b6fd7c26589d42993127550ff3846660cb14d2fe2We get the following key: 0x791809cb7b659d323733b3583cf491d9151ce599e978d9895fa8c749a243e1daafea37aa69baff2e2e165a1b6fd7c26589d42993127550ff3846660cb14d2fe2.
Lets use the AES routine saved in the script to decrypt the file.
from Crypto.Cipher import AES
import hashlib
import os, random, struct
"""
Code provided by Gavrila
"""
def AESDecryptFile(key, in_filename, chunksize=24*1024):
out_filename = os.path.splitext(in_filename)[0]
with open(in_filename, 'rb') as infile:
origsize = struct.unpack('<Q', infile.read(struct.calcsize('Q')))[0]
iv = infile.read(16)
decryptor = AES.new(key, AES.MODE_CBC, iv)
with open(out_filename, 'wb') as outfile:
while True:
chunk = infile.read(chunksize)
if len(chunk) == 0:
break
outfile.write(decryptor.decrypt(chunk))
outfile.truncate(origsize)
password = 0x791809cb7b659d323733b3583cf491d9151ce599e978d9895fa8c749a243e1daafea37aa69baff2e2e165a1b6fd7c26589d42993127550ff3846660cb14d2fe2
m = hashlib.md5()
m.update(str("%x" %password))
AESkey128b = m.hexdigest()
AESDecryptFile(AESkey128b, 'BsidesAthens.zip.AES')❯❯❯ python Phase4-b.py
❯❯❯ unzip BsidesAthens.zip
Archive: BsidesAthens.zip
inflating: BsidesAthens.exe
inflating: Flag 4 - Almost there.txt
❯❯❯ cat "Flag 4 - Almost there.txt"
WOW! This is amazing!
You have reached your last challenge.
Find the password and you're done.
Good luck!The 4th flag is: > Flag 4 – Almost there
Phase 5
❯❯❯ file BsidesAthens.exe
BsidesAthens.exe: PE32 executable for MS Windows (console) Intel 80386 32-bitWe have a standard C++ binary
After checking the file with strings we can see there are some encoded looking ASCII strings.
Lets load the binary in a disassembler.
There is a conditional jump that checks if the password is correct or not.
Before that we can see a simple XOR routine.
The password is checked against XOR(“nbwqzlpkhb”, 3)
❯❯❯ python -c 'for c in "nbwqzlpkhb": print chr(ord(c)^3),' | sed -e 's/ //g'
matryoshkaC:\>BsidesAthens.exe
Please enter your key: matryoshka
Good job!
Flag 5 - Deep as it gets
You have amazing skills#,# but are you ready for a real challenge?
Maybe you should check: https://www.enisa.europa.eu/recruitment/vacancies
Press any key to continue ...The 5th flag is: > Flag 5 – Deep as it gets