Crazy story. Had SSH working over VPN (cisco, vpnc client, Ubuntu). After a while it just stopped. My employer didn’t change their VPN setup. Just stopped working. We checked logs, tried all kinds of stuff, nothing. Then one day, it started working again, but stopped a few hours later. So my guess is that I was connected to a different WiFi. Tried mobile hotspot using 3G, all fine. And I started to blame my router, tried to setup some forwarding, still nothing. Then I went on to check with my ISP, considering I have a custom router, and all the routers it was working on were their “official” routers. No luck, which isn’t a surprise, considering the usual ISP customer support. And then I ended up at these 2 topics:
http://stackoverflow.com/questions/25341773/cisco-ssh-key-exchange-fails-from-ubuntu-14-04-client-dh-key-range-mismatch
http://www.held.org.il/blog/2011/05/the-myterious-case-of-broken-ssh-client-connection-reset-by-peer
So what made it work for me is:
ssh -v -o KexAlgorithms=diffie-hellman-group14-sha1 -c aes256-ctr me@some.server
Drove me nuts, since the same machine works with different internet connection. I have no idea how the key exchange algorithm and the cipher specification make it work. And still don’t know the exact culprit, but my guess is it’s either the router or the ISP. My machine receives messages from the SSH server (when i run it without -0 -c), and then just times out on debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP.