Java Puzzle 5: Ball - Solution
Mar 18, 2012Cheating 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 theBallgets deserialized, andcaughtset to-1. - The value for
Ball.this$0that gets deserialized is an instance ofPlayer. - Before
Playergets assigned to that field (which would fail, because it's of the wrong type), itsreadResolvemethod is called, creating a newGamewithscore0 - That
Gamegets assigned toBall.this$0, andreadObject()returns theBall. ball.caught()is called withcaught == -1andthis$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
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:
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):
Obvious time-consuming solution is:
The trick is to find another one, I suppose :)
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++andscore++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!
Done. Good one!
As an alternative to manipulating the byte array, you can also override
ObjectInputStream.resolveClass:And since you seem to like hard-coded serialized versions in the code, here’s my version of that approach:
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
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.
Good puzzle. I got this is about serializable via Throwable in very first guess. But not success after failing with NotSerializableException.
These puzzles answers crack me up… Keep them coming!
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 ;-)
Nice try. That’s more or less the same solution as Oleg. Overflowing the long indeed takes quite a while; not really practical.
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?
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).