SSH Login fails with "hash mismatch" on server, "missing begin marker" on client
This was an odd one. Recently I was setting up key-based ssh access for a server and the client was failing to connect with the generic "Permission denied (publickey,gssapi-keyex,gssapi-with-mic)." error.
I checked the server log (Centos, so /var/log/secure) and found an interesting "error: hash mismatch" message.
Using -v to get debugging info on the client end also gave me a message of "key_parse_private2: missing begin marker" - this was a red-herring and I suspect it happens often even when connections are working just fine.
A bit of googling took me in all sorts of odd directions for what I was sure must have been a simple thing - both these machines had been doing key-based ssh just fine for some time.
Eventually it clicked - I had put a comment in the authorized_keys file on the server (like "# this key is for that thing") and that was what caused the issue (presumably when sshd got to that line it tried to interpret it, failed, and bailed). Removing the comment from ~/.ssh/authorized_keys on the server fixed everything.
I didn't see this possibility in the google results I saw so figured it was worth recording somewhere. Like here. There you go.