SSH: Two Factor Authentication
Solution 1:
Red Hat have added a patch to OpenSSH in RHEL (and therefore CentOS) 6.3 to require multiple authentication mechanisms, so you can do something like this:
RequiredAuthentications2 publickey,keyboard-interactive
See the release notes for not much more detail.
Unfortunately this feature doesn't seem to be in OpenSSH upstream nor Ubuntu 12.04, so unless you want to find the patch and recompile OpenSSH I'm afraid you're out of luck.
Solution 2:
You are looking for Duo Security
Solution 3:
You can use both the Google Authenticator PAM module and public keys, but only one at the time will be used for a given authentication. That is, if a user logs in with an authorized public key, no token will be required.
Or, to say it otherwise: tokens are only required for password authentications, not SSH keys.
This limitation does not come from the Google Authenticator module by the way, but from SSH, which only implements two factor authentication (via ChallengeResponseAuthentication) for PAM, but doesn't call PAM when a valid public key is provided.
Solution 4:
This question is from 2012. Since, SSH has changed and the SSH2 protocol has been implemented.
On more recent versions of SSH ( >= 6.2), man sshd_config mentions:
AuthenticationMethods
Specifies the authentication methods that must be successfully completed for a user to be
granted access. This option must be followed by one or more comma-separated lists of
authentication method names. Successful authentication requires completion of every method
in at least one of these lists.
For example, an argument of ``publickey,password publickey,keyboard-interactive'' would
require the user to complete public key authentication, followed by either password or key-
board interactive authentication. Only methods that are next in one or more lists are
offered at each stage, so for this example, it would not be possible to attempt password or
keyboard-interactive authentication before public key.
This option is only available for SSH protocol 2 and will yield a fatal error if enabled if
protocol 1 is also enabled. Note that each authentication method listed should also be
explicitly enabled in the configuration. The default is not to require multiple authentica-
tion; successful completion of a single authentication method is sufficient.
This page http://lwn.net/Articles/544640/ also mentions the possibility of using a publickey and a PAM authentication at the same time.
Solution 5:
I know this question is a little stale, but for the sake of future people (myself included) who are looking for a solution, there's also talk of using the ForceCommand option in the sshd_config file to run a script which then performs the authentication. There's an example script here you can modify a bit to your needs, although in that example he calls it from the authorized_keys file instead of making it system-wide with sshd_config's ForceCommand.