OpenSSH - how to require PublicKeyAuthentication *and* login/password authentication

I have an Internet facing server that I need to allow shared (non-administrative) access to. I want to allow access only if the users key is in an authorized_keys file, but I don't trust some of these guys not to get their keys stolen, and I know some of them don't secure their private keys with a passphrase, despite me asking them to.

Basically, what I want is to have sshd require both ChallengeResponseAuthentication AND PubKeyAuthentication so that they always have to type a password as well as having an authorized keypair.

Everything I've read makes me think this isn't something open sshd will let me do: I tell it what auth methods are OK, and it tries them in a certain (inbuilt) order of preference until one of them works and then the user is allowed in.

Am I going to have to look for a different sshd or download and hack the code myself, or am I missing something?

You can configure a forced command in the authorized_keys file. This could do a sudo or su or some shell script that in turn invokes some type of login password requirement.

Each user may have two accounts. One for SSH key-based access that in turn invokes a forced command requiring them to enter a password before getting an actual shell.

"Disable unnecessary SSH features using other options we cover later. Under SSH1, you may disable port forwarding with no-port-forwarding, agent forwarding with no-agent-forwarding, and tty allocation using no-pty."

http://oreilly.com/catalog/sshtdg/chapter/ch08.html

you should introduce 2 factor authentication and not ssh keys + challenge password.

With strong 2 factor authentication you have something you know (the password) and something you possess (OTP -that changes every time). This way someone knowing the password of the user will still be unable to login to the server, because he doesn't know the current OTP.

There are SMS-based, app-based (i.e. google authenticator) and hardware-token-based OTP solutions. Always use TOTP instead of HOTP.

2 factor is more secure than ssh-private keys + challenge password, that are always the same ;-)