Bug 1228013 - Server responded "Algorithm negotiation failed"
Summary: Server responded "Algorithm negotiation failed"
Keywords:
Status: CLOSED NOTABUG
Alias: None
Product: Fedora
Classification: Fedora
Component: openssh
Version: 22
Hardware: Unspecified
OS: Windows
unspecified
medium
Target Milestone: ---
Assignee: Jakub Jelen
QA Contact: Fedora Extras Quality Assurance
URL:
Whiteboard:
Depends On:
Blocks:
TreeView+ depends on / blocked
 
Reported: 2015-06-04 05:34 UTC by Gerd Pokorra
Modified: 2015-09-07 23:19 UTC (History)
6 users (show)

Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed: 2015-06-08 10:43:58 UTC
Type: Bug


Attachments (Terms of Use)
screen shot from the client cipher list (24.83 KB, image/png)
2015-06-05 18:12 UTC, Gerd Pokorra
no flags Details
debug file generated with: /usr/sbin/sshd -ddd 2>&1 | tee sshd.F22.debug3.txt (6.74 KB, text/plain)
2015-06-05 18:46 UTC, Gerd Pokorra
no flags Details
file name: sshd.F21.debug3.txt (19.76 KB, text/plain)
2015-06-05 18:48 UTC, Gerd Pokorra
no flags Details
debug from the windows client during the connection problem (23.37 KB, text/plain)
2015-06-05 19:02 UTC, Gerd Pokorra
no flags Details

Description Gerd Pokorra 2015-06-04 05:34:40 UTC
Description of problem:

After an upgrade from Fedora 21 to Fedora 22 I can no longer connect to the computer by 'ssh' from a windows system using the client program "SSH Secure Shell".


Version-Release number of selected component (if applicable):

I downloaded the windows ssh client form: http://www.soft-ware.net/ssh-secure-shell
I use the wersion: SSH Secure Shell 3.2.9

[gz016@vgerd1 ~]$ rpm -qa | grep openssh
openssh-server-6.8p1-6.fc22.x86_64
openssh-clients-6.8p1-6.fc22.x86_64
openssh-6.8p1-6.fc22.x86_64
[gz016@vgerd1 ~]$ 


When I try to connect to the computer (f22) I get the following error message in a window:
"Server responded "Algorithm negotiation failed". Key exchange with the 
remote host failed. This can happen for example if the remote host 
computer does not support the selected algorithms."


In the file /etc/ssh/sshd_config I have the following host key entries:

# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
#HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key

Comment 1 Jakub Jelen 2015-06-04 07:35:18 UTC
I can only guess that it is related to new feature: Hostkey rotation [1]. But without more debug information I can't acknowledge.

Probably your client is not handling this extension correctly, so first of all check if you have latest version of your client.
If the latest version will not help, I would ask you for some debug information from client (preferably) and server.

I remember there were problems with Tera Term, which was implementing protocol wrong way. If there is problem in the windows client, please report bug to your client.

[1] http://www.openssh.com/txt/release-6.8

Comment 2 Gerd Pokorra 2015-06-04 13:13:12 UTC
The client has installed the latest version (3.2.9).

I am not sure if the client provide logging information. I will have a
closer look for it tomorrow.

Here are some logging from the server:

grep 141.99.6.13 messages* | grep fail
...
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2407> pid=3958 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=unsupported-cipher
direction=? cipher=? ksize=? rport=1296 laddr=141.99.6.11 lport=22
exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=failed'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-1112> pid=3958 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=login
acct="(unknown)" exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13
terminal=ssh res=failed'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2407> pid=3960 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=unsupported-cipher
direction=? cipher=? ksize=? rport=1297 laddr=141.99.6.11 lport=22
exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=failed'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-1112> pid=3960 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=login
acct="(unknown)" exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13
terminal=ssh res=failed'



grep 141.99.6.13 messages*
...
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2404> pid=3959 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:0e:14:46:7b:db:58:44:f1:c0:ca:9a:14:06:fe:9f:c1:2e:24:31:d7:32:48:13:45:38:9f:b1:7e:9e:bb:48:f2 direction=? spid=3959 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2404> pid=3959 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:19:84:f8:ba:36:95:fe:90:b1:43:b2:97:5a:ec:b1:f5:dd:df:74:2b:75:5e:6f:51:57:3f:a5:e1:34:2f:e9:93 direction=? spid=3959 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2404> pid=3959 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:9a:c5:98:b1:7e:b2:bb:98:05:cd:62:b9:79:8c:ac:49:b1:b0:36:ce:87:05:85:36:8f:7f:51:d2:b5:3c:05:f1 direction=? spid=3959 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2407> pid=3958 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=unsupported-cipher
direction=? cipher=? ksize=? rport=1296 laddr=141.99.6.11 lport=22
exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=failed'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2404> pid=3958 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:9a:c5:98:b1:7e:b2:bb:98:05:cd:62:b9:79:8c:ac:49:b1:b0:36:ce:87:05:85:36:8f:7f:51:d2:b5:3c:05:f1 direction=? spid=3959 suid=74  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2404> pid=3958 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:0e:14:46:7b:db:58:44:f1:c0:ca:9a:14:06:fe:9f:c1:2e:24:31:d7:32:48:13:45:38:9f:b1:7e:9e:bb:48:f2 direction=? spid=3958 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2404> pid=3958 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:19:84:f8:ba:36:95:fe:90:b1:43:b2:97:5a:ec:b1:f5:dd:df:74:2b:75:5e:6f:51:57:3f:a5:e1:34:2f:e9:93 direction=? spid=3958 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-2404> pid=3958 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:9a:c5:98:b1:7e:b2:bb:98:05:cd:62:b9:79:8c:ac:49:b1:b0:36:ce:87:05:85:36:8f:7f:51:d2:b5:3c:05:f1 direction=? spid=3958 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:19:44 vgerd1 audit: <audit-1112> pid=3958 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=login
acct="(unknown)" exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13
terminal=ssh res=failed'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2404> pid=3961 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:0e:14:46:7b:db:58:44:f1:c0:ca:9a:14:06:fe:9f:c1:2e:24:31:d7:32:48:13:45:38:9f:b1:7e:9e:bb:48:f2 direction=? spid=3961 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2404> pid=3961 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:19:84:f8:ba:36:95:fe:90:b1:43:b2:97:5a:ec:b1:f5:dd:df:74:2b:75:5e:6f:51:57:3f:a5:e1:34:2f:e9:93 direction=? spid=3961 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2404> pid=3961 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:9a:c5:98:b1:7e:b2:bb:98:05:cd:62:b9:79:8c:ac:49:b1:b0:36:ce:87:05:85:36:8f:7f:51:d2:b5:3c:05:f1 direction=? spid=3961 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2407> pid=3960 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=unsupported-cipher
direction=? cipher=? ksize=? rport=1297 laddr=141.99.6.11 lport=22
exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=failed'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2404> pid=3960 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:9a:c5:98:b1:7e:b2:bb:98:05:cd:62:b9:79:8c:ac:49:b1:b0:36:ce:87:05:85:36:8f:7f:51:d2:b5:3c:05:f1 direction=? spid=3961 suid=74  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2404> pid=3960 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:0e:14:46:7b:db:58:44:f1:c0:ca:9a:14:06:fe:9f:c1:2e:24:31:d7:32:48:13:45:38:9f:b1:7e:9e:bb:48:f2 direction=? spid=3960 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2404> pid=3960 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:19:84:f8:ba:36:95:fe:90:b1:43:b2:97:5a:ec:b1:f5:dd:df:74:2b:75:5e:6f:51:57:3f:a5:e1:34:2f:e9:93 direction=? spid=3960 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-2404> pid=3960 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=destroy kind=server
fp=SHA256:9a:c5:98:b1:7e:b2:bb:98:05:cd:62:b9:79:8c:ac:49:b1:b0:36:ce:87:05:85:36:8f:7f:51:d2:b5:3c:05:f1 direction=? spid=3960 suid=0  exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13 terminal=? res=success'
messages:Jun  3 13:21:29 vgerd1 audit: <audit-1112> pid=3960 uid=0
auid=4294967295 ses=4294967295
subj=system_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=login
acct="(unknown)" exe="/usr/sbin/sshd" hostname=? addr=141.99.6.13
terminal=ssh res=failed


Can you see if hostkey rotation is the reason for the problem?

Comment 3 Jakub Jelen 2015-06-05 10:25:59 UTC
OK. Probably not. In audit you can see "unsupported-cipher" as so it was in the first description. It looks like your client is not offering any ciphers that are accepted by server. Server list was shortened with this release.

You can verify what ciphers server accepts by running
sshd -T | grep ciphers

You should be able to set up some of the ciphers from list in your client.


You can also set up log level in sshd config (DEBUG2 should be enough) and you should get some message like this:
> Jun  5 12:16:57 localhost sshd[29426]: debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-gcm@openssh.com,aes256-gcm@openssh.com,chacha20-poly1305@openssh.com,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se [preauth]

to see what is offered by client and why it failed. Successful connection should end with something like:
> Jun  5 12:16:57 localhost sshd[29426]: debug1: kex: client->server aes128-ctr hmac-sha1-etm@openssh.com none [preauth]
> Jun  5 12:16:57 localhost sshd[29426]: debug1: kex: server->client aes128-ctr hmac-sha1-etm@openssh.com none [preauth]

Comment 4 Gerd Pokorra 2015-06-05 18:12:05 UTC
Created attachment 1035394 [details]
screen shot from the client cipher list

Comment 5 Gerd Pokorra 2015-06-05 18:39:00 UTC
I am afraid that the client is only able to use the CBC mode.

output of working F21:
sshd -T | grep cipher
ciphers 3des-cbc,blowfish-cbc,cast128-cbc,arcfour,arcfour128,arcfour256,aes128-cbc,aes192-cbc,aes256-cbc,rijndael-cbc@lysator.liu.se,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,chacha20-poly1305@openssh.com


output of saver F22:
sshd -T | grep cipher
ciphers aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,chacha20-poly1305@openssh.com


The free client was only developed until 2003.


If I copy the executable /usr/sbin/sshd of the F21 to the F22 system and restart the ssh daemon, then the error disappearance.


At the client it is also possible to enable debugging, but there is not much to see. At the attached image (picture) of the client cipher list also the mode of operation is not to see.


I generated debug 3 level files from the F21 and F22 sshd and will upload them as files.

Comment 6 Gerd Pokorra 2015-06-05 18:46:21 UTC
Created attachment 1035395 [details]
debug file generated with: /usr/sbin/sshd -ddd 2>&1 | tee sshd.F22.debug3.txt

Comment 7 Gerd Pokorra 2015-06-05 18:48:40 UTC
Created attachment 1035396 [details]
file name:  sshd.F21.debug3.txt

generated with: /usr/sbin/sshd -ddd 2>&1 | tee ...

Comment 8 Gerd Pokorra 2015-06-05 19:02:48 UTC
Created attachment 1035397 [details]
debug from the windows client during the connection problem

Comment 9 Gerd Pokorra 2015-06-06 04:24:21 UTC
I added the line

Ciphers 3des-cbc,blowfish-cbc,cast128-cbc,arcfour,arcfour128,arcfour256,aes128-cbc,aes192-cbc,aes256-cbc,rijndael-cbc@lysator.liu.se,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,chacha20-poly1305@openssh.com

to the file /etc/ssh/sshd_config at the computer running with F22 and restarted sshd.

The output of the command 'sshd -T | grep cipher' on F22 now is also like the f21 output:
ciphers 3des-cbc,blowfish-cbc,cast128-cbc,arcfour,arcfour128,arcfour256,aes128-cbc,aes192-cbc,aes256-cbc,rijndael-cbc@lysator.liu.se,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,chacha20-poly1305@openssh.com

I can test the client only at the office and will be there at the latest on Monday. If I have done the test, then I will report.

Comment 10 Gerd Pokorra 2015-06-06 05:32:21 UTC
The error message is still the same. I can generate a new debug file from the client next week.

Comment 11 Jakub Jelen 2015-06-08 06:16:58 UTC
> The free client was only developed until 2003.
So I guess it is right time to throw it away ... cbc modes are possibly vulnerable, see cbc.adv in [1].

As a workaround you can specify these ciphers in server sshd_config (you don't need to copy executables around), but I would recommend you to use some more modern client these days. Certainly it is not a bug in openssh package.


[1] http://www.openssh.com/security.html

Comment 12 Gerd Pokorra 2015-06-08 10:43:58 UTC
I agree, it is the right time to throw this client away. Other ssh windows clients works fine. Thank you very much for your help with your in-depth knowledge.

Comment 13 Rafael Uchôa 2015-09-07 23:19:28 UTC
If you trust in your server network, you can put in:

/etc/ssh/sshd_config

Ciphers aes128-cbc,aes192-cbc,aes256-cbc,blowfish-cbc,arcfour
KexAlgorithms diffie-hellman-group1-sha1

It worked for me using the 'SSH Secure Shell'.


Note You need to log in before you can comment on or make changes to this bug.