How do RSA tokens work?

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!