Checkout Kushtaka! A defensive cyber security product I'm building!

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



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

img

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

img

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.

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

By the way, let me email you what I learn about leadership, infosec, and product!

(It is a friendly list, I won't be a jerk with your private info)
$ 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
$
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 
 2public 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 
 2public 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 
 2public 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 
 2public 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 
 2public 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 
 2public 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 
 2public 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 
 2public 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 
 2public 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 
 2public 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.

-1720652315/37 (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.