Payload location and key search techniques often rely on having a collection of stego images that use the same embedding key. This is a plausible scenario if the steganographer reuses the embedding key. In practice, however, the collection may contain several embedding keys. As a consequence, we must be able to separate these stego images by embedding key prior to applying these attacks. This paper addresses this fundamental problem. We first investigate the situation where the cover images are also available. Our analysis shows that it is possible to determine whether two stego images share the same embedding key provided that the payload sizes are not too large. We then present a practical algorithm to separate stego images by embedding key in the case when the cover images are not available. Our algorithm uses a cover estimator to reconstruct the cover images. Using the residuals computed from the stego-estimate image pairs, our algorithm separates the stego images via spectral clustering. Experimental results show that our algorithm performs well against popular matrix embedding schemes. Once separated, we perform exhaustive key search, using the computed residuals, to recover the embedding key.