Ubuntu – Unable to resolve “Permission denied (publickey)” error on Debian server

I am trying to connect to an Ubuntu server, from a Debian server. Both are VMs on Azure.

I can connect to the Ubuntu server without issue from my local computer (Mac).

I have set up the public key from the Debian server on the Azure settings for the Ubuntu VM. I have checked the authorized_keys file on the Ubunty server, and the Debian public key is in there.

When I try to connect, I get the relatively common Permission denied (publickey) error. I've read through many posts on serverfault, stackexchange, and numerous other support forums. Most make suggestions related to permissions on the ssh related files and folders, and ownership. To the best of my knowledge, I've done/checked all that but the issue remains.

Here's some info of the setup: (IP address and username has been obscured)

The results of the ssh command:

OpenSSH_6.7p1 Debian-5+deb8u3, OpenSSL 1.0.1t  3 May 2016
debug1: Reading configuration data /home/jonathan/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to 52.XXX.XXX.144 [52.XXX.XXX.144] port 22.
debug1: Connection established.
debug1: identity file /home/jonathan/.ssh/id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /home/jonathan/.ssh/id_rsa-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.7p1 Debian-5+deb8u3
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.2p2 Ubuntu-4ubuntu2.2
debug1: match: OpenSSH_7.2p2 Ubuntu-4ubuntu2.2 pat OpenSSH* compat 0x04000000
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr umac-128-etm@openssh.com none
debug1: kex: client->server aes128-ctr umac-128-etm@openssh.com none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA 2f:e1:fa:17:6d:90:c3:d2:f6:09:28:99:7d:49:3e:8a
debug1: Host '52.XXX.XXX.144' is known and matches the ECDSA host key.
debug1: Found key in /home/jonathan/.ssh/known_hosts:2
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/jonathan/.ssh/id_rsa
debug1: Authentications that can continue: publickey
debug1: No more authentication methods to try.
Permission denied (publickey).
jonathan@workstation1:~/.ssh$ chmod 644 authorized_keys
jonathan@workstation1:~/.ssh$ ssh -v -i ~/.ssh/id_rsa USERNAME@52.XXX.XXX.144
OpenSSH_6.7p1 Debian-5+deb8u3, OpenSSL 1.0.1t  3 May 2016
debug1: Reading configuration data /home/jonathan/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to 52.XXX.XXX.144 [52.XXX.XXX.144] port 22.
debug1: Connection established.
debug1: identity file /home/jonathan/.ssh/id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /home/jonathan/.ssh/id_rsa-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.7p1 Debian-5+deb8u3
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.2p2 Ubuntu-4ubuntu2.2
debug1: match: OpenSSH_7.2p2 Ubuntu-4ubuntu2.2 pat OpenSSH* compat 0x04000000
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr umac-128-etm@openssh.com none
debug1: kex: client->server aes128-ctr umac-128-etm@openssh.com none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA 2f:e1:fa:17:6d:90:c3:d2:f6:09:28:99:7d:49:3e:8a
debug1: Host '52.XXX.XXX.144' is known and matches the ECDSA host key.
debug1: Found key in /home/jonathan/.ssh/known_hosts:2
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/jonathan/.ssh/id_rsa
debug1: Authentications that can continue: publickey
debug1: No more authentication methods to try.
Permission denied (publickey).

Permissions and ownership of the Debian (local) ~/.ssh/ files:

drwx------  2 jonathan jonathan 4.0K Jul 11 12:57 .
drwxr-xr-x 10 jonathan jonathan 4.0K Jul 11 11:38 ..
-rw-r--r--  1 jonathan jonathan 1.4K Jul 11 01:49 authorized_keys
-rw-r--r--  1 jonathan jonathan  131 Jul 11 13:01 config
-rw-------  1 jonathan jonathan 3.3K Jul 11 12:25 id_rsa
-rw-r--r--  1 jonathan jonathan  751 Jul 11 12:25 id_rsa.pub
-rwx------  1 jonathan jonathan  223 Jul 11 13:24 known_hosts

The content of my ~/.ssh/config file:

Host azure-ubuntu-ksf
   Hostname 52.XXX.XXX.144
   User USERNAME
   PubKeyAuthentication yes
   IdentityFile ~/.ssh/id_rsa

Permissions of ~/.ssh folder itself:

drwx------  2 jonathan jonathan 4.0K Jul 11 12:57 .ssh

I added my id_rsa key to the ssh-agent

jonathan@workstation1:~$ eval `ssh-agent`
Agent pid 53351
jonathan@workstation1:~$ ssh-add ~/.ssh/id_rsa
Enter passphrase for /home/jonathan/.ssh/id_rsa:
Identity added: /home/jonathan/.ssh/id_rsa (/home/jonathan/.ssh/id_rsa)

Here is the sshd_config content:

# Package generated configuration file
# See the sshd_config(5) manpage for details

# What ports, IPs and protocols we listen for
Port 22
# Use these options to restrict which interfaces/protocols sshd will bind to
#ListenAddress ::
#ListenAddress 0.0.0.0
Protocol 2
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key
#Privilege Separation is turned on for security
UsePrivilegeSeparation yes

# Lifetime and size of ephemeral version 1 server key
KeyRegenerationInterval 3600
ServerKeyBits 1024

# Logging
SyslogFacility AUTH
LogLevel INFO

# Authentication:
LoginGraceTime 120
PermitRootLogin without-password
StrictModes yes

RSAAuthentication yes
PubkeyAuthentication yes
#AuthorizedKeysFile %h/.ssh/authorized_keys

# Don't read the user's ~/.rhosts and ~/.shosts files
IgnoreRhosts yes
# For this to work you will also need host keys in /etc/ssh_known_hosts
RhostsRSAAuthentication no
# similar for protocol version 2
HostbasedAuthentication no
# Uncomment if you don't trust ~/.ssh/known_hosts for RhostsRSAAuthentication
#IgnoreUserKnownHosts yes

# To enable empty passwords, change to yes (NOT RECOMMENDED)
PermitEmptyPasswords no

# Change to yes to enable challenge-response passwords (beware issues with
# some PAM modules and threads)
ChallengeResponseAuthentication no

# Change to no to disable tunnelled clear text passwords
PasswordAuthentication yes

# Kerberos options
#KerberosAuthentication no
#KerberosGetAFSToken no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes

# GSSAPI options
#GSSAPIAuthentication no
#GSSAPICleanupCredentials yes

X11Forwarding yes
X11DisplayOffset 10
PrintMotd no
PrintLastLog yes
TCPKeepAlive yes
#UseLogin no

#MaxStartups 10:30:60
#Banner /etc/issue.net

# Allow client to pass locale environment variables
AcceptEnv LANG LC_*

Subsystem sftp /usr/lib/openssh/sftp-server

# Set this to 'yes' to enable PAM authentication, account processing,
# and session processing. If this is enabled, PAM authentication will
# be allowed through the ChallengeResponseAuthentication and
# PasswordAuthentication.  Depending on your PAM configuration,
# PAM authentication via ChallengeResponseAuthentication may bypass
# the setting of "PermitRootLogin without-password".
# If you just want the PAM account and session checks to run without
# PAM authentication, then enable this but set PasswordAuthentication
# and ChallengeResponseAuthentication to 'no'.
UsePAM yes

ClientAliveInterval 180
PasswordAuthentication no

The tail end of the auth.log on the server

    Jul 11 13:27:16 www sshd[52373]: User MYUSERNAME from 52.XXX.XXX.216 not allowed because none of user's groups are listed in AllowGroups
Jul 11 13:27:16 www sshd[52373]: input_userauth_request: invalid user MYUSERNAME [preauth]
Jul 11 13:27:16 www sshd[52373]: Connection closed by 52.XXX.XXX.216 port 49249 [preauth]
Jul 11 13:29:45 www sshd[52381]: User MYUSERNAME from 52.XXX.XXX.216 not allowed because none of user's groups are listed in AllowGroups
Jul 11 13:29:45 www sshd[52381]: input_userauth_request: invalid user MYUSERNAME [preauth]
Jul 11 13:29:45 www sshd[52381]: Connection closed by 52.XXX.XXX.216 port 49382 [preauth]
Jul 11 13:30:11 www sshd[52384]: Accepted publickey for jonathan from 218.185.229.5 port 50631 ssh2: RSA SHA256:MZ0VmU5IYI0nRz75N1qZ1i7vxsm5P0UuTdgnaPri8mQ
Jul 11 13:30:11 www sshd[52384]: pam_unix(sshd:session): session opened for user jonathan by (uid=0)
Jul 11 13:30:11 www systemd-logind[1359]: New session c10 of user jonathan.
Jul 11 13:30:11 www systemd: pam_unix(systemd-user:session): session opened for user jonathan by (uid=0)
Jul 11 13:32:16 www sudo: jonathan : TTY=pts/0 ; PWD=/home/MYUSERNAME ; USER=root ; COMMAND=/bin/ls .ssh
Jul 11 13:32:16 www sudo: pam_unix(sudo:session): session opened for user root by jonathan(uid=0)
Jul 11 13:32:16 www sudo: pam_unix(sudo:session): session closed for user root
Jul 11 13:32:35 www sudo: jonathan : TTY=pts/0 ; PWD=/home/MYUSERNAME ; USER=root ; COMMAND=/bin/ls -lah .ssh
Jul 11 13:32:35 www sudo: pam_unix(sudo:session): session opened for user root by jonathan(uid=0)
Jul 11 13:32:35 www sudo: pam_unix(sudo:session): session closed for user root
Jul 11 13:32:54 www sudo: jonathan : TTY=pts/0 ; PWD=/home/MYUSERNAME ; USER=root ; COMMAND=/bin/cat .ssh/authorized_keys
Jul 11 13:32:54 www sudo: pam_unix(sudo:session): session opened for user root by jonathan(uid=0)
Jul 11 13:32:54 www sudo: pam_unix(sudo:session): session closed for user root
Jul 11 13:33:31 www sshd[52484]: fatal: Unable to negotiate with 41.238.56.8 port 56263: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1 [preauth]
Jul 11 13:33:32 www sshd[52486]: fatal: Unable to negotiate with 41.238.56.8 port 56267: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1 [preauth]
Jul 11 13:33:34 www sshd[52488]: fatal: Unable to negotiate with 41.238.56.8 port 56274: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1 [preauth]
Jul 11 13:33:38 www sshd[52490]: fatal: Unable to negotiate with 41.238.56.8 port 56283: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1 [preauth]
Jul 11 13:33:46 www sshd[52492]: fatal: Unable to negotiate with 41.238.56.8 port 56301: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1 [preauth]
Jul 11 13:34:45 www sshd[52496]: fatal: Unable to negotiate with 1.162.49.50 port 38855: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1 [preauth]
Jul 11 13:35:38 www sshd[52500]: fatal: Unable to negotiate with 220.170.196.198 port 47162: no matching key exchange method found. Their offer: diffie-hellman-group14-sha1,diffie-hellman-group-exchange-sha1,diffie-hellman-group1-sha1 [preauth]
Jul 11 13:44:34 www sshd[52523]: fatal: Unable to negotiate with 119.48.16.182 port 36725: no matching key exchange method found. Their offer: diffie-hellman-group14-sha1,diffie-hellman-group-exchange-sha1,diffie-hellman-group1-sha1 [preauth]
Jul 11 13:52:06 www sshd[52539]: User MYUSERNAME from 52.XXX.XXX.216 not allowed because none of user's groups are listed in AllowGroups
Jul 11 13:52:06 www sshd[52539]: input_userauth_request: invalid user MYUSERNAME [preauth]
Jul 11 13:52:06 www sshd[52539]: Connection closed by 52.XXX.XXX.216 port 50568 [preauth]
Jul 11 13:55:32 www sshd[52551]: fatal: Unable to negotiate with 177.135.98.161 port 43336: no matching key exchange method found. Their offer: diffie-hellman-group14-sha1,diffie-hellman-group-exchange-sha1,diffie-hellman-group1-sha1 [preauth]

IP of local VM is 52.XXX.XXX.216

IP of server is 52.XXX.XXX.144

Is there anything else that would be helpful to see?

I've been trying to fix this for the best part of 2 hours. If anyone has any helpful suggestions, I'd greatly appreciate it.