That, and I don't trust "an app." The whole reason I want a second factor is to get away from computers as primary authentication mediums, and a smart phone is a computer.
I don't think anyone realizes how much malware is in the Android marketplace. And that's beside the malware that vendors and carriers install on there by default. Do not trust your phone.
The Authenticator app is open-source [1] and extremely minimal. It doesn't run with permissions to access any data on the phone, or even communicate over the network; all it does is read the system clock every 30 seconds and compute an HMAC.
The app isn't what worries me, it's what else is running on the phone. Android malware comes in the form of a rootkit, usually, which means it has total control over your device.
Not scared? How about this article[1] from over a year ago, which details over 50 apps in the Marketplace using a rootkit which not only controls anything you do, but can download new code to keep changing at a whim?
So it's basically the same security as adaptive authentication (aka challenge questions) but with the added annoyance and security flaws of using either SMS or an app.
With adaptive authentication, you basically add a series of heuristics based on the browser's request to calculate a number. A ratio applied to that number determines the likelihood that a user is the same as the one who has logged in before. If the ratio is not close enough, challenge questions are asked of the user to verify they are the real user.
The number is cached both on the server side and in the browser. As long as the number stays the same, and the heuristics of the browser's request stay the same, no additional challenge questions are asked upon logging in again. This also times out after a period of time, so eventually the user must be challenged again.
The difference between that and Google's method is the idea that the SMS and/or App are "something you have" instead of an additional "something you know". But since the challenge questions can be anything (including made-up information that is fake and nobody would ever guess - like a second password), there isn't the same risk as with losing a traditional password, and it isn't something an attacker can find out by social engineering or research.
As we've seen before, you can intercept SMS/voice two-factor auth, and Android malware is rampant. But the only way to get a challenge answer is to use lead pipe cryptography or intercept it at the computer - and once they have your computer it's game over. How secure your authentication is comes down to how you implement it.
I will stick with my trusty dumb physical token and challenge questions as that is the most difficult method to attack.
I accept your criticisms of SMS for authentication (I recently switched from SMS to the Android app), but I like two factor better than the approach you describe. If I log on to GMail from a public computer at a library with a keylogger installed, they will obtain my password but not enough to log in as me after I have signed out. Under the scenario you describe, I'd also type the answer to a challenge question, and they'd have both the password and the answer to the challenge question. That would leave me in a significantly worse position.
