YubiKey Security

[phantomcircuit]

While working on implementing YubiKeys for various projects it struck me that the stated security of a yubikey token (128 bits) is substantially overstated.

The security of the tokens as most people use them is more like 18 bits.

If you're relying on these tokens for security I strongly suggest that you utilize username/password/OTP authentication and limit authentication attempts per user to something fairly low.

For most users this makes little difference, but it's definitely something to keep in mind when designing an authentication system.

[rjk]

Could you elaborate on the "as most people use them" part? As far as I know, it uses one full AES block, and contains fields for the serial, an 8 hz counter, and some other things.

[phantomcircuit]

I'm waiting on a response from Yubico before disclosing the exact nature of the flaw.

[2weiX]

on the day i ordered mine


obv.

[phantomcircuit]

MtGox has verified they perform a check which is not standard.

This substantially increases the security of yubikeys at gox.

It's important to note that the search space is still significantly smaller than the stated 128 bits.

[Stephen Gornick]

MtGox has verified they perform a check which is not standard.

This substantially increases the security of yubikeys at gox.

Phew.  Thanks for sharing this and for updating status.

[phantomcircuit]

Some people have figured it out so I guess I should just explain what the issue is.

The YuibKey OTP algorithm is fairly simple.

Each slot on the token is assigned a public id, a secret id, and an aes key.  The security of this system is supposedly based on the security of 128 bit aes, it's not.

The otp generated by the token is formatted like this.  public_id + aes(secret_id+counter+timestamp+session counter+random nonce+crc16)

Nominally the verification mechanism is to simply decrypt the encrypted portion, check the crc16, and compare the counter and session counter with the last used values; if they are higher then the otp is valid.

The issue here is that you do not need the correct aes key to generate random deciphered text. as they're only using a crc16 to verify everything approximately 1 in 2^16 (65535) attempts will generate a valid looking token.

Of course there are minor complications like the counter value has to actually be larger than any previously used counter (incidentally this means the security of a yubikey goes up as it's used!)

MtGox checks both the public id and the secret id; Unfortunately this does not appear to be the default authentication mode and I didn't see any warning of this issue when reading through the documentation.

If you're checking the secret id then you've got at least 48 bits of security which is probably better than most peoples passwords.

Obviously even the relatively broken authentication model when used with traditional username/password is more secure than not.

[Inaba]

So are you talking about MTGox's authentication or Yubikey's?  You keep going back and forth when talking about them, so I am unclear on which on you are referring to specifically.

[eldentyrell]

The otp generated by the token is formatted like this.  public_id + aes(secret_id+counter+timestamp+session counter+random nonce+crc16)

Nominally the verification mechanism is to simply decrypt the encrypted portion, check the crc16, and compare the counter ... as they're only using a crc16 to verify everything approximately 1 in 2^16 (65535) attempts will generate a valid looking token.

So the bug is that they aren't checking that the decrypted secret_id matches the actual secret_id.

Yes, that is a pretty serious bug in the Yubico server-side software.  Fortunately it should be fixable in software on the server side only (no need for new yubikeys) by doing what MtGox is doing:

MtGox checks both the public id and the secret id; Unfortunately this does not appear to be the default authentication mode and I didn't see any warning of this issue when reading through the documentation.

If what you write is true, Yubico needs to issue an advisory right away.  If they don't, you should consider issuing one.  Most security centers will accept a third-party advisory if you show you've contacted the company and they've refused to issue their own advisory.

Thanks for catching this.

[eldentyrell]

So are you talking about MTGox's authentication or Yubikey's?  You keep going back and forth when talking about them, so I am unclear on which on you are referring to specifically.

He's talking about software which was written by Yubico (maker of Yubikey) and deployed by Yubikey customers (like MtGox) -- although apparently MtGox has fixed the bug on the copy they're running.

[rjk]

Interesting. Yubico's free cloud authentication is tempting, but if it has this kind of flaw it is probably best to run your own auth server the same as MtGox is doing. But that means you also have to issue your own Yubikeys.

I've always wondered why Yubico would offer the auth service for free; it seems to me that if they wanted to be competitive and make a quick buck, they could just be a lot cheaper than Symantec VIP, but still have a steady revenue stream from a subscription model.

[Stephen Gornick]

From the Yubico blog:

Clarifications about YubiKey system security
2012-06-07
by jas4711

Recently, there was a discussion on the Bitcoin forum about the security of the YubiKey system.

As we understand the claimed problem, it is said that there would be a chance of about 1 in 65.000 to guess a valid OTP from a YubiKey. This would indeed be a very serious problem. We have verified that in the two current implementations supported by Yubico, the probability to correctly guess a valid OTP is less than 1 in 10.000.000.000.000.000.000. Considering the fact that guessing would have to be done over a network, and the latency involved in OTP validation, this is not a feasible attack. Based on what we have learned so far (see details below) we do not believe there is cause for actions for any of our customers or users.

Yubico invites further analysis of our solutions as it builds up confidence in them. We will update this blog entry as new information is available.

The vulnerability that has been described is that it is possible to create fake OTPs by trying OTPs until one of them succeed, and that this for some reason this will work with non-negligible probability. Before we proceed, we want to note that similar attacks is possible with any OTP or even password scheme, attackers can always try authentication many times. For example, with 6-digit OATH TOTP there is a 1 in a 1.000.000 probability to guess the current OTP for a particular user. We’d also like to note that nothing so far has even suggested that the AES key can be recovered.

The YubiKey algorithm is documented in the YubiKey Manual. Section 2 covers the basic steps, where a byte string is prepared and encrypted using AES in ECB mode and converted to a series of characters. Section 6 explains the details of the byte string. For more in depth discussion about security properties, see our YubiKey Security Evaluation.

The claim that has been made is that if you attempt random OTPs, validation of them would succeed with non-negligible probability. To protect against this attack, the YubiKey technology employ a couple of mechanisms. In typical scenarios, the Yubikey OTP is sent from a client to a centralized server for validation. The validation server will decrypt the OTP ciphertext to get a plaintext. Since AES in ECB mode is used, decryption will always succeed, for all random inputs. The next step is to validate the 48-bit private ID field and the 16-bit CRC value. For random inputs, the probability for the fields to match is one in 2^(48+16)=2^64. This is less than 1 in a 10.000.000.000.000.000.000. We believe this makes the attack unlikely to work in practical scenarios, since attackers rarely get a chance to attempt this many authentications. Note again that there is no risk that the 128-bit AES key is discovered this way. We are aware that CRC-16 is not cryptographic secure hash value, and this is intentional and the security of the YubiKey is not dependent on any cryptographic properties of the CRC-16 function.

The claim has been that validation software does not compare the 48-bit private ID field, turning the likelyhood of success into 1 in 2^16 or 1 in 65.536. This would be serious, but we have been unable to confirm this. Because Yubico’s server-side software is Free and Open Source (FOSS) we can provide pointers to the code and the relevant code is here for anyone to analyze. As you can see, it compares the internal identity with what is stored in the database. For the YubiCloud service Yubico employes hardware-based YubiHSMs to perform the decryption, as does several of our customers, which uses the python-pyhsm server software — however, in that scenario, the YubiHSM is responsible for performing the UID comparison. We have verified that the YubiHSM properly implement the comparison.

Finally, we’d also like to note that if a server implementation incorrectly did not perform the 48-bits internal ID comparison correctly, an attack normally result in a Denial-of-Service against the user’s YubiKey. This is because with random OTPs, the counter values will normally be far higher than what the YubiKey device has, and thus any real OTP from the YubiKey device will no longer work.

 - http://status.yubico.com/2012/06/07/clarifications-about-yubikey-system-security

[molecular]

From the Yubico blog:

Clarifications about YubiKey system security
2012-06-07
by jas4711

[...]
The vulnerability that has been described is that it is possible to create fake OTPs by trying OTPs until one of them succeed, and that this for some reason this will work with non-negligible probability. Before we proceed, we want to note that similar attacks is possible with any OTP or even password scheme, attackers can always try authentication many times.

[...]

urm. I had the impression the attack would not require an actual network-try of the guessed OTP and you could evaluate validity locally?

Did I understand wrongly or did they get it wrong?

EDIT: fixed quoting

[bitpop]

If their php library can be fixed so easily, is it being patched?

[rjk]

If their php library can be fixed so easily, is it being patched?

It wasn't broken.

[bitpop]

If their php library can be improved so easily, is it being patched?

[molecular]

If their php library can be improved so easily, is it being patched?

Probably their process of making changes to this library is not free and the reward does not exceed the cost.

[bitpop]

Can mtgox share this improvement they found all by themselves?

[rjk]

Can mtgox share this improvement they found all by themselves?

They didn't invent any new improvement, they are simply using it to it's full extent and not cutting corners in the deployment of the system. If you need more details, read the technical docs.

[bitpop]

then why are we blaming yubico?