How do RSA tokens work?

Question

I would like to understand how RSA tokens (SecurID) work, what is the algorithm used there, is it the same algorithm as the regular RSA encryption/decryption ?

Solution 1

Citing on Wiki

The RSA SecurID authentication mechanism consists of a "token" — either hardware (e.g. a USB dongle) or software (a soft token) — which is assigned to a computer user and which generates an authentication code at fixed intervals (usually 60 seconds) using a built-in clock and the card's factory-encoded random key (known as the "seed". The seed is different for each token, and is loaded into the corresponding RSA SecurID server (RSA Authentication Manager, formerly ACE/Server) as the tokens are purchased1.

So, it may have something related to the RSA public key algorithm. Little known about real internals of SecurID (security by obscurity), but there are some analysis, e.g. initial securid analysis and more at bottom of SecurID page in wikipedia.

Also, hardware tokens are Tamper resistant so it is almost impossible to duplicate stolen token.

UPDATE: Thanks to eyaler, there are no any public/private keys in classic SecurID; they are based on "shared secret", not on asymmetric algorithm. Wikipedia says, that variant of AES-128 is used to generate token codes from secret key ("seed"). The secret key is encoded into key at factory.

Solution 2

You can have a look at how it's really done at http://seclists.org/bugtraq/2000/Dec/459

The (oversimplified) mechanism is

hash = <some initial value>
every x seconds do:
   hash = hashfunction(hash + secret_key)
   print hash

Solution 3

I can give you a sense of how the Blizzard Mobile Authenticators work, since their code has been open-sourced. (archive)

The basic gist is:

• generate a hash using various secrets
• but also include the number of 30-second intervals since some starting time (e.g. 1/1/1970)

In brief pseudo-code it is:

String GetCurrentFOBValue()
{
   // Any code is released into the public domain. No attribution required.

   // Calculate the number of intervals since January 1 1970 (in UTC)
   // The Blizzard authenticator rolls over every 30 seconds,
   // so codeInterval is the number of 30 second intervals since January 1 1970.
   // RSA tokens roll over every minute; so your counter can be the number 
   // of 1 minute intervals since January 1, 1970
   // Int64 codeInterval = GetNumberOfIntervals();
   Int64 codeInterval = (DateTime.Now - new DateTime(1970,1,1)).TotalSeconds / 30;

   // Compute the HMAC_SHA1 digest of the code interval, 
   // using some agreed-upon 20-bytes of secret key material.
   // We will generate our 20-bytes of secret key material by
   // using PBKDF2 from a password. 
   // Blizzard's mobile authenticator is given secret key material
   // when it enrolls by fetching it from the web-site.
   Byte[] secret = PBKDF2("Super-secret password that our FOB knows", 20); //20 bytes

   // Compute a message digest of codeInterval using our shared secret key
   Byte[] hmac = HMAC(secret, codeInterval);

   // Pick four bytes out of the hmac array, and convert them into a Int32.
   // Use the last four bits of the digest as an index 
   // to which four bytes we will use to construct our Int32
   int startIndex = hmac[19] & 0x0f;

   Int32 value = Copy(hmac, startIndex, 4).ToUInt32 & 0x7fffffff; 

   // The blizzard authenticator shows 8 digits
   return String.Format("%.8d", value % 100000000);

   // But we could have just as easily returned 6, like RSA FOBs do
   return String.Format("%.6d", value % 1000000);
}

Solution 4

@VolkerK's answer links to C code that describes the algorithm for "64-bit" RSA tokens, which use an essentially custom algorithm (reversed-engineered ~2000).

However, if you're interested in the algorithm used by the more modern "128-bit" tokens (including the ubiquitous SID700 hardware tokens and equivalent soft-tokens), then have a look at the source code for stoken, an open-source project which thoroughly documents their workings; securid_compute_tokencode is the main entry point.

Essentially, the algorithm works like this:

• Generate keys from the current time and serial number
• Repeatedly encrypt the secret/seed with 128-bit AES
• Extract digits from the decimal representation of the output and add in the PIN for good measure

It's not all that different from the open standard TOTP algorithm (part of the Initiative For Open Authentication) used in Google Authenticator, YubiKey, Symantec VIP access, etc. … just MOAR SPESHUL AND PROPRIETARY for EKSTRA SECURITEH!

View more solutions

Comments

[osgx]

What type of tokens? One which is able to sign data or encrypt/decrypt keys, or the SecurID?

[CodesInChaos]

There is a standard for such authenticators TOTP, but I don't know if RSA tokens follow that standard.

[tomasyany]

For a very complete explanation (although not veeeeery technical), see ais-cur.com/IntrotoSecurID.pdf

[Kellen Stuart]

This should be migrated to the security stack exchange. Moderator launch!

[John Bødker]

You can find a good overall explanation here: How do RSA SecureID ® Keys Work?

[John Bødker]

Take a look at How do RSA SecureID ® Keys Work?

[CodesInChaos]

That code looks like an implementation of TOTP with its silly "use last byte to determine which bytes to output" feature.

[mistertodd]

@CodesInChaos Yes, the Battle.NET authenticator is a FOB.

[Tim D]

Rather than reference "bottom of SecureID page in wikipedia" please link directly to the paragraph, or better yet, summarize here.

[Ustaman Sangat]

But this would imply that, if hash at time T, say h(T) is known, the hash at time t + T, h(t+T) has to be computed by sequentially computing all intermediate hashes.

[tomasyany]

And how can we be sure that the time on the token will be the same that on the server. Of course they can start being the same, but unless it is a super duper atomic swiss watch, I don't think they will remain the same (unless the token can be connected to internet from time to time to update the internal clock).

[VolkerK]

Those "unconnected" tokens usually have a lifespan. During that time the device's rtc must be accurate enough to "stay" within a certain timespan window. It doesn't matter (much) if it drifts for a second over two years; the server compensates by accepting a larger window (within specified limits). But if the rcc drifts much further or loses track all together the token is void.

[tomasyany]

@VolterK Not completely true. You can't rely on "accurate enough" for this kind of things. I found the actual answer on ais-cur.com/IntrotoSecurID.pdf (page 10 and 12). They adjust the possible time drifts with the input from the user. I don't have the space to give a more detail explanation here, but in the link I put they explain it very clear in the section "Valid Token Time Window and Clock Drift Adjustment".

[VolkerK]

So which part of my comment is wrong or "not completey true"? The brochure you've linked to says exactly the same thing - the server accepts some drift. This also covers "time delay" caused by these slow conducting wetbags (aka humans). RTC accuracy isn't a big problem, battery life maybe still is. Even my 2€ (4DM) watch back in the days when I though knight rider is cool (mid-80ies) would have been accurate enough for a year or so. And a DS3231 e.g. is supposed to stay within 2ppm/yr and costs <50c, see amazon.com/Donop-DS3231-AT24C32-precision-Arduino/dp/B00HCB7‌​VYS

[tomasyany]

@VolkerK No, the brochure doesn't say exactly the same thing, it's similar but no the same. The difference is that the system doesn't rely on accuracy, it updates the time on the server according to the token given by the user. So if for example the user gives the last (but not current) token, the server now knows that the token time has drifts, and so updates his time to match the token's. In other words, you could use the same token forever, as far as you use regularly. If you don't use it for years, then the token you will give to the server will be too old for the server to update itself.

[tomasyany]

@VolkerK ... but even that last problem can be fixed. My whole point is that the server updates himself with the received code, and that is where your comment was not completely true: for it does matter "if it drifts for a second over two years" (more like it matters when it moves from a minute over a year).

[VolkerK]

Ok, that's a (generous) additional feature of the RSA turnkey solution. The device's clock still needs to stay within a certain time frame. I retract the concrete second and minute statement and replace it by "some maximum timespan (which you have to look up in the product's documentation)".

[jsha]

RFC 6238 doesn't mention RSA or SecurID. Is there another source suggesting they use the same algorithm?

[Chaitanya Uttarwar]

if this is ture then, FYI I learnt 1 passcode and used it after 2 hours and it worked.. how is this possible ??

[Joe Phillips]

I see no mention of time in this example. It implies the same hash and value would be produced every time?

[VolkerK]

@JoePhillips: "every x seconds do" <- there you go ;-)

[Joe Phillips]

@VolkerK Sorry, what I should've said was that the time isn't being hashed, so the hash would never change? You would have to include the current time inside the hash function somewhere?