YubiKey Key Storage Module Review

Overview

Today, I'm reviewing the YubiKey Key Storage Module code. It is a PHP application designed to be run on a locked down server.

Operation

The basic premise of it's running is this; there are 3 participants:

• The end user
• The YubiKey Key Storage Module (YubiKey-KSM) server
• An application server

The YubiKey-KSM is assumed to be running on a 'locked-down' server, separate to the application server. An authentication looks something like this:

1. The end user provides an OTP from their YubiKey to the application server
2. The application server hands the OTP to the YubiKey-KSM sever
3. The YubiKey-KSM server replies with an authentication success or failure message
4. If the OTP validated, the application server performs any further authentication, checks the counter values of the OTP are valid, and the grants access if all of the authentication is a success.

Attack

Worst Case

The attack is quite simple; if you assume the authentication server isn't completely impenetrable (For example, using a MySQL database).

This means that an attacker can simply grab a user's OTP credentials and use them immediately, without any hindrance.

Logs

The logs contain OTPs and their associated plain-texts. Enough said. Even successful authentications are written out to the logs. These can be reused by an attacker.

Man-in-the-Middle (MITM)

A man in the middle can harvest OTPs from a user (if there is, for example a poor application with doesn't use SSL on it's sign-in page, or perhaps a phising attack), then these harvested OTPs can be reused with the YubiKey-KSM PHP implementation.

Improvements

Hashing

Protecting the user's inner name (the secret) one should be a top priority. Hashing the password with a good configuration of scrypt should take ~100ms.

Cracking that hash would be difficult. If we assume that scrypt had been used correctly, and it takes one attacker's CPU 100ms to check one guess, it will take on average 1.5x10⁵ CPU-years to guess an internal name. Even being able to concurrently guess 10⁶ passwords at once reduces this to 57 days. That's a lot of CPU time and a hell-of-a-lot of RAM (assuming decent scrypt settings).

This still doesn't stop the attacker gaining the AES key for all the YubiKeys and just decrypting any that they see to extract the credentials. And bear in mind that OTPs can be printed to the YubiKey-KSM logs when a failure occurs

Logs

Just stop writing the OTPs and their plain texts to logs, ever.  Just don't do it. You wouldn't steal a car, you wouldn't log a user's password in plain-text, don't log a user's plain-text OTP credentials.

Use The Counter

Storing the last-seen counter against the user's public name is an absolute must. Don't leave any step of the validation up to the application server. If you've seen that counter value before, just stop, declare it to be an authentication failure and move on with your life! This helps to protect against a MITM attack

Attacking the Defences

A better way would be to simply retrieve the AES key (as outlined in the worst case) and attempt to sniff the incoming OTPs directly, thus breaking the secrecy of the internal name and counter. This allows an attacker to generate valid OTPs at will, even with all of the defences above implemented.

Conclusion

Using your own YubiKey-KSM is not an especially fantastic idea at the moment, with the code as it stands at this time. A few patches here and there, and it'll be much better. Some improvements might be:

• Allowing for different databases much more easily, 
• Hashing the credentials, 
• Asserting that the request for validation is genuine, 
• Rate limiting the number of requests for OTP validations that can be made in a given second,
• Not writing sensitive information to log files, 
• Checking the counter on the OTP before declaring an OTP valid).

These are quite a substantial modification to the system. However, excluding the 3^rd point, none of the above actually change the interface that the YubiKey-KSM server presents to the outside world.

Time-Hard Password Hashing in Java

Overview

So, you want to write your web application using, for example, Java, and you want to store user's credentials?

Well, standard is to hash them with bcrypt or scrypt and a random salt which is unique to each user. But, how do they actually work? Today, we'll cover hash stretching.

Any source code in this article is instructional only, use the real scrypt in production!

Onto The Rack

As mentioned above, what you should be doing is hashing the password with (for example) bcrypt and a really good unique salt. Here's a method for stretching the hash of a user's pass phrase.

The plan is to repeatedly hash the user's password and hash so that to get the user's password, they have to do a very specific (read, high) amount of work.

public class StretchedHash {
  private MessageDigest hash;

  public StretchedHash(MessageDigest hash) {
    assert hash != null : "You cannot stretch a user's password with a null hashing algorithm.";
    this.hash = hash;
  }

  public void hash(String password, String salt, Integer stretch) {
    assert stretch > 0 : "You cannot negatively stretch the hash of credentials";
    // We use funny concatenation to force a one-to-one mapping.
    byte[] digestBytes = hash.digest((salt.length().toString() +
                                      password + salt).getBytes());
    for (i = 0; i < Math.pow(2,Double.valueOf(stretch)); i++) {
      digestBytes = hash.digest(digestBytes);
    }
    return new BigInteger(digestBytes).toString(16);
  }
}

Problems?

This solution does not actually guard against GPUs very well. SHA-512 has a very small memory foot print, and so can be farmed out to GPUs nicely. Even stretching the hash doesn't help that much, the hashes can still be checked very, very fast on a rig with a few GPUs.

Even worse, many hashing algorithms (e.g. SHA1) is very small in hardware, meaning that it is trivial to implement several on an FPGA, or have them fabricated in custom silicon.

The way to make this better is to force it to require multi-megabyte amount of RAM. But not only that, this requirement should go up as time goes on -- just like the amount of CPU time required should go up.

This makes the problem evident. You are buying servers to serve your application to honest users. Your attacker is specialising in one thing: Getting your user's credentials. Unless you specialise your hardware to defend well, you're always going to be at a disadvantage.

In my opinion, shared secrets (i.e. passwords) is a soon-to-be-dead form of authentication, as there are just too many vectors of attack, and the end user will often re-use the same shared secrets for different services. People are bad at strong authentication.

The state of Java in FreeBSD

Available Implementations

• Sun's JDK
• Sun's Linux JDK
• OpenJDK
• DiabloJDK

We're going to focus on OpenJDK, since Oracle is probably giving Sun's Java a very slow death. We know at least two things:

1. OpenJDK is written in Java.
2. BSD's ports system uses source code to build the packages locally

Points 1 and 2 together mean that I need Java to build Java. This is the same problem that Haskell has when you attempt to build it. There's a few ways of solving it:

1. Have a cheap and cheerful Java compiler written in a language that you already have a compiler for.
2. Use an existing Java compiler to build Java.

OpenJDK does not supply a compiler written in anything other than Java. This means that to install Java, you're relying on a non-free Java. 

Luckily, there are multiple solutions:

• A bare-bones (aka bootstrap) Java compiler written in C/C++ to bootstrap OpenJDK into life
• Binaries from OpenJDK

However, both of these have some major problems.

Writing a bootstrap compiler in C/C++

Java is a big language. I presume something like 95% - 99% of the language features in Java are in use in the OpenJDK compiler and virtual machine.

This means that any bootstrap compiler & associated VM will be very big. Possibly warranting it's own project.

Being produced by the OpenJDK community and written in something-other-than Java will also likely be an issue -- I assume the OpenJDK community is most proficient and prefers writing things in Java.

Binaries from OpenJDK

This is a problem, since the binaries that OpenJDK sends out will have to be for every OS and every architecture that they want to support. This is a huge burden and simply not feasible

Can you imagine having to either cross-compile then test on, or directly compile OpenJDK on  ARM, AMD64, x86, MIPS, SPARC? Not to mention the array of OSes that may run on the above architectures. 

FreeBSD's Solution

FreeBSD's solution attempts to neatly side-step the solution. Their port of OpenJDK relies on the "DiabloJDK". This is Sun's Oracle's JDK licensed by the FreeBSD foundation for usage. I'm not sure what the exact terms are, but this makes me uneasy (personally).

To install OpenJDK, you grab the DiabloJDK package off Oracle's un-navigable site and stick it in a very particular directory. When OpenJDK is being built, it uses DiabloJDK to build itself. You are then free to remove the DiabloJDK.

This is, officially, a bitch. Oracle require you to signup and agree to their Ts & Cs before allowing you to download stuff from their site. However, it does mean that OpenJDK don't actually have to bother very much about FreeBSD-specificities.

That's right folks, to get an open implementation of Java on your FreeBSD box, the standard method is to get a non-free implementation of Java on your FreeBSD box.

My (Proposed) Solution(s)

PyPy

We write a small, Java interpreter in PyPy (RPython), and directly run the un-compiled OpenJDK code on itself to compile it. 

Interpreters are supposed to be quick and easy to write in PyPy and it should therefore be within someone's grasp to do so.

Obviously, you'd need to install PyPy before this, and I think that requires Python, which is a very odd dependency for OpenJDK to have.

LLVM

LLVM is also supposed to be nice for interpreters and the like. Why not have OpenJDK depend on the LLVM tool chain? Maybe we can have a Java-to-LLVM bitcode compiler?

This is (as in the PyPy idea) a little bit of a strange idea, but most languages eventually need a C compiler to bootstrap them, why not use something closely related?

YubiKey Man-in-the-middle

Overview

This is just a brief outline of a man-in-the-middle attack on a YubiKey. It's already a widely known attack. [Edit 24th October 2012: As pointed out by Simon Josefsson this attack is valid for almost any OTP type device] 

Participants

• Alice, the valid user
• Bob the Bank, the person/service Alice wants to prove her identity to.
• Mallory the attacker

Attack

Mallory goes to the Bank's website and copies their design to a new place. He then puts up the credible-looking-but-actually-malicious website. As an aside, The HTML5 fullscreen API actually makes this quite easy, as you could make something that looks a lot like the user's browser, complete with green padlock to signify a good SSL connection and the bank's URL.

He then convinces Alice to visit the bad website and enter her credentials. When she enters her username, password and YubiKey OTP, Mallory uses them to empty Alice's account and then redirects Alice to the bank home page, making it seem like she's entered a bad password.

Alternatively, Mallory calls Alice and claims to be Bob. Alice believes him and hands over credentials, including an OTP. Mallory immediately uses it to interfere with Alice's account.

This actually becomes even more problematic, as Mallory could then potentially add his own YubiKey to Alice's account as an authorised user of Alice's account and remove Alice's access. Mallory can now access Alice's account at will.

Defense 

Even with the hardening technique mentioned in the clarification of my previous YubiKey post, this technique still works! 

The "correct" defense is for the YubiKey to refuse to give out an OTP except to someone who can prove their identity to the YubiKey, e.g. by passing a signed message to the YubiKey. However, this massively decreases the usability of the system and increases the cost to deploy, as it will require system-specific drivers.

The softer version of this is for people to not reveal their OTPs until they have been invalidated by usage.

OpenPGP SmartCard

Overview

The OpenPGP SmartCard is a card (not unlike the EMV/Chip-n-PIN cards in the UK) for storing private keys. It provides cryptographic functions (signing, encryption and decryption) on board the card.

Cost

An OpenPGP SmartCard from Kernel Concepts costs 13.90EUR, and a card reader with integrated PIN pad is 50.00EUR, for a total cost of 63.90EUR. This is significantly pricier than a YubiKey.

Hardware Required

Computer, assumed to be Linux, but binaries probably (?) exist for other operating systems. Not to mention the driver for the card reader.

All of the functionality of the card can easily be replicated in software, and it effectively is done so widely.

Usages

• GnuPG/PGP private key storage & usage
• SSH private Key storage & usage

Since all cryptographic functions are carried out on the card, as opposed to the machine, the private key is never on a host system, allowing for significantly more secure PGP and SSH private keys.

Given co-operation of browser vendors and service implementers, the OpenPGP SmartCard could reasonably be used in a challenge/response protocol not unlike that implemented by SSH to verify an authentication request for a user.

Weaknesses

For this section, we assume a challenge/response protocol has been designed for the card, not unlike that used in SSH.

Server-Side

If authentication server has been compromised, then no keys need to be revoked -- the authentication server only holds the public keys for each of the users. At worst, it could grant access to attackers and deny it to legitimate users.

If the implementation of RSA on the cards is not sufficiently hardened against timing attacks, then the server could mount a timing attack to discover the signing key stored on the card, given enough authentication attempts. Newer implementations of RSA are not vulnerable to this, by blind-signing a challenge-token the timing attack is defeated.

Client-Side

If the card can be stolen and disassembled, then the private key can be recovered, assuming it is stored unencrypted on the card. If the key is stored encrypted on the card (e.g. using the user's PIN) then the key cannot be recovered, assuming that the algorithm used to encrypt the key does not have any cryptographic breaks, or the user's pin remains secure.

Since cryptographic functions are supplied on-card, it should be relatively easy to strongly verify that the server requesting authentication is valid, thus eliminating many man-in-the-middle attacks.

Other

If the function used to generate the private keys is not sufficiently random, then the private keys of a given user could be guessed by an attacker. 

Hardening Techniques

I'm open to suggestions. The only real problem with this system vs. the YubiKey system is that the implementation is more often an exercise left to the reader.

Conclusion

An organisation with sufficient funds could use OpenPGP SmartCards to provide security in excess of that provided by a YubiKey, and long-term costs could potentially be lower, as a compromised authentication server does not mandate the re-issuing/re-burning of all cards.

However, it would be a significant investment for an organisation to deploy OpenPGP SmartCards, despite the additional security and functionality.

YubiKey

Overview

A YubiKey is a small USB key that is provided by Yubico [Edited to correct name]. When plugged into a computer, it provides a one-time password that uniquely identifies the YubiKey.

Cost

One YubiKey costs ~25USD (19.20EUR at the time of writing). Discounts are available for large purchase volumes.

Hardware Required

Computer of any major (Mac, Linux, Windows) OS. YubiKey token.

A software YubiKey could easily be implemented, e.g. as an application for a smart phone.

Operation

When a plugged into a host system, and a button on the YubiKey is pressed, a one-time-password is produced (OTP) and "typed" (by the fact that it is a USB HID) into the host system.

The OTP is as follows:

• Secret ID (6B)
• Session Counter (2B)
• Timestamp (3B)
• Session Use (1B)
• Output from an LSFR (a psuedo-random number, 2B)
• Checksum, CRC-16 (2B)

This is for a total of 16 bytes. The output is encrypted using AES-ECB and a 128-bit key which is also presumed unique to the device. This is then encoded in BASE16  [Edit 25th Oct 2012: It's not quite BASE16, it's referred to as ModHex and is specific to YubiKey. Thanks to Simon Josefsson] and "typed" to the host system.

The server which authenticates the device retrieves the plain-text of the OTP and verifies the secret ID. If the OTP decrypt successfully and secret ID matches a given username [Edit 25th Oct 2012: The sever also ensures that the session counter and Session Use have not already been seen and have increased monotonically. Thanks to Simon Josefsson], then the authentication was a success.

Weaknesses

Server-Side

If the server is compromised, all keys must be re-issued (keys can be "re-burnt" without re-purchasing). This is because the authenticating server will spill all of the YubiKeys' AES keys and secret IDs. 

Client-Side

If the client is compromised (i.e. the key falls into the hands of an attacker), the attacker could disassemble the device and retrieve the AES key and the secret ID. This would allow them to arbitrarily forge a user's YubiKey authentication. 

An attacker could also perform a live man-in-the-middle attack, by tricking or forcing the user to reveal credentials, and subsequently using them to login to services. This is because the YubiKey does not verify the authenticity of the authentication request before sending a token.

Other

If the procedure to generate the AES keys and secret IDs is not sufficiently random, an attacker could simply start guessing AES key/secret ID pairs and requesting authentication. I am not sufficiently familiar with the procedure for generating the AES keys or IDs, so it may be cryptographically strong (i.e. un-guessable without searching the whole space).

Hardening Techniques

First and foremost, protecting against man-in-the-middle attacks should be very high on the list, as it a very simple attack to perform. This means forcing the YubiKey to authenticate the authenticity of the request before providing credentials at any point. There should be no way to have the YubiKey present an OTP without it first verifying the credentials of a server (e.g. digital signature based challenge/response protocol). 

However, if you're implementing that, why not make it bi-directional (i.e. the server can authenticate the YubiKey using the exact same protocol)? Mostly because doing even single direction challenge/response authentication is very difficult, and breaks the assumption that the YubiKey is only a USB HID.

Secondly, if the server spills the AES keys and secret IDs, it is game over -- time to revoke the keys and force re-issuing or re-burning of the keys. A simple solution to have the YubiKey sign the OTP and send the signature to the server. The server would hold the public-key of the YubiKey. If this was spilt, it would not compromise the security of the system. This would, however, increase the length of the OTP substantially. It would also mean that secret IDs no longer need to be secret. This would not, however, protect against man-in-the-middle attacks.

Conclusion

Overall, the use of a YubiKey, combined with the use of a username and password (i.e. hardware and secret token for authentication) does make an authentication system significantly more secure. However, there is room to significantly increase the security of the YubiKey system, without major impact to the usability of the system.

Given that the YubiKey requires little extra software or hardware, it is a cost-effective and user-friendly method for increasing the amount of time, effort and skill an attacker must have to compromise a system.

Clarification, 2012-10-23 13:00

The hardening technique mentioned in the last paragraph is as follows:

• The server maintains a list of YubiKey unique IDs/public keys.
• The YubiKey writes out a message of the following format:
• Unique ID
• Session Counter
• Session Use
• Timestamp
• PRNG output
• Digital Signature of the above fields
• The server can then verify the OTP by checking the following:
• The ID is valid,
• The Session Counter/Use is greater than previously seen counters
• The digital signature is valid for the fields.

This output could optionally be encrypted using AES-EBC, but there's no need. The power of the system comes from the fact that the only place the private key is kept is the YubiKey (part of the assumption of this slightly modified system)

This would mean that should the server be compromised the unique IDs/keys be spilt, there would be no need to re-issue/re-burn the keys. This is useful when keys are used across multiple (>2 in the case of YubiKey 2.2), disconnected authentication servers (for example, if I used my YubiKey to gain access to my VPS host, to gain access to my banking and several other websites).

The YubiKey would need to also be able to "type" it's public key as part of registering itself with an authentication provider.

The draw backs of this modified system are as follows:

1. Cost. You'd need to re-issue the keys for any system that already uses the YubiKeys, not to mention that you need more computational power to perform a digital signature -- each YubiKey would be more expensive
2. You're relying on the digital signature algorithm. Depending on your algorithm chosen, will rely on the discrete logarithm problem or integer factorisation. These are assumptions, not guarantees.
3. The OTP would be much longer when typed. I don't actually think this is much of a problem, personally.