Side-Channel Attacks on Symmetric Encryption Schemes: The Case for Authenticated Encryption

Vaudenay recently demonstrated side-channel attacks on a common encryption scheme, CBC Mode encryption, exploiting a "valid padding" oracle [Vau02]. Mirroring the side-channel attacks of Bleichenbacher [Ble98] and Manger [Man01] on asymmetric schemes, he showed that symmetric encryption methods are just as vulnerable to side-channel weaknesses when an adversary is able to distinguish between valid and invalid ciphertexts.

Our paper demonstrates that such attacks are pervasive when the integrity of ciphertexts is not guaranteed. We first review Vaudenday's attack and give a slightly more efficient version of it. We then generalize the attack in several directions, considering various padding schemes, other symmetric encryption schemes, and other side-channels, demonstrating attacks of various strengths against each. Finally we argue that the best way to prevent all of these attacks is to insist on integrity of ciphertexts [BN00] in addition to semantic security as the "proper" notion of privacy for symmetric encryption schemes.