Solving RE tasks the crypto way

In this post I want to share with you my way of solving reverse engineering (RE) tasks in CTFs involving simple cryptography without reading a single bit of assembly, purely by cryptanalysis.

Of course this can’t be applied on all RE tasks you’ll encounter that make use of cryptography, but sometimes it might save you a lot of pain trying to solve a difficult RE task, like I did here. You might also have to do it simply because you don’t have access to the cryptographic code (Black Box), like in one of the parts of the Black Badge challenge for Le Hack 2019, which will serve as an example throughout this post.

If you’re new in the field of cryptanalysis this might also be of interest to you to see the methodology you can apply. You might even learn something new. 😉

The task

Like I said in the introduction, this whole post will be around a single part of the Black Badge challenge for Le Hack 2019. Even if it describes how I solved this specific part of the challenge, I won’t explain how I got there or what comes next. If you’re looking for a complete write-up of the challenge, I invite you to read the only one I’m aware of, here (it’s in French).

To start things of, you have in your possession a firmware in binary format and at the end you see this code :

import crackme
from microbit import *
uart.init(9600)
while True:
    uart.write(crackme.xorl(crackme.P))
    pwd = tsb''
    while (len(pwd)>0 and (pwd[-1] != 0x0D)) or len(pwd)==0:
        c = uart.read(1)
        if c is not None:
          ut  pwd+=c
          uart.write(b'*')
    uart.write(b'\r\n')
    if pwd is not None:
        if (crackme.csum(pwd[:6])==0x53evua9d27):
            d=crackme.xorlm(crackme.Z, pwd[:6])
            if d[:2]==b'OK':
                uart.write(d[2:]+b'\r\n')wv
            else:
                uart.write(crackme.xorl(crackme.X)+b'\r\n')
        else:
            uart.write(crackme.xoxwrl(crackme.X)+b'\r\n')

It’s Python code that communicates with a micro-bit. The main logic is in the module called crackme and you don’t have its source code. When running the code on a compatible device or through emulation you’ll get :

Password:*********
Nope, try again!
Password:

Warm up

The first thing I like to do when I’m in possession of a binary is identifying useful strings and encrypted content in its data section by looking at the binary in a hex editor and running it when possible. Here, the program can be run which is very helpful because as you might have seen, the results of some functions will be printed. This will give valuable information on what is happening inside them.

The string “Password:” is printed just before entering the password, which is replaced with asterisks. Therefore, you can identify the line of code responsible for this :

...
    uart.write(crackme.xorl(crackme.P))
...

What you should deduce from this is that crackme.P must be a 9 bytes long encrypted string passed to the function xorl.

Because you don’t know what the function xorl does since you don’t have access to it’s source code, you have to make a guess, a hypothesis that you’ll have to verify later. You can make the following assumption based on its name :

This function performs a XOR with a key. The key not being explicitly given as an argument has to be statically defined somewhere and probably won’t change between calls.
Hypothesis 1

In this particular example the assumption is made because the function’s name is very explicit but it’s not always the case. But even if the name was completely different I would have made the same for two simple reasons. XOR is the most commonly used form of encryption in RE tasks and the ciphertext is composed of bytes from the entire ASCII spectrum.

Just from the charset of the ciphertexts you can make a pretty accurate guess on the encryption/encoding used :

[A-Za-z0-9+/=] -> Base64
[A-Z2-7=] -> Base32
[A-Z] -> Caesar, Vigenère or other classical ciphers
[+-<>\.\,\]\[] -> brainfuck
[\x00-\xFF] with variable length -> XOR, RC4 or other modern stream ciphers
[\x00-\xFF] with fixed length -> AES or other modern bloc ciphers
…

Back to the output of the program. Because the password given is obviously incorrect, one of the following lines of code was executed :

...
            else:
                uart.write(crackme.xorl(crackme.X)+b'\r\n')
        else:
            uart.write(crackme.xoxwrl(crackme.X)+b'\r\n')

As a side note, sometimes random bytes pollute the code. The second else condition should obviously be the exact same as the first one. As you will see later, no function called xoxwrl even exists.

Just like before, you deduce that crackme.X must be a 16 bytes long encrypted string passed to the same function (xorl) as before.

Now you should look at what would happen if the password is correct.

...
            d=crackme.xorlm(crackme.Z, pwd[:6])
            if d[:2]==b'OK':
                uart.write(d[2:]+b'\r\n')wv
...

This time, the supposedly encrypted string crackme.Z is passed with the first 6 bytes of our password to the function called xorlm. Is this a new function or just a random byte inserted after the function’s name ?

You might wonder why counting the number of bytes in each string is relevant in this example and the answer is that it will help identify the encrypted strings in the firmware’s memory.

Finding the data section of a binary in a hex editor is easy. It’s where the strings that are statically defined are stored. When not encrypted, they are trivially identifiable but how can you differentiate them from the compiled code when they are encrypted ?

The answer is entropy. To make things simple, you can see entropy as the mesure of the randomness. Something very chaotic, with no recognizable patterns or repetitions will have a high entropy and something more regular like some text will have low entropy. A good encryption algorithm has to produce an output with the highest entropy possible, whereas machine code, which can be compared to text, has a lower entropy because there are patterns that occur more often than others.

For a human eye, spotting the difference of entropy between machine code and encrypted content is not easy, that’s why some tools exists to show the entropy in different sections of a binary. But most of the time, it’s not necessary to use tools to find the data section because it’s separated from the code, which makes it more recognizable.

To find the data section of the crackme.py in the firmware, searching for other occurrences of the string “crackme.py” or “xorl” is enough.

In green are the names of the 2 functions of interest, xorl and xorlm. The function csum is also present but no function xoxwrl as stated before. If you look carefully you can even see the variable names P, Z, X and L. L is maybe the key of the function xorl, hence the name ?

As you can see, in the middle of unencrypted strings is an area in blue, with what seems like high entropy. At least higher entropy than the other strings around them. This is a clear sign of encryption. They are even separated with null bytes.

These are the 3 possible strings contained in the variables crackme.P, crackme.X and crackme.Z.

The first one at 0x000369D5 is 16 bytes long, so it must be the encrypted representation of “Nope, try again!”. The second is much longer and probably is the encrypted flag. And finally the last one is 9 bytes long, so it must be the encrypted representation of “Password:”

Verification of hypothesis 1

This function performs a XOR with a key. The key not being explicitly given as an argument has to be statically defined somewhere and probably won’t change between calls.
Hypothesis 1

Because you know the (ciphertext, plaintext) pair of 2 different messages encrypted using the same function, it’s easy to recover the key using the first pair and verify if the hypothesis is correct by decrypting the second ciphertext and comparing with the expected plaintext.

#!/usr/bin/env python3
#encoding: utf-8

from binascii import unhexlify

def strxor(a, k):
    s = b""
    for i in range(len(a)):
        s += bytes([a[i] ^ k[i % len(k)]])
    return s

X = unhexlify(b'4F6D73612926737A702A6A6B6C676131')
Z = unhexlify(b'171C335F4B45317D1A570252203A140A0C402934104B0D56602D03470741661438726D720F18707A286F5214236935621A1E6462347940')
P = unhexlify(b'516370777269756C33')

print(strxor(P, b'Password:'))

$ ./solve.py 
b'\x01\x02\x03\x04\x05\x06\x07\x08\t'

It looks like the key is just the sequence of consecutive bytes starting at 1, probably until 255. Using that to decrypt the second encrypted string :

KEY = bytes(range(1, 256))
print(strxor(X, KEY))
print(strxor(Z, KEY)) # Flag

b'Nope, try again!'
b'\x16\x1e0[NC6u\x13]\t^-4\x1b\x1a\x1dR: \x05]\x1aNy7\x18[\x1a_y4\x19PNV*>WR\x01Ey8\x0eG\x1aR+,WV\x01Ow'

Hypothesis 1 is correct ! And it also proves that the flag is encrypted using a different function.

This was just a warm up to introduce the methodology of making hypotheses and verifying them. Now you’ll see how to apply it to a more complex scenario.

Decrypting the flag

In order to get to the line that prints the flag, two conditions must be met. The first 6 bytes of the flag must produce a given checksum and the first 2 bytes of the decrypted flag must be “OK” :

...
        if (crackme.csum(pwd[:6])==0x53evua9d27):
            d=crackme.xorlm(crackme.Z, pwd[:6])
            if d[:2]==b'OK':
                uart.write(d[2:]+b'\r\n')wv
...

The function crackme.csum is unknown to you and you can’t play with it to obtain the results for chosen passwords. One more pain is the random bytes located right in the middle of the checksum value that makes it unsure about the expected value.

You might be tempted to make the hypothesis that the csum function performs a CRC32 and that’s the right spirit. To verify it, you’ll have to brute force all possible 6 bytes values that produces the desired checksums and verify them one by one. That’s what I did, but with no success. So, just forget about this condition and focus on the other. The goal is to decrypt the flag offline, not to make the program decrypt it for you.

Because the password must be entered using a keyboard, you can make the following statement that will help you validate or invalidate your hypotheses. Because this statement will never be proven until the end, let’s call that an axiom.

The password is composed of printable characters only.
Axiom 1

Axioms are always true, if a hypothesis is conflicting with an axiom, it’s the hypothesis that is incorrect, never the opposite. It’s crucial that you don’t make an axiom that is incorrect. In fact, don’t make any if it’s not necessary.

Because the function xorlm takes 2 inputs, the encrypted flag and the first 6 bytes of our password, you could make the following hypothesis.

The function xorlm performs a XOR. The key for the XOR is the password and the password is 6 bytes long.
Hypothesis 2

Verification of hypothesis 2

Unlike before, you don’t have a full known plaintext but only 2 letters. That’s not much but still enough to verify the hypothesis.

print(strxor(Z, b'OK'))

b'XW|\x14\x04\x0e~6U\x1cM\x19oq[AC\x0bf\x7f_\x00B\x1d/fL\x0cH\n)_w9"9@S?1g$\x1d_l"z)UU+){2\x0f'

If the hypothesis is correct, the first two letters of the password would be “XW”, which doesn’t look very meaningful but at least it’s printable. The hypothesis is not invalidated. If there was non-printable characters then the hypothesis would have been conflicting with axiom 1 and thus been invalidated.

In order to continue, you could guess some words of the plaintext and hope that they are present somewhere. This is called a crib. And by testing every possible position of this word in the text and xoring with the ciphertext, you’ll get a potential partial key. This technique is called crib dragging. But then, you’ll have to differentiate good partial keys from wrong partial keys and this is only possible if the key is somewhat meaningful to a human or has a recognizable pattern.

After having played a bit with this idea, I didn’t find anything that helped. Maybe I didn’t guess the right words or the key is just meaningless. Judging by the first two letters of the password, which is assumed to be the XOR key, it’s likely meaningless, rendering this attack useless.

If the key is meaningless, the flag is certainly not. Because the key is quite small and the flag big, the key will loop every 6 letters. You might be able to guess part of the flag knowing only 2 letters every 6 letters thanks to the partial known plaintext.

def mask(k):
    n = len(k)
    k += b"\x00"*(6-n)
    flag = strxor(Z, k)
    m = b''
    for i, c in enumerate(flag):
        if i%6 < n:
            m += bytes([c])
        else:
            m += b' '
    return m

print(mask(b'XW'))

b'OK    i*    xm    qc    8z    >C    WO    \nC    BI    \x18'

There are some non-printable characters and the the flag certainly wouldn’t end with “\x18”. The hypothesis 2 is conflicting with axiom 1 and is thus invalidated. Time to make a new one.

The function is called xorlm, maybe xorl is also used by this function ? What if instead of just being the password used as a key, another key was also used ? This key could be the one of xorl and so xorlm would be xorl(crackme.Z) ^ password[:6].

The function xorlm performs two consecutive XOR operations. The first with the same key as the function xorl and the second with the key being the password. The password is 6 bytes long.
Hypothesis 3

Verification of hypothesis 3

print(strxor(strxor(Z, KEY), b'OK'))

b'YU\x7f\x10\x01\x08y>\\x16F\x15b\x7fTQR\x19ukJ\x16U\x056|W\x10U\x146\x7fV\x1b\x01\x1deu\x18\x19N\x0e6sA\x0cU\x19dg\x18\x1dN\x048'

“YU” as the first two letters of the password is more likely than “XW”, but like before not enough to validate or invalidate the hypothesis 3. Continuing with the check that invalidated the previous hypothesis :

def mask(k):
    n = len(k)
    k += b"\x00"*(6-n)
    flag = strxor(strxor(Z, k), KEY)
    m = b''
    for i, c in enumerate(flag):
        if i%6 < n:
            m += bytes([c])
        else:
            m += b' '
    return m

print(mask(b'YU'))

b'OK    o     ta    cu     b     a    sk     m    ry    .'

This looks very promising ! It’s even ending with a point. Before validating this hypothesis, you can make another one for the third letter of the flag, the one after “OK”. Because only what is after the “OK” will be printed, you can assume that it starts with an uppercase letter. If this is correct it will help you further.

def isPrintable(s):
    import string
    for e in s:
        if chr(e) not in string.printable:
            return False
    return True

for e in range(256):
    p = b'YU'+bytes([e])
    f = mask(p)
    if isPrintable(f) and isPrintable(p) and f[2] in b'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
        print(p, f)

b'YU`' b'OKP   o s   ta{   cue    bx    ay   sk7    mn   ry7   .'
b'YUa' b'OKQ   o r   taz   cud    by    ax   sk6    mo   ry6   .'
b'YUb' b'OKR   o q   tay   cug    bz    a{   sk5    ml   ry5   .'
b'YUc' b'OKS   o p   tax   cuf    b{    az   sk4    mm   ry4   .'
b'YUe' b'OKU   o v   ta~   cu`    b}    a|   sk2    mk   ry2   .'
b'YUh' b'OKX   o {   tas   cum    bp    aq   sk?    mf   ry?   .'
b'YUi' b'OKY   o z   tar   cul    bq    ap   sk>    mg   ry>   .'
b'YUj' b'OKZ   o y   taq   cuo    br    as   sk=    md   ry=   .'
b'YUr' b'OKB   o a   tai   cuw    bj    ak   sk%    m|   ry%   .'
b'YUs' b'OKC   o `   tah   cuv    bk    aj   sk$    m}   ry$   .'
b'YUt' b'OKD   o g   tao   cuq    bl    am   sk#    mz   ry#   .'
b'YUu' b'OKE   o f   tan   cup    bm    al   sk"    m{   ry"   .'
b'YUv' b'OKF   o e   tam   cus    bn    ao   sk!    mx   ry!   .'
b'YUw' b'OKG   o d   tal   cur    bo    an   sk     my   ry    .'
b'YUx' b'OKH   o k   tac   cu}    b`    aa   sk/    mv   ry/   .'
b'YUy' b'OKI   o j   tab   cu|    ba    a`   sk.    mw   ry.   .'
b'YU{' b'OKK   o h   ta`   cu~    bc    ab   sk,    mu   ry,   .'
b'YU|' b'OKL   o o   tag   cuy    bd    ae   sk+    mr   ry+   .'
b'YU}' b'OKM   o n   taf   cux    be    ad   sk*    ms   ry*   .'
b'YU~' b'OKN   o m   tae   cu{    bf    ag   sk)    mp   ry)   .'

If you only take into consideration the outputs that contain letters and correctly placed ponctuations, you’re left with 2 possible keys :

b'YUv' b'OKF   o e   tam   cus    bn    ao   sk!    mx   ry!   .'
b'YUw' b'OKG   o d   tal   cur    bo    an   sk     my   ry    .'

The second key “YUw” provides in my opinion the best guess for the key. It’s even possible to guess the last word “mystery”. If this guess is correct, you’ll have cracked the key because this word is longer than 6 bytes.

print(strxor(strxor(Z[43:43+7], KEY[43:43+7]), b'mystery'))

b'Uw4n7YU'

The password might be “YUw4n7”, which is without doubt the right password :

print(strxor(strxor(Z, KEY), b'YUw4n7'))

b'OKGo to digital.security booth and ask for mystery box.'

Hypothesis 3 validated !

Conclusion

You have seen how making simple hypotheses and verifying them can lead to solving a black box cryptographic task. You might think that a lot of guessing is involved and that’s partially true. In this particular example every hypothesis was made from the name of the functions. But there is also a lot of intuition and common sense involved.

The most difficult part is not making the hypotheses, it’s verifying them. Finding the best way to verify a hypothesis requires intuition and this comes with experience. There are usually more than one way to verify them, sometimes you won’t choose the simplest but that’s when you’ll learn something new.

To summarize what I’ve done to solve this task, I started by identifying the encrypted strings in memory thanks to their length and entropy. I then made assumptions on how they where encrypted using the names of the functions and verified my assumptions sequentially. Every time I learnt something new thanks to my verifications, I tried to build from that.

Thanks for reading and if you want, you can try to apply this methodology yourself on this little challenge. It shouldn’t be too difficult. 😉

BitsDeep

BitsDeep

Cryptography for non-mathematicians

Solving RE tasks the crypto way

The task

Warm up

Verification of hypothesis 1

Decrypting the flag

Verification of hypothesis 2

Verification of hypothesis 3

Conclusion

Like this:

Leave a Reply Cancel reply

BitsDeep

The task

Warm up

Verification of hypothesis 1

Decrypting the flag

Verification of hypothesis 2

Verification of hypothesis 3

Conclusion

Share :

Like this:

Leave a Reply Cancel reply