Corrupted MAC on input?
А если на 6.6p1-alt3 попробовать этот же MAC, -o 'macs umac-64@openssh.com'?
А если на 6.7p1-alt1 попробовать какой-нибудь другой MAC, например, -o 'macs hmac-sha2-256'?

У меня на чистой установке не воспроизвелось:
...
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.7
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.9
debug1: match: OpenSSH_5.9 pat OpenSSH_5* compat 0x0c000000
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes256-ctr umac-64@openssh.com none
debug1: kex: client->server aes256-ctr umac-64@openssh.com none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA 02:5e:95:b0:f6:1c:a7:13:0e:06:cf:86:44:d2:2f:1b
debug1: Host '[xxx]:222' is known and matches the ECDSA host key.
debug1: Found key in /usr/src/.ssh/known_hosts:1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
...

Похоже что при обновлении 6.6->6.7 изменился список приемлимых шифров. 27.11.2014 обновился на нескольких машинах (конфиг openssh-server из пакетов, неизменный):
===8<========================================================
Transaction starting at Thu 27 Nov 2014 09:43:00 AM KRAT
Installing libedit3 3.1.20141030-alt1
Upgrading openssh-server 6.6p1-alt3 to 6.7p1-alt1
Upgrading openssh-server-control 6.6p1-alt3 to 6.7p1-alt1
Upgrading openssh 6.6p1-alt3 to 6.7p1-alt1
Upgrading openssh-clients 6.6p1-alt3 to 6.7p1-alt1
Upgrading openssh-common 6.6p1-alt3 to 6.7p1-alt1
Transaction succeeded at Thu 27 Nov 2014 09:43:03 AM KRAT
===8<========================================================

и только к концу рабочего дня обнаружил, что не могу подключиться к ним графическим клиентом из под ОС Windows, который жалуется, что не нашел общих шифров с сервером. На серверах при этом такие логи:

===8<========================================================
Nov 27 16:14:31 xxx sshd[971798]: fatal: no matching cipher found: client aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour,aes192-cbc,aes256-cbc,rijndael128-cbc,rijndael192-cbc,rijndael256-cbc,rijndael-cbc@lysator.liu.se server aes256-gcm@openssh.com,aes128-gcm@openssh.com,aes256-ctr,aes192-ctr,aes128-ctr,chacha20-poly1305@openssh.com [preauth]
Nov 27 16:14:38 xxx sshd[971849]: fatal: no matching cipher found: client aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour,aes192-cbc,aes256-cbc,rijndael128-cbc,rijndael192-cbc,rijndael256-cbc,rijndael-cbc@lysator.liu.se server aes256-gcm@openssh.com,aes128-gcm@openssh.com,aes256-ctr,aes192-ctr,aes128-ctr,chacha20-poly1305@openssh.com [preauth]
Nov 27 16:15:47 xxx sshd[972055]: fatal: no matching cipher found: client aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour,aes192-cbc,aes256-cbc,rijndael128-cbc,rijndael192-cbc,rijndael256-cbc,rijndael-cbc@lysator.liu.se server aes256-gcm@openssh.com,aes128-gcm@openssh.com,aes256-ctr,aes192-ctr,aes128-ctr,chacha20-poly1305@openssh.com [preauth]
Nov 27 16:21:23 xxx sshd[973207]: fatal: no matching cipher found: client aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour,aes192-cbc,aes256-cbc,rijndael128-cbc,rijndael192-cbc,rijndael256-cbc,rijndael-cbc@lysator.liu.se server aes256-gcm@openssh.com,aes128-gcm@openssh.com,aes256-ctr,aes192-ctr,aes128-ctr,chacha20-poly1305@openssh.com [preauth]
===8<========================================================

обошел проблему путём включения в список разрешенных шифров на клиенте aes192-ctr, aes128-ctr, aes256-ctr (не знаю, почему они у меня были выключены).

Но это явный баг.

(In reply to comment #3)
> обошел проблему путём включения в список разрешенных шифров на клиенте
> aes192-ctr, aes128-ctr, aes256-ctr (не знаю, почему они у меня были выключены).
> 
> Но это явный баг.

Это явный, но не баг, см. /usr/share/doc/openssh-6.7p1/CHANGES:

Changes since OpenSSH 6.6
=========================

Potentially-incompatible changes

 * sshd(8): The default set of ciphers and MACs has been altered to
   remove unsafe algorithms. In particular, CBC ciphers and arcfour*
   are disabled by default.

   The full set of algorithms remains available if configured
   explicitly via the Ciphers and MACs sshd_config options.

Если что, 6.7p1-alt1 на 3.6.1p2-alt6 сходил всё так же.

Извиняюсь, проморгал. Но не ожидал такой пороси от казалось бы минорного обновления. С другой стороны, хорошо, security is supposed to break things :-)

(In reply to comment #1)
> Corrupted MAC on input?
> А если на 6.6p1-alt3 попробовать этот же MAC, -o 'macs umac-64@openssh.com'?
> А если на 6.7p1-alt1 попробовать какой-нибудь другой MAC, например, -o 'macs
> hmac-sha2-256'?

ping?
И еще, какая архитектура у того хоста с openssh-server-5.9p1-alt2?

(В ответ на комментарий №7)
> (In reply to comment #1)
> > Corrupted MAC on input?
> > А если на 6.6p1-alt3 попробовать этот же MAC, -o 'macs umac-64@openssh.com'?
> > А если на 6.7p1-alt1 попробовать какой-нибудь другой MAC, например, -o 'macs
> > hmac-sha2-256'?
> 
> ping?
> И еще, какая архитектура у того хоста с openssh-server-5.9p1-alt2?

с другим mac пускало.
Я явно прописал список MACs на сервере, оказалось достаточно.
Это наш старый armv5, так что врядли что-то стоит делать.

(In reply to comment #8)
> (В ответ на комментарий №7)
> > (In reply to comment #1)
> > > Corrupted MAC on input?
> > > А если на 6.6p1-alt3 попробовать этот же MAC, -o 'macs umac-64@openssh.com'?
> > > А если на 6.7p1-alt1 попробовать какой-нибудь другой MAC, например, -o 'macs
> > > hmac-sha2-256'?
> > 
> > ping?
> > И еще, какая архитектура у того хоста с openssh-server-5.9p1-alt2?
> 
> с другим mac пускало.
> Я явно прописал список MACs на сервере, оказалось достаточно.
> Это наш старый armv5, так что врядли что-то стоит делать.

В старых реализациях umac-*@openssh.com на не-x86 были проблемы такого рода.