I am trying to connect to a server I have previously connected to. However newer version of OpenSSH does not use DSA keys. I get the following error when trying to connect:

Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the ***RSA*** key sent by the remote host is
Please contact your system administrator.
Add correct host key in /Users/john/.ssh/known_hosts to get rid of this message.
Offending ***DSA*** key in /Users/john/.ssh/known_hosts:25
***RSA*** host key for example.com has changed and you have requested strict checking.
Host key verification failed.

I have figured out that the problem is that DSA key is stored in known_hosts but there is no RSA key yet. Adding the RSA key fixes the problem.

I think the message is misleading, the RSA host key did not change.

I would expect OpenSSH to inform me that there is no RSA key yet and offer me to add the key. It should also check DNS for the key and show Matching host key fingerprint found in DNS. message (which I have set up).

Is it worth reporting to OpenSSH as a bug?

  • It is a correct message. Imagine if a m-i-t-m ssl proxy uses only dsa keys. This is exactly the same situation. Jan 4, 2017 at 10:00
  • @IporSircer there is no SSL proxy. Even the MitM needs to talk SSH protocol.
    – Jakuje
    Jan 4, 2017 at 10:43
  • okie. s/ssl/ssh/ Jan 4, 2017 at 10:45

1 Answer 1


I think the message is misleading, the RSA host key did not change.

The message is valid. The key in your known_hosts is DSA and the server sends RSA, they differ and it is wrong.

Since OpenSSH 6.8 the server sends all the keys after authentication to simplify the hostkey rotation or deprecation.

If you have new enough client and server, go on with workaround, temporary accept the DSA keys and let the client pick up the new ones:

ssh -oHostKeyAlgorithms=+ssh-dss your_remote_host

if the server has older version, you need to do that manually as you explain in the question.

This also needs a client configured to accept the new keys: UpdateHostKeys yes.

  • I still think the message is misleading. But thanks to your explanation I now fully understand why I am seeing such warning. Thanks also for the valuable information about UpdateHostKeys and -o HostKeyAlgorithms. It's been helpful. Jan 24, 2017 at 8:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .