redpwnCTF 2020 - JavaIsEZ2 (497pt)
JVM reversing + patching
June 25, 2020
rev
java
JavaIsEZ2 (497pt)
Rev
Files:
Overview:
We are given a Java class file and no remote connection. A class file contains compiled java bytecode that runs on the JVM. There are quite a few java decompilers that can produce farily good results so this was my first step.
Part 0: disassembly
Unfortunately, none of the decompilers I used were able to produce a result that looked reasonable (and most produced wildly different results). So my next approach was to dive into the bytecode itself.
We can use javap -c JavaIsEZ2.class to dump the disassembly:
public class JavaIsEZ2 {
static {};
Code:
0: iconst_2
1: anewarray #18 // class java/lang/String
4: dup
5: iconst_0
6: ldc #1 // String redpwn
8: aastore
9: dup
10: iconst_1
11: ldc #2 // String ctf2020
13: aastore
14: putstatic #19 // Field a:[Ljava/lang/String;
17: iconst_4
18: newarray long
20: dup
21: iconst_0
22: ldc2_w #20 // long 8248156489741230770l
25: lastore
26: dup
27: iconst_1
28: ldc2_w #22 // long -5342668067454976247l
31: lastore
32: dup
33: iconst_2
34: ldc2_w #24 // long -889275714l
37: lastore
38: dup
39: iconst_3
40: ldc2_w #26 // long -559038737l
43: lastore
44: putstatic #28 // Field a:[J
47: return
public static void main(java.lang.String[]);
Code:
0: goto 133
3: astore_1
4: aload_2
5: invokevirtual #31 // Method java/lang/String.toCharArray:()[C
8: astore_2
...
...
...
483: return
484: jsr 97
487: return
Exception table:
from to target type
53 95 53 Class java/lang/IllegalMonitorStateException
133 155 167 any
155 159 167 any
162 164 167 any
public static long print(long);
Code:
0: getstatic #32 // Field java/lang/System.out:Ljava/io/PrintStream;
3: lload_0
4: invokevirtual #51 // Method java/io/PrintStream.println:(J)V
7: lload_0
8: lreturn
}
So our class contains two methods: long JavaIsEZ2.print(long) and void JavaIsEZ2.main(String[]). The print function appears just to call System.out.println(arg) however the main function appears to do a lot more.
Additionally, we see an exception table:
Exception table:
from to target type
53 95 53 Class java/lang/IllegalMonitorStateException
133 155 167 any
155 159 167 any
162 164 167 any
This could explain why some decompilers were having a hard time reconstructing the logic.
Brief into to JVM
Before we jump into the disassembly, let’s go over some details about the JVM. Personally, I have not dealt in detail with java bytecode before so this was a great learning experience.
Here’s a handy instruciton reference: https://en.wikipedia.org/wiki/Java_bytecode_instruction_listings
Instructions in the JVM operate on an operand stack that contains 4 byte words. Additionally, values can be temporarily stored in local variables (for example iload_0, istore_0, etc…). Method calls on Java objects use instructions such as invokevirtual with a “method reference index” that identifies a certain method from a constant lookup table. The java disassembler is able to helpfully give us the full method name.
Within a method, the JVM can use subroutines with the jsr instruction and jump back with the ret instruction. There are no specific arguments or return values for subroutines, the existing context is simply preserved.
Another slight catch is that long and double are 8 byte values and actually take up two spaces on the operand stack.
try/catch blocks are implemented with an exception table that defines a region of bytecode and an exception handler address.
Part 1: reversing
Ok with that intro out of the way, let’s start reversing…
Our first instruction jumps to the entrypoint:
0: goto 133
[entrypoint]
133: aconst_null
134: checkcast #35 // class RedpwnCTF2020
137: ldc #5 // String java.utils.ArrayList
139: invokestatic #36 // Method java/lang/Class.forName:(Ljava/lang/String;)Ljava/lang/Class;
142: invokestatic #37 // Method java/util/concurrent/ThreadLocalRandom.current:()Ljava/util/concurrent/ThreadLocalRandom;
145: iconst_1
146: bipush 28
148: invokevirtual #38 // Method java/util/concurrent/ThreadLocalRandom.nextInt:(II)I
151: putstatic #39 // Field a:I
154: pop2
155: aload_0
156: aconst_null
157: astore_0
158: monitorexit
159: goto 133
162: aconst_null
163: athrow
164: goto 133
This section is a bit strange, it appears to try to cast null as RedpwnCTF2020 and then call Random.nextInt(1,28), storing the result in a local variable. At the end we simply loop back. The exeption table contains the following entry: 133 155 167 any so I assume one of these calls intentionally throws an exception causing execution to jump to 167.
167: ifnull 133
170: getstatic #39 // Field a:I (random num)
173: aload_0
174: swap [arg, rand]
175: istore 9 rand
177: arraylength [len]
178: iconst_1 [len, 1]
179: if_icmpne 484 len(arg)
182: iload 9 rand
184: ifne 162
In the next section, we check if the main argument (loaded with aload_0) has length 1. If not, we jump to 484:
484: jsr 97
487: return
97: astore 8
99: iconst_0
100: getstatic #32 // Field java/lang/System.out:Ljava/io/PrintStream;
103: ldc #3 // String That is pepega
105: invokevirtual #33 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
108: invokestatic #34 // Method java/lang/System.exit:(I)V
111: aload_0
112: ifnonnull 253
115: ret 8
This prints the error message “That is pepega” and exits.
If our input has length one (meaning we passed a single string argument), we continue at 187:
187: iconst_1
188: istore 9 [9 = 1]
190: aload_0
191: iconst_0
192: aaload [str]
193: invokevirtual #40 // Method java/lang/String.length:()I
196: bipush 32
198: if_icmpne 484
201: iload 9
203: ifeq 133
Here we load the first string arugment and ensure the length is 32. I assume the use of local variable 9 here is just to confuse any decompilers as it doesn’t actually affect the execution path.
206: iconst_0
207: istore 9 [9 = 0]
209: new #41 // class java/lang/StringBuilder
212: dup
213: invokespecial #42 // Method java/lang/StringBuilder."<init>":()V
216: ldc #6 // String flag{
218: invokevirtual #43 // Method java/lang/StringBuilder.append:(Ljava/lang/CharSequence;)Ljava/lang/StringBuilder;
221: aload_0
222: iconst_0
223: aaload
224: invokevirtual #43 // Method java/lang/StringBuilder.append:(Ljava/lang/CharSequence;)Ljava/lang/StringBuilder;
227: ldc #7 // String }
229: invokevirtual #43 // Method java/lang/StringBuilder.append:(Ljava/lang/CharSequence;)Ljava/lang/StringBuilder;
232: invokevirtual #44 // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
In this section, we see a StringBuilder being used to construct the string: flag{argument}.
235: astore_2 2 = flag{my_str}
236: jsr 3
239: iload_3 [hash]
240: ldc #8 // int 1140336659
242: if_icmpne 484
245: iload 9
247: ifne 162
The string is stored in local variable 2 and then we call the subroutine at address 3. Finally, local variable 3 (assumed to be the return value) is compared to the fixed value 1140336659.
Let’s look at this subroutine:
3: astore_1
4: aload_2
5: invokevirtual #31 // Method java/lang/String.toCharArray:()[C
8: astore_2 [2 = f.toCharArray()]
9: iconst_0
10: istore_3 [3 = 0]
11: aload_0
12: ifnull 190
15: iconst_0
16: istore 4 [4 = 0]
We start by converting the string to a char array.
18: iload 4
20: aload_2
21: arraylength [4, len]
22: iconst_m1
23: ixor [4, len ^ 0xff]
24: iconst_2
25: iadd [4, [~len] + 2]
26: ineg [4, ~[[~len]+2]]
27: if_icmpeq 46
30: aload_2
31: monitorenter
32: iload 4
34: iflt 253
37: iload 4
39: iconst_1
40: iadd
41: istore 4 [4 += 1]
43: goto 18
This section appears to loop over the char array although I don’t fully understand the purpose (and the values are not used anywhere).
46: iconst_0
47: istore 4 [4 = 0]
49: iconst_1
50: istore 10 [10 = 1]
52: aconst_null
53: pop
54: iload 10 [1]
56: ifeq 95
59: iload 10
61: iconst_1
62: isub
63: istore 10
65: bipush 31
67: iload_3
68: imul [0]
69: aload_2
70: iload 4 [arr, #4]
72: caload [arr[#4]]
73: iadd
74: istore 3 [3 = arr[#4] + 3]
76: aload_2
77: monitorexit
78: iconst_1
79: iload 4
81: iadd
82: istore 4 [4 += 1]
84: iload 10
86: iflt 133
89: iconst_1
90: istore 10
92: goto 54
95: ret 1
Here we find the meat of the function and we see that it’s computing a hash over the string input:
def hash(x):
h = 0
for c in x:
h = ((h * 31) + ord(c))
h &= 0xffffffff # truncate to 32 bits
return h
So our first condition is:
hash('flag{' + x + '}') == 1140336659
Since the hash is lossy, this isn’t enough to figure out the flag.
Let’s continue:
253: iconst_0
254: istore 7 [7 = 0]
256: aload_0
257: iconst_0
258: aaload [arg]
259: iload 7
261: ifne 273
[first half]
264: iconst_0
265: bipush 16
267: invokevirtual #45 // Method java/lang/String.substring:(II)Ljava/lang/String;
270: goto 278
[second half]
273: bipush 16
275: invokevirtual #46 // Method java/lang/String.substring:(I)Ljava/lang/String;
278: bipush 16
280: invokestatic #47 // Method java/lang/Long.parseLong:(Ljava/lang/String;I)J
283: lstore 5 Long.parseLong(str, 16)
Here we initialize a local variable 7 to zero. Based on this value we select one of two substrings:
int local_7 = 0
int local_5;
if (local_7) {
local_5 = Long.parseLong(arg.substring(0,16), 16);
} else {
local_5 = Long.parseLong(arg.substring(16), 16);
}
So we know now that our input must be a hex string.
285: getstatic #19 // Field a:[Ljava/lang/String;
288: iload 7
290: aaload
291: astore_2 [2 = ref]
292: jsr 3
295: iload_3 [hash]
296: i2l [hash]
297: dup2 [hash, hash]
298: bipush 32
300: lshl
301: lor [hash | (hash << 32)]
302: getstatic #28 // Field a:[J
305: iload 7
307: laload
308: lxor [xor]
309: lload 5 [xor, v]
311: getstatic #28 // Field a:[J
314: iload 7
316: iconst_2
317: iadd
318: laload [xor,v,#28[l+2]]
319: lmul
320: lcmp
Next, we load index local_7 from a static string array containing ["redpwn", "ctf2020"] and compute a hash on it. This hash value is expanded to a long value and xored with a[local_7] where a is a static long array with the values: [8248156489741230770, -5342668067454976247, -889275714, -559038737]. Finally, we multiply our parsed long value with a[local_7+2] and compare it to the xored value.
This loops once more with local_7 == 1 for the other substring and if both checks pass, it prints Oh nice, you found my key :O.
Part 2: solving
At this point, my plan was to replicate this logic in python and figure out the equations needed to solve. Essentially, we would end up with two equations:
A * x1 = B (mod 2^64)
C * x2 = D (mod 2^64)
where A,B,C,D are constants and we need to solve for x1 and x2 (each half of the flag).
I reimplemented the hashing and hash expansion in python and came up with values, however they didn’t work :(.
In order to figure out the issue, I spent some time looking for way to debug java bytecode.
Unfortunately, after about 4 hours and trying nearly a dozen tools, I was unable to find a good JVM debugger that could let me single step bytecode and/or view the operand stack. It seems like most existing java debuggers are intended for debugging with source and don’t provide the low-level features that I’m used tool with tools like gdb. (If anyone knows of a good java debugger please let me know!)
At this point, I shifted my goal to patching the class file. If I could inject print statements, I would be able to examine the intermediate values and figure out the correct equations to solve. This process took another few hours of searching to find a tool that could actually patch class files that would run afterwards. (I imagine some of the difficulty is that I’m running on a newer JDK than most of these tools were built for).
I ended up finding this excellent tool: https://github.com/GraxCode/JByteMod-Beta
To solve the problem, I wanted to print out the two long values right before comparison. I came up with the following bytecode:
Operand stack:
...
[val_b] (2 values)
[val_a] (2 values)
Injected bytecode (between lmul and lcmp):
(The usage of pop2, dup2, etc…) is necessary because long values take up two positions on the stack and cannot be split.
Additionally, I patched the first hash check to always pass so I could reach this point. I came up with the following equations:
18446744072820275902 x1 = 10198587584865437604 mod 18446744073709551616
18446744073150512879 x2 = 17687011372936338328 mod 18446744073709551616
I plugged this into wolfram alpha to get:
x1 = 0x1fc34325972c1de8
x2 = 0x4f162351e2a0bb6e
flag{1fc34325972c1de84f162351e2a0bb6e}