Time to dream the solution to the dreams puzzle. As a reminder, here’s the challenge:

package sleep;

import dream.Dream;

public class Sleeper {
	private int level;
	
	public synchronized int enter(Dream dream) {
		level++;
		try {
			dream.dream(this);
		} finally {
			level--;
		}
		return level;
	}
}

package sleep;

import dream.Dream;

public class Main {
	public static void main(String[] args) {
		if (new Sleeper().enter(new Dream()) != 0) {
			// The goal is to reach this line
			System.out.println("Am I still dreaming?");
		}
	}
}

Solution

The synchronized on the dream method means that it takes the monitor (lock) of the Sleeper object when we enter it, and it releases it again when we leave it. No other thread can enter the method while the monitor is held.

But here’s the catch: the monitor isn’t necessarily held all the time while the method is running. With Object.wait you can release a monitor in the middle of a synchronized method.

How do we apply that to solve this puzzle? When we enter the outer dream, we use wait to release the monitor. But first we launch a separate thread, that will also enter a dream. Entering that inner dream makes the second thread take the monitor. So in the inner dream, we use wait a second time to release the monitor. That allows the main thread stop waiting, take the monitor back, and leave the outer dream. And there we are: we have woken up from the outer dream, back where we started in main, but the dream within the dream goes on in the second thread.

package dream;

import sleep.Sleeper;

public class Dream {
	private static void doWait(Sleeper s) {
		try {
			s.wait(200);
		} catch (InterruptedException e) {
		}
	}
	
	public void dream(final Sleeper s) {
		new Thread() {
			public void run() {
				s.enter(new Dream() {
					@Override
					public void dream(Sleeper s) {
						doWait(s);
					}
				});
			}
		}.start();
		
		doWait(s);
	}
}

And the winner is…

I got more answers than I expected. The first one came from David Shay. Congrats!

It’s a bit repetitive, but as promised, you can see and compare all dreams as comments below this post.

Conclusion

The moral of the story: synchronized on a method doesn’t mean two different threads can’t be in it at the same time. It only ensures that such threads cannot execute concurrently; at least one of them must be waiting.

You can prevent this kind of abuse and other problems, by using a private object as monitor:

public class Sleeper {
	private final Object lock = new Object();
	
	public int dream(Dream dream) {
		synchronized(lock) {
			...
		}
	}
}

But that still leaves me unsure if I actually woke up this morning.

Here’s another challenging Java Puzzle! The same rules as for the clowns puzzle apply. [Update: In short: anything in your code is allowed; any trick outside the code is not. You must run with -Djava.security.manager, so setAccessible won't work.].

We’ve learned our lesson from the clowns: There are no hidden calls behind the scenes here, and we embrace recursion; we count on it.

Have you ever woken up from a dream, to then discover that you’re actually still dreaming? If you then wake up, how do you know you’re back in reality? This puzzle implements a solution to that problem: you count the recursion level of your dreams as you enter and exit them:

package sleep;

import dream.Dream;

public class Sleeper {
	private int level;
	
	public synchronized int enter(Dream dream) {
		level++;
		try {
			dream.dream(this);
		} finally {
			level--;
		}
		return level;
	}
}

A sleeper starts sleeping and enters a dream (level one). He can have a dream within that dream, and even enter deeper dreaming levels. But when he leaves the outer dream, he’s awake again, so he should be at level zero again, right?

package sleep;

import dream.Dream;

public class Main {
	public static void main(String[] args) {
		if (new Sleeper().enter(new Dream()) != 0) {
			// The goal is to reach this line
			System.out.println("Am I still dreaming?");
		}
	}
}

The counting of the levels looks really safe, so this seems impossible:

• Every time you enter a dream level is increased. Because of the finally block, there’s no way to leave a dream without decreasing it again.
• The synchronized block makes sure no other thread can call it concurrently. The level is returned from the dream method to make sure it’s read within the synchronized block.
• dream is the very first thing that’s called on the Sleeper, so the level must be zero when entering it. The value that’s returned from it must be zero too then, because even if we call it recursively we must enter as many dreams as we exit.

// this is the only file you're allowed to edit
package dream;

import sleep.Sleeper;

public class Dream {
	public void dream(Sleeper s) {
		// TODO implement me
	}
}

Do you eat Java, breathe Java, and even dream in Java? Can you find the flaw in this reasoning? Can you imagine a really weird dream, that would make the sleeper lose count? If so, leave your code in a comment here!

To give everyone a fair chance, those comments will stay were hidden for a while. They will become public soon are now public, together with a follow-up blog post.
To be notified of that and the next puzzles, follow the feed or twitter.

PS: This puzzle is appearing simultaneously in the Java Specialists’ Newsletter.

Spoiler warning: If you want to find out how you can fit 20 clowns into a Volkswagen, read on. If you haven’t seen or tried solving the clowns java puzzle yourself, do that first!

As a reminder: here’s the code it’s all about:

package clowns;

import java.util.HashSet;
import java.util.Set;

public class Volkswagen {
    private static final int CAPACITY = 5;
    private Set<Clown> clowns = new HashSet<Clown>();

    public synchronized void add(Clown clown) {
        if (clowns.size() >= CAPACITY) {
            throw new IllegalStateException("I'm full");
        } else {
            clowns.add(clown);
        }
    }

    public synchronized void done() {
        if (clowns.size() == 20) {
            // The goal is to reach this line
            System.out.println("I'm a Volkswagen with 20 clowns!");
        }
    }
}

Path to the solution

Imagine this was a real car with real clowns.

– It’s impossible to get twenty clowns in! There are only five seat belts, and this Volkswagen really insists on safety. When a clown enters, it first checks if there aren’t already five of them sitting in it. Only after that checks it allows another one to sit (clowns.add(clown)). As soon as there are five clown sitting, there’s no way to pass the check anymore, so no way to add any extra clown.
– You’re right that we can’t add them one by one. But there is a window of opportunity between the check when they enter the car, and when they really sit down. Make all twenty clowns simultaneously enter the car. They will all pass the check of the Volkswagen, because it only counts clowns that are already sitting down. And only after the check let them sit.
– The car’s synchronized protection prevents anyone else from doing anything with it between the check and the sitting down.
– Indeed, it prevents someone else from interfering. It doesn’t prevent the Volkswagen or the clown itself to do it if they’re given the opportunity (on the same thread).
– But they don’t get that opportunity; the car is a control freak. After the check it immediately makes them sit in their seats (in the Set).
– Did you have a look at those seats? They’re numbered, and they always first asks a person at which number they want to sit (.hashCode()). We’ve got some weird clowns here: when they’re given the opportunity to decide that, right before answering, they can quickly pull another clown into the car. And that clown then does exactly the same with another clown. That goes on until there’s a stack of twenty of them recursively pulling each other in. As long as their ass doesn’t touch the seat, the seat-belt sign won’t come on.
– That must be quite a sight.

The solution

Call Volkswagen.add recursively, by overriding Clown.hashCode():

package you;

import clowns.Clown;
import clowns.Volkswagen;

public class You {
    static int counter = 0;
    static Volkswagen vw = new Volkswagen();

    public static void main(String args[]) {
        vw.add(new RecursiveClown());
        vw.done();
    }

    static class RecursiveClown extends Clown {
        public int hashCode() {
            if (++counter < 20) {
                vw.add(new RecursiveClown());
            }
            return super.hashCode();
        }
    }
}

And the winner is…

The first solution came from Heinz Kabutz, famous from The Java Specialists’ Newsletter. He actually pushed me to publish these puzzles in the first place and promoted them. To show my infinite gratitude I’m going to disqualify him for having seen the puzzle in advance.

I received 7 correct solutions that passed the clarified rules. All used the same principle: adding them simultaneously using hashcode. Half of them also danced around the Volkswagen a bit in different threads to accomplish that. That’s fine; there’s no ban on dancing clowns here.

Congrats to all of you, especially Manuel Alvarez who was the first, and runner-up Jean-Louis Willems with the first short solution.

Conclusion

A simple check at the beginning of a synchronized method is not enough to guarantee safety if you’re not very careful with which code you give control to. But should you really worry about crazy recursive clowns when writing your simple Volkswagen code?

No, you shouldn’t. Well, not unless it’s about privileged code handling a sandbox — such as code of the JDK itself when running an applet. But it sure is interesting to explore these dark corners of Java. We’ll continue on that track soon with a puzzle about dreams…

Introduction

This is the first in a series of Java puzzles, that put your Java skills to the test, in a challenging and fun way!
A puzzle consists of some given Java code with a line in it that seems to be impossible to reach. It’s up to you to find the hole in it, abuse a subtle behavior of Java to make execution reach that line anyways.

There almost aren’t any rules; any cheating inside your code is allowed; it is the whole point of the puzzle. [Clarification: Cheating the environment is not]. You must run with the security manager enabled (java -Djava.security.manager), otherwise it would be too easy (with setAccessible for example). [Update: Use common sense, and see the exact rules if you're in doubt].

The puzzle

How can you fit 20 clowns into a Volkswagen? Two classes are given: an empty Clown class, and a Volkswagen class to which you can add clowns. When you try to add a Clown, it is checked that it isn’t already full. But if you just try hard enough, there’s always room for some extra clowns…

package clowns;

public class Clown {
}

package clowns;

import java.util.HashSet;
import java.util.Set;

public class Volkswagen {
    private static final int CAPACITY = 5;
    private Set<Clown> clowns = new HashSet<Clown>();

    public synchronized void add(Clown clown) {
        if (clowns.size() >= CAPACITY) {
            throw new IllegalStateException("I'm full");
        } else {
            clowns.add(clown);
        }
    }

    public synchronized void done() {
        if (clowns.size() == 20) {
            // The goal is to reach this line
            System.out.println("I'm a Volkswagen with 20 clowns!");
        }
    }
}

Write a class that when executed pushes 20 clowns into the little car, and reaches the marked line. Here is one that won’t really work, just to get you started:

package you;

import clowns.Clown;
import clowns.Volkswagen;

public class You {
    public static void main(String args[]) {
        // TODO put 20 clowns into a Volkswagen
        Volkswagen vw = new Volkswagen();
        for (int i = 0; i < 20; i++) {
            vw.add(new Clown());
        }
        vw.done();
    }
}

You can copy-paste the code into your IDE, or get it from github (zip).
If you’ve solved it, let me know (email or Twitter). If you’re the first, you’ll get… the honor of being the first. compare it to the solution posted here.
The solution and a new challenge will follow, so stay tuned!

Update: Don’t post answers as comments here, they will be blocked by moderation. You may comment, but no spoiler. If you have an alternative solution, post it as a comment on the solution post
Update 2: Added clarification of the rules.

My review of Vaadin‘s security revealed these vulnerabilities, now fixed in Vaadin 6.6.7.

What is Vaadin? In their own words: Vaadin is a Java framework for building modern web applications. Its server-side architecture [and] security mechanisms to prevent eg. man-in-the-middle and cross-site scripting attacks [...] make Vaadin one of the most secure UI frameworks in existence.

Separator injection

In a Vaadin application, the server sends updates to the client using JSON, but the client uses a custom format to send updates to the server. This format uses exotic characters as a separator between records/variables. But, prior to Vaadin 6.6.7, there is no mechanism to escape those characters when they occur within the data. If an attacker can trick a client into sending his crafted data to the server, he can perform actions in the user interface on behalf of the victim.
In other words, the result is similar to that of cross site request forgery (CSRF).
If certain UI components, such as the rich text area (which allows a user to set arbitrary HTML) are used anywhere in the application, this also leads to cross site scripting (XSS).

There are multiple ways a client can be tricked into sending such data. For example a user could be tricked into copy-pasting a certain string. But there is also an automated way: if the application uses the URL fragment (with the UriFragmentUtility), the characters can be injected in there. Whether that last trick actually works depends on the browser. It works on Chrome but doesn’t seem to work on Firefox, probably due to the way such characters are encoded.

More concretely, how does the format work? Suppose the user changes the text in a in a text field (with id PID1) to “test”, and then presses a button (PID2; setting “state” to true). The client could then send the following (slightly simplified), were [xx] is the character with the given hexadecimal ascii value:

0a09a5e2-3190-4f16-a75b-284b98d221ce[1D]test[1F]PID1[1F]text[1F]s[1E]true[1F]PID2[1F]state[1F]b
1D is the burst separator, 1F the field separator, and 1E the record separator. The “s” means type string, and “b” type boolean. The first part is the anti-CSRF token.

If the text value instead of “test” would have been true[1F]PID3[1F]state[1F]b, then the server would interprete that as the user clicking on the button PID3. That can be done in the url fragment, with a url like this: http://vaadin-application/#true%1FPID3%1Fstate%1Fb.

This is Vaadin ticket 7669.

Classpath directory traversal

The Servlet in Vaadin takes care of the communication, but also serves static resources (html, javascript, css, images…). It looks for these resources in the “VAADIN” directory on the web application’s classpath. Usually these resources would be found in a jar of the application, such as the Vaadin jar itself. But if the classpath also contains a directory (instead of only jars), also resources outside of the VAADIN directory can be retrieved using a simple /../ directory traversal. That allows an attacker to download the (byte)code of the application or configuration files (possibly containing passwords).

If this is exploitable in practice depends on how the application was packaged, and which servlet container is running it.

For example, creating a simple Vaadin application skeleton using the maven archetype with mvn archetype:generate -DarchetypeGroupId=com.vaadin -DarchetypeArtifactId=vaadin-archetype-clean -DarchetypeVersion=1.5.6 -DgroupId=tst -DartifactId=tst -Dversion=0 -Dpackaging=war and starting it with mvn package jetty:run, the main application class could be reached at the url /tst/VAADIN/../tst/MyVaadinApplication.class.

This is Vaadin ticket 7670.

Contributory XSS

There some places in the Vaadin framework that make it easy for a developer to introduce XSS problems. These are not directly exploitable by themselves, but in combination with other code can turn into vulnerabilities.

Exceptions on the server-side in handling updates from the client are often shown with an exclamation mark in a red circle next to the UI component that caused it; and hovering over that icon shows a tooltip with the exception stacktrace in it. HTML in that tooltip in the message of the exception (or its cause in the stacktrace) is not escaped.
For example, take a Vaadin application that shows a number in a text input field (without adding an explicit validator). If you paste HTML in that text field, parsing of that text to a number will fail with a NumberFormatException whose message includes the HTML text, that will then be shown unescaped.

I didn’t find an automated way to exploit this that doesn’t involve convincing a user to copy-paste some HTML. But this issue has the danger of turning another normal bug (that results in an otherwise harmless exception) into a security vulnerability.

This is Vaadin ticket 7671.

The src attribute of a number of UI components, which can contain a URL, is often handled without escaping. This seems to be the case for at least Embedded (when type is browser, i.e. an iframe), VWindow, VMenuBar, VFilterSelect, VView and Action. In an application where users are allowed to configure such a URL, which would then be used in such a component when shown to another user, this would be an exploitable XSS. That would be unusual, but not impossible; for example for the Embedded component, imagine a form where users can include an iframe in their posts.

This is Vaadin ticket 7672.

Finally, in a slightly different category, there are strings that are shown intentionally as HTML without escaping, in places where it is not clearly documented in the Vaadin API. This is the case in the tooltip (description) of all components, caption of a Panel or a notification (as in Window.showNotification). If you use user-provided text in any of those, you must take care of escaping yourself. Future versions of Vaadin (starting from 6.7) will provide plain-text modes at least for some of these.

Conclusion

Vaadin is still a framework with a particularly good security architecture and counter-measures. But no program or framework is completely immune to security vulnerabilities. Vaadin’s reaction to these vulnerabilities was quick and thorough.

Now it’s time to update your Vaadin applications to a newer version!

Springsource recently released Spring 3.0.6 fixing a bunch of security vulnerabilities I reported that affect applications using Spring and serialization (cve-2011-2894). Today Springsource finally made a security announcement. Here are some details on these vulnerabilities.

Serializable proxy to bean factory

Affected: Applications that have Spring AOP on the classpath and deserialize a stream from an untrusted source

Result: Arbitrary code execution

Short version: The problem is that the JdkDynamicAopProxy, DefaultListableBeanFactory and some other Spring classes are Serializable and can be configured to execute arbitrary code when the application uses these deserialized objects.

JdkDynamicAopProxy is used internally by the DefaultAopProxyFactory. It is an InvocationHandler , so it can be used with a java.lang.reflect.Proxy to dynamically handle method calls. Which object the proxy should delegate calls to, the target, can be configured in the JdkDynamicAopProxy with a TargetSource.
Certain TargetSources can be configured to point to a bean in a BeanFactory, which can contain arbitrary code in the form of bean definitions.
All of these objects (Proxy, JdkDynamicAopProxy, AbstractBeanFactoryBasedTargetSource, DefaultListableBeanFactory, AbstractBeanDefinition) are Serializable, and the Proxy can be configured to implement any interface the application might expect. That means an attacker can send them in the place of any object in a stream, and when the receiving application calls any method on the deserialized object, it will trigger the execution of the arbitrary code.

A DefaultListableBeanFactory is under normal circumstances never included in a serialized stream. It has a writeReplace method that before it’s being serialized replaces it with a SerializedBeanFactoryReference; a reference to an already existing bean factory. But it’s only the serialization that is prevented (at the attacker’s side, where it’s easily overridden), not the deserialization.

The application doesn’t even have to use Spring in its directly publically exposed part to be vulnerable. It just needs Spring AOP available on the classpath.
An application is vulnerable if it deserializes a stream from an untrusted source. That includes any application using RMI, or Spring’s HttpInvoker.

The vulnerability has been fixed in Spring by making it impossible to deserialize a DefaultListableBeanFactory except through the SerializedBeanFactoryReference. And the id used by the SerializedBeanFactoryReference has been made easier to configure because it should not be predictable by a client.

Another way this issue can be avoided is by not allowing a java.reflect.Proxy or JdkDynamicAopProxy to be deserialized when it is received from a client. Unfortunately some Spring applications actually depend on that to work, so this has not been disabled in Spring itself. But for most applications completely blocking it should be fine, so that’s what I strongly recommend. Starting from Spring 3.0.6, the RemoteInvocationSerializingExporter can be configured to not accept any java.lang.Proxy by setting acceptProxyClasses to false. The advantage of that solution is that it not only blocks this concrete attack, but also possible future variations. There is some danger that similar vulnerabilities might pop up again later, because accepting a JdkDynamicAopProxy means also accepting any serializable TargetSource, Advisor, Advise,… Those have not been written with security against this kind of attack in mind. Blocking it removes that unwanted attack surface.

Exposed ProxyFactory

Affected: Applications using HttpInvokerServiceExporter (and possibly other exporters)

Result: Arbitrary code execution

An HttpInvokerServiceExporter exposes the methods of a specified service interface over HTTP, using Java serialization.
But it accidentally not only exposes those methods, but also the methods of the Advised interface of the ProxyFactory it uses internally.
One of those exposed methods is setTargetSource, which can be abused to change the way that the exporter will handle all calls after that.
This can be exploited in a way similar to the previous vulnerability: by sending a targetSource that points to a bean factory that can contain arbitrary code.

It is fixed in Spring by making the proxy opaque.

About ContextPropagatingRemoteInvocation

Those were two vulnerabilities using Spring AOP. The rest of this post is about variants of one type of attack in Spring Security.
First I’ll give a short introduction to the relevant parts of Spring Security and ContextPropagatingRemoteInvocation to make clear what this is all about.

In Spring Security, an Authentication object represents either a (not authenticated yet) request for authentication, or the result of the authentication. It usually contains a username, password and/or the list of authorities granted to the user.
The checking of an authentication request and building of the resulting authentication happens in an AuthenticationProvider.
The information inside the unauthenticated Authentication object should not be trusted, it still has to be checked. Usually that Authentication object is created by the application itself, and filled with the information provided by the user (usually just the username and password).

When using the ContextPropagatingRemoteInvocation, not only some specific attributes of this Authentication object are provided by the user, but he provides the whole Authentication object, in serialized form.
The ContextPropagatingRemoteInvocation can be used to authenticate requests to any service exposed with a HttpInvokerServiceExporter. It doesn’t have to be enabled explicitly on the server; even applications that normally handle authentication in another way are still vulnerable to these problems.

The essence of all of the following problems is that the code is not written to handle such arbitrary untrusted Authentication objects.
The fix applied in Spring for this issue is not to allow such arbitrary Authentication requests in a ContextPropagatingRemoteInvocation anymore; but instead allow only a username and a password.

ContextPropagatingRemoteInvocation authentication

Affected: Applications using HttpInvokerServiceExporter, with Spring Security

Result: Privilege escalation: authenticate without credentials

This is the combination of a problem in Spring and the JDK. Because Oracle is still investigating their side of the issue, I’m still keeping the details private.

Password in BadCredentialsException

Affected: Applications using HttpInvokerServiceExporter with the DaoAuthenticationProvider (and possibly other providers).

Result: Privilege escalation: expose passwords

The DaoAuthenticationProvider.additionalAuthenticationChecks method throws a BadCredentialsException that contains as extraInformation the UserDetails, which also contain the (possibly hashed) correct password.
So when a user logs in with the wrong password, he receives a response that contains the right password.

There is already an option available in Spring to avoid this: AbstractAuthenticationManager.clearExtraInformation. But that’s an obscure detail not documented anywhere except in the javadoc, so most applications don’t enabled this.

PreAuthenticatedAuthenticationProvider

Affected: Applications using HttpInvokerServiceExporter, with the PreAuthenticatedAuthenticationProvider

Result: Privilege escalation: authenticate without credentials

The use for the PreAuthenticatedAuthenticationProvider, is that an application can be set up for example behind a trusted reverse proxy (usually to integrate into a single-sign-on solution) that provides an http header that contains a username. That header is then parsed by the RequestHeaderAuthenticationFilter that puts the username in a PreAuthenticatedAuthenticationToken. That token is then trusted (without having to provide a password) when authentication happens by the PreAuthenticatedAuthenticationProvider.
The javadoc of RequestHeaderAuthenticationFilter that this is only safe to be used in a setup where the source (proxy) of the request can be trusted. Still, it seems reasonable to assume it’s safe to use with Spring remoting (i.e., in combination with a HttpInvokerServiceExporter).

The problem is that nothing prevents a PreAuthenticatedAuthenticationToken from being provided directly by a ContextPropagatingRemoteInvocation. The PreAuthenticatedAuthenticationProvider doesn’t check that the PreAuthenticatedAuthenticationToken comes from a trusted source.

In this kind of setup the PreAuthenticatedGrantedAuthoritiesUserDetailsService could commonly be used to provide the details of the user that is logging in, and with that an attacker can give himself any authority he wants. This vulnerability probably applies to any AuthenticationUserDetailsService.

The intent of the PreAuthenticatedAuthenticationProvider is similar to the RunAsImplAuthenticationProvider: there is an Authentication coming from a trusted source, without real credentials. The RunAsImplAuthenticationProvider doesn’t have the same problem though, because it requires a secret key to be provided in the token.

Authorities in JaasAuthenticationProvider

Affected: Applications using HttpInvokerServiceExporter, with the JaasAuthenticationProvider

Result: Privilege escalation: acquiring any GrantedAuthority

The JaasAuthenticationProvider blindly copies the GrantedAuthorities of a request Authentication into the result Authentication. So a client can tell the server which authorities he wants, and the server blindly grants them. There’s nothing more to it than that.

Principal in JaasAuthenticationProvider

Affected: Applications using HttpInvokerServiceExporter, with the JaasAuthenticationProvider, and an exposed service with a particular behaviour

Result: Privilege escalation: authenticate as another user

In addition to the granted authorities (see above), the JaasAuthenticationProvider also copies the principal given in the request, although only its toString was authenticated using JAAS. The provided principal can be any object, it doesn’t need to implement a particular interface. If it is an object whose toString changes afterwards, that also changes with which username you are logged in.

I don’t know of any object in Spring or the JDK that could easily be (ab)used as principal for this; one that out of itself changes the result of its toString method.
So this is probably only exploitable in practice if the service being called changes the content of objects it receives as parameters in a way the attacker can control, so that its toString changes from one username to another one, and then still in the same request, looks up the name of the currently logged in user (which has then switched), and then for example returns a result that should only be visible to that user.

That’s a not completely impossible, but a bit farfetched scenario.

Conclusion

If you are using Spring and receiving serialized streams from an untrusted source (with RMI, Spring Remoting with HttpInvoker,…) you should upgrade to a fixed version of Spring asap.

Standard Java serialization is a powerful and flexible mechanism. But that leads unexpected security consequences and many opportunities for abuse. Vulnerabilities related to it keep popping up. Most of those where about breaking out of a local sandbox, but here it applies in a remote context. I don’t expect that stream of problems to end.

It continues to be a useful mechanism in the right situation, and applying these updates will avoid the specific issues here for now. But I recommend you stop using it altogether for untrusted remoting if you care about your security.