This specific challenge was not actually solved by me during quals. Aegis officially scored and I'm sure others helped out. That said, I like to look at challenges afterwards and identify what I could do to solve it more efficiently next time. What follows is a walk-through on solving this challenge with my revenge tool.
I decided to create revenge since I think that the frida tool is pretty useful, but i really hate the API. I don't enjoy coding in javascript (or typescript for that matter). My preferred language is python. Frida does expose a python library, but it is effectively just enough to be able to run javascript scripts. My goal with revenge is to make a much more pythonic library around frida and add extra libraries and functionality based around frida as the framework.
This particular challenge is an android reverse engineering challenge. Given the authors, and their recent addition of Java to their symbolic execution engine angr, it is very likely this challenge was placed in to showcase their tool. There's a writeup on solving this challenge with angr posted here. That said, i think most people solved with frida since this challenge lends itself to a dynamic approach. There are plenty of writeups out there right now on solving this challenge, so I will skip a lot of the common information and mostly focus on what is specific to my solution, the revenge library.
To get started, lets install and run this challenge. I ran it via an emulator, but you can run it directly on your phone hardware if you want. The following is how you can load up the challenge with revenge:
from revenge import Process, types, common, devices
android = devices.AndroidDevice(type="usb")
android.install("veryandroidoso.apk")
p = android.spawn("*ooo*", gated=False, load_symbols=["*dex", "libnative-lib.so"])
First, we create an AndroidDevice object, that will automatically discover your android device, install the latest version of frida server to it, and then connect to it. The second line simply installs this apk. The final line tells revenge to spawn a new process, don't "gate" it (i.e.: let it fully start), and load up the symbols specifically for the dex file and libnative-lib.so. The later library was discovered via running it as will be shown below. You technically don't need that load_symbols directive, but by default it will attempt to load the symbols for EVERY loaded library, which turns out to take a little bit on an android emulator.
While we won't get into all the options for my tool here, looking at what libraries are present is generally useful. Take a peek at the following:
print(p.modules)
"""
+------------------------------------------------+----------------+-----------+----------------------------------------------------------------------------------------------------+
| name | base | size | path |
+------------------------------------------------+----------------+-----------+----------------------------------------------------------------------------------------------------+
| app_process64 | 0x72b0cf156000 | 0x8000 | /system/bin/app_process64 |
| libandroid_runtime.so | 0x72b0cb644000 | 0x1fb000 | /system/lib64/libandroid_runtime.so |
| libbinder.so | 0x72b0cd94d000 | 0xa3000 | /system/lib64/libbinder.so |
| libcutils.so | 0x72b0ce76b000 | 0x14000 | /system/lib64/libcutils.so |
| libhwbinder.so | 0x72b0cb84e000 | 0x2b000 | /system/lib64/libhwbinder.so |
| liblog.so | 0x72b0cdbd8000 | 0x1a000 | /system/lib64/liblog.so |
| libnativeloader.so | 0x72b0cdaae000 | 0x8000 | /system/lib64/libnativeloader.so |
| libutils.so | 0x72b0cbe1b000 | 0x21000 | /system/lib64/libutils.so |
| libwilhelm.so | 0x72b0cb374000 | 0x44000 | /system/lib64/libwilhelm.so |
| libc++.so | 0x72b0ce2c0000 | 0x100000 | /system/lib64/libc++.so |
| libc.so | 0x72b0cd50f000 | 0xf0000 | /system/lib64/libc.so |
| libm.so | 0x72b0ce6ca000 | 0x51000 | /system/lib64/libm.so |
| libdl.so | 0x72b0cb5b1000 | 0x5000 | /system/lib64/libdl.so |
| libmemtrack.so | 0x72b0cd785000 | 0x5000 | /system/lib64/libmemtrack.so |
| libandroidfw.so | 0x72b0cb462000 | 0x5a000 | /system/lib64/libandroidfw.so |
| libappfuse.so | 0x72b0cbc9e000 | 0xf000 | /system/lib64/libappfuse.so |
| libbase.so | 0x72b0cd1d7000 | 0x13000 | /system/lib64/libbase.so |
| libcrypto.so | 0x72b0ccbdb000 | 0x151000 | /system/lib64/libcrypto.so |
| libnativehelper.so | 0x72b0ccb88000 | 0x9000 | /system/lib64/libnativehelper.so |
| libdebuggerd_client.so | 0x72b0cb10a000 | 0x7000 | /system/lib64/libdebuggerd_client.so |
| libui.so | 0x72b0cb4d5000 | 0x26000 | /system/lib64/libui.so |
| libgraphicsenv.so | 0x72b0cd146000 | 0x4000 | /system/lib64/libgraphicsenv.so |
| libgui.so | 0x72b0cd083000 | 0xb2000 | /system/lib64/libgui.so |
| libsensor.so | 0x72b0cc34e000 | 0x1b000 | /system/lib64/libsensor.so |
| libcompiler_rt.so | 0x72b03dc48000 | 0x54000 | /system/lib64/libcompiler_rt.so |
| libwebviewchromium_loader.so | 0x72b03dc1e000 | 0x4000 | /system/lib64/libwebviewchromium_loader.so |
| base.odex | 0x72b035094000 | 0x10000 | /data/app/ooo.defcon2019.quals.veryandroidoso-PeOp_XuyROu7FjImPHN_CQ==/oat/x86_64/base.odex |
| libnative-lib.so | 0x72b034f6a000 | 0x5000 | /data/app/ooo.defcon2019.quals.veryandroidoso-PeOp_XuyROu7FjImPHN_CQ==/lib/x86_64/libnative-lib.so |
| gralloc.ranchu.so | 0x72b0348cc000 | 0x10000 | /vendor/lib64/hw/gralloc.ranchu.so |
| frida-agent-64.so | 0x72b031dd7000 | 0x154e000 | /data/local/tmp/re.frida.server/frida-agent-64.so |
| linux-vdso.so.1 | 0x7fffc76ac000 | 0x1000 | linux-vdso.so.1 |
| linker64 | 0x72b0ceff9000 | 0x120000 | /system/bin/linker64 |
+------------------------------------------------+----------------+-----------+----------------------------------------------------------------------------------------------------+
len(p.modules)
186
This is one such way to identify special loaded libraries for the apk. In this case, we can see "base.odex" (common for any apk) and "libnative-lib.so" (special for us). Not all apk will have special libraries, but this one does. Just for fun, we can take a look at the symbols:
native = p.modules['libnative-lib.so']
native.symbols
{'__cxa_atexit': 126101128388608,
'__cxa_finalize': 126101128388608,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m0': 126101128391200,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m1': 126101128391296,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m2': 126101128391392,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m3': 126101128391488,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m4': 126101128391584,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m5': 126101128391680,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m6': 126101128391776,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m7': 126101128391872,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m8': 126101128391984,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_m9': 126101128392096,
'Java_ooo_defcon2019_quals_veryandroidoso_Solver_ttt': 126101128391184,
's1': 126101128400912,
's2': 126101128401936,
's3': 126101128402960,
's4': 126101128405008,
's5': 126101128403984,
'_edata': 126101128405008,
'_end': 126101128406032,
'__bss_start': 126101128405008}
This shows us there are some Java bindings into functions named "m0" through "m9" and "ttt". It also shows symbols for "s1" - "s5" which are not directly exposed to the Java runtime. The numbers after are the current loaded addresses. This means, if you want to read what's at s1 directly, you can use that address.
Here's a quick look at the onCreate method for this challenge
protected void onCreate(Bundle paramBundle)
{
super.onCreate(paramBundle);
setContentView(2131099648);
Log.i("veryandroidoso", "started!");
Solver.cc = this;
paramBundle = (Button)findViewById(2131034114);
final EditText localEditText = (EditText)findViewById(2131034118);
paramBundle.setOnClickListener(new View.OnClickListener()
{
public void onClick(View paramAnonymousView)
{
paramAnonymousView = MainActivity.this.parse(localEditText.getText().toString());
if (paramAnonymousView != null)
{
if (Solver.solve(paramAnonymousView[0], paramAnonymousView[1], paramAnonymousView[2], paramAnonymousView[3], paramAnonymousView[4], paramAnonymousView[5], paramAnonymousView[6], paramAnonymousView[7], paramAnonymousView[8])) {
MainActivity.this.win();
} else {
MainActivity.this.fail();
}
MainActivity.this.finish();
return;
}
MainActivity.this.fail();
MainActivity.this.finish();
}
});
It's clear that our string input gets parsed by the parse function and then sent over to Solver.solve as 9 integers. I won't go over the parse routine, but effectively it just checks for "OOO{" + 18 lowercase or numbers + "}". It then interprets those numbers in two character pairs as hex, i.e.: "OOO{12}" would be 0x12.
The Solver.solve is a large function, mainly due to a ton of switch (or really, if/else) statements. Here's an example of the first section:
static boolean solve(int paramInt1, int paramInt2, int paramInt3, int paramInt4, int paramInt5, int paramInt6, int paramInt7, int paramInt8, int paramInt9)
{
int j = scramble(13);
if (paramInt1 == 0) {
i = m0(100, getSecretNumber(j));
} else if (paramInt1 == 1) {
i = m0(190, getSecretNumber(j));
} else if (paramInt1 == 2) {
i = m0(88, getSecretNumber(j));
} else if (paramInt1 == 3) {
i = m0(240, getSecretNumber(j));
} else if (paramInt1 == 4) {
i = m0(97, getSecretNumber(j));
} else if (paramInt1 == 5) {
i = m0(216, getSecretNumber(j));
} else if (paramInt1 == 6) {
CLIPPED
if ((i & 0xFF) != 172) {
return false;
}
Effectively, it's looking up a resultant number based on our input and some secret number. From there, it's checking if the output is 172, and if not it will fail. This is obviously very helpful for us, since it allows us to brute force one character at a time. But right off the bat we have a few questions. Specifically, is scramble deterministic? What about getSecretNumber? With revenge, we don't actually have to reverse the source to find out. We can simply call those functions and see for ourselves.
Solver = p.java.classes['*ooo*.Solver']
#
Solver.scramble(13)()
# 80
Solver.scramble(13)()
# 80
Solver.getSecretNumber(80)()
# 113
Solver.getSecretNumber(80)()
# 113
What's happening here is that I'm asking revenge to instantiate a class object for me, and selecting (in this case via glob) the Solver class. Once I have this, I'm using this class to call it's method. Calling scramble a couple times, and getSecretNumber a couple times, I feel confident that those values are likely not changing. In fact, we can go ahead and enumerate all the values for these methods. This will be useful later on in the writeup, but I'll demonstrate here:
scramble_enum = []
for i in range(512):
scramble_enum.append(Solver.scramble(i)())
# [67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...]
We can do the same thing with getSecretNumber.This also allows us to easily see that scramble is not so random. With this in mind, let's use revenge to brute force what the correct "m0" function call should be.
j = Solver.scramble(13)()
j_secret = Solver.getSecretNumber(j)()
d = {}
for i in range(0, 255):
d[i] = Solver.m0(i, j_secret)()
for i,j2 in d.items():
if j2 == 172:
print(i)
So here, we're pretty much emulating what the Java is itself doing. We're creating j by calling scramble. We're then creating j_secret so we don't have to keep calling getSecretNumber (slow). We're then simply populating a lookup table all possible i values. Finally, we're looping through that and determining which i value creates the output that this specific check wants. One final step is to take that value (53 in this case), and look it up in the Java code to find out what input related to that. I.e.: ctrl-f for "m0(53,". This turns out to be 180 (which is 0xb4). Easy as that, we know the first to chars of our flag should be "b4".
At this point, you basically repeat this exact process for each check. Example of the next one:
j = Solver.scramble(j)()
j_secret = Solver.getSecretNumber(j)()
d = {}
for i in range(0, 255):
d[i] = Solver.m0(i, j_secret)()
for i,j2 in d.items():
if j2 == 6:
print(i)
Note I actually called scramble as the program does, specifically passing j again to get the next j value. It should be pointed out that some of the next checks use a bitmask other than 0xff, and thus end up with more than one possible "passing" outcome.
After repeating this same process, we finally get to the check for int parameter 9. Up to this point, we have ended up with a smallish search space. However, this final check does not allow us to play the same trick. Specifically, "m9" function is called first. This function takes as an argument an integer that is based on all previous steps. This adds confusion to our next step since we have many combinations up to this point that could be the right answer (i.e.: they didn't explicitly fail the check). Using the above techniques for running the function, we can call "m9" with various arguments, and then check "m8" function to see if it changes. Sure enough, the "m8" function is affected by the call to "m9" prior to it, and thus the ambiguity is tied together. What does this mean for us?
There are a few options here. For my purposes, at this point I noted that at max, we have 255 options for the final integer. That, combined with our already decreased search space, should allow us to brute force the final solution out. However, after running Solver.solve a few times, i discovered it is quite slow.
Looking at the source for those calls to scramble and getSecretNumber, I could see sub calls to sleep and other more complicated things. This all seemed very unnecessary, since the output is static and effectively a lookup table. So why not actually make it into one?
That's what I did first here. revenge exposes an easy way to replace a given method in java. Sadly, this still requires some javascript writing, but I promise it's not bad. I used the exact same process for both scramble and getSecretNumber. From above, we already enumerated the static lists that these methods expose. Therefore, all I want to do is replace the method with a very quick and simple lookup of the correct value. This can be done by using the magic property "implementation".
The implementation property can be used generically on any Java method. Here's how to use it in this case:
Solver.scramble.implementation = """function (i) { return [67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, ...][i];}"""
Easy as that, we've just replaced the scramble method of Solver with our function, which simply takes the integer passed in and returns the corresponding value in the list. Doing the exact same thing with getSecretNumber, we find that Solver.solve runs a bunch faster.
At this point, you might think we would repeat the for type loops from above to brute force the solution out of Solver. The problem with that is, while it would eventually find the answer, it would take too long. Calling in the way above is nice in that it's a synchronous call, and provides you the answer directly back. The downside is that it will be slow, due to the setup overhead involved in creating a new script, injecting it, scheduling it for run, and finally getting the result back. For things that require more performance, I've created a "BatchContext".
A "BatchContext" is a class in revenge that handles batching up requests. The backend is more complicated than that, but the idea is basically to keep a single Frida script running (instead of injecting, running, and removing each time), and communicate with it via send/recv in batches. The size of these batches is variable, and right now is 2048 items, where each item is a string that will be evaluated by the context. This will hopefully make more sense with an example from this challenge.
In this case, we want to brute force Solver.solve. Since we want to try a lot of possible values, we're going to use a BatchContext. This BatchContext will return the results of each instruction to us to whatever callable we give it. The things returned will be returned as a list of tuples (item, return), where item is the string we asked it to execute, and return is the result value of it. Here's how it works out for our case:
def on_message(messages):
for item, ret in messages:
if ret is not False:
print("Found one: " + item)
with p.java.BatchContext(on_message=on_message) as context:
for combo in itertools.product(i1_resolved, i2_resolved, i3_resolved, i4_resolved, i5_resolved, i6_resolved, i7_resolved, i8_resolved, range(256)):
Solver.solve(*combo)(context=context)
Those ix_resolved arguments are simply the lists I discovered from the steps above. Our on_message handler is going to be doing the logic to determine if we have discovered a winning solution or not. It will be called whenever our Frida script's buffer is full, and will be given a list of messages. We know from the source of this challenge that when solve fails it returns False, and when it succeeds it returns True. Thus, all we're doing in our callback is iterating over what was executed and checking if the return was True or False. When we find a winner, we print it out to the screen.
The BatchContext makes use of the "with" python construct. While it's possible to run this context without that, it's not recommended. The internal loop makes use of itertools to actually iterate through the possibilities (which is super handy on many occasions). It takes the iteration and passes it directly into the Java.solve call, with the extra "context=context" being the critical part here. That "context=context" tells revenge to run the script in the batch context provided, which is why we also don't bother to check the output from this call, as it will be None.
After a short wait (i think it took a minute or so), we get the following message printed out to the screen:
Found one: Java.use('ooo.defcon2019.quals.veryandroidoso.Solver').solve(250,180,52,22,72,73,68,190,186)
We can tell from that call, that the winning numbers are 250, 180, 52, 22, 72, 73, 68, 190, 186. Simply hex it up and we have the flag "OOO{fab43416484944beba}".