[BUG] - Sends duplicate userauth-request - fails with AsyncSSH 2.14.1 and multiple SSH keys

Are you using paramiko as a client or server?

Client

What feature(s) aren't working right?

Keys/auth

What version(s) of paramiko are you using?

3.4.0

What version(s) of Python are you using?

3.11.6

What operating system and version are you using?

Ubuntu 23.10

If you're connecting as a client, which SSH server are you connecting to?

AsyncSSH

If you're using paramiko as part of another tool, which tool/version?

pyinfra and https://github.com/matthijskooijman/nuttssh, v0.3

Expected/desired behavior

Connecting a paramiko client to an AsyncSSH v2.14.1 or above server works.

Actual behavior

The connection fails when there are multiple keys available (and the first key does not grant access).

Looking at debug output and code, the problem is that paramiko sends a new userauth-request before each key, and AsyncSSH rejects all but the first one with "Sending disconnect: Unexpected service in service request"

This problem has surfaced with AsyncSSH 2.14.1, since that version fixes an authentication injection issue for which asyncssh rejects unexpected userauth-request service requests.

The OpenSSH client sends only one userauth-request and works with AsyncSSH without issues.

How to reproduce

To prepare (you can just paste the entire code block into a shell):

python3 -m venv venv
./venv/bin/pip install asyncssh paramiko

cat > client.py <<EOF
import paramiko
import logging

logging.basicConfig(level=logging.DEBUG)
c = paramiko.SSHClient()
c.set_missing_host_key_policy(paramiko.client.WarningPolicy)
c.connect('localhost', port=2222)
EOF

cat > server.py << EOF
import asyncio
import asyncssh
import logging

logging.basicConfig(level=logging.DEBUG)

auth_keys = asyncssh.import_authorized_keys("")
host_key = asyncssh.generate_private_key('ssh-rsa')

loop = asyncio.get_event_loop()
loop.run_until_complete(asyncssh.listen(port=2222, server_host_keys=[host_key], authorized_client_keys=auth_keys))
loop.run_forever()
EOF

This is a super-simple AsyncSSH server that supports key auth, but has no accepted keys (so will always fail to auth), and a paramiko client that just tries to auth with whatever keys are in the agent (so this example requires a running agent with 2 or more keys).

Then start the server in one terminal with:

./venv/bin/python server.py

And connect with:

./venv/bin/python client.py

The client outputs (initial output omitted, this from the first auth attempt):

DEBUG:paramiko.transport:Trying SSH agent key b'5070c6d2826e4c3517da2bf30218a831'
DEBUG:paramiko.transport:userauth is OK
DEBUG:paramiko.transport:Finalizing pubkey algorithm for key of type 'ssh-rsa'
DEBUG:paramiko.transport:Our pubkey algorithm list: ['rsa-sha2-512', 'rsa-sha2-256', 'ssh-rsa']
DEBUG:paramiko.transport:Server-side algorithm list: ['rsa-sha2-256', 'rsa-sha2-512', 'ssh-rsa-sha224@ssh.com', 'ssh-rsa-sha256@ssh.com', 'ssh-rsa-sha384@ssh.com', 'ssh-rsa-sha512@ssh.com', 'ssh-rsa', 'sk-ssh-ed25519@openssh.com', 'sk-ecdsa-sha2-nistp256@openssh.com', 'ssh-ed25519', 'ssh-ed448', 'ecdsa-sha2-nistp521', 'ecdsa-sha2-nistp384', 'ecdsa-sha2-nistp256', 'ecdsa-sha2-1.3.132.0.10', 'ssh-dss', 'rsa-sha2-256', 'rsa-sha2-512', 'ssh-rsa-sha224@ssh.com', 'ssh-rsa-sha256@ssh.com', 'ssh-rsa-sha384@ssh.com', 'ssh-rsa-sha512@ssh.com', 'ssh-rsa', 'sk-ssh-ed25519@openssh.com', 'sk-ecdsa-sha2-nistp256@openssh.com', 'ssh-ed25519', 'ssh-ed448', 'ecdsa-sha2-nistp521', 'ecdsa-sha2-nistp384', 'ecdsa-sha2-nistp256', 'ecdsa-sha2-1.3.132.0.10']
DEBUG:paramiko.transport:Agreed upon 'rsa-sha2-512' pubkey algorithm
INFO:paramiko.transport:Authentication (publickey) failed.
DEBUG:paramiko.transport:Trying SSH agent key b'6d9c0436805a5c88ba4575867ef71376'
INFO:paramiko.transport:Disconnect (code 7): Unexpected service in service request
DEBUG:paramiko.transport:Trying SSH agent key b'5f8a7ce6912a86dbc1e31c19b3977fb6'
Traceback (most recent call last):
  File "/home/matthijs/test/paramiko-bug/client.py", line 7, in <module>
    c.connect('localhost', port=2222)
  File "/home/matthijs/test/paramiko-bug/venv/lib/python3.11/site-packages/paramiko/client.py", line 485, in connect
    self._auth(
  File "/home/matthijs/test/paramiko-bug/venv/lib/python3.11/site-packages/paramiko/client.py", line 818, in _auth
    raise saved_exception
  File "/home/matthijs/test/paramiko-bug/venv/lib/python3.11/site-packages/paramiko/client.py", line 754, in _auth
    self._transport.auth_publickey(username, key)
  File "/home/matthijs/test/paramiko-bug/venv/lib/python3.11/site-packages/paramiko/transport.py", line 1664, in auth_publickey
    raise SSHException("No existing session")
paramiko.ssh_exception.SSHException: No existing session

You can see the first key fails, normally, but then the second key is rejected with "Unexpected service in service request"

The corresponding server output is:

INFO:asyncssh:[conn=0] Beginning auth for user matthijs
DEBUG:asyncssh:[conn=0] Verifying request with rsa-sha2-512 key
INFO:asyncssh:[conn=0] Sending disconnect: Unexpected service in service request (7)

Trying the same with SSH shows it tries all keys (and then of course still fails to auth, since the server has no authorized keys):

ssh localhost -p 2222 -o StrictHostKeyChecking=no -v
(... output before authentication stripped ...)
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering public key: /home/matthijs/.config/gsconnect/private.pem RSA SHA256:K2VrKB9006x9fYJKPzhOVnEYicEu2i51OucQmkRzpBg agent
debug1: Authentications that can continue: publickey
debug1: Offering public key: /home/matthijs/.ssh/id_rsa.1 RSA SHA256:qmFfdAmKfzhnKbQAmdx7x2K0EHodoEvVgD7zr2oTHxk agent
debug1: Authentications that can continue: publickey
debug1: Offering public key: /home/matthijs/.ssh/id_rsa.2 RSA SHA256:VdKF9waRlLAGKQBeEyI/dsbhu6UI2LQnbe9YQN5NCjo agent
debug1: Authentications that can continue: publickey
debug1: Trying private key: /home/matthijs/.ssh/id_rsa
debug1: Trying private key: /home/matthijs/.ssh/id_ecdsa
debug1: Trying private key: /home/matthijs/.ssh/id_ecdsa_sk
debug1: Trying private key: /home/matthijs/.ssh/id_ed25519
debug1: Trying private key: /home/matthijs/.ssh/id_ed25519_sk
debug1: Trying private key: /home/matthijs/.ssh/id_xmss
debug1: Trying private key: /home/matthijs/.ssh/id_dsa
debug1: No more authentication methods to try.
matthijs@localhost: Permission denied (publickey).

And the corresponding server output:

INFO:asyncssh:[conn=2] Beginning auth for user matthijs
DEBUG:asyncssh:[conn=2] Trying public key auth with rsa-sha2-512 key
DEBUG:asyncssh:[conn=2] Trying public key auth with rsa-sha2-512 key
DEBUG:asyncssh:[conn=2] Trying public key auth with rsa-sha2-512 key

Anything else?

Related issues and PRs:

• I suspect #1390 is essentially the same issue, but against some cisco SSH server
• #1687 is a PR from 2020 that says to remove the duplication and could fix this issue. It also has some references to the SSH spec to support this implementation.
• #2216 is a PR from 2023 that adds an option to remove the duplication (in addition to making other changes).

I have tested both PRs and both indeed fix this problem (I compared the #1390 with the version that PR was based on, and #2216 with the resend_service_requests=False option vs default options, so I did not apply those PRs against current master due to conflicts).

Start with client.py _auth and transport.py auth_publickey, then reproduce the connection using AsyncSSH 2.14.1 or newer and multiple SSH agent keys. Compare the behavior and SSH-spec references discussed in PRs #1687 and #2216; done means all available keys can be tried without the server disconnecting for an unexpected service request.