PublickeyUnverifiedError on some servers

Steps to reproduce:

The following code produces an error for some SSH servers:

import ssh2
from ssh2.session import Session
import socket

addr = "..."
keypath = "..."
username = "..."
password = "..."

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((addr, 22))

session = Session()
session.handshake(sock)

session.userauth_publickey_fromfile(username=username, privatekey=keypath, passphrase=password)

Expected behaviour:

ssh2 connects to the remote server.

Actual behaviour:

Traceback (most recent call last):
  File "/home/raphael/tmp/connection_test/min_test.py", line 17, in <module>
    session.userauth_publickey_fromfile(username=username, privatekey=keypath, passphrase=password)
  File "ssh2/session.pyx", line 222, in ssh2.session.Session.userauth_publickey_fromfile
  File "ssh2/utils.pyx", line 168, in ssh2.utils.handle_error_codes
ssh2.exceptions.PublickeyUnverifiedError

Additional info: This error initially occurred for only one server (computing cluster, to be precise), but another one that used to work now raises this error. I do not administer these servers nor have root privileges, so I don't know exactly what happened. I can connect to a third cluster with the same code successfully. They however seem to use the exact same OpenSSH version:

$ sshd -V
OpenSSH_7.4p1, OpenSSL 1.0.2k-fips  26 Jan 2017

This appears to be linked to ssh2, as I can connect through the terminal to the server with the same private key just fine. Moreover, Paramiko also works as expected with the same credentials and the following code:

import paramiko
ssh = paramiko.SSHClient()

addr = "..."
keypath = "..."
username = "..."
password = "..."

ssh.set_missing_host_key_policy(paramiko.AutoAddPolicy())
ssh.connect(addr, username=username, password=password, key_filename=keypath)

I use ssh2 0.27.0, although I did confirm that earlier versions down to 0.19.0 result in the same behaviour. I also tried using ParallelSSH, but with a similar result (pssh.exceptions.AuthenticationError). I don't know what else to try at this point.

ParallelSSH / ssh2-python

PublickeyUnverifiedError on some servers #166