YubiKey Side Channel Attacks?

Overview

Sometime ago, I wrote about the YubiKey, and I've also mentioned how the YubiKey is vulnerable to a simple MiTM attack, by simply phising the user. This is nothing complicated, and it's hard to defend against these sort of things.

Given the paper "Cache-timing attacks on AES" by Bernstein (2005) and recently "Fine grain Cross-VM Attacks on Xen and VMware are possible!" by Apecechea et. al. (2014) we now have to begin asking the question, what threats does this pose beyond OpenSSL, PolarSSL and libgcrypt?

This is not an actual attack by any means, it is speculation of what might be an interesting and fruitful avenue of research.

YubiKey

As in my previous post, the YubiKey's OTP mechanism is relatively simple; take one AES block (128b), including a counter and a secret Id. Encrypt said block (in the YubiKey "dongle") with a secret key shared between the dongle and the server, and type it into the host machine to be sent to the server for checking.

The server decrypts the OTP received and checks the various internal values, e.g. the secret Id, the counter value, etc. If all's well, access is granted.

The Attack

Apecechea's attack relies on co-locating a VMs with a target, profiling the hardware architecture, then sending chosen plaintexts to the target to be encrypted under an unknown key.

I am wondering if, given a VM which verifies YubiKey OTPs, one could co-locate a couple of malicious VMs, profile the server hardware, then send lots of OTPs to be validated (i.e. decrypted) to the target VM.

If this exposed the secret key for the YubiKey, one could then decrypt any previous YubiKey OTP, and extract the secret Id and other values, and simply forge valid YubiKey OTPs.

Mitigations

AES-NI

According to Apecechea's paper, AES-NI aware implementations were much more difficult to attack. This could well be a saving grace in many situations, not just the YubiKey situation.

YubiKey HSM

I am not familiar with  the YubiKey hardware security module, I know that it has undergone review, but I don't think that review extended to side-channel or physical attacks.

If the HSM is a constant-time verifier of YubiKey OTPs, then this is a winner. Any organisation using a YubiKey HSM is automatically saved.

Append a MAC

Appending a message authentication code (though, I'm going to guess that AES-CMAC is a bad idea) of the OTP would allow forgeries to be rejected outright without any decryption of the OTP.

This does not stop attackers from trying to get as many OTPs with valid MACs as possible and using them as part of their attack, but it would take a much longer time, since the paper calls for 2^26 to 2^28 attempts.

It would also make the typed OTP much longer, and that means more "typing" for the device, and more complexity in the device. The newer YubiKeys have OATH capabilities, so they should have HMAC hardware in them, which may make this more feasible.

Using a MAC may obviate the need for an OTP anyways, so what the hey.

Rate Limiting

Simply limiting the number of attempts you allow per second as a general rule would alleviate the problem, as the attacker does need a fairly large amount of attempts (though, by no means prohibitive). Making it take 1 second OTP verification would make the attack take 2^26 seconds (roughly 2 years) per YubiKey the attacker wished to break.

This obviously is not a great way to do things, but it's better than nothing, and combined with suitable key rotation (say, once a year), you'll be quite safe. But remember, attacks only get better.

Hardened AES

This would be super, but it would seem that new side-channel attacks on AES just won't stop. Be they power, timing, or cache-based, we're not fighting a winning battle here.

In much the same way as patching OpenSSL against BEAST lead to Lucky13, I worry that we're going to end up chasing our tail with this one, since the performance trade-off is so great.

Constant Time Encryption

It should be the case that something like Salsa20 is constant-time when implemented correctly. It should have no leakages.

Salsa20 is also more amenable to an embedded environment than AES, and offers similar security guarantees.

If I were the YubiKey guys, this is where I'd be focusing my attention and looking to migrate to, assuming I wanted to keep the current usage pattern of the YubiKey (Plug it in, have it "type" a password). It is a much faster, simpler algorithm, it's designed to be strong against side-channel attacks, the reference implementation is public domain, and written so that it makes no use of malloc, so that you can get it in an embedded system easily.

Seriously, Salsa20 is where it's at.

Conclusion

Looking at the YubiKey, since the verification makes use of AES, it makes sense to ask if it is safe against Bernstein's cache-timing attacks. On the assumption it is not safe against it, what measures can be taken.

Overall, I would say that a good implementation of rate limiting should be used, whilst looking to migrate away from AES to a constant time cipher like Salsa20. My strong preference would be Salsa20.

Salt with your Fries?

Overview

When storing a password or other sensitive data, a salt is a must. This post deals with the nitty-gritty of salt generation.

If you're here for simple advice, use bcrypt with a nice wrapper which handles salt generation for you.

Properties of a Salt

A decent salt must satisfy two minimal requirements: 

• Unique
• Unpredictable 

Uniqueness is fairly obvious, if your password database uses a static salt for all passwords, then it only defeats pre-computed dictionaries and rainbow tables. It does not protect you after your database is leaked, and your attacker knows the salt -- they can simply re-compute the dictionary using the salt and often break many passwords this way. Having a different salt for each password will force the attacker to create a dictionary for every password in the database.

Unpredictability is not immediately obvious. However, take a well known open-source system that uses a sequential integer as the primary key in the database and it's salt. This clearly satisfies uniqueness. However, if an account (say, for example, admin) is always the first account on the system and therefore always uses the salt "1". An attacker can pre-compute their dictionary with salt "1", when the database is leaked, the attacker can simply look up the hash value in the dictionary and see the password.

This however, presents a major problem. If I can't predict the value of a salt, how can I be sure it will not collide & violate uniqueness? 

The first, naive solution, is to simply throw away colliding salts. However, once you have a certain number of passwords, you'll spend all your time generating salts. 

The better solution is to ignore collisions, but make them extremely unlikely. With sufficient randomness, we can also ensure that collisions happen extremely rarely, even in a system which uses sharding or other "splitting" methods. It is this solution that we will explore. 

Unique Violations

The primary strength of a salt lies with the fact that an attacker must attack each password individually, or for our purposes, almost individually.

If each password can be expected to share a salt with two or three other passwords, then this is quite bad, as the amount of passwords that an attacker can crack by trying the salts is non-zero.

Ideally, an adversary picking a salt at random from a leaked set of passwords should have a negligible chance of picking a salt which will have suffered a collision, hence attacking any single salt gives them a negligible chance of breaking more than one password with that salt.

A simple manipulation of the Birthday Paradox allows us to determine the minimum bit-length for any salt conforming to this requirement, the equation that derived is:

b = log₂(n² - n) - log₂(p) - 1

Where p is the probability we're looking for, n is the expected size of the password database and b is the bit-length of the salt.

So, for our requirement on a system that's expected to use 10,000 passwords, and have an attacker not expect to have more than one collision in that set would need p set to 10^-5.

b = log₂(10¹⁰ - 10⁵) - log₂(10^-5) - 1
b = 48.83

Or about 48-bits of entropy, minimum.  

Existing Standards

NIST and RSA both give recommendations on the minimum salt length to be used in any key derivation function. NIST (NIST-SP800-132) recommends 128-bits and RSA (PKCS #5 v2.1) recommends only 64-bits. 

Most BCrypt implementations, when asked to get a salt for themselves will return a 128-bit salt, which is more than enough, and happens to comply with NIST's recommendations.

It is probably the case that RSA's recommendations are not sufficient for use in large organisations.

Conclusions

Simply put, if in doubt, just use bcrypt.

However, for your organisation, you can easily calculate the minimum bit-length required to ensure the desired amount of salt collisions. I would always plonk myself down on the safe-side of town and go with NIST's recommendations of 128-bits.

You should always bear in mind that poor random number generation from your OS or other source can lead to more collisions. The post above assumes good, uniformly distributed salts.

Shared-Secret Authentication

Overview

Authentication is difficult. Barring the issues of lost passwords, weak passwords, the philosophical concept of "identity", and a host of other issues, we'll be looking at performing authentication "correctly" for users.

Issues

Credential Leaks

This is a simple attack. An attacker somehow gets their grubby little mitts on a set of (username, secret) and the gig is up.

But even if you're storing a hash of the user's secret, there are still pit-falls.

Timing Attacks

Timing attacks are often overlooked, but they're usually only a problem for high-value targets. They almost always comprise a high level of knowledge about the internal system, but can be used to effectively do things like enumerate all of the usernames on your system.

This can be a problem, what if, like Facebook, your username is the user's email? This is bad, because it means that you are responsible for leaking the data to an attacker who may just add them to a spam list, or use it as another step in an attack on a user.

Online Brute-force Attacks

These are the simplest to imagine. Just start guessing the credentials and sending them to the server for authentication. You have to know nothing about the system to do this, with the exception of where it is.

These attacks can become more sophisticated, by using a botnet to distribute the authentication requests around the world, and by statistically guessing credentials. When combined with a timing attack to enumerate usernames and good statistical guessing of passwords, this actually becomes quite a formidable threat.

Replay Attacks

A replay attack is where an attacker captures a valid (usually encrypted) request to a system. The system doesn't distinguish one request from another, so when the attacker re-issues the request, the system gladly carries out the request again. This could be as simple as logging the user in, or moving money from one account to another.

Defences

Credential Leaks

These come in many forms. 

• You leak your database, and the shared-secrets (i.e. passwords) are not protected by a hash.
• You leak your database, and the shared-secrets are protected by a weak hash algorithm.
• The credentials passed in plain text over the wire on the way to your server.
• The credentials might be extracted from a "secure" tunnel. 

Given the broad nature of this issue, I will issue a few simple golden rules.

Ensure that any shared secrets are stored in your database using a strong hashing algorithm. I recommend scrypt and a reasonable password policy. With reasonable parameters, this ensures that any attacker has to spend a lot of cash to break an scrypt hashed password.  This covers the first two bullet points above.

And don't forget, that when hashing the password, you need to hash it with a salt which is cryptographically random and fairly big.

For the second two on a web application, always use SSL, and turn compression off. Do not store shared secrets on the client in cookies or anywhere else in the client. If you're not writing a web application, ensure that you use something equivalent to SSL on your connection between the server and the client. If you can't have this, you're going to need something other than shared-secrets for your authentication.

In general (for a web application) you want to ensure that your application is immune to XSS attacks, as it may actually be very easy for an attacker to use your site to send credentials elsewhere. This could be done by injecting a JavaScript keylogger into an otherwise perfectly valid page. If you're doing all this over SSL, then the subject of the attack will fully trust all of the script on the page to be from you, not an attacker, and will probably let the keylogger do it's business. Not cool.

Timing Attacks

This is quite feasible. Given a login procedure something along these lines:

1. Get the user's hash from the database. If there is no hash, return false.
2. Hash the given secret and compare it to the one in the database. Return the appropriate value.

Given that a good hash function should take ~100ms per password hash, an attacker can send hundreds of username guesses and random passwords down the wire. The attacker then measures the response time. The ones with a large response time are the ones which had their random passwords hashed, which means that a username was present.

There are several ways to defend, the most common is to attempt to engineer your solution to take the same amount of time regardless of the path it takes. This conflates your authentication code with code which tries to defeat a timing attack.

A better method is to leave your authentication code as-is, and wrap your authentication in an object which forces all requests to have the same average response time, regardless of whether or not the authentication was successful or not.

This has the benefit that, if your authentication process needs to query an external system, as well as internal systems, the external system need not be timing-attack resilient, and can be as simple as possible. It also keeps any code for checking locally-managed passwords simple.

The wrapper would simply keep a track of the average time that it took to perform a successful authentication. In the event that the authentication was unsuccessful, the wrapper would force the authentication to take the average time on total. Some code which has this idea can be found on my GitHub.

The source code above is in Java, and can be built using

ant dist

and run using

java -jar ./dist/lib/TimingAttack.jar

It will print out a series of authentication results and times to reach the result. You should see that the time on each should be (on average) the same, regardless of the result.

This doesn't protect against other side-channel attacks. If, for example, a malicious application was running on the same CPU as your application, there are a host of attacks (e.g. cache-miss side-channel attacks) that can leak information about what your application is doing. 

Online Brute-force Attacks

This is actually a very tough nut to crack. If we assume that the attacker is as sophisticated as possible; getting a botnet to do statistically very good guessing for them; then we have a serious problem on our hands.

The first way to help deal with this is to force (or encourage) your users to pick very strong, difficult to guess passwords.

The second way is to rate limit any guesses. In general, this is A Good Thing^TM as it prevents an attacker from using up system resources at an unreasonable rate, and thus protects against a simple denial of service attack.

The second way could be achieved by keeping a global (for Java, read Singleton) RateLimiter class which keeps a record of IPs and the most recent time they sent a request in. If it's been too recent, make them wait a long time.

An example of such a rate limiting can be found in the same GitHub repository as the previous example. It can be run in a very similar way, first build it:

ant dist

and run using

java -jar ./dist/lib/OnlineBruteForceAttack.jar

A potential modification would be to slow down the request for each user account individually, as opposed for each IP address. That way, each IP gets some number of guesses that get a reasonable response time for each user, thus helping any folks with NATs. However, this means that an attacker can DoS a user. Some combination of IP Address and account would be in order, but even that won't slow an attacker down much.


Replay Attacks

These are usually dealt with by correctly using SSL. SSL uses nonces (cryptographically strong random numbers) to ensure that two requests can be distinguished.

In a system which does not use SSL, you basically have to implement nonces yourself. This is not hard, but I won't cover it here. Basically you stick a random number into the request. If you've seen that number previously, discard it. If you didn't generate that number, discard it.

Conclusion

The "best" [Edit: shared-secret based] authentication system requires good passwords (for some value of good), hashes them with a really good hashing algorithm (my opinion is that a correctly-configured scrypt is the way forward), and defends against timing-attacks and simple brute-force attacks is the best.

However, you need to balance this against the needs of your user. How sensitive is the data you're storing? How well compartmentalised is your application? (i.e. can a compromise of one account lead to another user's data being exposed?) Do you have the time to implement all of this, or do you just want to scrypt the password and call it a day -- for now?

Either way, as I've mentioned before on this blog, I want shared-secret authentication to die.