Hacky Easter 2015 – Jad And Ida

Introduction

Hello all! Sorry I’ve been silent for some time, life was busy! I come back with fresh write-ups however, for some interesting challenges! Hacky Easter 2015 is what I have been busy with during the nights and evenings, and it’s a CTF where flags are QR codes!

This is the write-up for challenge Challenge 25, called Jad & Ida!

Challenge 25 banner.
Challenge 25 banner.

The Challenge

Challenge 25, of the Hard category, presented us with a zip file. Before opening the archive, we get a feeling that this will be a reverse engineering challenge, as IDA is perhaps the most known disassembler and JAD is a very famous Java decompiler. The jadandida.zip file that we are given contains the following:

unzip -l jadandida.zip | awk '{print $4}'</p>
<p>Name<br />
----<br />
bin/<br />
bin/ps/<br />
bin/ps/hacking/<br />
bin/ps/hacking/jadida/<br />
bin/ps/hacking/jadida/JadAndIda$LizzleDLL.class<br />
bin/ps/hacking/jadida/JadAndIda.class<br />
lib/<br />
lib/jna.jar<br />
lib/libhe2015_Lizzle.dll<br />
lib/platform.jar<br />
run.bat<br />
runwith_32bit_jre.txt<br />
s3cr3t.bin 

We are indeed facing both native code and Java bytecode. Our weapons of choice for this one, however, shall be slightly different. We will be using IDA and ByteCode Viewer (https://github.com/Konloch/bytecode-viewer/), which is a very nice collection of open-source Java decompilers and disassemblers!

Understanding the Java

On the vast majority of  cases, reversing Java is easier that reversing native code (speaking in general, and ignoring obfuscators or other similar goodies). As such, staying true to our laziness and on the path of least resistance, let us Java! Opening up JadAndIda.class in ByteCode Viewer will give us the following:

ByteCode Viewer output for the JadAndIda.class file.
ByteCode Viewer output for the JadAndIda.class file.

We can see that disassembling Java in this case means decompiling Java as we get back readable source code. Moreover, the source code has still got the original names of the variables used (rather than var0, var1, etc), something that makes our life even easier! This has now turned into a source-code review exercise!

Starting at the top of the file, we can see that the code is trying to import a native library, called libhe2015_Lizzle.dll (the extension is omitted for the System.loadLibrary call on Windows), a native library found in the archive.

The main function is where everything is happening though, so that’s next! In short, the binary prompts us for a password, runs it through the functions bizzle, shizzle, rizzle and fizzle ten times. If the result of that computation matches “v3O] pmWm<Y(0=21” then the plain-text version of the password would be used to decrypt the file s3cr3t.bin, which is presumably a QR code. The other possibility is a rude response, so let’s try and find the key instead!

The Password Check

As stated earlier, the value we provide will undergo a transformation and then get compared to a static value. Essentially the program is comparing the hash (term used loosely) of an unknown value to the hash of a known value and test if they match. If the hashes match, then so should the values which produced the hashes. This is how you are meant to store and check passwords, as you only store a irreversible transformation of the secret (it’s hashed value) rather than the secret itself, preventing adversaries from poking the binary and easily obtaining the secret.

In addition to the above, there a couple more crucial characteristics that a hashing algorithm must provably satisfy in order to be cryptographically secure, and the most important are:

  • Determinism: the value of a transformation should always be the same. In other words if hash(a) = b, then every time we perform the transformation on a we should get b.
  • Easy one way, hard the other: computing a given b should be hard (like impossibly hard). It should be easy to compute hash(a) but computationally impossible to compute reverse(b) = a.
  • Collision Resistance : two different values should not produce the same result. In other words, if a != b then hash(a) should not equal hash(b). If such a situation were to occur then people could get access to our encrypted data without knowing our secret password!
  • Length : The result of hashing should avoid leaking the size of the secret. If a secret of length two has a hash of length L, so should a secret of length 100,000. This way the attackers will observe hashes of length L and this will not inform them about the size of the secret.
  • Small changes in the input should produce very different hashes. If this were not true, then the attackers might be able to infer a mapping for the secret. As an example, if hash(abcd) = xyza and hash(abce) = xyzb then the attackers will be able to infer the relationship between the secret and the hashed value.
  • Hash space: Related to the collision resistance, the space of the produced hashes must be sufficiently big so that it won’t get exhausted easily.

In light of this knowledge, let’s see what bizzle, rizzle, shizzle and fizzle actually do:

The transofrmation functions.
The transofrmation functions.

So bizzle and rizzle are written in Java, while shizzle and fizzle come from our native code. Very quickly we can see that bizzle just right-shifts the characters by one, to their next ASCII code and wraps around a to z and A to Z. Rizzle on the other hand just reverses the case of a string’s characters, making rizzle equal to un-rizzle!

The Native Component

The DLLs export two functions, Shizzle and Fizzle. Starting with Shizzle:

Code of Shizzle function.
Code of Shizzle function.

IDA disassembles this function as being an int shizzle(char *src, int a) function, however I believe it was intended to be an int shizzle(char *src, char *dst). The check cmp 10h, eax also reveals something about the secret. It will return a null pointer in the dst argument if the input is not 16 characters long. You know what else is 16 characters long? “v3O] pmWm<Y(0=21” !

At location loc_65C012C3 we can see the true purpose of this function, which just reverses the input. Following on, Fizzle:

Code for the fizzle function.
Code for the fizzle function.

Fizzle is also of the form int fizzle(char *src, char *dst) and we can see that it performs the same length checks as Shizzle, but looks a fair bit more complicated. In particular, some arithmetic is being performed on the input (shifting, adding, etc) as well as a rearranging the order of the input.

This is going to take a while to reverse engineer and understand. Or is it?

Be True, Be Lazy.

At first I started reading at Fizzle’s code, and half-way through I thought “Fizzle this shizzle, let’s get smart!”. So instead of carrying on writing un-fizzle, I instead thought about doing some cryptanalysis.

Testing the properties regarding cryptographic strength for hash algorithms (or at least the subset listed earlier), I threw at Fizzle multiple words that had a small edit distance. Some interesting results emerged:

shizzle('aaaaaaaaaaaaaaaa') = K\o)@Yt6fgjov$/&lt;<br />
shizzle('aaaaaaaaaaaaaaab') = K\o)@Yt7fgjov$/&lt;<br />
shizzle('baaaaaaaaaaaaaaa') = K\o)@Yt6ggjov$/&lt;<br />
shizzle('caaaaaaaaaaaaaaa') = K\o)@Yt6hgjov$/&lt;<br />
shizzle('caaaaaaaaaaaaaab') = K\o)@Yt7hgjov$/&lt;<br />
shizzle('caaaaaaaaaaaaaaa') = K\o)@Yt6hgjov$/&lt;<br />
shizzle('cbaaaaaaaaaaaaaa') = K\o)@Yt6hhjov$/&lt;<br />
shizzle('cbbaaaaaaaaaaaaa') = K\o)@Yt6hhkov$/&lt;<br />
shizzle('cbbbaaaaaaaaaaaa') = K\o)@Yt6hhkpv$/&lt;<br />
shizzle('cbbbbaaaaaaaaaaa') = K\o)@Yt6hhkpw$/&lt;<br />
shizzle('cbbbbbaaaaaaaaaa') = K\o)@Yt6hhkpw%/&lt;<br />
shizzle('cbbbbbbaaaaaaaaa') = K\o)@Yt6hhkpw%0&lt;<br />
shizzle('cbbbbbbbaaaaaaaa') = K\o)@Yt6hhkpw%0=<br />
shizzle('cbbbbbbbbaaaaaaa') = L\o)@Yt6hhkpw%0=<br />
shizzle('aaaaaaaabaaaaaaa') = L\o)@Yt6fgjov$/&lt;<br />
shizzle('aaaaaaaacaaaaaaa') = M\o)@Yt6fgjov$/&lt; 

Oh Joy! There are so many things wrong with Fizzle! Observing the first four strings will indicate that an edit to the input of distance one will give an edit to the output of distance one as well! Going through the rest of the examples listed here will also reveal that there is a relationship between a character’s position in the input string and its position and shifting in the output string, as well as the fact that a characters transformation only depends on the input characters position and value and not in any form on the surrounding characters!

Fizzle is some sort of  a bad collection of 16 mono-alphabetic substitution ciphers with their order all scrambled up. So my idea was to brute-force each position’s input in order to get the corresponding output character, and in this way construct an oracle that would tell us what the input was, give the output mapping! What follows is some python and ctypes magic that decrypt the secret stored in their binary (commentary after the code):

<br />
#!/usr/bin/env python</p>
<p>import ctypes<br />
import pdb</p>
<p>lib = ctypes.cdll.LoadLibrary(&quot;libhe2015_Lizzle.dll&quot;)<br />
mega_map = [{chr(i):&quot;0&quot; for i in xrange(32,127) } for j in xrange(0,16)]<br />
oracle = []</p>
<p>def bizzle(string):<br />
    res = &quot;&quot;<br />
    for i in string:<br />
        code = ord(i)<br />
        if code &gt;= 97 and code &lt; 122:<br />
            code += 1<br />
        elif code == 122 :<br />
            code = 97<br />
        elif code &gt;= 65 and code &lt; 90 :<br />
            code += 1<br />
        elif code == 90:<br />
            code = 65</p>
<p>        res += chr(code)<br />
    return res</p>
<p>def rizzle(string):<br />
    res = &quot;&quot;<br />
    for i in string:<br />
        if i.isupper():<br />
            res += i.lower()<br />
        elif i.islower():<br />
            res += i.upper()<br />
        else:<br />
            res += i<br />
    return res</p>
<p>def shizzle(arg1):<br />
    global lib<br />
    shizzle_func = lib.Shizzle<br />
    res = ctypes.create_string_buffer(16) #must be writeable<br />
    shizzle_func(arg1,res) #return value is what whas in eax, in this case first char of string so don't use that<br />
    return res.value</p>
<p>def fizzle(arg1):<br />
    global lib<br />
    fizzle_func = lib.Fizzle<br />
    res = ctypes.create_string_buffer(16) #must be writeable<br />
    fizzle_func(arg1,res) #return value is what whas in eax, in this case first char of string so don't use that<br />
    return res.value</p>
<p>def unrizzle(string):<br />
    return rizzle(string)</p>
<p>def unshizzle(arg1):<br />
    return shizzle(arg1)<br />
    <br />
def unbizzle(string):<br />
    res = &quot;&quot;<br />
    for i in string:<br />
        code = ord(i)<br />
        if code &gt; 97 and code &lt;= 122:<br />
            code -= 1<br />
        elif code == 97 :<br />
            code = 122<br />
        elif code &gt; 65 and code &lt;= 90 :<br />
            code -= 1<br />
        elif code == 65:<br />
            code = 90</p>
<p>        res += chr(code)<br />
    return res</p>
<p>def unfizzle(ct):<br />
    res = [0 for i in xrange(0,16)]<br />
    for i,l in enumerate(ct):<br />
        res[(i+8)%16] = oracle[(i+8)%16][l]<br />
    return &quot;&quot;.join(res)</p>
<p>#build a 16 character long string that contains character char<br />
# at position index<br />
def build_str(index, char):<br />
    return index*&quot; &quot; + char + &quot; &quot;*(15-index)</p>
<p>#does magic<br />
def build_oracle():<br />
    for index,dictionary_copy in enumerate(mega_map):<br />
        dictionary = {chr(i):&quot;0&quot; for i in xrange(32,127) }<br />
        for char in dictionary_copy.keys():<br />
            string = build_str(index,char)<br />
            resp = fizzle(string)<br />
            target_letter = resp[(index+8) % 16] # verify this is correct<br />
            dictionary[target_letter] = char<br />
        oracle.append(dictionary)</p>
<p>def encrypt(string):<br />
    h2 = string<br />
    for i in xrange(0,10):<br />
        h2 = bizzle(h2)<br />
        h2 = shizzle(h2)<br />
        h2 = unrizzle(h2)<br />
        h2 = fizzle(h2)<br />
    return h2</p>
<p>def decrypt(string):<br />
    h = string<br />
    for i in xrange(0,10):<br />
        h = unfizzle(h)<br />
        h = unrizzle(h)<br />
        h = unshizzle(h)<br />
        h = unbizzle(h)<br />
    return h</p>
<p>def run():<br />
    password = &quot;abc1234==168.-!A&quot; #input('Provide decryption password')<br />
    build_oracle()<br />
    e_a = encrypt(password)<br />
    p_t = decrypt(e_a)<br />
    print &quot;secret = encrypted {:s} decrypted {:s}. decryption {:s}&quot;.format(e_a,p_t, &quot;matches&quot; if password == p_t else &quot;doesn't match&quot;)<br />
    print decrypt(&quot;v3O] pmWm&lt;Y(0=21&quot;)<br />
run()  <br />

The interesting bits are located in the run() function and its code flow with build_oracle() being the key function that builds our dictionary for the look-ups, but the whole script is presented for completeness. The above script implements two of the original functions in python and uses the code from the native ones as is through the use of ctypes. All of the reverse routines have been implemented, but unfizzle.

To reverse unfizzle firstly we create mega_map, which is a list of dictionaries, the dictionaries containing all characters in the range 0x20-0x7E.Each index in the mega_map list will correspond to an index in the cipher-text produced by fizzle, and each character in the dictionary at that index of the array would serve as reverse mapping, mapping from cipher-text back to the corresponding plain-text letter that was used. The run() method will build the oracle and run a sample encryption and decryption and then decrypt the embedded password.

In the beginning I was expecting the script to be slow when building the map as I expected it to have to produce 2^(16*8) combinations (2 bits, 8 bits per byte for 16 characters), however it turns out that in reality we only have to try 16*95, as there are only 95 printable characters and we don’t need to go through all of the key-space.

Conclusion

Even though the python script might be not the most elegant of its kind, it does produce an answer! The password was jadnIdal0vecod3n, and the Easter egg-flag was:

Eggizle 25!
Eggizle 25!

This challenge wasn’t hard, however it illustrated some significant points. It was crucial to understand what exactly each function did, and most of them were easy enough to read through the code or the assembly and figure them out. This would have been a trap for the fourth function, however, as I believe the method of cryptanalysis to be more fruitful in this case. The fourth function only looked hard.

Fizzle illustrated that you shouldn’t trust your own crypto because you think it is unbreakable, as per Schneier’s law. Bad crypto that is relied upon can and will let you down.

Remember kids : Don’t roll your own.

P.S. I apologize if any of my crypto-statements were inaccurate, I can’t really crypto apart from the basic stuff.

Advertisements
Hacky Easter 2015 – Jad And Ida

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s