Vulnerabilities in One Time Password (OTP) systems

Slashdot posted to Banks Begin To Use RSA Keys as Challenge-response vs response-only:

Challenge-response isn't inherently more secure than an auto-updating number based on time. Both are basically implementations of a pseudo-random function. With the auto-updater, the current time is essentially the challenge. And not having to type/scan in an explicit challenge is a lot more usable

Good point. There are also a number of vendors who have response-only tokens, less expensive competitors to RSA.

Also, the old X9.9 based Secure Net Key (SNK, aka Axent Defender) implementation of challenge-response was fatally flawed. There are still versions of this floating around, and it is an optional mode for the VASCO, Safeword, and CryptoCard tokens.

How long before someone finds a fast way of factoring large numbers and we're all screwed?

There's no direct relationship between the SecurID tokens sold by RSA and the old RSA algorithm.

Actually, the latest generation of SecurID tokens use AES, however RSA still ships backlogs of the older tokens which are built around a proprietary hash.

Like most other response-only tokens, the authentication is based not on large primes like public-key authentication but rather on a shared secret (one embedded in the token, the other stored on the authentication server.

Much work has been done towards cryptanalysis of response-only tokens, and a well-designed authentication system is very difficult to break blindly, just from observation of a few response pairs. There have been potentially successful attacks proposed against the old SecurID tokens due to a "vanishing differential" problem with certain seed values, but no proof of concept against that has succeeded, and the new AES tokens should not be vulnerable. More on this is available from the SecurID Users group.

As a counter-example, the old X9.9 challenge-response authentication system was based on DES encryption, and was not well-designed, was fatally flawed. Observation of a handful of challenges and responses cojuld allow an attacker to determine the seed value and compromise the authenticator.