Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

enter image description here

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!

share|improve this question

migrated from math.stackexchange.com Dec 8 '11 at 12:34

This question came from our site for people studying math at any level and professionals in related fields.

3  
Given the serial code of the fob, it is possible to predict the numbers. The tool is called Cain & Abel. "The calculator produces valid tokens given the serial number and the activation key of an RSA SecurID device." oxid.it –  dls Dec 8 '11 at 3:50
1  
this would be on topic on security stack exchange if you want to migrate it –  Rory Alsop Dec 8 '11 at 8:56
    
ok sure, I can't see any way to do that though. no close option here –  wim Dec 8 '11 at 12:13
1  
I will sum Tom's answer in 570 characters or less. The algorithm used to generate the code is public knowlege because you can run your own RSA Authentication server. This means if you know the serial, the seed, and valid time value uou can generate the current and future code. As Tom points RSA's security was compromised, what exactly was leaked is unknown, what is known is the information leaked requires devices to be replaced ( a list of devices serials connected to their seed values would explain this fact ). –  Ramhound Dec 8 '11 at 19:26
    
Yes, it can be predicted by the chance of 1/1000000 on a single attempt :) –  Dog eat cat world Dec 9 '11 at 12:49
add comment

2 Answers

up vote 16 down vote accepted

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.)

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.