Hacking Java Bytecode for Programmers (Part4) – Krakatau And The Case Of The Integer Overflow

Jun 25, 2013

Index

Introduction

A funny thing happened on the way to crafting my next blog post. I met this very talented twenty-one year old student who goes by the handle Storyyeller, on an online forum. He offered to help educate me on how to write bytecode by hand. How freaking pro.

Along the way, Storyyeller mentioned Krakatau. Software that he is actively writing to help with the assembling and disassembling of Java class files. He also sent me a link to a command line application he had written. This application is a puzzle. To solve it, you must hack it. Which gave me the idea that for this article, we are going to reverse engineer Storyyeller’s application. Download the following crackme1.1.jar application now.

As a reminder, please go back and read the other articles if you need to catchup.

CHALLENGE ACCEPTED!

The first thing we will do after downloading the .zip file, is unzip the .zip archive found inside. Then run the program.

$ java -jar crackme1.1.jar 
Please enter a 32bit signed int
$ java -jar crackme1.1.jar 1
Incorrect
$ java -jar crackme1.1.jar -908
Incorrect
$

Storyyeller said, that in order to crack this application, one needs to enter a 32bit integer to get the program to print “Correct”.

Given that rule set, we need to uncompress the .jar file to see what is going on. If you are not aware, a Java .jar file is essentially a zip archive. It is a package/container that holds all the needed binaries and libraries for the application to function, made this way primarily for ease of distribution.

$ unzip crackme1.1.jar
Archive:  crackme1.1.jar
  inflating: META-INF/MANIFEST.MF    
  inflating: Code.class              
  inflating: author.txt              
$

Unzipping the .jar dumps the contents and we can see that there are three files.

  1. The MANIFEST.MF file enclosed in the META-INF directory
  2. The author.txt file
  3. The _Code.class_ binary file

Unlike C, where the main() function is always used to tell the compiler “START THE PROGRAM HERE”, the _MANIFEST.MF _file found in a .jar archive can be used to specify the program entry point. It can also be used to set the CLASSPATH along with several other parameters. In a large application the information in this file could prove useful, but for us, the .jar contained only a single binary file. Code.class. So it is obvious what binary file we should operate on. (The author.txt file should be self explanatory)

At this point run javap on the_ Code.class_ file to see what is dumped.

$ javap -verbose Code.class

The result you will recieve, is rather, well, odd.

img

An endless printing of new line characters will be dumped to screen. If we redirect the output to file and wait a while, eventually a >2GB file will materialize. No bueno.

The initial take away here is that _javap_ can be manipulated. Lets try and figure out how Storyyeller is screwing with our output.

The Hard Way

In order to do this, I ended up writing a script to parse the constant pool of the Code.class file. The two import pieces of information found when parsing the Constant Pool where at index #34 and #35.

Full Output

  1 $ ./dis.py Code.class
  2 Magic           cafebabe
  3 Minor           
  4 Major           49
  5 ConstantPoolCount   38
  6  
  7 CONSTANT_Utf8_info { 
  8     pool_index  hex_offset  byte_offset tag length  bytes
  9     1      0xa     10     01  17 6a
 10 }
 11 CONSTANT_Utf8_info { 
 12     pool_index  hex_offset  byte_offset tag length  bytes
 13     2      0x1e        30     01  6  64
 14 }
 15 CONSTANT_Utf8_info { 
 16     pool_index  hex_offset  byte_offset tag length  bytes
 17     3      0x27        39     01  39 28
 18 }
 19 CONSTANT_Utf8_info { 
 20     pool_index  hex_offset  byte_offset tag length  bytes
 21     4      0x51        81     01  8  69
 22 }
 23 CONSTANT_Utf8_info { 
 24     pool_index  hex_offset  byte_offset tag length  bytes
 25     5      0x5c        92     01  3  28
 26 }
 27 CONSTANT_Utf8_info { 
 28     pool_index  hex_offset  byte_offset tag length  bytes
 29     6      0x62        98     01  8  43
 30 }
 31 CONSTANT_Utf8_info { 
 32     pool_index  hex_offset  byte_offset tag length  bytes
 33     7      0x6d        109        01  9  49
 34 }
 35 CONSTANT_Utf8_info { 
 36     pool_index  hex_offset  byte_offset tag length  bytes
 37     8      0x79        121        01  31 50
 38 }
 39 CONSTANT_Utf8_info { 
 40     pool_index  hex_offset  byte_offset tag length  bytes
 41     9      0x9b        155        01  16 6a
 42 }
 43 CONSTANT_Utf8_info { 
 44     pool_index  hex_offset  byte_offset tag length  bytes
 45     10     0xae        174        01  3  6f
 46 }
 47 CONSTANT_Utf8_info { 
 48     pool_index  hex_offset  byte_offset tag length  bytes
 49     11     0xb4        180        01  21 4c
 50 }
 51 CONSTANT_Utf8_info { 
 52     pool_index  hex_offset  byte_offset tag length  bytes
 53     12     0xcc        204        01  19 6a
 54 }
 55 CONSTANT_Utf8_info { 
 56     pool_index  hex_offset  byte_offset tag length  bytes
 57     13     0xe2        226        01  7  70
 58 }
 59 CONSTANT_Utf8_info { 
 60     pool_index  hex_offset  byte_offset tag length  bytes
 61     14     0xec        236        01  21 28
 62 }
 63 CONSTANT_Utf8_info { 
 64     pool_index  hex_offset  byte_offset tag length  bytes
 65     15     0x104       260        01  4  43
 66 }
 67 CONSTANT_Utf8_info { 
 68     pool_index  hex_offset  byte_offset tag length  bytes
 69     16     0x10b       267        01  4  6d
 70 }
 71 CONSTANT_Utf8_info { 
 72     pool_index  hex_offset  byte_offset tag length  bytes
 73     17     0x112       274        01  22 28
 74 }
 75 CONSTANT_Class_info {
 76     pool_index  hex_offset  byte_offset tag name_index  
 77     18     0x12b       299        07  1
 78 }
 79 CONSTANT_Class_info {
 80     pool_index  hex_offset  byte_offset tag name_index  
 81     19     0x12e       302        07  9
 82 }
 83 CONSTANT_Class_info {
 84     pool_index  hex_offset  byte_offset tag name_index  
 85     20     0x131       305        07  12
 86 }
 87 CONSTANT_Class_info {
 88     pool_index  hex_offset  byte_offset tag name_index  
 89     21     0x134       308        07  15
 90 }
 91 CONSTANT_NameAndType_info {
 92     pool_index  hex_offset  byte_offset tag name_index  descriptor_index
 93     22     0x137       311        0c  0002        0003
 94 }
 95 CONSTANT_NameAndType_info {
 96     pool_index  hex_offset  byte_offset tag name_index  descriptor_index
 97     23     0x13c       316        0c  0004        0005
 98 }
 99 CONSTANT_NameAndType_info {
100     pool_index  hex_offset  byte_offset tag name_index  descriptor_index
101     24     0x141       321        0c  000a        000b
102 }
103 CONSTANT_NameAndType_info {
104     pool_index  hex_offset  byte_offset tag name_index  descriptor_index
105     25     0x146       326        0c  000d        000e
106 }
107 CONSTANT_Methodref_info { 
108     pool_index  hex_offset  byte_offset tag class_index name_and_type_index
109     26     0x14b       331        0a  0012        0016
110 }
111 CONSTANT_Methodref_info { 
112     pool_index  hex_offset  byte_offset tag class_index name_and_type_index
113     27     0x150       336        0a  0012        0017
114 }
115 CONSTANT_Methodref_info { 
116     pool_index  hex_offset  byte_offset tag class_index name_and_type_index
117     28     0x155       341        0a  0014        0019
118 }
119 CONSTANT_Fieldref_info {
120     pool_index  hex_offset  byte_offset tag class_index name_and_type_index
121     29     0x15a       346        09  0013        0018
122 }
123 CONSTANT_String_info {
124     pool_index  hex_offset  byte_offset tag string_index
125     30     0x15f       351        08  0006
126 }
127 CONSTANT_String_info {
128     pool_index  hex_offset  byte_offset tag string_index
129     31     0x162       354        08  0007
130 }
131 CONSTANT_String_info {
132     pool_index  hex_offset  byte_offset tag string_index
133     32     0x165       357        08  0008
134 }
135 CONSTANT_Integer_info {
136     pool_index  hex_offset  byte_offset tag bytes       int_value
137     33     0x168       360        03  668f182d    1720653869
138 }
139 CONSTANT_Utf8_info { 
140     pool_index  hex_offset  byte_offset tag length  bytes
141     34     0x16d       365        01  65535  0a
142 }
143 CONSTANT_Class_info {
144     pool_index  hex_offset  byte_offset tag name_index  
145     35     0x1016f     65903      07  34
146 }
147 CONSTANT_NameAndType_info {
148     pool_index  hex_offset  byte_offset tag name_index  descriptor_index
149     36     0x10172     65906      0c  0022        000b
150 }
151 CONSTANT_Fieldref_info {
152     pool_index  hex_offset  byte_offset tag class_index name_and_type_index
153     37     0x10177     65911      09  0023        0024
154 }
155 $

We can see that a Utf8 string resides at index #34 in the constant pool. It’s length, in bytes, is 65535. A long string can easily indicate obfuscation. Lets make the string smaller.

Open the Code.class file with Bless and go to offset 0x16d.

img

Since we are in the Constant Pool portion of the binary file, 01 is the correct tag for a CONSTANT_Utf8 string.

The two bytes following the tag are the strings length. Converting FF FF to decimal gives us the value 65535. This again helps confirm that we are in the correct location of the file.

Lets find the end of the string by searching for the offset 0x1016f.

UPDATE: People have asked how I knew to go to offset 0x1016f. When I parsed the Contant Pool with my script, the output shows the beginning byte of every member in the Constant Pool. Since I knew where #34 and #35 started, I could just go to the start of #35 (0x1016f) and move back one byte to get to the end of index #34.

img

Again, still being inside the Constant Pool, we know that 07 is the tag for a CONSTANT_Class. Which if we look at the output from my script, we know to be located at index #35.

CONSTANT_Class_info {
    pool_index  hex_offset  byte_offset tag name_index

    35     0x1016f     65903      07  34
}

What we are going to do, is manually highlight the hex string and replace it with the Hexadecimal notation for a literal “Space” (\s in programmer speak).

img

Delete the large, multi-lined (lots of lines fall off the screen) segment of hexadecimal bytes that we have highlighted and replace it with a single hexadecimal value of 20.

img

We are not finished though, we need to then change FF FF to 00 01 to specify a string length of one.

0001

Make sure the file is saved and then run javap over Code.class again.

$ javap -verbose Code.class
...output truncated...
    65514: getstatic     #37                // Field " "." ":Ljava/io/PrintStream;
    65517: getstatic     #37                // Field " "." ":Ljava/io/PrintStream;
    65520: getstatic     #37                // Field " "." ":Ljava/io/PrintStream;
    65523: getstatic     #37                // Field " "." ":Ljava/io/PrintStream;
    65526: getstatic     #37                // Field " "." ":Ljava/io/PrintStream;
    65529: getstatic     #37                // Field " "." ":Ljava/io/PrintStream;
    65532: getstatic     #37                // Field " "." ":Ljava/io/PrintStream;
    Exception table:
       from    to  target type
           1    51    42   any
}
$

Eureka! Much more usable output and we really can put together a story of what Storyyeller did.

Storyyeller obviously knew that by creating a .class file in such a way, he woud basically make javap dump over 2GB of individual string characters, essentially DOS’ing javap.

 The Krakatau Way

In the previous section, I created a script and then we manipulated the file by hand using Bless. That is a lot of work! There HAS to be an easier way and luckily there is. We can use Krakatau.

First, delete the Code.class file and then unzip crackme1.1.jar again.

$ rm Code.class
$ unzip crackme1.1.jar
Archive:  crackme1.1.jar
replace META-INF/MANIFEST.MF? [y]es, [n]o, [A]ll, [N]one, [r]ename: A
  inflating: META-INF/MANIFEST.MF    
  inflating: Code.class              
  inflating: author.txt              
$

Then, clone Krakatau from github.

thedude$ git clone https://github.com/Storyyeller/Krakatau.git
Cloning into 'Krakatau'...
remote: Counting objects: 1135, done.
remote: Compressing objects: 100% (415/415), done.
remote: Total 1135 (delta 747), reused 1100 (delta 713)
Receiving objects: 100% (1135/1135), 413.12 KiB | 600 KiB/s, done.
Resolving deltas: 100% (747/747), done.
thedude$

Next, disassemble Code.class using Krakatau.

thedude$ python Krakatau/disassemble.py Code.class 
Krakatau  Copyright (C) 2012-13  Robert Grosse
This program is provided as open source under the GNU General Public License. 
See LICENSE.TXT for more details.
 
processing target Code.class, 1/1 remaining
Class written to /home/thedude/krak/Code.j
9.16616106033  seconds elapsed
thedude$

This will create a Code.j file that uses the same assembly manipulation syntax as the Jasmin assembler.

“Jasmin as an assembler takes ASCII descriptions of JVM Classes, written in a simple assembler-like syntax using the Java Virtual Machine instruction set. It converts them into binary JVM Class files, suitable for loading by a Java runtime system.”

Basically, instead of looking at hexadecimal like we did in the previous section, we will now have a file that will be much easier to manipulate.

Open the Code.j file using a text editor (I use vim) and goto line 21871.

I highlighted the text inside the single quotes and replaced that big long string with the word Krakatau.

 1         getstatic [_37]
 2         getstatic [_37]
 3         getstatic [_37]
 4         getstatic [_37]
 5         getstatic [_37]
 6         getstatic [_37]
 7         getstatic [_37]
 8         getstatic [_37]
 9 .end method
10  
11 .const [_34] = Utf8 'Krakatau'
12 .const [_35] = Class [_34]
13 .const [_37] = Field [_35] [_34] Ljava/io/PrintStream;

Save the file and use Krakatau to assemble Code.j.

$ python Krakatau/assemble.py Code.j
Krakatau  Copyright (C) 2012-13  Robert Grosse
This program is provided as open source under the GNU General Public License. 
See LICENSE.TXT for more details.
 
Processing file Code.j, 1/1 remaining
Class written to /home/thedude/krak/Code.class
$

Now run javap over our newly created Code.class file.

    65448: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65451: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65454: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65457: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65460: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65463: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65466: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65469: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65472: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65475: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65478: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65481: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65484: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65487: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65490: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65493: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65496: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65499: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65502: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65505: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65508: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65511: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65514: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65517: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65520: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65523: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65526: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65529: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    65532: getstatic     #14                // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    Exception table:
       from    to  target type
           1    51    42   any
}
thedude$

YES! That output looks very familiar. Except this time around, it only took a couple minutes to get to this point.

Again, use vim or your favorite text editor to open the Code.j file and remove the L51 label and all the getstatic calls beneath it.

Also, on line 9, since we removed the L51 label, we need to respecify the bounds of the method.

FROM

.catch [] from L1 to L51 using L42

TO

.catch [] from L1 to L42 using L42

Your entire Code.j file should now look like this.

.version 49 
.class super final public Code
.super java/io/PrintStream
 
.method static final synchronized public main : ([Ljava/lang/String;)V
        .limit stack 2
        .limit locals 1
        .catch [] from L1 to L42 using L42
        aload_0
L1:
        jsr L7
        getstatic [_37]
L7:
        astore_0
        iconst_0
        aaload
        invokestatic java/lang/Integer decode (Ljava/lang/String;)Ljava/lang/Integer;
        invokevirtual java/lang/Integer intValue ()I
        bipush -37
        imul
        bipush 42
        iadd
        ldc 1720653869
        if_icmpne L32
        ldc ‘Correct!’
        goto L34
L32:
        ldc ‘Incorrect’
L34:
        getstatic java/lang/System out Ljava/io/PrintStream;
        swap
        invokevirtual java/io/PrintStream println (Ljava/lang/String;)V
        return
L42:
        pop
        ldc ‘Please enter a 32bit signed int’
        goto L34
        getstatic [_37]
.end method
 
.const [_34] = Utf8 ‘Krakatau’
.const [_35] = Class [_34]
.const [_37] = Field [_35] [_34] Ljava/io/PrintStream;

Assemble our Code.j file using Krakatau.

$ python Krakatau/assemble.py Code.j
Krakatau  Copyright (C) 2012-13  Robert Grosse
This program is provided as open source under the GNU General Public License. 
See LICENSE.TXT for more details.
 
Processing file Code.j, 1/1 remaining
Class written to /home/thedude/krak/Code.class
$

Run javap over the newly created Code.class file.

thedude$ javap -c Code.class 
public final class Code extends java.io.PrintStream {
  public static final synchronized void main(java.lang.String[]);
    Code:
       : aload_0       
       1: jsr           7
       4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
       7: astore_0      
       8: iconst_0      
       9: aaload        
      10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
      13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
      16: bipush        -37
      18: imul          
      19: bipush        42
      21: iadd          
      22: ldc           #4                  // int 1720653869
      24: if_icmpne     32
      27: ldc           #2                  // String Correct!
      29: goto          34
      32: ldc           #3                  // String Incorrect
      34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
      37: swap          
      38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      41: return        
      42: pop           
      43: ldc           #1                  // String Please enter a 32bit signed int
      45: goto          34
      48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
    Exception table:
       from    to  target type
           1    42    42   any
}
thedude$

Nice! This output makes much more sense. We can now begin to try and figure out what the required 32bit integer is.

Stepping through the logic

We can easily see that there is a single Main() method.

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

On operation 9, we can see the aaload opcode. Indicating it is loading argument[0] onto the stack.

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

10 is invoking the method Integer.decode on argument[0].

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

Operation 13 is casting the value as an int.

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

This is where things get interesting. Now that argument[0] is cast as an integer an on the stack, at operation 16, you can see Storyyeller used bipush to push integer -37 onto the operand stack.

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

He then multiplies the integer we supplied with -37 using imul at operation 18.

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

The result is kept on the stack. Storyyeller then pushes the integer 42 at Operation 19, again using bipush, onto the operand stack.

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

Our result along with integer 42 are added using iadd on operation 21.

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

At operation 22 the integer 1720653869 is called onto the stack using ldc and Storyyeller then compares 1720653869 to the result using the if_icmpne at Operation 24.

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

If the mathematical result (using our supplied integer) and 1720653869 are NOT equal, jump to operation 32 and print “Incorrect” else print “Correct!”;

 1 $ javap -c Code.class 
 2 public final class Code extends java.io.PrintStream {
 3   public static final synchronized void main(java.lang.String[]);
 4     Code:
 5        0: aload_0       
 6        1: jsr           7
 7        4: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
 8        7: astore_0      
 9        8: iconst_0      
10        9: aaload        
11       10: invokestatic  #20                 // Method java/lang/Integer.decode:(Ljava/lang/String;)Ljava/lang/Integer;
12       13: invokevirtual #24                 // Method java/lang/Integer.intValue:()I
13       16: bipush        -37
14       18: imul          
15       19: bipush        42
16       21: iadd          
17       22: ldc           #4                  // int 1720653869
18       24: if_icmpne     32
19       27: ldc           #2                  // String Correct!
20       29: goto          34
21       32: ldc           #3                  // String Incorrect
22       34: getstatic     #29                 // Field java/lang/System.out:Ljava/io/PrintStream;
23       37: swap          
24       38: invokevirtual #35                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
25       41: return        
26       42: pop           
27       43: ldc           #1                  // String Please enter a 32bit signed int
28       45: goto          34
29       48: getstatic     #14                 // Field Krakatau.Krakatau:Ljava/io/PrintStream;
30     Exception table:
31        from    to  target type
32            1    42    42   any
33 }
34 $

Use The Mathz Luke

At this point, we could express the value we need to derive with the following equation.

x(-37) – 42 = 1720653869

Obviously we need to solve for x. Which begs the question.

What 32 bit number could we enter into Storyyeller’s application in order for it to eventually equal 1720653869?

Using the following equation, should yield our answer.

(1720653869/-37) – 42 = x

But instead, we find that x is an not an integer and is irreducible.

-172065231537 (irreducible)

WTH?

Idea

It is at this point where one should realize that Storyyeller has royally screwed with us. The given problem is not solvable in the traditional sense. Which means that we need to get more creative.

Hopefully his cli application is open to a integer overflow exploit.

Integer Overflow

1100110100011110001100000101101 is the binary representation of 1720653869 but Storyyeller isn’t validating the bitness. What this means, is that we can trick the application into misinterpreting the result of Storyyeller’s initial equation x(-37) + 42 for our favor.

“WAT?” you ask.

I feel you. It really is kind of confusing at first. Have a look at this.

answer      	x           	overflow	binary                               
1720653869.0	-46504157.4865	                        1100110100011110001100000101101

One way to test our hypothesis, is to continually add 2^31 to our answer as that is the amount of bits in a 32 bit system. Like a clock or safe, we will continue to flip the bits until either we run out of targetable 32bit numbers or we find our answer.

(NOTE: Ordinarily you would use some modular arithmetic to solve this. But I’m going to use a show/do methodolgy to hopefully make more sense on what actually happens under the hood when an integer overflows)

The first time we add 2^31 we get the following.

answer      	x           	overflow	binary                               
1720653869.0	-46504157.4865	        	      1100110100011110001100000101101
3868137517.0	-104544256.081	       1	     11100110100011110001100000101101

Essentially we just added 1 bit to the end of the binary number (dont forget the end is on the left). You can see that the overflow column reminds us that there is 1 overflow bit and that in that space, we have assigned a binary “1”. Again, X is what we are trying to solve for, it needs to be a 32bit integer. -104544256.081 obviously isn’t as we can see it has a remainder.

So lets do it again by adding 2^31.

answer      	x           	overflow	binary                               
1720653869.0	-46504157.4865	        	      1100110100011110001100000101101
3868137517.0	-104544256.081	       1	     11100110100011110001100000101101
6015621165.0	-162584354.676	      10	    101100110100011110001100000101101

Still no luck. Lets use some code to print a bunch of values for us to analyze.

# We know Storyyeller is evaluating that our input, after multiplication and addition, equals 1720653869
# So the following expression should help articulate trying to solve for x
# x(-37) + 42 = 1720653869
# Love Love Love WolframAlpha
# http://www.wolframalpha.com/input/?i=x%28-37%29+*+42+%3D+1720653869
 
import re
import math
 
def getOverflow(original, derivative):
        needle = str(bin(original))[2:] + "$"
        haystack = str(bin(int(derivative)))[2:]
        overflow = re.sub(needle, '', haystack)
        return overflow
 
def calcAnswer(answer):
        # 2 ^ 31
        bit_offset = 2147483648
        # start the sequence at zero
        answer_sequence = 0
        #bit_ceiling = 2147483648
        #bit_floor = (bit_offset * -1) + 1
        print
        print "%s\t%s\t%s\t%s" % ('answer'.ljust(12),'x'.ljust(12),'overflow'.ljust(8),'binary'.ljust(37))
        while True:
 
                if(answer_sequence == 0):
                        # if 0 assign the answer with no offset
                        answer_sequence = float(answer)
                else:
                        # else add in the offset to flip the binary bit
                        answer_sequence = float(answer_sequence) + float(bit_offset)
 
                x = (answer_sequence - 42) / -37
                overflow = getOverflow(answer,answer_sequence)
                binary = str(bin(int(answer_sequence)))[2:]
                print "%s\t%s\t%s\t%s" % (answer_sequence,x, overflow.rjust(8),binary.rjust(37))
                # must be rational
                # if we wanted more logic, we could add a check to validate bitness 
                # and break if the bitness grew past 32bit.
                if(int(x) == float(x)):
                        print "The solution is %s" % int(x)
                        break
 
        print

calcAnswer(1720653869)

And if we run it.

$ python mathz.py 
answer      	x           	overflow	binary                               
1720653869.0	-46504157.4865	        	      1100110100011110001100000101101
3868137517.0	-104544256.081	       1	     11100110100011110001100000101101
6015621165.0	-162584354.676	      10	    101100110100011110001100000101101
8163104813.0	-220624453.27	      11	    111100110100011110001100000101101
10310588461.0	-278664551.865	     100	   1001100110100011110001100000101101
12458072109.0	-336704650.459	     101	   1011100110100011110001100000101101
14605555757.0	-394744749.054	     110	   1101100110100011110001100000101101
16753039405.0	-452784847.649	     111	   1111100110100011110001100000101101
18900523053.0	-510824946.243	    1000	  10001100110100011110001100000101101
21048006701.0	-568865044.838	    1001	  10011100110100011110001100000101101
23195490349.0	-626905143.432	    1010	  10101100110100011110001100000101101
25342973997.0	-684945242.027	    1011	  10111100110100011110001100000101101
27490457645.0	-742985340.622	    1100	  11001100110100011110001100000101101
29637941293.0	-801025439.216	    1101	  11011100110100011110001100000101101
31785424941.0	-859065537.811	    1110	  11101100110100011110001100000101101
33932908589.0	-917105636.405	    1111	  11111100110100011110001100000101101
36080392237.0	-975145735.0	   10000	 100001100110100011110001100000101101
The solution is -975145735
$

We can see that the script has found a hit on -975145375 which suddenly means that -975145375(-37) + 42 = 1720653869.

“No it doesn’t Jared!” you say.

And you are correct.

-975145735*-37 + 42 = 36080392237

But here is where the overflow comes in.

By design, Storyyeller purposely doesn’t validate the bitness of the result before he evaluates it against 1720653869. He has given us the opportunity to allow the binary bits to overflow. Any extraneous bits that can’t be used in a 32bit system simply are NOT accounted for.

answer      	x           	overflow	binary                               
1720653869.0	-46504157.4865	        	      1100110100011110001100000101101
36080392237.0	-975145735.0	   10000	 100001100110100011110001100000101101

Which means the five bits in the overflow column, 1-0-0-0-0, overflow and drop off converting 36080392237 into 1720653869.

Or their binary equivalents (10000)1100110100011110001100000101101 into 1100110100011110001100000101101.

Test the answer now against Storyyeller’s application.

$ java -jar crackme1.1.jar -975145735
Correct!
$

Success!!!

Conclusion

You should now know how to further exploit bytecode by hand along with slapping around the constant pool a bit. You should realize that doing such things by hand is insanely tedious. You should understand how to install and utilize Krakatau. And you should be aware and comprehend what Integer Overflow is and hopefully now go and investigate ideas on how to prevent your applications from suffering them.

Thanks again to Storyyeller for not only writing Krakatau but also crafting the crackme. I know it takes a lot of effort and it is much appreciated.