Github not recognizing ssh key

Question

I've been using ssh keys with github for a while now. Suddenly i can't push and I'm getting a Permission denied (publickey) error. Here's what I've tried so far:

• Checked the ssh key is in the correct directory (~/.ssh)
• Tried reuploading my public key to github (I get a message that the key already exists)
• Double checked that the output of ssh-add -l -E sha256 on my system agrees with the string in my ssh settings on my github account
• Followed all the steps in the "Troubleshooting ssh" section of the github docs. (Everything seems gucci)
• Banged my head against the wall for an hour

So far nothing has helped. This is my last resort. I'll greatly appreciate any and all suggestions. Here's the output of my ssh -vT git@github.com

OpenSSH_7.2p2 Ubuntu-4ubuntu2.10, OpenSSL 1.0.2g  1 Mar 2016
debug1: Reading configuration data /home/MY_USER_NAME/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to github.com [140.82.114.3] port 22.
debug1: Connection established.
debug1: identity file /home/MY_USER_NAME/.ssh/id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_rsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_dsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_dsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_ecdsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_ecdsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_ed25519 type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_ed25519-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_7.2p2 Ubuntu-4ubuntu2.10
debug1: Remote protocol version 2.0, remote software version babeld-fb957b4d
debug1: no match: babeld-fb957b4d
debug1: Authenticating to github.com:22 as 'git'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: curve25519-sha256@libssh.org
debug1: kex: host key algorithm: rsa-sha2-512
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: kex: client->server cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ssh-rsa SHA256:nThbg6kXUpJWGl7E1IGOCspRomTxdCARLviKw6E5SY8
debug1: Host 'github.com' is known and matches the RSA host key.
debug1: Found key in /home/MY_USER_NAME/.ssh/known_hosts:4
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp256-cert-v01@openssh.com,sk-ssh-ed25519-cert-v01@openssh.com,sk-ecdsa-sha2-nistp256-cert-v01@openssh.com,rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ssh-dss-cert-v01@openssh.com,sk-ssh-ed25519@openssh.com,sk-ecdsa-sha2-nistp256@openssh.com,ssh-ed25519,ecdsa-sha2-nistp521,ecdsa-sha2-nistp384,ecdsa-sha2-nistp256,rsa-sha2-512,rsa-sha2-256,ssh-rsa,ssh-dss>
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/MY_USER_NAME/.ssh/id_rsa
debug1: Server accepts key: pkalg rsa-sha2-512 blen 279
debug1: Authentications that can continue: publickey
debug1: Trying private key: /home/MY_USER_NAME/.ssh/id_dsa
debug1: Trying private key: /home/MY_USER_NAME/.ssh/id_ecdsa
debug1: Trying private key: /home/MY_USER_NAME/.ssh/id_ed25519
debug1: No more authentication methods to try.
Permission denied (publickey).

---

Update: I'm having the same problem with a different github account that has a different set of keys. Same computer.

Answer 1

For anyone who had to generate a new ssh key because they used the wrong email like I had, here is how I fixed it:

1. Generate new ssh key with correct email in new file.
2. Update ~/.ssh/config with correct new file.
3. Ensure your git profile is referencing correct email with git config --list (you should see user.email=YOUR_CORRECT_EMAIL listed)
4. If not, update email with git config --global user.email "NEW_EMAIL" and optionally update user.name if that is not accurate.
5. Reset all commits you had added with the wrong email with git reset HEAD~<number of commits>.
6. Commit your changes.

You should now be good to go.

Answer 2

One possible root cause is the Host or HostName can't intercept your target FQDN or IP address in the SSH connection. Try to modify Host or HostName to match with your target server.

Also enable debug mode for git command.

git -c core.sshCommand="ssh -vvv" clone

Answer 3

Note that if you have an old DSA key, you'll see "Server accepts key:", but will still ultimately fail. GH is phasing out DSA keys, so it may have been 'accepted', but not allowed to proceed.

Answer 4

So, I eventually figured it out. Turns out my computer just didn't like the fact that I had multiple ssh keys (possibly because one of them was password protected and others weren't?) Moving all but one of the ssh keys out from the ~/.ssh directory and restarting the computer solved my problem. I previously have tried removing all but one of the ssh keys but apparently a reboot was also needed.

Answer 5

My answer might not help or sound silly. But in my situation, I'm just deleting the know_hosts file and pull/push again, then everything works as expected.