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.
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:
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
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:
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:
void flare2015crackme6_algo_helper(const TCHAR* pszKeyFilename, const byte* pPrimeTable, size_t uSizePrimeTable, const byte* pKeyData, size_t uSizeKeyData, TCHAR* pszRetResult)
const byte* pCurKeyData = pKeyData;
const byte* pLastKey = pKeyData+uSizeKeyData;
word wCurKeyData = 0;
word wCurPrime = 0;
dword uTotal = 1;
uint uCurPower = 0;
uint uKeyIdx = 0;
//if current key slot has a nonzero value
wCurKeyData = *((word*)pCurKeyData);
//this value corresponds to the prime number at the same location
// raise this prime number to wCurKeyData
wCurPrime = *((word*)(pPrimeTable + uKeyIdx*sizeof(word)));
uCurPower = 1;
for(uint p=0; p<wCurKeyData; ++p)
uCurPower *= wCurPrime;
//multiply power by running total
uTotal *= uCurPower;
pCurKeyData += 2;
} while (pCurKeyData<pLastKey);
byte byteLo = *((byte*)&uTotal);
byte byteHi = *(((byte*)&uTotal)+1);
*pszRetResult = (TCHAR)byteHi;
*(pszRetResult+1) = (TCHAR)byteLo;
//load table of prime numbers
const uint uMaxPrimeFile = 0x1B28; //6952 bytes
ResultCode iRetCode = bufPrimes.load(TEXT("prime_table.bin"));
_tprintf(TEXT("ERROR: unable to load prime_table\n"));
else if (bufPrimes.getSize() != uMaxPrimeFile)
_tprintf(TEXT("ERROR: prime_table is %u bytes but should be %u\n"),bufPrimes.getSize(),uMaxPrimeFile);
//loop through each file we need to load
TCHAR* pCurResult = szResult;
const TCHAR* pLastResult = szResult+MAX_ARRAY_ITEMS(szResult);
uint uFileNum = 1;
for(; uFileNum<=23 && CODE_SUCCEEDED(iRetCode); ++uFileNum)
//load each file
iRetCode = bufKeyFile.load(szTemp);
_tprintf(TEXT("ERROR: unable to load key file %s\n"),szTemp);
else if (bufKeyFile.getSize() != uMaxPrimeFile)
_tprintf(TEXT("ERROR: key file %s is %u bytes but should be %u\n"),szTemp,bufKeyFile.getSize(),uMaxPrimeFile);
else if (pCurResult>=pLastResult-1) //is there room for two chars?
_tprintf(TEXT("ERROR: not enough room to store result\n"));
//process each file
pCurResult += 2; //advance two chars
//did all the files process successfully?
if (pCurResult>=pLastResult) //is there room for null terminator?
_tprintf(TEXT("ERROR: not enough room to null terminate result\n"));
*pCurResult = 0;
_tprintf(TEXT("decrypted solution: \"%s\"\n"),szResult);
Running the above program on our saved buffers, resulted in:
Plugging the resulting characters back in to the Android app confirms the solution!
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.
Response from Should_have_g0ne_to_tashi_email@example.com:
Subject: FLARE-On Challenge #6 Completed!
Date: Mon, 17 Aug 2015 04:20:56 -0400
You are an unstoppable force of computer science. I have no choice but to give you yet another challenge. The password is to the zip archive is "flare", but you probably already know that don't you?
You are literally saving lives.