Cloud computing platforms, such as Amazon EC2 [1], enable customers to lease several virtual machines (VMs) on a per-hour basis. The customer can now obtain a dynamic and diverse collection of machines spread across the world. In this paper we consider how this aspect of cloud computing can facilitate anonymous communications over untrusted networks such as the Internet, and discuss some of the challenges that arise as a result.