Can the numbers on RSA SecurID tokens be predicted?

Question

My workplace uses these SecurID tokens which provide you with a temporary password, the code will expire after a short time. I have always been fascinated by the things, because it seems as though all the logic to calculate the next number must be physically located inside the device.

Given physical access to the token, is it possible to predict the numbers? How? Without physical access, is it theoretically possible to predict future numbers from previous numbers, with or without knowledge of the seed?

*I'm not attempting to crack it, just interested out of mathematical curiousity!

Answer 1

What SecurID tokens do is not completely public knowledge; RSA (the company) is quite wont on releasing details. What can be inferred is the following:

• Each device embeds a seed. Each seed is specific to a device.
• The seed of a device can be deterministically computed from a master seed and the device serial number. The serial number is printed on the device. This computation uses cryptographic one-way functions so you cannot guess the master seed from a device seed.
• From the device seed and an internal clock, the number is computed, yet again with a cryptographic one-way function.
• The derivation algorithms have been leaked, if only because the verification servers must also run the same algorithm, so these algorithms exist as concrete software in various places; leaking and reverse-engineering are mostly unavoidable in these conditions.

Under these assumptions, then:

• If you know the device seed, then you can compute future numbers at will.
• If you know the master seed and the device serial number, you can compute the device seed.
• Knowing seeds from other devices should gain you nothing into guessing the seed for a given device, unless the cryptographic one-way function which turns the master seed into device seeds has been botched up somehow.
• Knowing past numbers from a token should gain you nothing into guessing the future numbers from the same device, unless the cryptographic one-way function which turns the device seed into numbers has been botched up somehow.
• Extracting the device seed from the physical device itself is theoretically feasible but expensive, because the device is tamper-resistant: it is armored and full of sensors, and will commit electronic suicide if it detects any breach. If we take the example of smartcards, extraction of the device seed is likely to cost several thousands of dollars, and be destructive to the device (so you cannot do it discreetly).

On March 2011, some systems have been compromised in RSA, and it seems probable that the attackers manage to steal one or a few master seeds (it is plausible that the devices are built in "families" so there are several master seeds). RSA has stated that 40 millions SecurID tokens must be replaced. If you know the serial number of a token (it may be printed on the outside of the token), you can use the Cain & Abel tool that @dls points to; presumably, that tool implements the leaked algorithm and master seed(s), and can thus produce the future token outputs (I have not tried it). This would work only with servers which still accept the tokens from the 40-million batch which is to be replaced. I do not know how far RSA and its customers have gone in this process, so it may be that this attack will not work anymore. It really depends on the reactivity of the people who manage server you attack.

(If these system administrators have not replaced the compromised devices after nine months, then chances are that they are quite lax on security issues, and the server may have quite a few other remotely exploitable security holes.)

Answer 2

If you have its secret information, you can generate the numbers just as it would. If you do not, it's theoretically possible to make predictions based on what you've seen because the numbers are mathematically related. However, their relationship is complex enough that it is believed to be computationally infeasible to do so. That is to say, the amount of computation needed to make that prediction would take substantially more time than the lifespan of the token. If, for example, an average token were replaced every 10 years, an algorithm which computes its secret information or its series of values which takes a billion years to run when run in parallel by all known computers would be unhelpful in practice.

This computational infeasibility is the fundamental basis for all useful mathematical cryptographic systems. But in all cases, all we have are cryptographic tools where reversing them or solving for their secret information is believed to be computationally infeasible. New discoveries may reveal that some schemes are easier to break than were believed.

Answer 3

I work at RSA on the SecurID project. The earlier answers are correct.

If you know the seed, you have a chance to work out the passcode (the temporary code displayed). But all the devices are given a random seed when they are manufactured, and the seed value is not stored anywhere.

Even if you own an Authentication Manager, you cannot guess the passcode since only the Admin can upload the token list. The information on this list is necessary to generate the passcode for a certain SecurID or Soft Token. If On-Demand Authentication is enabled, the user can request a passcode via SMS or email, but the code is still based on the token that is assigned to the user.