SSHD - blocking password authentication

On several systems I have this sshd_config

Port 22
Protocol 2
PermitRootLogin no
StrictModes yes
PasswordAuthentication no
ChallengeResponseAuthentication no
MaxStartups 2
AllowUsers john joe

Can anyone explain the difference between keyboard-interactive and password authentication? How can I test my sshd server for these?

These systems are accessible using SSH via the internet (port-forwarding at firewall). Despite turning off password authentication I am still seeing syslog records for invalid users and invalid passwords being rejected by sshd - obviously some bot-net(s) are attempting brute-force password guessing.

If I try to ssh in, without setting up a public key, my session is closed with a message "Permission denied (publickey)" before I have an opportunity to enter a username. So I don't see how these password attempts are ocurring.

Here's an example from syslog (all lines prefixed 'Oct 12 08:40:49 host sshd[14790]:')

Could not reverse map address 203.0.113.1.
User root not allowed because not listed in AllowUsers
input_userauth_request: illegal user root
Failed password for illegal user root from 203.0.113.1 port 35902 ssh2
Received disconnect from 203.0.113.1: 11: Bye Bye

How are these invalid passwords getting through? Is the server still therefore vulnerable to brute-force password guessing?

AFAIK using PasswordAuthentication the client prompts for your username and password and then sends both to the server. In keyboard-interactive the client asks for your username, sends it to the server and then the server responds back with a password prompt which is in turn relayed back via the client to you.

The whole thing has been done to be able to implement further security measures to make sure you (the user) actually interactively types the password and it is not stored in some way and then only entered.

PasswordAuthentication is only one type of KbdInteractiveAuthentication (the actual keyword used in ssh_config and sshd_config).

KbdInteractiveAuthentication encompasses a variety of methods: S/Key is another, as is PAM. (This is an RFC spec, which is documented here

There's a list of KbdInteractiveDevices you can specify in ssh_config. (If unspecified, it takes the servers list. Since there's no option for that in sshd_config, I'm assuming it's a compile time option, but I have not verified this.)

I didn't think the manpages (ssh_config and sshd_config) were particularly helpful in understanding the relationships here, but the O'Reilly SSH book is a decent reference.