[BUG] - MessageOrderError: Expecting packet from (31,), got 91 connecting to Odoo.sh due to immediate post-auth rekeying

Are you using paramiko as a client or server?

Client

What feature(s) aren't working right?

SSH

What version(s) of paramiko are you using?

Tried 2.12.0 and 3.5.1

What version(s) of Python are you using?

3.12.8

What operating system and version are you using?

MacOS (Darwin 24.3.0)

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

No response

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

Fabric

Expected/desired behavior

Paramiko should ideally be able to handle this connection sequence, similar to how OpenSSH does, and successfully establish the channel and execute commands even if the server initiates an early rekey.

Actual behavior

When attempting to connect and run any command (even simple ones like uname -r) against an Odoo.sh SSH server using Paramiko (via Fabric), the connection fails immediately after successful authentication with the following error:

paramiko.ssh_exception.MessageOrderError: Expecting packet from (31,), got 91

Traceback:

Traceback (most recent call last):
  File ".../paramiko/transport.py", line 2219, in run
    raise exc_class(
paramiko.ssh_exception.MessageOrderError: Expecting packet from (31,), got 91

# Full traceback during channel open/run command would follow
# e.g., originating from transport.open_session() -> transport.open_channel()

How to reproduce

I am basically calling Connection(host, user).run("uname -r") via fabric

Anything else?

Environment:

• Paramiko version: Tested with 3.5.1 and 2.12.0 (latest 2.x)
• Python version: 3.12
• Operating System: macOS (Darwin 24.3.0)
• Server: Odoo.sh hosted SSH server (SSH-2.0-Odoo.sh)

Analysis & Evidence:

Based on detailed Paramiko debug logs (paramiko.util.log_to_file("paramiko.log")) and comparison with successful ssh -vvv connections using OpenSSH (9.8p1):

1. Authentication using public key succeeds in both Paramiko and OpenSSH.
2. Immediately after successful authentication (Authentication (publickey) successful!), the Odoo.sh server initiates an SSH key exchange/rekeying process (sends SSH_MSG_KEXINIT / type 20). This is visible in both Paramiko and ssh -vvv logs.
3. During this server-initiated rekeying process, the server also sends the channel open confirmation (SSH_MSG_CHANNEL_OPEN_CONFIRMATION / type 91).
4. OpenSSH (ssh -vvv logs show receiving type 91 while rekeying in progress) appears tolerant of receiving the channel confirmation message (type 91) interleaved during the rekey process initiated by the server. It successfully completes both the rekey and the command execution.
5. Paramiko, however, seems to have a stricter expectation during this rekeying phase. It is expecting a rekey-specific reply (like SSH_MSG_KEXDH_REPLY / type 31) but instead receives the channel confirmation (type 91), triggering the MessageOrderError. This failure occurs consistently across Paramiko v3.5.1 and v2.12.0.

Question:

Is this server behavior (initiating a rekey immediately post-authentication and interleaving channel messages) considered valid according to SSH standards? Could Paramiko's state machine potentially be made more robust to handle this specific message ordering, which seems to be tolerated by OpenSSH?

Could this also just be some weird behavior since the server is a container and is possibly behind a proxy for ssh?

Full paramiko.log

DEB [20250412-03:16:24.769] thr=1   paramiko.transport: starting thread (client mode): 0x53e1970
DEB [20250412-03:16:24.770] thr=1   paramiko.transport: Local version/idstring: SSH-2.0-paramiko_2.12.0
DEB [20250412-03:16:24.780] thr=1   paramiko.transport: Remote version/idstring: SSH-2.0-Odoo.sh
INF [20250412-03:16:24.780] thr=1   paramiko.transport: Connected (version 2.0, client Odoo.sh)
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: === Key exchange possibilities ===
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: kex algos: curve25519-sha256@libssh.org, diffie-hellman-group14-sha1, kex-strict-s-v00@openssh.com
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: server key: rsa-sha2-512, rsa-sha2-256
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: client encrypt: aes128-ctr, aes192-ctr, aes256-ctr
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: server encrypt: aes128-ctr, aes192-ctr, aes256-ctr
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: client mac: hmac-sha2-256, hmac-sha2-512, hmac-sha2-256-etm@openssh.com, hmac-sha2-512-etm@openssh.com
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: server mac: hmac-sha2-256, hmac-sha2-512, hmac-sha2-256-etm@openssh.com, hmac-sha2-512-etm@openssh.com
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: client compress: none
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: server compress: none
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: client lang: <none>
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: server lang: <none>
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: kex follows: False
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: === Key exchange agreements ===
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: Kex: curve25519-sha256@libssh.org
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: HostKey: rsa-sha2-512
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: Cipher: aes128-ctr
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: MAC: hmac-sha2-256
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: Compression: none
DEB [20250412-03:16:24.790] thr=1   paramiko.transport: === End of kex handshake ===
DEB [20250412-03:16:24.845] thr=1   paramiko.transport: kex engine KexCurve25519 specified hash_algo <built-in function openssl_sha256>
DEB [20250412-03:16:24.853] thr=1   paramiko.transport: Switch to new keys ...
DEB [20250412-03:16:24.854] thr=2   paramiko.transport: Adding ssh-rsa host key for acc2-<BUILDID>.dev.odoo.com: b'e2c6f211753ebbcb5337a618d9a46650'
DEB [20250412-03:16:24.854] thr=1   paramiko.transport: Got EXT_INFO: {'server-sig-algs': b'ssh-ed25519,rsa-sha2-512,rsa-sha2-256'}
DEB [20250412-03:16:25.023] thr=2   paramiko.transport: Trying discovered key b'0a8557d5f0a0f0e407f2dbf864850d6b' in ~/.ssh/<IDENTITY_FILE>
DEB [20250412-03:16:25.036] thr=1   paramiko.transport: userauth is OK
DEB [20250412-03:16:25.036] thr=1   paramiko.transport: Finalizing pubkey algorithm for key of type 'ssh-rsa'
DEB [20250412-03:16:25.036] thr=1   paramiko.transport: Our pubkey algorithm list: ['rsa-sha2-512', 'rsa-sha2-256', 'ssh-rsa']
DEB [20250412-03:16:25.036] thr=1   paramiko.transport: Server-side algorithm list: ['ssh-ed25519', 'rsa-sha2-512', 'rsa-sha2-256']
DEB [20250412-03:16:25.036] thr=1   paramiko.transport: Agreed upon 'rsa-sha2-512' pubkey algorithm
INF [20250412-03:16:25.642] thr=1   paramiko.transport: Authentication (publickey) successful!
DEB [20250412-03:16:25.643] thr=2   paramiko.transport: [chan 0] Max packet in: 32768 bytes
DEB [20250412-03:16:25.654] thr=1   paramiko.transport: === Key exchange possibilities ===
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: kex algos: curve25519-sha256@libssh.org, diffie-hellman-group14-sha1, kex-strict-s-v00@openssh.com
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: server key: rsa-sha2-512, rsa-sha2-256
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: client encrypt: aes128-ctr, aes192-ctr, aes256-ctr
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: server encrypt: aes128-ctr, aes192-ctr, aes256-ctr
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: client mac: hmac-sha2-256, hmac-sha2-512, hmac-sha2-256-etm@openssh.com, hmac-sha2-512-etm@openssh.com
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: server mac: hmac-sha2-256, hmac-sha2-512, hmac-sha2-256-etm@openssh.com, hmac-sha2-512-etm@openssh.com
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: client compress: none
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: server compress: none
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: client lang: <none>
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: server lang: <none>
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: kex follows: False
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: === Key exchange agreements ===
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: Kex: curve25519-sha256@libssh.org
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: HostKey: rsa-sha2-512
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: Cipher: aes128-ctr
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: MAC: hmac-sha2-256
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: Compression: none
DEB [20250412-03:16:25.655] thr=1   paramiko.transport: === End of kex handshake ===
ERR [20250412-03:16:25.661] thr=1   paramiko.transport: Exception (client): Expecting packet from (31,), got 91
ERR [20250412-03:16:25.663] thr=1   paramiko.transport: Traceback (most recent call last):
ERR [20250412-03:16:25.663] thr=1   paramiko.transport:   File "/Library/Frameworks/Python.framework/Versions/3.12/lib/python3.12/site-packages/paramiko/transport.py", line 2123, in run
ERR [20250412-03:16:25.663] thr=1   paramiko.transport:     raise SSHException(
ERR [20250412-03:16:25.663] thr=1   paramiko.transport: paramiko.ssh_exception.SSHException: Expecting packet from (31,), got 91
ERR [20250412-03:16:25.663] thr=1   paramiko.transport: 

Start in paramiko/transport.py around the reported exception at lines 2123/2219, then trace the rekey handling alongside transport.open_session() and transport.open_channel(). Use the supplied Paramiko debug log and Odoo.sh reproduction to examine the type 91 message during rekeying. Done means the connection can complete authentication, channel opening, and command execution without MessageOrderError.