The OSCI-transport protocol is used for data exchange between public agencies. It is the obligatory communication protocol for public administrations and therefore the basis for e-government in Germany [1]. It attempts to provide a secure channel [2] for communication between government agencies [3]. Right now the protocol is used in many different areas such as the population registration [4], the public health system [5] and the justice system (currently migrating to version 2.0) [6]. OSCI-transport claims to provide confidentiality, integrity, authenticity and non-repudiation for content exchanged even over insecure channels such as the Internet [1]. This, among other things, means that an attacker should not be able to read or manipulate messages.