CHALLENGE MATERIALS:

filename:		android.apk		DOWNLOAD
md5		8afcfdae4ddc16134964c1be3f741191
size		1.03 mb (1,078,129 bytes)
type		Android 'Froyo' App (Java + Native ARM code)
Original FLARE Author		Moritz Raabe
tool:		Android Studio (SDK) / ADB tool / Android Emulator		Visit Website
tool:		dex2jar / DEX Converter		Visit Website
tool:		JD-GUI 1.4.0 / Java Decompiler		Visit Website
tool:		Apktool / APK Resource Decompiler		Visit Website
tool:		IDA / Disassembler		Visit Website

SUMMARY:
This is your basic-looking Android app that asks for the password, but you'll find the password is buried pretty deep. Android development skills are not completely necessary, however ARM assembly or C-pseudocode (IDA's C decompiler output) analysis skills are necessary to break this one.

FIRST LAUNCH:
The android.apk file can be installed directly on a physical Android device (such as a phone) or on an emulated Android device using the ADB tool (Android Debug Bridge). The ADB tool and the Android emulator are bundled with Google's Android Studio (a.k.a. the Android SDK). Installing the Android SDK just so you can participate in this challenge might be kind of a pain, so an alternative is to choose from one of the many free emulators, such as BlueStacks that can launch APK files directly. Assuming that you are using the SDK, you can install the APK using ADB as shown:

    adb install android.apk

After installation, navigate on the target device to your app-listings screen and locate the app with the FLARE logo labeled "The FLARE On Challenge".   
Once launched, you should see a text entry screen followed by a "Validate" button.


If anything but the correct password is entered, a large "NO" fills the screen.

DECOMPILING THE APP:
The first thing we want to look at is the logic that processes the entered text in the app.

Since all APK's are actually ZIP files containing the meta-information, resources and bytecode necessary for Android to run and maintain the app, let's start by renaming the file to android.zip so we can get inside. Within android.zip, extract the classes.dex file into your dex2jar directory and open a command prompt there.

NOTE: The compiled Java code for the app is located in classes.dex. We need to convert it from Dalvik bytecode (.DEX) to Java bytecode before we can decompile it. Run the following command to perform the Java conversion:

    d2j-dex2jar classes.dex

This will produce a file named something like "classes-dex2jar.jar". Now Open the Java Decompiler tool (jd-gui.exe), select "Open File..." from the "File" menu and locate the JAR file you just created from dex2jar. This will populate the tool's Window with a source code tree of the decompiled Java which should be very close to the original source. You have the option to save off all the source code ("File" -> "Save All Sources") or you can simply view it directly in the tool window itself. The built-in viewer has handy syntax hilighting and is lightweight, so it will do just fine for our source-code viewing purposes.

Since we don't care about the android library boilerplate code, navigate directly to the app's code by opening "com.flareon.flare" in the left pane and selecting "MainActivity.class". You should see the corresponding code appear in the right pane.

JAVA CODE ANALYSIS:
Looking in the left pane, we can this app consists of two Activity classes, MainActivity and ValidateActivity. If you don't know the Android Java framework, an Activity can be thought of as screen that displays something. In the case of this app, the MainActivity handles the text box and the validate button. The ValidateActivity handles displaying whether or not we entered the correct password.



In MainActivity, the onCreate() method invokes setContentView with a large-looking number. This is simply the resource id for MainActivity's layout which happens to be res/layout/layout_main.xml. We can assume the validateEmail() method is called when the "Validate" button is clicked although there is no code visible that hooks up this method to the "Validate" button. This is because the method is referenced in the layout_main.xml file. You can find this file in the APK, but it is also in binary form and needs processing to see the original text. Although not absolutely required for this tutorial, you can decompile these resources by copying android.apk to the [installed] Apktool directory and running:

    apktool d android.apk

An "android" directory will be created with all of the decompiled resources including readable XML files. The generated APKTool.yml indicates the minimum Android device supported is SDK version 8 (Froyo) although version 22 (Lollipop) is the target.

Unfortunately for us, a comparison with the correct password doesn't jump out at us like we were hoping! validateEmail() packages up the text entered by the user into an Intent object (used to pass data from one Activity to another) and passes it to our ValidateActivity screen. Now, let's have a look at ValidateActivity:



Just after the activity unpackages the user input (passed in container "com.flare_on.flare.MESSAGE"), it calls:

    paramBundle.setText(validate(str));

The validate method obviously returns the result text to display for this screen. The validate() method declaration below seems has no implementation in the Java source. We do see that it is declared "native" and that higher up in the class is a call to:

    System.loadLibrary("validate")

Therefore we can assume the validation code implementation is within this library dependency. According to the SDK docs, the string passed to loadLibrary() has a "lib" prepended to it, and an '.so' appended to it to generate the library filename. Therefore, we know this call looks for a library named libvalidate.so. This file can be extracted directly from the APK (as a ZIP) from the "lib/armeabi" directory. The Linux "readelf" tool says this file is an ARM 32-bit v5TE ELF binary. Luckily IDA Pro supports ARM architectures.

PASSWORD VALIDATION ALGORITHM:
Load libvalidate.so in IDA. From the "Exports" tab, notice the symbol named "Java_com_flareon_flare_ValidateActivity_validate". Double-click on that export and from the disassembly window, hit <TAB> to switch to C-pseudocode mode. As you study the algorithm, it is helpful to rename variables as you figure out what their purpose is with the "n" key. Also, add comments to the far right of the pseudocode with the "/" key. What I ended up with is the following annotated function:



Right off the bat, we can see that the condition satisfied at line #66 causes the function to return "That's it!" which appears to be the correct password response. But, since we need to find the key, the algorithm must be understood. Looking to line #45, the keyBuffer variable is referenced which represents a static chunk of data embedded within the ELF file. A view of this data shows:



This is clearly a buffer of prime numbers. Lets start at the top where we initialize a chunk of 6952 bytes to zero at line #21; I happen to call this the scratch buffer. Line #23 obtains the user input string, whose length must be less than or equal to 46 (line #28), otherwise the "No" message is returned without further processing. This is a clue that the correct password is probably 46 characters. A for loop begins looping over each two-character sequence in input string. This character pair is interpreted as a 16-bit numeric WORD value (line #40) which enters a factoring loop between lines #43 and #55. At the beginning of this loop, our scratch buffer of 6952 bytes contains all zeros. With each iteration of the factoring loop, we loop through each prime number in the prime table to see if it evenly divides the double-character input WORD's numeric value. When a factor is found, we increment the corresponding WORD entry in the scratch buffer by 1 (line #48) and reduce the running value until we are left with the value of 1 (i.e. the number has been fully factored) at which point we jump to SCRATCH_BUFFER_COMPLETE (at line #56). This loop should work for any number, as all numbers can be factored into prime components. Our scratch buffer at this point represents two characters factored into 6952 bytes of mostly zeros, but whose nonzero values indicate corresponding positions in the prime table. You heard right, that's about 6k per two-characters encoded! Each double-character representation in the scratch buffer corresponds to an "expected" buffer whose contents must match; these are our key buffers. If the outer for loop has exhausted all of the user input without encountering a buffer mismatch, then the function returns "That's it!". If we wanted to make this algorithm susceptible to manual brute force, we would eliminate the check at line #65 that ensures "curidx_char == 23". Then, the algorithm will give us a success message if each pair of two-character inputs entered are correct, thus far. This would allow you to brute force each position of the password, one character at a time.

CRACKING THE PASSWORD:
We need to save off the 23 key buffers that are used to compare against the user input scratch buffer. To do this, double-click on the 2nd argument to memcpy on line #22 as this is the pointer to the key buffer table. Then you'll see something like this:



To save off each of the buffer entries, double-click one to go to its starting location in memory. Hit the <HOME> key to go to the beginning of the line and press ALT+l (lowercase L) to begin the selection. Using a hex or programmer's calculator (such as evl), add the size of each buffer (6952) to the beginning hex address minus one and display the result in hex. This is the ending address of the current buffer. Page down until you have selected the entire buffer up to and including this address. This should be easy to spot, as the end of a buffer usually marks the beginning of another (although they are out of order in the file itself on purpose of course). Now go to "Edit" -> "Export data..." to enter the export dialog. Select the "Raw bytes" radio-button and type the filename to save the buffer as. The order of the buffers in the table is significant, not the buffer's position in the file! Once saved, each key buffer should be exactly 6952 bytes and represents two ASCII characters of the correct password. Unless you want to write a small program to generate the first 3476 prime numbers (3476 * 2 byte WORD = 6952 bytes), perform the same steps to save off a copy of the prime number table at .rodata:00002214.

Then we just need a program to loop through each buffer in sequence, and any time a nonzero WORD is encountered, multiply a running number by the prime number at that position times that position's value. After each position in the buffer has been looked at, the final running WORD value will represent the next two ASCII bytes of the password.

After you have saved off each of the 23 buffers (as keydataXX.bin), along with the prime number table (as prime_table.bin), you could run it through a program similar to the one I wrote below to decode the factored positions back into the numeric value, giving us our password ASCII codes:


Running the above program on our saved buffers, resulted in:



Plugging the resulting characters back in to the Android app confirms the solution!


CONCLUSION:
One thing that puzzled me is on line #57 of the algorithm, when we compared the expected buffer against the encoded user input scratch buffer, only 3476 bytes appears to be compared which is half the size of the buffer and I don't think the j_j_memcmp() function dealt in WORDs. This wouldn't stop the validation algorithm from working for the correct password, but it might result in validating other incorrect password variations. This seems like a bug to me, although I could be wrong.

The official solution focused on solely using Apktool to decode the APK and read the smali files instead of using a decompiler to access the .java files. Knowing smali certainly has educational merit and this approach certainly has you dependent on fewer tools. The author also explained the algorithm via the the ARM disassembly of libvalidate.so rather than using IDA's handy C-pseudocode feature, something that would have taken me longer considering I had very little experience in ARM assembly at the time of the challenge. I do however appreciate the author's ARM assembly "primer" to help those in need ramp up quickly! The author also used an IDAPython script to decode the 23 buffers rather than writing a C++ program to determine the final solution.

E-MAIL RESPONSE:
Response from Should_have_g0ne_to_tashi_$tation@flare-on.com:

---

<< Flare-On 2015 Index  --  Go on to Challenge #7 >>