Mon, Jul 05, 21
Welcome back to my walkthrough of hackthissite.org’s CTF missions. I will be going through my thought process of how I solved these missions, and therefore also giving away the solutions. If you came across this to give you hints, watch out for spoilers! Good luck, have fun.
This mission gives us 120 seconds to return the last serial number that has been encrypted using the shown PHP script.
The code snip below is the source code that I wrote to complete this challenge, written in python. Writing this code was a lot of fun and I would greatly suggest any reader to try and complete this mission for themselves. I decided to take a greedy approach using recursion in order to find the solution - as it was the approach that made the most sense to me. There is a more ‘naive’ way that one could complete this mission, and that is to try and compute all permutations of an MD5 hash and attempt to decrypt the ciphertext with each permutation. This is ‘naive’ as it is not the most optimal solution and would take a considerable more time in order to complete. The code is well commented and is hopefully self-explanitory in what it does.
import hashlib
serialChars = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J",
"K", "L", "M", "N", "O", "P", "Q", "R", "S", "T",
"U", "V", "W", "X", "Y", "Z", "0", "1", "2", "3",
"4", "5", "6", "7", "8", "9"]
hexChars = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f"]
def getEncrypted():
"""
Extracts ciphertext from a file to a list of ints.
"""
with open("cipher.txt", 'r') as f:
cipher = f.readlines()
cipherList = cipher[0].split(" ")
encryptedChars = list(map(int, cipherList))
return encryptedChars
def MD5Hash(string):
"""
Computes the MD5 hash of a given string
"""
hashedVal = hashlib.md5(string.encode())
return hashedVal.hexdigest()
def evalCrossTotal(string):
"""
Computes sum of a MD5 hash.
"""
intTotal = 0
for char in string:
intTotal += int(char, base=16)
return intTotal
def checkSpecialChar(linepos, char):
"""
Checks whether the given char, and it's position in a line of plaintext, is a special
character that we expect to have within the plaintext.
"""
res = False
rem = linepos % 20
if (rem in [3, 7, 11, 15] and char == '-'):
res = True
elif (rem == 8 and char == 'O'):
res = True
elif (rem == 9 and char == 'E'):
res = True
elif (rem == 10 and char == 'M'):
res = True
elif (rem in [16, 18] and char == '1'):
res = True
elif (rem == 17 and char == '.'):
res = True
elif (rem == 19 and char == '\n'):
res = True
return res
def checkNormalChars(linepos, char):
"""
Return True if current linepos is for a normal char and it is a valid char.
Else Return False
"""
isInNormalCharPos = (linepos % 20) in [0, 1, 2, 4, 5, 6, 12, 13, 14]
isNormalChar = char in serialChars
res = True if (isInNormalCharPos and isNormalChar) else False
return res
def checkChrVal(chrVal, linepos):
"""
Checks whether a given int, it could be a
"""
res = False
if (chrVal >= 0 and chrVal <= 1114112):
res = True
plaintext = chr(chrVal)
if (not checkSpecialChar(linepos, plaintext)):
if (not checkNormalChars(linepos, plaintext)):
res = False
return res
def crackPassword(cipher, intMD5Total = None, MD5pass = None, plaintext="", i=0, linepos=0):
"""
Cracks the MD5 hashed password in a recursive fashion.
Assumes a starting value for the plaintext, with a starting value for the MD5 hashed
password and attempts to see if such a combination is possible.
Once all 32 chars of the hashed password have been cracked, attempts to decrypt the
rest of the ciphertext with the found hashed MD5 password value. There is a possibility
that it may not decrypt correctly, thus it will continue looking for another valid
MD5 hash.
"""
# attempting to crack the MD5 hashed password value
if (i < 32):
# if @ first entry, we permute amongst possible first plaintext & MD5pass characters
if (i == 0):
for char in serialChars:
for hexChar in hexChars:
# calculate starting intMD5Total & second intMD5Total
intMD5TotalStart = ord(char) + int(hexChar, base=16) - cipher[i]
intMD5Total = evalCrossTotal(MD5Hash(char)[:16] + MD5Hash(str(intMD5TotalStart))[:16])
# evaluate this permutation branch
res = crackPassword(cipher, intMD5Total, hexChar, char, i + 1, (linepos + 1) % 20)
if (res["status"] == 0):
# if we have found decrypted, terminate the code
return res
# if we have not found any valid decryption, then something has went wrong
return {"status": 1}
# we are in a permutation branch, we keep branching off for any valid decrypted plaintext
else:
for hexChar in hexChars:
chrVal = intMD5Total + cipher[i] - int(hexChar, base=16)
if (not checkChrVal(chrVal, linepos)):
continue
plaintextTemp = plaintext + chr(chrVal)
# at this point we know that for this branch, we have a valid plaintext, keep going further
intMD5TotalTemp = evalCrossTotal(MD5Hash(plaintextTemp[:i+1])[:16] + MD5Hash(str(intMD5Total))[:16])
res = crackPassword(cipher, intMD5TotalTemp, MD5pass + hexChar, plaintextTemp, i + 1, (linepos + 1) % 20)
if (res["status"] == 0):
# if we have found decrypted, terminate the code
return res
# if we have not found any valid decryption, then something has went wrong
return {"status": 1}
# we have a valid complete MD5 hashed password value, need to test it against rest of ciphertext
else:
res = decrypt(cipher, MD5pass, plaintext, linepos, intMD5Total)
return res
def decrypt(cipher, MD5pass, plaintext, linepos, intMD5Total):
"""
Attempts to decrypt the rest of the ciphertext given the cracked MD5 hashed password value.
There is a possibility that this cracked value will not result with a valid decryption, so
we must not assume that once a cracked value has been found, thus we must check our values.
"""
for i in range(32, len(cipher)):
chrVal = cipher[i] + intMD5Total - int(MD5pass[i % 32], base=16)
if (not checkChrVal(chrVal, linepos)):
return {"status": 1}
plaintext += chr(chrVal)
intMD5Total = evalCrossTotal(MD5Hash(plaintext[:i+1])[:16] + MD5Hash(str(intMD5Total))[:16])
linepos = (linepos + 1) % 20
return {"status": 0,
"plaintext": plaintext,
"MD5pass": MD5pass}
if __name__ == "__main__":
# retrieve stored ciphertext
cipher = getEncrypted()
# try to crack ciphertext
res = crackPassword(cipher)
# handle result of cracking
if (res["status"] == 0):
print(res["plaintext"])
else:
print("Something went wrong")