Java Puzzle 5: Ball - Solution

Mar 18, 2012

Cheating in the ball game was hard. Only three great Java minds managed to crack it: mihi, polygenelubricants and crazybob.
As a reminder, here's the puzzle:

package game;

public final class Game {

    private final Ball ball = new Ball();
    private volatile long score;

    public final class Ball extends Throwable {
        private volatile long caught;

        private Ball() {
        }

        public synchronized void caught() {
            if (caught++ < score++) {
                // The goal is to reach this line
                System.out.println("You cheated!");
            }
        }
    }

    public void play() throws Ball {
        throw ball;
    }
}

The approach

If you couldn't throw a ball, it wouldn't be any fun. But extending Throwable also makes it implements Serializable, and that's where the real fun starts. Using serialization, we can create a ball that supposedly has been caught as many times as our serialized data claims.

The Game looks like it spoils the fun. You can't throw it; but more importantly you can't serialize it. If you try to naively serialize a ball directly, it will also try to serialize the game it is attached to, leading to a NotSerializableException.

Note that technically the reference from the ball to its game is just a field called something like this$0. With "attach" I mean assigning to that field. So this problem is equivalent to serializing an object that has a normal field that is not serializable.

The catch is that we don't need to serialize the game and ball at all. We only need to deserialize the ball, and attach it to a Game. The Game instance doesn't need to come directly from the serialized stream. We can put a substitute in its place, and override readResolve to replace it with a Game before it gets attached to the Ball.

Cheating in practice

There are multiple ways to create the raw data (byte array) that contains such a ball attached to a substitute game. Here's mine; there are other ways in the comments below.
We create a class similar to Ball (Ba). We give it the same serialVersionUID as Ball and our desired caught value. It's attached to our substitute implementing readResolve (Player). We serialize that and replace just the name of the Ba class with the Ball class. Converting the byte[] to a String and back allows us to use String.replace for that.
The name Ba is chosen so that play.Player$Ba has the same length as game.Game$Ball. Without that, directly replacing one with the other would corrupt the stream.

package play;

import game.Game;
import game.Game.Ball;

import java.io.*;

public class Player implements Serializable {

    public static void main(String[] args) throws Exception {
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        new ObjectOutputStream(bos).writeObject(new Player().new Ba());
        byte[] bytes = new String(bos.toByteArray(), "ISO-8859-1")
                .replace("play.Player$Ba", "game.Game$Ball")
                .getBytes("ISO-8859-1");
        Ball ball = (Ball) new ObjectInputStream(new ByteArrayInputStream(bytes))
                .readObject();
        ball.caught();
    }

    class Ba implements Serializable {
        static final long serialVersionUID = -7172046060844866133L;

        private long caught = -1;
    }

    Object readResolve() {
        return new Game();
    }
}

This is what happens:

  • When calling readObject(), first the Ball gets deserialized, and caught set to -1.
  • The value for Ball.this$0 that gets deserialized is an instance of Player.
  • Before Player gets assigned to that field (which would fail, because it's of the wrong type), its readResolve method is called, creating a new Game with score 0
  • That Game gets assigned to Ball.this$0, and readObject() returns the Ball.
  • ball.caught() is called with caught == -1 and this$0.score == 0, and you are caught cheating!

Conclusion

Creating serializable objects that have a reference to a non-serializable object is a bad idea because you cannot serialize them. But with some dirty tricks, you can still deserialize them.

Java serialization is full of nasty unexpected possibilities. You could do a whole series of puzzles about just that. But if you're really into that nastiness, all you need to do is look at the JDK security vulnerabilities over the last years.


12 comments

mihi wrote on 2012-03-15 20:27

Throwable is well known for creating squiggly lines in Eclipse because it is Serializable. So, let’s use this to our advantage :-)

It is a bit tricky since an nonstatic inner class will hold a reference to the outer class (this$0), which is not serializable, so we have to replace this one on serialization and reinstate it on deserialization.

We could also use this to deserialize two Balls for the same Game object, that could both be used to score for the same game, but I took the (for me) easier route to deserialize a cheated ball with a caught counter of -1, which gets connected to a new Game object with score 0).

Here is my solution:

package play;

import game.Game;
import java.io.*;

public class Play {

    public static class GamePlaceholder implements Serializable {
        public Object readResolve() { return new Game(); }
    }

    public static void main(String[] args) throws Exception {
        ByteArrayInputStream bais = new ByteArrayInputStream(new byte[] {
                (byte) 0xac, (byte) 0xed, (byte) 0x0, (byte) 0x5, (byte) 0x73, (byte) 0x72, (byte) 0x0, (byte) 0xe, (byte) 0x67, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x2e, (byte) 0x47, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x24, (byte) 0x42, (byte) 0x61, (byte) 0x6c, (byte) 0x6c, (byte) 0xbc, (byte) 0x47, (byte) 0xf9, (byte) 0x6b, (byte) 0x3c, (byte) 0x8, (byte) 0x78, (byte) 0xe4, (byte) 0x2, (byte) 0x0, (byte) 0x2, (byte) 0x4a, (byte) 0x0, (byte) 0x6, (byte) 0x63, (byte) 0x61, (byte) 0x75, (byte) 0x67, (byte) 0x68, (byte) 0x74, (byte) 0x4c, (byte) 0x0, (byte) 0x6, (byte) 0x74, (byte) 0x68, (byte) 0x69, (byte) 0x73, (byte) 0x24, (byte) 0x30, (byte) 0x74, (byte) 0x0, (byte) 0xb, (byte) 0x4c, (byte) 0x67, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x2f, (byte) 0x47, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x3b, (byte) 0x78, (byte) 0x72, (byte) 0x0, (byte) 0x13, (byte) 0x6a, (byte) 0x61, (byte) 0x76, (byte) 0x61, (byte) 0x2e, (byte) 0x6c, (byte) 0x61,
                (byte) 0x6e, (byte) 0x67, (byte) 0x2e, (byte) 0x54, (byte) 0x68, (byte) 0x72, (byte) 0x6f, (byte) 0x77, (byte) 0x61, (byte) 0x62, (byte) 0x6c, (byte) 0x65, (byte) 0xd5, (byte) 0xc6, (byte) 0x35, (byte) 0x27, (byte) 0x39, (byte) 0x77, (byte) 0xb8, (byte) 0xcb, (byte) 0x3, (byte) 0x0, (byte) 0x3, (byte) 0x4c, (byte) 0x0, (byte) 0x5, (byte) 0x63, (byte) 0x61, (byte) 0x75, (byte) 0x73, (byte) 0x65, (byte) 0x74, (byte) 0x0, (byte) 0x15, (byte) 0x4c, (byte) 0x6a, (byte) 0x61, (byte) 0x76, (byte) 0x61, (byte) 0x2f, (byte) 0x6c, (byte) 0x61, (byte) 0x6e, (byte) 0x67, (byte) 0x2f, (byte) 0x54, (byte) 0x68, (byte) 0x72, (byte) 0x6f, (byte) 0x77, (byte) 0x61, (byte) 0x62, (byte) 0x6c, (byte) 0x65, (byte) 0x3b, (byte) 0x4c, (byte) 0x0, (byte) 0xd, (byte) 0x64, (byte) 0x65, (byte) 0x74, (byte) 0x61, (byte) 0x69, (byte) 0x6c, (byte) 0x4d, (byte) 0x65, (byte) 0x73, (byte) 0x73, (byte) 0x61, (byte) 0x67, (byte) 0x65, (byte) 0x74, (byte) 0x0, (byte) 0x12, (byte) 0x4c, (byte) 0x6a,
                (byte) 0x61, (byte) 0x76, (byte) 0x61, (byte) 0x2f, (byte) 0x6c, (byte) 0x61, (byte) 0x6e, (byte) 0x67, (byte) 0x2f, (byte) 0x53, (byte) 0x74, (byte) 0x72, (byte) 0x69, (byte) 0x6e, (byte) 0x67, (byte) 0x3b, (byte) 0x5b, (byte) 0x0, (byte) 0xa, (byte) 0x73, (byte) 0x74, (byte) 0x61, (byte) 0x63, (byte) 0x6b, (byte) 0x54, (byte) 0x72, (byte) 0x61, (byte) 0x63, (byte) 0x65, (byte) 0x74, (byte) 0x0, (byte) 0x1e, (byte) 0x5b, (byte) 0x4c, (byte) 0x6a, (byte) 0x61, (byte) 0x76, (byte) 0x61, (byte) 0x2f, (byte) 0x6c, (byte) 0x61, (byte) 0x6e, (byte) 0x67, (byte) 0x2f, (byte) 0x53, (byte) 0x74, (byte) 0x61, (byte) 0x63, (byte) 0x6b, (byte) 0x54, (byte) 0x72, (byte) 0x61, (byte) 0x63, (byte) 0x65, (byte) 0x45, (byte) 0x6c, (byte) 0x65, (byte) 0x6d, (byte) 0x65, (byte) 0x6e, (byte) 0x74, (byte) 0x3b, (byte) 0x78, (byte) 0x70, (byte) 0x71, (byte) 0x0, (byte) 0x7e, (byte) 0x0, (byte) 0x6, (byte) 0x70, (byte) 0x75, (byte) 0x72, (byte) 0x0, (byte) 0x1e, (byte) 0x5b, (byte) 0x4c,
                (byte) 0x6a, (byte) 0x61, (byte) 0x76, (byte) 0x61, (byte) 0x2e, (byte) 0x6c, (byte) 0x61, (byte) 0x6e, (byte) 0x67, (byte) 0x2e, (byte) 0x53, (byte) 0x74, (byte) 0x61, (byte) 0x63, (byte) 0x6b, (byte) 0x54, (byte) 0x72, (byte) 0x61, (byte) 0x63, (byte) 0x65, (byte) 0x45, (byte) 0x6c, (byte) 0x65, (byte) 0x6d, (byte) 0x65, (byte) 0x6e, (byte) 0x74, (byte) 0x3b, (byte) 0x2, (byte) 0x46, (byte) 0x2a, (byte) 0x3c, (byte) 0x3c, (byte) 0xfd, (byte) 0x22, (byte) 0x39, (byte) 0x2, (byte) 0x0, (byte) 0x0, (byte) 0x78, (byte) 0x70, (byte) 0x0, (byte) 0x0, (byte) 0x0, (byte) 0x2, (byte) 0x73, (byte) 0x72, (byte) 0x0, (byte) 0x1b, (byte) 0x6a, (byte) 0x61, (byte) 0x76, (byte) 0x61, (byte) 0x2e, (byte) 0x6c, (byte) 0x61, (byte) 0x6e, (byte) 0x67, (byte) 0x2e, (byte) 0x53, (byte) 0x74, (byte) 0x61, (byte) 0x63, (byte) 0x6b, (byte) 0x54, (byte) 0x72, (byte) 0x61, (byte) 0x63, (byte) 0x65, (byte) 0x45, (byte) 0x6c, (byte) 0x65, (byte) 0x6d, (byte) 0x65, (byte) 0x6e, (byte) 0x74,
                (byte) 0x61, (byte) 0x9, (byte) 0xc5, (byte) 0x9a, (byte) 0x26, (byte) 0x36, (byte) 0xdd, (byte) 0x85, (byte) 0x2, (byte) 0x0, (byte) 0x4, (byte) 0x49, (byte) 0x0, (byte) 0xa, (byte) 0x6c, (byte) 0x69, (byte) 0x6e, (byte) 0x65, (byte) 0x4e, (byte) 0x75, (byte) 0x6d, (byte) 0x62, (byte) 0x65, (byte) 0x72, (byte) 0x4c, (byte) 0x0, (byte) 0xe, (byte) 0x64, (byte) 0x65, (byte) 0x63, (byte) 0x6c, (byte) 0x61, (byte) 0x72, (byte) 0x69, (byte) 0x6e, (byte) 0x67, (byte) 0x43, (byte) 0x6c, (byte) 0x61, (byte) 0x73, (byte) 0x73, (byte) 0x71, (byte) 0x0, (byte) 0x7e, (byte) 0x0, (byte) 0x4, (byte) 0x4c, (byte) 0x0, (byte) 0x8, (byte) 0x66, (byte) 0x69, (byte) 0x6c, (byte) 0x65, (byte) 0x4e, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x71, (byte) 0x0, (byte) 0x7e, (byte) 0x0, (byte) 0x4, (byte) 0x4c, (byte) 0x0, (byte) 0xa, (byte) 0x6d, (byte) 0x65, (byte) 0x74, (byte) 0x68, (byte) 0x6f, (byte) 0x64, (byte) 0x4e, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x71, (byte) 0x0,
                (byte) 0x7e, (byte) 0x0, (byte) 0x4, (byte) 0x78, (byte) 0x70, (byte) 0x0, (byte) 0x0, (byte) 0x0, (byte) 0x5, (byte) 0x74, (byte) 0x0, (byte) 0x9, (byte) 0x67, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x2e, (byte) 0x47, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x74, (byte) 0x0, (byte) 0x9, (byte) 0x47, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x2e, (byte) 0x6a, (byte) 0x61, (byte) 0x76, (byte) 0x61, (byte) 0x74, (byte) 0x0, (byte) 0x6, (byte) 0x3c, (byte) 0x69, (byte) 0x6e, (byte) 0x69, (byte) 0x74, (byte) 0x3e, (byte) 0x73, (byte) 0x71, (byte) 0x0, (byte) 0x7e, (byte) 0x0, (byte) 0x9, (byte) 0x0, (byte) 0x0, (byte) 0x0, (byte) 0x15, (byte) 0x74, (byte) 0x0, (byte) 0x1a, (byte) 0x70, (byte) 0x6c, (byte) 0x61, (byte) 0x79, (byte) 0x2e, (byte) 0x43, (byte) 0x68, (byte) 0x65, (byte) 0x61, (byte) 0x74, (byte) 0x65, (byte) 0x64, (byte) 0x42, (byte) 0x61, (byte) 0x6c, (byte) 0x6c, (byte) 0x53, (byte) 0x65, (byte) 0x72, (byte) 0x69, (byte) 0x61, (byte) 0x6c,
                (byte) 0x69, (byte) 0x7a, (byte) 0x65, (byte) 0x72, (byte) 0x74, (byte) 0x0, (byte) 0x1a, (byte) 0x43, (byte) 0x68, (byte) 0x65, (byte) 0x61, (byte) 0x74, (byte) 0x65, (byte) 0x64, (byte) 0x42, (byte) 0x61, (byte) 0x6c, (byte) 0x6c, (byte) 0x53, (byte) 0x65, (byte) 0x72, (byte) 0x69, (byte) 0x61, (byte) 0x6c, (byte) 0x69, (byte) 0x7a, (byte) 0x65, (byte) 0x72, (byte) 0x2e, (byte) 0x6a, (byte) 0x61, (byte) 0x76, (byte) 0x61, (byte) 0x74, (byte) 0x0, (byte) 0x4, (byte) 0x6d, (byte) 0x61, (byte) 0x69, (byte) 0x6e, (byte) 0x78, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0x73, (byte) 0x72, (byte) 0x0, (byte) 0x19, (byte) 0x70, (byte) 0x6c, (byte) 0x61, (byte) 0x79, (byte) 0x2e, (byte) 0x50, (byte) 0x6c, (byte) 0x61, (byte) 0x79, (byte) 0x24, (byte) 0x47, (byte) 0x61, (byte) 0x6d, (byte) 0x65, (byte) 0x50, (byte) 0x6c, (byte) 0x61, (byte) 0x63, (byte) 0x65, (byte) 0x68, (byte) 0x6f, (byte) 0x6c,
                (byte) 0x64, (byte) 0x65, (byte) 0x72, (byte) 0x11, (byte) 0x8c, (byte) 0x10, (byte) 0xc5, (byte) 0x66, (byte) 0x72, (byte) 0x37, (byte) 0xa1, (byte) 0x2, (byte) 0x0, (byte) 0x0, (byte) 0x78, (byte) 0x70,
        });
        ObjectInputStream ois = new ObjectInputStream(bais);
        Game.Ball b = (Game.Ball)ois.readObject();
        b.caught();
    }
}

This works with a security manager enabled.

I created the cheated ball like this (this does not work with a security manager enabled, but it could be done with a security manager enabled by using an external library that can output and manipulate serialized Java objects):

package play;

import game.Game;
import java.io.*;
import java.lang.reflect.Field;

public class CheatedBallSerializer {
    public static void main(String[] args) throws Exception {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(baos) {
            {enableReplaceObject(true);}
            protected Object replaceObject(Object obj) throws IOException {
                if (obj instanceof Game)
                    return new Play.GamePlaceholder();
                return obj;
            }
        };
        try {
            new Game().play();
        } catch (Game.Ball b) {
            Field f = b.getClass().getDeclaredField("caught");
            f.setAccessible(true);
            f.set(b, -1L);
            oos.writeObject(b);
        }
        oos.close();
        byte[] data = baos.toByteArray();
        for (int i = 0; i < data.length; i++) {
            System.out.print("(byte)0x"+Integer.toHexString(data[i] & 0xFF)+",");
        }
    }
}
Oleg Šelajev wrote on 2012-03-16 22:12

Obvious time-consuming solution is:

package play;

import game.Game;
import game.Game.Ball;

public class LoooooooooooooooooooongPlay {
  public static void main(String[] args) {
    Game game = new Game();
    Ball ball = null;
    try {
      game.play();
    }
    catch (Ball b) {
      ball = b;
    }
    breakBalance(ball);
    for (int i = 0; i < Long.MAX_VALUE; i++) {
      ball.caught();
    }
    ball.caught();

  }

  static int c = 0;

  static void breakBalance(Ball ball) {
    if (c < 1400) {
      c++;
      breakBalance(ball);
    }
    else {
      fatality(ball);
    }
  }

  private static boolean foundStackOverflow = false;
  private static boolean usedStackOverflow = false;

  private static void fatality(Ball ball) {
    try {
      fatality(ball);
    }
    catch (StackOverflowError e) {
      foundStackOverflow = true;
      return;
    }
    if (foundStackOverflow && !usedStackOverflow) {
      usedStackOverflow = true;
      ball.caught();
    }
  }
}

The trick is to find another one, I suppose :)

Wouter wrote on 2012-03-19 00:37

I made caught and score a long (instead of int) to make overflowing practically impossible.

Btw, that’s also related to why I made them volatile: to avoid that some jit optimization might affect the order of the caught++ and score++ and then you could break it with the alternative solution to the car puzzle.

The goal is to find a more practical solution, yes. But very nice try!

polygenelubricants wrote on 2012-03-17 11:17
package play;

import game.Game;
import game.Game.Ball;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Arrays;

public class TwoBallsOneGame {
    private static final Game GAME = new Game();
    private static final Ball BALL = ball();

    private static Ball ball() {
        try {
            GAME.play();
            throw new IllegalStateException();
        } catch (Ball ball) {
            return ball;
        }
    }

    public static final class GameProxy implements Serializable {
        private static final long serialVersionUID = 1L;

        private Object readResolve() {
            return TwoBallsOneGame.GAME;
        }
    }

    public static void main(String[] args) throws IOException, ClassNotFoundException {
//        ByteArrayOutputStream baos = new ByteArrayOutputStream();
//        ObjectOutputStream oos = new ObjectOutputStream(baos) {
//            {
//                enableReplaceObject(true);
//            }
//
//            @Override
//            protected Object replaceObject(Object obj) {
//                if (obj instanceof Game) {
//                    return new GameProxy();
//                }
//                return obj;
//            }
//        };
//        oos.writeObject(BALL);
//        oos.close();
//        System.out.println(Arrays.toString(baos.toByteArray()));

        byte[] byteArray = // run above code (without security manager) to get these bytes
                {-84, -19, 0, 5, 115, 114, 0, 14, 103, 97, 109, 101, 46, 71, 97, 109, 101, 36, 66, 97, 108, 108, -56, -25, -52, 127, -114, -125, 61, 49, 2, 0, 2, 66, 0, 6, 99, 97, 117, 103, 104, 116, 76, 0, 6, 116, 104, 105, 115, 36, 48, 116, 0, 11, 76, 103, 97, 109, 101, 47, 71, 97, 109, 101, 59, 120, 114, 0, 19, 106, 97, 118, 97, 46, 108, 97, 110, 103, 46, 84, 104, 114, 111, 119, 97, 98, 108, 101, -43, -58, 53, 39, 57, 119, -72, -53, 3, 0, 3, 76, 0, 5, 99, 97, 117, 115, 101, 116, 0, 21, 76, 106, 97, 118, 97, 47, 108, 97, 110, 103, 47, 84, 104, 114, 111, 119, 97, 98, 108, 101, 59, 76, 0, 13, 100, 101, 116, 97, 105, 108, 77, 101, 115, 115, 97, 103, 101, 116, 0, 18, 76, 106, 97, 118, 97, 47, 108, 97, 110, 103, 47, 83, 116, 114, 105, 110, 103, 59, 91, 0, 10, 115, 116, 97, 99, 107, 84, 114, 97, 99, 101, 116, 0, 30, 91, 76, 106, 97, 118, 97, 47, 108, 97, 110, 103, 47, 83, 116, 97, 99, 107, 84, 114, 97, 99, 101, 69, 108, 101, 109, 101, 110, 116, 59, 120, 112, 113, 0, 126, 0, 6, 112, 117, 114, 0, 30, 91, 76, 106, 97, 118, 97, 46, 108, 97, 110, 103, 46, 83, 116, 97, 99, 107, 84, 114, 97, 99, 101, 69, 108, 101, 109, 101, 110, 116, 59, 2, 70, 42, 60, 60, -3, 34, 57, 2, 0, 0, 120, 112, 0, 0, 0, 2, 115, 114, 0, 27, 106, 97, 118, 97, 46, 108, 97, 110, 103, 46, 83, 116, 97, 99, 107, 84, 114, 97, 99, 101, 69, 108, 101, 109, 101, 110, 116, 97, 9, -59, -102, 38, 54, -35, -123, 2, 0, 4, 73, 0, 10, 108, 105, 110, 101, 78, 117, 109, 98, 101, 114, 76, 0, 14, 100, 101, 99, 108, 97, 114, 105, 110, 103, 67, 108, 97, 115, 115, 113, 0, 126, 0, 4, 76, 0, 8, 102, 105, 108, 101, 78, 97, 109, 101, 113, 0, 126, 0, 4, 76, 0, 10, 109, 101, 116, 104, 111, 100, 78, 97, 109, 101, 113, 0, 126, 0, 4, 120, 112, 0, 0, 0, 5, 116, 0, 9, 103, 97, 109, 101, 46, 71, 97, 109, 101, 116, 0, 9, 71, 97, 109, 101, 46, 106, 97, 118, 97, 116, 0, 6, 60, 105, 110, 105, 116, 62, 115, 113, 0, 126, 0, 9, 0, 0, 0, 15, 116, 0, 20, 112, 108, 97, 121, 46, 84, 119, 111, 66, 97, 108, 108, 115, 79, 110, 101, 71, 97, 109, 101, 116, 0, 20, 84, 119, 111, 66, 97, 108, 108, 115, 79, 110, 101, 71, 97, 109, 101, 46, 106, 97, 118, 97, 116, 0, 8, 60, 99, 108, 105, 110, 105, 116, 62, 120, 0, 115, 114, 0, 30, 112, 108, 97, 121, 46, 84, 119, 111, 66, 97, 108, 108, 115, 79, 110, 101, 71, 97, 109, 101, 36, 71, 97, 109, 101, 80, 114, 111, 120, 121, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 120, 112};

        ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(byteArray));
        Ball b = (Ball) ois.readObject();
        b.caught();
        BALL.caught();
    }
}
Bob Lee wrote on 2012-03-18 23:18

Done. Good one!

package play;

import game.Game;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.Serializable;

public class Play {

  private static final Game game = new Game();

  public static void main(String[] args) throws IOException, ClassNotFoundException {
    ObjectInputStream in = new ObjectInputStream(new ByteArrayInputStream(toByteArray(payload)));
    Game.Ball copy = (Game.Ball) in.readObject();
    copy.caught();

    try {
      game.play();
    } catch (Game.Ball ball) {
      ball.caught();
    }
  }

  public static class GameProxy implements Serializable {
    Object readResolve() {
      return game;
    }
  }

  private static byte[] toByteArray(int[] bytes) {
    byte[] result = new byte[bytes.length];
    for (int i = 0; i < bytes.length; i++) result[i] = (byte) bytes[i];
    return result;
  }

  private static final int[] payload = {
      0xAC, 0xED, 0x00, 0x05, 0x73, 0x72, 0x00, 0x0E, /* ????sr?? */
      0x67, 0x61, 0x6D, 0x65, 0x2E, 0x47, 0x61, 0x6D, /* game.Gam */
      0x65, 0x24, 0x42, 0x61, 0x6C, 0x6C, 0x9C, 0x77, /* e$Ball?w */
      0xC6, 0x1B, 0x56, 0x9A, 0x25, 0xAB, 0x02, 0x00, /* ??V?%??? */
      0x02, 0x4A, 0x00, 0x06, 0x63, 0x61, 0x75, 0x67, /* ?J??caug */
      0x68, 0x74, 0x4C, 0x00, 0x06, 0x74, 0x68, 0x69, /* htL??thi */
      0x73, 0x24, 0x30, 0x74, 0x00, 0x0B, 0x4C, 0x67, /* s$0t??Lg */
      0x61, 0x6D, 0x65, 0x2F, 0x47, 0x61, 0x6D, 0x65, /* ame/Game */
      0x3B, 0x78, 0x72, 0x00, 0x13, 0x6A, 0x61, 0x76, /* ;xr??jav */
      0x61, 0x2E, 0x6C, 0x61, 0x6E, 0x67, 0x2E, 0x54, /* a.lang.T */
      0x68, 0x72, 0x6F, 0x77, 0x61, 0x62, 0x6C, 0x65, /* hrowable */
      0xD5, 0xC6, 0x35, 0x27, 0x39, 0x77, 0xB8, 0xCB, /* ??5'9w?? */
      0x03, 0x00, 0x03, 0x4C, 0x00, 0x05, 0x63, 0x61, /* ???L??ca */
      0x75, 0x73, 0x65, 0x74, 0x00, 0x15, 0x4C, 0x6A, /* uset??Lj */
      0x61, 0x76, 0x61, 0x2F, 0x6C, 0x61, 0x6E, 0x67, /* ava/lang */
      0x2F, 0x54, 0x68, 0x72, 0x6F, 0x77, 0x61, 0x62, /* /Throwab */
      0x6C, 0x65, 0x3B, 0x4C, 0x00, 0x0D, 0x64, 0x65, /* le;L??de */
      0x74, 0x61, 0x69, 0x6C, 0x4D, 0x65, 0x73, 0x73, /* tailMess */
      0x61, 0x67, 0x65, 0x74, 0x00, 0x12, 0x4C, 0x6A, /* aget??Lj */
      0x61, 0x76, 0x61, 0x2F, 0x6C, 0x61, 0x6E, 0x67, /* ava/lang */
      0x2F, 0x53, 0x74, 0x72, 0x69, 0x6E, 0x67, 0x3B, /* /String; */
      0x5B, 0x00, 0x0A, 0x73, 0x74, 0x61, 0x63, 0x6B, /* [??stack */
      0x54, 0x72, 0x61, 0x63, 0x65, 0x74, 0x00, 0x1E, /* Tracet?? */
      0x5B, 0x4C, 0x6A, 0x61, 0x76, 0x61, 0x2F, 0x6C, /* [Ljava/l */
      0x61, 0x6E, 0x67, 0x2F, 0x53, 0x74, 0x61, 0x63, /* ang/Stac */
      0x6B, 0x54, 0x72, 0x61, 0x63, 0x65, 0x45, 0x6C, /* kTraceEl */
      0x65, 0x6D, 0x65, 0x6E, 0x74, 0x3B, 0x78, 0x70, /* ement;xp */
      0x71, 0x00, 0x7E, 0x00, 0x06, 0x70, 0x75, 0x72, /* q?~??pur */
      0x00, 0x1E, 0x5B, 0x4C, 0x6A, 0x61, 0x76, 0x61, /* ??[Ljava */
      0x2E, 0x6C, 0x61, 0x6E, 0x67, 0x2E, 0x53, 0x74, /* .lang.St */
      0x61, 0x63, 0x6B, 0x54, 0x72, 0x61, 0x63, 0x65, /* ackTrace */
      0x45, 0x6C, 0x65, 0x6D, 0x65, 0x6E, 0x74, 0x3B, /* Element; */
      0x02, 0x46, 0x2A, 0x3C, 0x3C, 0xFD, 0x22, 0x39, /* ?F*<<?"9 */
      0x02, 0x00, 0x00, 0x78, 0x70, 0x00, 0x00, 0x00, /* ???xp??? */
      0x00, 0x78, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ?x?????? */
      0x00, 0x00, 0x73, 0x72, 0x00, 0x13, 0x70, 0x6C, /* ??sr??pl */
      0x61, 0x79, 0x2E, 0x50, 0x6C, 0x61, 0x79, 0x24, /* ay.Play$ */
      0x47, 0x61, 0x6D, 0x65, 0x50, 0x72, 0x6F, 0x78, /* GameProx */
      0x79, 0x20, 0x5E, 0xBB, 0x74, 0xB4, 0x98, 0xC5, /* y ^?t??? */
      0x7F, 0x02, 0x00, 0x00, 0x78, 0x70              /* ????xp   */
  };
}
Wouter wrote on 2012-03-19 00:30

As an alternative to manipulating the byte array, you can also override ObjectInputStream.resolveClass:

package play;

import java.io.*;

public class Player2 {

    public static void main(String[] args) throws Exception {
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        new ObjectOutputStream(bos).writeObject(new play.Game().new Ball());
        byte[] bytes = bos.toByteArray();
        ByteArrayInputStream bis = new ByteArrayInputStream(bytes);
        ObjectInput in = new ObjectInputStream(bis) {
            @Override
            protected Class<?> resolveClass(ObjectStreamClass desc)
                    throws IOException, ClassNotFoundException {
                if (desc.getName().equals("play.Game$Ball")) {
                    return game.Game.Ball.class;
                }
                return super.resolveClass(desc);
            }
        };
        game.Game.Ball ball = (game.Game.Ball) in.readObject();

        ball.caught();
    }

}

// must be called Game for the "resolveClass" to be allowed
class Game implements Serializable {
    public final class Ball implements Serializable {
        final static long serialVersionUID = -7172046060844866133L;

        private long caught = -1;
    }

    Object readResolve() {
        return new game.Game();
    }
}
Wouter wrote on 2012-03-19 01:02

And since you seem to like hard-coded serialized versions in the code, here’s my version of that approach:

package play;

import java.io.*;

public class Player implements Serializable {

    public static void main(String[] args) throws Exception {
        byte[] bytes = ("\254\355&#92;&#48;00&#92;&#48;05sr&#92;&#48;00&#92;&#48;16game.Game$Ball\234w\306" +
                "&#92;&#48;33V\232%\253&#92;&#48;02&#92;&#48;00&#92;&#48;02J&#92;&#48;00&#92;&#48;06caughtL&#92;&#48;00&#92;&#48;06this$0t" +
                "&#92;&#48;00&#92;&#48;15Lplay/Player;xp\377\377\377\377\377\377\377\377sr" +
                "&#92;&#48;00&#92;&#48;13play.Player\351\337@6\255%\200\373&#92;&#48;02&#92;&#48;00&#92;&#48;00xp")
                .getBytes("ISO-8859-1");

        ((game.Game.Ball) new ObjectInputStream(new ByteArrayInputStream(bytes))
                .readObject()).caught();
    }

    Object readResolve() {
        return new game.Game();
    }
}
mihi wrote on 2012-03-19 01:10

In fact, a different length would not be that much of a problem, since almost everywhere in Java (class files, serialized data) class names and short strings (<64KB) are prefixed by a 2-byte length field and there are no other “derived” length fields that might have to be adjusted. So you'd just have to include that length field in your replace operation).

Practical example where I (ab)used this to change an URL inside serialized data: http://dev.metasploit.com/redmine/projects/framework/repository/entry/modules/exploits/multi/misc/java_rmi_server.rb#L95

And inside a class file: http://dev.metasploit.com/redmine/projects/framework/repository/entry/modules/exploits/multi/browser/java_signed_applet.rb#L170

eugene wrote on 2012-03-19 09:21

Darn! We (me and my two colleagues) were so close to solving it. First we had the solution with stackoverflow, but gave up on it fast because volatile and long - you probably wanted to almost exclude stackoverflow issue. Then we were sure with the Serializable approach, but could figure it out from start to end.

Thank you so much for this! Congrats to everyone who solved it.

Cheers, Eugene.

Dennis wrote on 2012-03-19 16:18

Good puzzle. I got this is about serializable via Throwable in very first guess. But not success after failing with NotSerializableException.

Jonathan Fisher wrote on 2012-03-19 18:02

These puzzles answers crack me up… Keep them coming!

Dominique Laurent wrote on 2012-04-17 01:32

This one was hard.

I’ve found a solution.

It’s based on the StackOverflow which was used in Puzzle3 and the fact that the Ball inner class has an access$108() method generated by the compiler to get and increment the score field of the Game outter class.

The problem is that once this is done, caught is actually higher, not lower, than score.

You then need to cause a buffer overflow to inverse this.

And the buffer overflow requires calling caught() until caught reaches Long.MAX_VALUE, which will certainly take quite a while ;-)

package play;

import game.Game;

/**
 * Play
 */
public final class Play {

    private static void recurse(Game.Ball ball) {
        try {
            ball.caught();
            recurse(ball);
        } catch (StackOverflowError error) {
            error.printStackTrace();
        }
    }

    public static void main(String[] args) throws Exception {
        long start = System.currentTimeMillis();
        try {
            new Game().play();
        } catch (final Game.Ball ball) {
            // we synchronize to avoid having to reacquire the lock at each iteration:
            synchronized (ball) {

                // use a StackOverflowError to have score > caught because
                // score is incremented via a compiler-generated game.Game.access$108() method
                // which we can prevent from occurring by the StackOverflowError
                recurse(ball);

                // now use a buffer overflow to have score < caught
                // just be patient when caught will be equal to Long.MIN_VALUE it will be lower than
                // score which will be Long.MAX_VALUE:
                for (long i = 0; i < Long.MAX_VALUE; i++) {
                    ball.caught();
                }
            }
        }
        System.out.println("Time taken = " + (System.currentTimeMillis() - start) + " milliseconds");
    }
}
Wouter wrote on 2012-06-30 21:53

Nice try. That’s more or less the same solution as Oleg. Overflowing the long indeed takes quite a while; not really practical.

Luciano wrote on 2013-03-20 00:46

So, the solution is manipulating the serialized data? What’s the difference between that and using setAccesible? Aren’t this puzzles supposed to be fun?

Wouter wrote on 2013-03-20 01:10

One difference is that the security manager allows it; but that’s more a consequence, not the real point.

The real difference is that setAccessible is explicitly disabling a safety mechanism of the JVM, to access internals you (as a non-privileged code) should not have access to. Serialization on the other hand is (although you usually don’t really want to see it that way) part of your public API. And, if any code anywhere in the same JVM deserialize any external data, even your external API (exposed outside the JVM). (So I could even argue that the serialized format, although it’s mostly implicit, is an even more public API than public methods that are just accessible inside the JVM). Not realizing it is part of your external API leads to security vulnerabilities such as the recent flood of rails vulnerabilities and http://wouter.coekaerts.be/2011/amf-arbitrary-code-execution .

I’m sorry you didn’t find this fun. Others liked it… Given how big a source of surprises (and vulnerabilities) serialization is, it would be weird not to have such a puzzle in the series. But I promise this is and will be the only one that (deliberately) involves serialization (without upfront warning).