Information leakage and side channel attacks

A while ago, I introduced a toy implementation of the Vigenere cipher to illustrate how running key ciphers work. This is a fun cipher to work with, since you can implement it with a pencil and paper. Just remember, it’s not anywhere near secure enough to be used in practice.

In short, it’s quite vulnerable to eavesdropping attacks and trivial to break. It’s also quite easy to use incorrectly.

The Vigenere cipher is effectively a simplified version of a one-time pad. So long as your key is sufficiently random and never reused, a one-time pad is unbreakable. Given the Vigenere cipher is most frequently used with fragments of books for a key, it’s easy to accidentally (or intentionally) reuse a key.

Reusing a key for a one-time pad voids the security afforded by that encryption cipher. Through careful frequency analysis, and a technique called a “crib drag,” you can quickly and easily recover the plaintext of multiple messages.

Once you’ve mastered this kind of attack, you’ll naturally want to try your hand at attacking more secure ciphers, like AES. This is a complex cipher that can be difficult to use correctly, and incorrect implementations are easy targets for attack.

Padding oracle

For a simple illustration, assume we’re leveraging a server that implements 128-bit AES. The encryption algorithm itself isn’t our attack vector; we want to target the padding it uses.

Block ciphers, like AES, expect an integer number of full blocks. If our plaintext is too small, we have to add padding to the message such that it’s log enough to encrypt. In our illustration, we can leverage PKCS #7-style padding. In this scheme, the end of the message is padded with a repeating integer representing the number of padded bytes.

A message padded with four bytes would end in \04\04\04\04. A 6-byte padded message would end in \06\06\06\06\06\06.

Neither the encryption scheme or the way it uses padding are vulnerable in and among themselves. The server implementing the encryption, though, can leak vital information about both.

If the server is configured in such a way that it returns information to client requests, we trick the server into spilling its secrets by modifying the final bytes of a message. A valid message (with valid padding) will return a successful response. A corrupted message will return a failure.

Through repeatedly submitting a slightly modified string of already-encrypted bytes, we can leverage the above behavior to eventually decrypt the message one byte at a time.

Attacking the way the server leaks information about itself is using a side channel to decrypt the message. It’s not an uncommon attack, and seeing how simple it is in practice can be sobering!

Applications in the real world

Different components of our products can be vulnerable to similar attacks in different ways. A website returning a 4XX level error in response to badly-formed (encrypted) data versus a 2XX response is one such example. As engineers, we code things in a certain way to be helpful – if we intercept an error we want to provide feedback. Unfortunately some of that feedback might provide a useful exploit route for individuals with nefarious intent.

When it comes to usernames and passwords, I know it’s considered a vulnerability when some sites take longer or return a different message for usernames that exist but fail to match a particular password. I’ve seen backs fall prey to this – an invalid username results in a quick error; a valid username (i.e. account number) with an invalid password results in a longer feedback look and a redirect. This behaviors leaks information, and I’ve personally had my bank account hijacked due to this exact kind of behavior.

Even seemingly reasonable, supposedly well-implemented systems can fall prey to this kind of attack. We should all look very carefully at the next applications we built to ensure we’re not implementing dangerous cryptographic footguns.