Can't connect to Jammy hosts (openssh >= 8.8p1-1)

python3-paramiko can't connect to Jammy hosts, likely because of the stricter signature requirements introduced in openssh 8.8p1-1.

Reproducer:

1. Setup a passwordless keypair and add localhost to known_hosts:

$ sudo apt install -y openssh-server openssh-client ipython3 python3-paramiko
$ ssh-keygen -f ~/.ssh/id_rsa_insecure
$ SSH_AUTH_SOCK= ssh-copy-id -i ~/.ssh/id_rsa_insecure localhost

2. Verify setup:

paride@stramonio:~$ SSH_AUTH_SOCK= ssh -i ~/.ssh/id_rsa_insecure localhost date
2022-02-23T12:35:39 CET

3. Try the same with paramiko from python3-paramiko:

$ ipython3

In [1]: import paramiko, os
In [2]: client = paramiko.SSHClient()
In [3]: client.load_system_host_keys()
In [4]: client.connect('localhost', key_filename=os.path.expanduser('~/.ssh/id_rsa_insecure'))
Unknown exception: q must be exactly 160, 224, or 256 bits long
[Full Traceback Below]

4. Try with a newer paramiko:

$ python3 -m venv /tmp/newparamiko
$ source /tmp/newparamiko/bin/activate
$ pip install -q paramiko==2.9.2
$ ipython3

In [1]: import paramiko, os
In [2]: client = paramiko.SSHClient()
In [3]: client.load_system_host_keys()
In [4]: client.connect('localhost', key_filename=os.path.expanduser('~/.ssh/id_rsa_insecure'))
In [5]: # It works!

The Point 3. failure can be reproduced by installing older versions of paramiko via pip, so the issue is not specific to Ubuntu. Likely related upstream changes/issues:

* https://github.com/paramiko/paramiko/pull/1643
* https://github.com/paramiko/paramiko/issues/1955

--- Point 3. Traceback ---

Traceback (most recent call last):
  File "/usr/lib/python3/dist-packages/paramiko/transport.py", line 2109, in run
    handler(self.auth_handler, m)
  File "/usr/lib/python3/dist-packages/paramiko/auth_handler.py", line 298, in _parse_service_accept
    sig = self.private_key.sign_ssh_data(blob)
  File "/usr/lib/python3/dist-packages/paramiko/dsskey.py", line 109, in sign_ssh_data
    key = dsa.DSAPrivateNumbers(
  File "/usr/lib/python3/dist-packages/cryptography/hazmat/primitives/asymmetric/dsa.py", line 244, in private_key
    return backend.load_dsa_private_numbers(self)
  File "/usr/lib/python3/dist-packages/cryptography/hazmat/backends/openssl/backend.py", line 827, in load_dsa_private_numbers
    dsa._check_dsa_private_numbers(numbers)
  File "/usr/lib/python3/dist-packages/cryptography/hazmat/primitives/asymmetric/dsa.py", line 282, in _check_dsa_private_numbers
    _check_dsa_parameters(parameters)
  File "/usr/lib/python3/dist-packages/cryptography/hazmat/primitives/asymmetric/dsa.py", line 274, in _check_dsa_parameters
    raise ValueError("q must be exactly 160, 224, or 256 bits long")
ValueError: q must be exactly 160, 224, or 256 bits long