На стороне клиента проблема выглядит так:

sabitov@yam ~ $ ssh 1.2.3.4
Connection closed by 1.2.3.4

На стороне циски наблюдаем при этом такую картину:

Cisco881 #debug ip ssh de
Cisco881 #debug ip ssh detail 
ssh detail messages debugging is on
Cisco #
Apr 23 06:13:24.167: SSH1: starting SSH control process
Apr 23 06:13:24.167: SSH1: sent protocol version id SSH-2.0-Cisco-1.25
Apr 23 06:13:24.187: SSH1: protocol version id is - SSH-2.0-OpenSSH_6.6p1-hpn14v4
Apr 23 06:13:24.187: SSH2 1: SSH2_MSG_KEXINIT sent
Apr 23 06:13:24.191: SSH2 1: SSH2_MSG_KEXINIT received
Apr 23 06:13:24.191: SSH2:kex: client->server enc:aes128-cbc mac:hmac-md5 
Apr 23 06:13:24.191: SSH2:kex: server->client enc:aes128-cbc mac:hmac-md5 
Apr 23 06:13:24.419: SSH2 1: SSH2_MSG_KEX_DH_GEX_REQUEST received
Apr 23 06:13:24.419: SSH2 1: Range sent by client is - 1024 < 3072 < 8192 
Apr 23 06:13:24.419: SSH2 1:  Invalid modulus length
Apr 23 06:13:24.419: %SSH-5-SSH2_SESSION: SSH2 Session request from 5.6.7.8 (tty = 1) using crypto cipher '', hmac '' Failed
Apr 23 06:13:24.419: %SSH-5-SSH2_CLOSE: SSH2 Session from 5.6.7.8 (tty = 1) for user '' using crypto cipher '', hmac '' closed
Apr 23 06:13:24.519: SSH1: Session disconnected - error 0x00
Cisco #

Видно, что клиент с циской договорились до enc:aes128-cbc mac:hmac-md5, и проблема состоит в «Invalid modulus length». Дело в том, что в RFC4419 нет никаких упоминалий, что длина этого самого modulus'а должна быть степенью двойки. Но разработчики Cisco, как видим, самые умные… :( Если принудительно сменить алгоритм шифрования и MAC-алгоритм, то можно получить еще один пример кривости в реализации ssh-сервера от Cisco.

На клиенте:

sabitov@yam ~ $ ssh -c aes256-cbc -m hmac-sha1 1.2.3.4
Connection closed by 1.2.3.4

На Cisco:

Apr 23 06:30:40.099: SSH1: starting SSH control process
Apr 23 06:30:40.099: SSH1: sent protocol version id SSH-2.0-Cisco-1.25
Apr 23 06:30:40.127: SSH1: protocol version id is - SSH-2.0-OpenSSH_6.6p1-hpn14v4
Apr 23 06:30:40.127: SSH2 1: SSH2_MSG_KEXINIT sent
Apr 23 06:30:40.127: SSH2 1: SSH2_MSG_KEXINIT received
Apr 23 06:30:40.127: SSH2:kex: client->server enc:aes256-cbc mac:hmac-sha1 
Apr 23 06:30:40.127: SSH2:kex: server->client enc:aes256-cbc mac:hmac-sha1 
Apr 23 06:30:40.351: SSH2 1: SSH2_MSG_KEX_DH_GEX_REQUEST received
Apr 23 06:30:40.351: SSH2 1: Range sent by client is - 1024 < 8192 < 8192 
Apr 23 06:30:40.351: SSH2 1:  Client DH key range mismatch with max built-in
                        DH key on server!
Apr 23 06:30:40.351: %SSH-5-SSH2_SESSION: SSH2 Session request from 5.6.7.8 (tty = 1) using crypto cipher '', hmac '' Failed
Apr 23 06:30:40.351: %SSH-5-SSH2_CLOSE: SSH2 Session from 5.6.7.8 (tty = 1) for user '' using crypto cipher '', hmac '' closed
Apr 23 06:30:40.451: SSH1: Session disconnected - error 0x00

И решается вся эта петрушка очень просто (на клиенте):

sabitov@yam ~ $ ssh -Q kex 
diffie-hellman-group1-sha1
diffie-hellman-group14-sha1
diffie-hellman-group-exchange-sha1
diffie-hellman-group-exchange-sha256
ecdh-sha2-nistp256
ecdh-sha2-nistp384
ecdh-sha2-nistp521
diffie-hellman-group1-sha1
curve25519-sha256@libssh.org
sabitov@yam ~ $ ssh -o KexAlgorithms=diffie-hellman-group14-sha1 1.2.3.4

-----------------------------------------------------------------------
xxxxxxxx Group Cisco router
for more information please call +7-383-xxx x xxx
-----------------------------------------------------------------------
Password: 

Чтобы не вводить каждый раз многабукаф прописываем параметры соединения в конфиг:

.ssh/config

Host 1.2.3.4
        KexAlgorithms diffie-hellman-group14-sha1

— Andrew A. Sabitov 2014-04-23 13:39