It’s been a few days since the attack on RSA / SecurID was made public. Last Friday, I considered potential risks the compromise may pose to RSA’s customers. Since then, the security world has been buzzing with analysis of risks, worst-case scenarios, and second-guessing of the offical RSA press releases.

Late yesterday, RSA released additional information via their SecureCare system. However, as this is only available to RSA customers, I haven’t been able to directly review it. Rich Mogull, at Securosis, has posted his take in an update last night, and includes some very good, specific recommended actions. I’d like to take a moment to present some back-of-the-envelope numbers relating to a theoretical attack scenario, especially in light of what (little) was just revealed by RSA.

Briefly, we still don’t know what was compromised in the breach, nor do we have any real way to quantify the risk that may present to users of RSA tokens. The just-released note included the following:

“To compromise any RSA SecurID deployment, the attacker needs to possess multiple pieces of information about the token, the customer, the individual users and their PINs. Some of this information is never held by RSA and is controlled only by the customer. In order to mount a successful attack, someone would need to have possession of all this information.”

This still doesn’t tell us much. Which information is “controlled only by the customer”? The user’s password and PIN, certainly, but what else? The token’s serial number? It’s seed value? Beyond those items, what else is left to have been compromised at RSA?

Again, my fear remains that seeds, in some form, were compromised. If that is the case, then is there any way to estimate how easy it could be to attack one or more accounts using compromised seed information? Though there’s quite a bit we don’t know, it is still possible to make a rough estimate at the effort required, with a few simple (and I believe, easily defensible) assumptions.

A quick disclaimer: I do not have knowledge of the algorithms, aside from what I’ve been able to glean from others' attempts at reverse-engineering them, and most of that dates to the older version of the system. So it’s quite possible that some of these assumptions will be wrong. But based on what I’ve been able to learn, I’m confident that I’m at least on the right track. It is my hope that this thought exercise will help RSA customers with a more concrete understanding of the system to accurately guage their own levels of risk.

First, let’s remember that any attacker will need to have more than just a list of seeds. They’ll need to identify the specific seed in use by their target. And they’ll need the target’s PIN and possibly a password as well. A key reason for using this kind of authentication is that you presume the PIN and password can be collected using other means, such as phishing, or man-in-the-middle attacks.

Assumption 1: The attacker already has all required information (userid, PIN, password, recent valid tokencodes) for one or many targets at your organization.

RSA supports many different kinds of tokens – and further research indicates that some of these have slightly different features. Tokens can create 6- or 8-digit tokencodes, for example. Soft tokens may be configured to incorporate the user’s PIN directly into the resultant tokencode, while hardware tokens keep it separate. It’s even possible that different models of hardware tokens use slightly different algorithms, with the differences all tracked in the authentication server. Of course, none of these algorithms have been publicly released by RSA. Determining which token types are in use at the target’s organizaton might be possible through network based attacks, or even simple visual observation of token fobs hanging from lanyards.

Assumption 2: The attacker is well-funded and has already acquired or reverse-engineered the algorithm used by a large fraction of your organization’s tokens.

As has been described before, current tokens use a 128-bit seed value for their cryptographic algorithm, which is far too large to brute force. But a compromise that reveals, for example, all seeds which have ever been issued, could reduce that significantly. However, at least some soft tokens can create seeds dynamically, in a secure exchange with private authentication servers. These seeds need never be sent to RSA (though it’s possible they are, again, that’s not entirely clear).

Assumption 3: The attacker has acquired seeds used by 40 million already-issued hardware tokens, which are in use by a large proportion of your user population.

Finally, because the algorithms are unpublished, we still do not know whether tokens use actual clock time, or some internal ticker that’s simply synchronized with the server. Because this can have a significant impact on the speed needed for the attack, we’ll consider both possibilities.

So, the attacker has the algorithm, a list of seeds, and one or many userids, PINs, and associated valid tokencodes. How do they identify the seed used by a given person, and thus, gain the ability to replicate their token and impersonate that user at will?

Let’s assume they have a single seed, and they’re 99% sure it’s for a given user. But they want to double-check. Take the tokencode they’ve already acquired, and look at the timestamp from when it was used. Put that timestamp, and the potential seed, into the algorithm, and see if the result matches the tokencode you have. If it does, bingo. If it doesn’t, maybe back the timestamp up 30 seconds, and also 30 seconds the other way, just to account for clock skew.

Total effort: 3 calls of the algorithm.

How long would this take? It’s impossible to tell without understanding how the algorithm works. If the system performs many successive encryption operations, then it could be very slow. However, since hardware tokens are constantly computing new tokencodes, it’s likely this would produce too much of a drain on the battery.

Assumption 4: The algorithm is very nearly equivalent to a simple AES-128 encryption of some small data set.

According to Wikipedia, a single AES-128 encryption of a 25-byte payload should take about 1 microsecond (for certain modes of AES). That’s probably on the high-end for the payload size, but since this is just a back-of-the-envelope calculation, we’ll go with it.

Assumption 4a: The algorithm can perform 1 million tokencode computations per second.

So, to verify a single seed, against a single observed tokencode, with a known absolute time for the tokencode, should take 3 microseconds.

Now, what if the token doesn’t use absolute clock time, but instead uses a counter unique to each token? A single year contains (approximately) 525,000 minutes. A token which changes every 30 seconds, therefore, goes through 1.05 million tokencodes in a year. If a token has a useful lifetime of 5 years, that’s just over 5 million values. In practice, tokens proably only last about 3 years or so, but this is probably a good upper limit.

To verify, then, a tokencode using an internal counter, the attacker would need to have two consecutive token codes (not difficult, given assumption #1), and would need to run through all 5 million potential time values. If the algorithm can compute a million tokencodes per second, that’s 5 seconds to test. (Actually, marginally more, as whenever a ‘hit’ is encountered, the 2nd tokencode will need to be computed to verify it wasn’t a coincidental result.)

This is all assuming the attacker has a pretty good idea of the target’s seed, which is pretty unlikely. How long, then, would it take to run the above tests against 40,000,000 compromised seeds? Simply take the two figures (3 microseconds and 5 seconds) and multiply by the size of the seed list.

# SeedsAbsolute time (clock-based)Relative time (token-based timer)
1 3 microseconds 5 seconds
40 mil 2 minutes 6.3 years

As you can see, if the tokens use a real, clock-based time, then an attack could complete in just a few minutes. If each token has its own clock (synchronized with the server at activation), then an attack across 40 million seeds takes much longer. However, this assumes a single CPU. In an 8-core system, it could conceivably take 1/8 as long, or 289 days. Put together a rack with a dozen such systems, and now the attack is only 24 days. Even if we double the guess, that’s well within the time defined by a typical password aging policy, and certainly worth the effort to a well-funded attacker.

Once again, the bottom line is that the lack of specific details from RSA, and the obscurity of their underlying algorithms, makes it nearly impossible to know what the true risk is. I’ve made a few assumptions here, but I don’t think they’re far off. If, as many are growing to suspect, some large number of token seeds have been compromised, then I believe the risk is real, and could be significant for some customers.

The Securosis analysis properly identifies high-value targets such as corporate executives or defense contractors, as having the highest risk to this sort of (hopefully still theoretical) attack. If it is the case that seeds have been compromised, then these organizations should probably be evaluating options. Moving high-profile users to soft tokens with newly-generated seeds would be a good short-term solution until new, uncompromised tokens can be acquired.

Finally, all organzations should review the first, key assumption: that an attacker already has (or can readily acquire) a valid userid, PIN, and tokencode combination. Reminding users of ways to verify secure communications (to reduce the chances of a man-in-the-middle attack) is a good first step. Additional traning to recognize the inevitable phishing attacks should probably also be seriously considered. Changing passwords and/or PINs more frequently, at least until the compromise has been better described and risks better assessed, may also be wise.