One-Time Passwords via cell phone?

Recap for new viewers: a replacement method for passwords as authticators must be Convenient, Secure, and Ephemeral.

If the primary security weakness of passwords is due to their static nature, then use of a dynamic string of characters, aka One-Time Password (OTP), may address this problem.  A OTP cannot, by definition, be used more than once - which neatly addresses most problems of password interception.  If, however, the OTP is generated based on entering a static password on an untrusted machine, then I argue that there is no additional security, merely security theater.  If I'm at an internet kiosk, or any other case in which I don't control the machine I'm using, then I shouldn't enter my password on that machine.  If the machine might store the static data I use for authentication, whether password or biometric or RFID etc., then the owner/pwner of that machine can pretend to be me.  There must be external generation of the OTP.

Comments from the previous post seem to imply that a OTP may be a decent password replacement as long as it is externally generated.  From the "something I [ know | have | am ]" set, only "something I have" seems to be able to provide a dynamic and potentially secure authentication.  The complaint about "something I have" is that it's inconvenient.  However, a potential external generator is a cell phone.  In our current society, a cell phone has become almost a necessity - which implies that it is sufficiently convenient to carry.  (More specifically, forgetting a cell phone generally causes more pain than forgetting a password, so we tend to remember to bring them.)

I'm familiar with two methods of using cell phones as OTP generators.  One method takes input of a PIN and returns the OTP.  ("PIN" is fundamentally just another term for "password".)  The "advantage" of this type of app is generally that it does not require any connection from the phone to the network, whether voice, SMS, or data - saving on cost.  If the phone is not "sync'd" in some way to the service, or if the app returns the same string each time, then it's just a password manager - which doesn't solve the problem examined by this post.  In some way, the phone should be set so it's "unique", and can reliably be an authenticator of  me and only me.

The other method of using a phone for OTP is to simply to present the server-generated OTP to me, via phone call or SMS.  I like the simplicity of this solution, as it doesn't rely on software loaded on the phone, but only on the uniqueness of my phone number.  (My plan gives me unlimited SMS messages, so I personally don't have any cost concerns.)

In either method, if I lose the phone, I want to be able to revoke its status as an authentication token - its representation of "me" must be ephemeral.  Even if my first thought isn't "oops, better de-register my phone as an OTP generator", it's still more likely that I'll take action than if someone else starts using my password.

Since Google is edging into the VOIP market through GOOG411, Google Voice, etc., it seems like an obvious step for them to take to add SMS OTP delivery for their services.

Here's what I see for a method to register for phone-based OTP delivery, just in case Google hasn't learned from their Buzz experience:

1. User sets preference for "Strong authentication".
2. Google lists a phone number and registration code, with instructions to SMS.
3. Google sends back a reply code (SMS).
4. User enters the reply code in the webUI.

Problems:

• DoS: attacker constantly tries to log on as user, creating large number of SMS / calls.
• Need alternate login method for "lost my phone" situation: automatically de-registers phone.
• SMS isn't always "timely" in its delivery.

Question: is it sufficient to have a fallback to password if the SMS method isn't available?  The "password" login method should arguably trigger an SMS message if it's used.  Of course, the other question is whether, by removing the need to enter the password every time, the user will forget the password.

Good comments so far... I'd reply to them if I could figure out how to make Blogger let me.  Until then, more posts!