We study a problem of optimal auction design in the realistic case in which the players can collude both on the way they play in the auction and on their participation decisions. Despite the fact that the principal's opportunities for extracting payments from the agents in such a situation are limited, we show how the asymmetry of information between the colluding agents can be used to reduce the revenue losses from collusion. In a class of environments we show that the principal is even able to achieve the same revenue as when the agents do not collude. For cases in which it is not possible to do so we provide an optimal mechanism in the class of mechanisms with linear and symmetric menus and discuss the potential benefits of using asymmetric and nonlinear mechanisms. To address the problem of multiplicity of equilibria we show how the optimal mechanisms can be implemented as uniquely collusion-proof mechanisms.