SSH attacks, how do their usernames end up in auth.log? (pw auth disabled)

Question

So this computer is reachable on port 22 (from everywhere).
Since messages indicating failed login attempts (usernames like root, cgi, bash, production...) have been flooding /var/log/auth.log, I have disabled password authentication from external IPs (using public key authentication only).
And this works, when trying to ssh into that machine from an external IP (without key) I don't even get the username prompt:

Permission denied (publickey).

So how do all those fake usernames still end up in auth.log?

  1 Aug  4 17:02:48 host sshd[17190]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=217.116.204.99  user=root
  2 Aug  4 17:02:48 host sshd[17190]: pam_winbind(sshd:auth): getting password (0x00000388)  
  3 Aug  4 17:02:48 host sshd[17190]: pam_winbind(sshd:auth): pam_get_item returned a password  
  4 Aug  4 17:02:48 host sshd[17190]: pam_winbind(sshd:auth): request wbcLogonUser failed: WBC_ERR_AUTH_ERROR, PAM error:

PAM_USER_UNKNOWN (10), NTSTATUS: NT_STATUS_NO_SUCH_USER, Error mess 4 age was: No such user
5 Aug 4 17:02:50 host sshd[17190]: Failed password for root from 217.116.204.99 port 40054 ssh2
6 Aug 4 17:02:50 host sshd[17190]: Received disconnect from 217.116.204.99: 11: Bye Bye [preauth]
...
513322 Apr 7 19:45:40 host sshd[15986]: input_userauth_request: invalid user cgi [preauth]
...

http://paste.debian.net/92403/

Answer 1

While you don't enter a username, if you are connecting from a linux/osx/bsd workstation the username is implicit (it defaults to the username you are logged in as), if you have windows and use putty try connecting without setting the Auto-login username, and present a key, it will ask for a username to try and match the pair.

Keys only replace passwords, each one is associated with a user (and therefor username), which is why you'll find the authorized_keys file under ~/.ssh/ .

What you are probably seeing are attackers doing something similar to ssh bash@<your.server.ip> . The server sees a username, but since they don't present a key, they are denied access.