Natty Narwhal: Problems connecting to servers behind (Cisco) firewalls using ssh

After upgrading to Natty Narwhal I couldn’t connect to my Linux based jump host (connected via VPN):

OpenSSH_5.8p1 Debian-1ubuntu2, OpenSSL 0.9.8o 01 Jun 2010
debug1: Reading configuration data /home/alj/.ssh/config
debug1: Applying options for *
debug1: Applying options for smallpox.xxx.dk
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to smallpox.xxx.dk [xxx.xxx.xxx.xxx] port 22.
debug1: Connection established.
debug1: identity file /home/alj/.ssh/id_rsa type -1
debug1: identity file /home/alj/.ssh/id_rsa-cert type -1
debug1: identity file /home/alj/.ssh/id_dsa type 2
debug1: Checking blacklist file /usr/share/ssh/blacklist.DSA-1024
debug1: Checking blacklist file /etc/ssh/blacklist.DSA-1024
debug1: identity file /home/alj/.ssh/id_dsa-cert type -1
debug1: identity file /home/alj/.ssh/id_ecdsa type -1
debug1: identity file /home/alj/.ssh/id_ecdsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.5p1 Debian-4ubuntu4
debug1: match: OpenSSH_5.5p1 Debian-4ubuntu4 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.8p1 Debian-1ubuntu2
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 [email protected]
debug1: kex: client->server aes128-ctr hmac-md5 [email protected]
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
Read from socket failed: Connection reset by peer

The key seem to be that Natty uses OpenSSH 5.8p1 – This problem seem to affect clients newer than 5.7p1, when connecting to older servers. And the problem seem to be restricted to connecting through some firewalls, I have no problem on my home network and when connecting to hosts running iptables.

If have found this workaround. Apparently is has something to do with the length of the cipher list and is not isolated to Ubuntu.

Edit /etc/ssh/ssh_config or $HOME/.ssh/config and add this in the Host * stanza or for the host you have problems connecting to:

        Ciphers aes128-ctr,aes192-ctr,aes256-ctr,aes128-cbc,3des-cbc
        MACs hmac-md5,hmac-sha1,hmac-ripemd160