Steganography embeds a secret message in a seemingly innocuous cover-object. This paper presents a framework for steganography with executables as cover-objects built on top of an existing binary rewriter. Executables differ significantly from previously explored cover-objects, we thus first identify the cover-specific redundancies that can be used to embed a secret message. Techniques are then proposed to exploit these redundancies to embed a secret message, obvious steganalytic attacks are identified and countered. As a proof-of-concept the introduced techniques are applied to and evaluated for the IA-32 architecture.