redpwnCTF 2020 - JavaIsEZ2 (497pt)

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): patch

(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}

comments powered by Disqus