As you say knowing that the first two bytes of a valid decrypt must be say the gzip header bytes 0x1f 0x8b does provide a small chink that can potentially be exploited. If you are that paranoid they are easy to hide. Making two passes with the encryption algorithm is one easy way.