Hang any SSHD on the internet, and within minutes you get these attempts. You can choose to log the passwords if you like and this is what you would see.
Wow you're right. I just setup my own VPS yesterday. Decided to check the auth logs and the first invalid user attempt occurred less than 3 hours from my first login.
The "POSSIBLE BREAK-IN ATTEMPT!" message worried me for a bit but a little googling and the fact I've disabled password login calmed me down.
Presumably, changing my sshd port will drastically reduce these attempts right? Or do attackers routinely port scan servers?