#cryptonoobs

What are side channel attacks and how do they affect cryptography?

Suppose your birthday is coming up soon, and your best friend told you that they bought a gift for you. You’re anxious to know what they got you, so you ask them:

"Is it a new watch?" “No.” "Is it a hat?" “No.” "Is it a computer?" “No.” "Is it a book?" “No.” "Is it a video game?" “No.”

You’re not getting anywhere. Your friend will say “No.” no matter what you guess, even if you guess right. You need another source of information. You try asking again, but this time you pay close attention to their actions as they reply:

"Is it a new watch?" “No.” (expression=neutral, eyes=looking at you) "Is it a hat?" “No.” (expression=neutral, eyes=looking at you) "Is it a computer?" “No.” (expression=neutral, eyes=looking at you) "Is it a book?" “No.” (expression=nervous, eyes=looking away from you) "Is it a video game?" “No.” (expression=relief, eyes=looking at you)

Now can you guess what your gift is? From these results, you can be pretty sure that your gift is a book. If you want to be even more sure, you can ask the questions again. If your friend’s expression and eye movements are always changing after asking, “Is it a book?” you can be pretty sure that’s what it is.

That’s a side channel attack. You’re getting no information from the actual data in the response (“No.”), but the way the response is delivered is leaking the secret information you want.

Computers don’t make side channel attacks quite so obvious. They don’t have faces to convey emotions. So how is the information leaked in a side channel attack against a computer? There are a bunch of different ways:

How much power the computer uses when it does something.

How long it takes the computer to do something.

Which areas of the computer’s memory have been accessed.

Unintentional electromagnetic radiation emanating from the system.

Sounds coming from the system (beeps, hard drives working, etc.).

The time that network packets get sent out of the system.

These are some of the ways a computer can unintentionally leak information about what it is doing and the secrets that are stored inside of it.

This leakage can be devastating to cryptography software. Even if the cipher is secure, there are no attacks against the protocol, and the implementation follows the specification exactly, a secret might still be leaked out through these avenues, which we call “side channels.”

The next sections present some real examples of side channel attacks. They should give you a good idea of how devastating these attacks are on cryptography software.

Timing Analysis of Keystrokes inside SSH

This attack was presented in Timing Analysis of Keystrokes and Timing Attacks on SSH by Dawn Xiaodong Song, David Wagner, and Xuqing Tian.

Secure Shell (SSH) is a secure way of connecting to another computer and controlling it with a shell (terminal). All of the commands and responses are encrypted and authenticated, so someone eavesdropping on your Internet connection should not be able to figure out what you're doing on the remote system.

The ciphers are good, the protocols are good, and the implementation is good. Even so, the trio of researchers realized that information about what the user still gets leaked, through the time between the user's key presses.

When connected to a computer over SSH, every time you press a key, your computer immediately generates an Internet packet and sends it to the remote computer. That means, if you're eavesdropping on an SSH connection, you see a packet sent shortly after each key press. You don't know which keys were pressed, but you know what times they were pressed, and, more importantly, the times between key presses.

The researchers showed that, when a user is typing, the time between their key presses leaks information about what they're typing. For example, on a QWERTY keyboard, the time between pressing "a" then "j" (which is on the home row and is pressed by the index finger of the left then the right hand) is going to be a lot shorter than the time between pressing "z" and "1" (which is pressed by the same finger and the keys are very far apart).

Using this fact, the researchers constructed an attack tool that extracts about 1 bit of information per character pair when a user is typing a password. This means that if you can observe an encrypted SSH connection, and the user types a password, the information leaked through the keystroke timings greatly reduces the number of passwords you'd need to search to find the right password.

To remove this side channel, SSH should send packets at a fixed rate, even if the user is not typing or is in between key presses. If a packet gets sent every 50 ms no matter what, and there is no way to distinguish a keystroke packet from a "chaff" packet, then the eavesdropper won't learn anything about the time between key presses.

Cache Attacks on the AES Cipher

This attack was presented in Cache Attacks and Countermeasures: the Case of AES by Dag Arne Osvik, Adi Shamir, and Eran Tromer. A similar attack was demonstrated by Daniel J. Bernstein in Cache-timing attacks on AES.

All modern computers have a "cache" between main memory (RAM) and the CPU. This cache speeds up access to areas of memory that have been used recently. If an area of memory has been accessed recently, it's probably in the cache, so accessing it again will be quick. If the area hasn't been accessed in a long time, it has probably been evicted from the cache, so accessing it will be slow. The difference in time can leak information about what a process is doing.

This attack was applied to the AES cipher in the two papers linked above. Essentially, fast implementations of AES use lookup tables, which are arrays used to quickly convert one value into another. The indexes AES uses into these tables depend on the secret key, so there's a possibility that the difference in memory access time caused by the cache can leak information about the secret key. That is exactly what the authors demonstrated.

The authors demonstrate two different techniques for extracting the key. I'll give a simplified explanation of each.

In the first, called the Evict+Time attack, they evict part of one of the lookup tables from the cache, so that all of the AES lookup tables are in the cache except for one index in one table, then they run the encryption. If the encryption accesses that index that has been evicted from the cache, it will run slower, otherwise it will run at a normal speed. So, by timing how long the encryption takes, they can figure out if that table index was accessed or not. Since the table index depends on the key, this leaks information about the key.

The second type of attack, called Prime+Probe, first completely fills the cache with the attacker's data. The encryption process is run, and as it is running, the parts of the lookup table that it uses are loaded from main memory into the cache. Since the cache is full of the attacker's data, some of it will have to be evicted to make room for the part of the table. Once the encryption is done, the attacker accesses their data again (to see which parts have been evicted from the cache), and this tells them which table indexes were used by the encryption process, leaking information about the key.

There is no good cross-platform cross-architecture defense against this kind of attack. The only sure defense is to write code whose memory access pattern does not depend on secret information. That means, among other things, no using secret information as indexes into an array.

Power Analysis of RSA

This attack was presented in Power Analysis Attacks of Modular Exponentiation in Smartcards by Thomas S. Messerges, Ezzy A. Dabbish, and Robert H. Sloan.

RSA is a public key cryptosystem. Encrypting a message involves raising it to the power of the secret key. This is done using an algorithm called "square and multiply."

Here's a simple way to think about it: Loop over all bits in the secret exponent, and for each bit, if it is one, perform a multiply operation then a square operation. If the bit is zero, do not perform the multiply, just go straight to the square operation.

It turns out that by watching the amount of power a device uses, you can determine whether the multiply routine executed or not. That leaks the corresponding bit of the secret exponent. If multiply was executed, the bit is 1, if multiply was not executed, the bit is 0. So, by watching the power usage, you can extract the entire secret key. Here's what it looks like in a simulation:

This is obviously a devastating attack, since it leaks the entire secret key. To defend against it, you have to make sure that the amount of power your code uses doesn't depend on secret information.

Noise Floor

At DEF CON 21, @0xabad1dea gave a talk in which she demonstrates how you can use cheap (~$15) software defined radio hardware to learn information about a (very unshielded) system, including getting a (very) rough view of what's being shown on the monitor.

Conclusion

There you have it. That's only a very small sample of the side channel attacks that have been found. I would love to have written about more, especially this one, but I don't want this post to go on forever.

Side channel attack research is still very active. If you're interested, check out some of the papers I've linked to and the papers that they cite. You can even try to implement some of the attacks yourself.

What is "Crypto Noobs"?

"Crypto Noobs" is a series of posts where I answer your crypto questions. Each month, I will select one question and answer it in the next "Crypto Noobs" post.