In many standards, e.g. SSL/TLS, IPSEC, WTLS, messages are first pre-formatted, then encrypted in CBC mode with a block cipher. Decryption needs to check if the format is valid. Validity of the format is easily leaked out from communication protocols because the receiver usually sends an error message when the format is not valid. This is a side channel. In this paper we show that the validity of the format of the decryption is actually a hard core bit predicate. We demonstrate this by implementing an efficient and practical side channel attack which enables the decryption of any ciphertext. The attack complexity is O(NbW) where N is the message length in blocks, b is the block length in words, and W is the number of possible words (typically 256). We also discuss about extensions to other padding schemes and various ways to fix the problem.