HackTheBox – Brainy’s Cipher

In this write-up we will be visiting theĀ Brainy’s Cipher challenge from HackTheBox.

Brainy likes playing around with esoteric programming. He also likes math and has therefore encrypted his very secure password with a popular encryption algorithm. Claiming that his password cannot be retrieved now, he has sent the ciphertext to some of his friends. Can you prove to Brainy that his password can actually be recovered?


We are given a file with the following contents.

++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>>+++++++++++++++++++++++.-----------.<------------.---.++.---------.+.++.-.++.+.-----.++..++++.--.++++.+..-------.+.+++.---.+.+++++.-------.+.---.+++++++.+.-------..+++.-.+++++.-------.++.+++++.-----.+++++..-----.--.++++++++.-------.--.++++.+++.---.++..+++.------.+++.--.-..++++++.-.----..+++++.------.++++++.---.---.--.+++.++++.-------.+++++..-.++..-------.++++++.---.++..+++.----.++++.-------.++++++++..----.+++.+.------.--.-.++.-.+++++.--..--.++++.-.++++.---.------.+++++.++.+.---.+++.---.----.++++.--.+++.-----.+++++.+.---.--.+++++++.---.---...---.+.++++++++.----.++++.-----.++.--.-.--.++.-.-.+++++.--..+++++.-------.-.++++.++.-----.++++++.--------.+++.+++.-.+++.----.----.++++++.----.++++++.-------.-----.>+.<++++++++++++++.---------.+.++++++.--------.++.+++++++.--------.+++++++.----.+.----.+++...----.++++..++.----..+++.+++.-----.++++.--.++..-------.+++.++++.--.---.--.++++++..-----..+++++++.-------.+++++++.--------..++++++.++.--..++.----.+++.++.------.++++.+.-..+.+.-------.++++++.-.---.---.-.++++++++..-----.---.++.+.++..-.--.+++.++++.--..------.++++++++.-------.+++++++..---.+.++..---.----.+.++++++..-.-.-----.--.++++.--.+++++++.----.++++.-----.-.+.++.+..+..--.-.---.+++++.--.--.++++++.--------.++.---.+++++++..----.---.+++++++++.-...-------.++++++++.-------.++.-.+++++.----.-.+++++.---.----.+++++.++.-----.---.+++++++.++.---------...++.+++++++.------.+++++.-------.++++.-----.+++++.----.-----.>-------------.++++++++++++.<++++++++++++++.-----..-.----.++++++.-..-----.++.++++++.--.----..--.++.-.++++++++.------.+..--.+++++++.------.---.++++++.----.++++++.-.++.------.++++...--.---.+++++++.--------.++++++++.----..+.----.+..---.++++++++.+.---.-.---.--.++++++++.-----.+++++.----.+.+++.------.--..+++++++++.-.---.++.----.++++.-.------.+++++.--.++.+++.-----.++.++.--..----.-.+++++++.+.----.---.+++++.+++.---.-----.+++++.------.++++++.-.----..++.+++.--.---.++.++++++.--------..+++++.+++.---.-----.++.++++++.---.+++.-.-------.++.+++.-.---.+++.---.+.++.-----.+++++++.---.--.-..++++.++.-------.++++.+.--.++++..+.+.-.---.-.--.+.+++++.--.+++.------..--.++++++++.-.------.++++.+++.-----.+.----.-----.>------------.+++++++++++++.<++++++++++++++.-.---------.++++++..++.+.--.----.-.--.+++.---.++++++++..-----.+.--.--.++++++.+++.----.---.+.++.++++.------.++++++..--.----.++++..---.+++.----.--..++++++++.-.-----..---.+++++++++.---------.++++++.----.+++++.-.--.---.++++++.+.+.---------.++++++.----.++++.+++.-----.+++.--.+++.----.+++.------.++++++.----.++++++.---..------.+++++++.----.++.+.+.++.-..-------.++++++.-------.++++.---.++++.+++.-----.++++++..----.-.+++++..---.---.-..+.--.+++.---.++++.++.---.-.+++++.-..-------.++..+++.++++.----.---.++.+++++.--------.++++.+.------..+++++.---.++++++.-.------.+++.++.--.---.++.+++.-----.+++++.---.+.--.-.+++++++.+.-------.--.+++++.-----..+++++.++.---.+++++.-.--.-.----.-----.>--------------.<++++++++++++++.----.----.--.+++++++.+.--------.++++++++.--..+..---.---.+++++..++.--.++.--.+.------.+++++++.-----.+++++.---.++.++.----.++.----.++.-----.+++..+++++.-----.--.+++...++.----.++++++.--------.+++++++++.--------.+.++++.+.----..++++++.-------.++..++++.--------.++++++.-.-----.++.++++.++.---.-----.++.-.+.++++.++.---.--.-.++++.-..----..+++++++.-----.++++++.---.----.--.+++++.+.--.+++++.----.++++.---.--.+.++.++.--.+.------.+.-.+++.--.---.++.--.++++++++.------.--.+++++.-.-.++++++.------.++++++.------..+++.++.------..++++.-.++..-----.++++++.--------.++.+++++.--.-----.++++++++..-.-----.+++++++.------.+++.------.++.++.-.-.+++.----.+.+++++++.---.+.++..-----.++++.--------.+++++..-.+++++..---.-.-----.++.--.+++++++++.--------.+++++.+++.----.--.+++.--..++.---.++.++++.---.-.++++.--------.+++++..------.+++++++.++.-------.+++.--..++.+.---.++++++.---------.++.+++++.--.++.++.--------.+++++++.-.---.-.++.----.+++++++.--------.++++++.------.+++++++.---.+++.--.++++.---.---..-..++.++.-.-.---.++++++..--.+++.+.----.++++.---------..++.+.+++++.---.-.+.----.+++++++.--.---.--.+..-.-.++++++.--.++++.-.+.-----.+.+++.+.----.++.++..--------.++.+++++++.--------.+++++.+..-----.--.+.++++++.--.----.+.++++++.--------.++++++++.------.--.++++++...+.-------.+++++++++.-----.+.+.----.+++.-----.++++++.+.+.--------.+++.+++++.-------.+.+++++++.--.-------.++++++++.-.------.>++++++++++++++++++++++++++.

Looking at the contents of the file, it becomes obvious that we are looking at code from the esoteric programming language, Brainfuck. We can decode the contents of the file using a Brainfuck interpreter such as the one from dcode.fr.

Upon decoding the Brainfuck code, we obtain the following data.

{p:7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281,q:12802918451444044622583757703752066118180068668479378778928741088302355425977192996799623998720429594346778865275391307730988819243843851683079000293815051,dp:5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451,dq:9066897320308834206952359399737747311983309062764178906269475847173966073567988170415839954996322314157438770225952491560052871464136163421892050057498651,c:62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871}

Looking at the contents of the data, it contains 5 variables, p, q, dp, dq and c. Going by the p and the q we can assume that these are RSA variables, in which case the c could be our ciphertext. However, the dp and dq are not part of the standard RSA scheme. Some googling tells us that these variables are part of the private key and that they are used for RSA decryption when using the Chinese Remainder Theorem as a decryption performance optimization. In case you are interested in further information about how the Chinese Remainder Theorem is used in RSA decryption, please check out the following links.

The Chinese Remainder Theorem in itself is somewhat advanced and you do not need to actually understand it in order to solve the challenge. The RSA decryption mechanism using the Chinese Remainder Theorem is as follows.


RSA decryption using the Chinese Remainder Theorem

  • The private key contains optimization variables
    • d_p = d\ mod\ (p - 1)
    • d_q = d\ mod\ (q - 1)
    • q_{inv} = q^{-1}\ mod\ p
  • We compute the decrypted message m
    • m_1 = c^{d_p}\ mod\ p
    • m_2 = c^{d_q}\ mod\ q
    • h = (q_{inv} \times (m_1 - m_2))\ mod\ p
    • m = m_2 + (h \times q)\ mod\ (p \times q)

We can build a script to perform these steps for us. The final script should look as follows.

p = 7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281
q = 12802918451444044622583757703752066118180068668479378778928741088302355425977192996799623998720429594346778865275391307730988819243843851683079000293815051

dp = 5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451
dq = 9066897320308834206952359399737747311983309062764178906269475847173966073567988170415839954996322314157438770225952491560052871464136163421892050057498651

c = 62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871

qi = (1/q) % p

m1 = pow(c, dp, p)
m2 = pow(c, dq, q)

h = (qi * (m1 - m2)) % p
m = (m2 + (h * q)) % (p * q)

print ("%x" % m).decode('hex')

We can now run our script to decode the ciphertext.

And there you have it – the challenge has been solved!

Leave a Reply