Invalid host key verification message displays when connecting to existing host with new algorithm

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Connect to a host using, i.e., RSA
2. Verify the host's key fingerprint, which results in it being saved with the 
host's profile
3. Connect to the same host again later using ECDSA for whatever reason (it 
appears the new version prefers it)
4. A warning message that the host's key has changed is displayed

What is the expected output? What do you see instead?

I would expect that, when the connection algorithm changes, the application 
notify me that it's now connecting using a different algorithm and that I 
should verify the fingerprint.  The current output provides no feedback that 
the reason for the changed host fingerprint is because a different algorithm is 
being used.

What version of the product are you using (you can see this by using Menu
-> About in the Host List)?

1.8.2 2015.03.22

What type of system are you trying to connect to?

An Ubuntu Linux 12.04 system running OpenSSHd

If you are able to connect, what is the output of "echo $TERM", "uname -a",
and any other relevant information on the host?

No other relevant information.

Please provide any additional information below.

This behavior kind of freaked me out, needless to say, especially when I 
connected to the host from other connectivity (with a different client) and got 
no warning message, leading me to suspect that my cellular provider was 
proxying SSH connections all of a sudden.  Once I connected with alternate 
means, I was able to verify that the new fingerprint being presented was an 
ECDSA fingerprint as opposed to the RSA fingerprint that was saved with the 
profile.

Original issue reported on code.google.com by far...@gmail.com on 27 Mar 2015 at 7:54

[GoogleCodeExporter]

I've just spent an hour verifying my SSH host keys against backups due to this 
issue. I went into full paranoia mode. I believe this should be a high priority 
issue as this will cause both false negatives (people believing a host 
fingerprint alert to be fine because they have had it on other servers too) and 
false positives (where ECDSA is now preferred over RSA). 

The change log that I can see on Google Play did not suggest that a change to 
host key preference was in the update. I can't really see anything in the 
commit log which would explain this change of behaviour either. I've probably 
just missed something.

Could the behaviour be changed to tell users that the host key has been 
verified by RSA however a new ECDSA fingerprint can be saved for future use?

Phone: HTC One m8
Android 5.0.1 with Sense 6.0 

Thanks,

Tom

Original comment by tg.mufcn...@gmail.com on 31 Mar 2015 at 7:24

[GoogleCodeExporter]

I ran into the same problem.
Some previously saved host connections don't work anymore.

sshd server auth.log (debug level 3):
Apr  1 00:56:45 sshd[14005]: debug1: expecting SSH2_MSG_NEWKEYS [preauth]
Apr  1 00:56:45 sshd[14005]: Connection closed by 192.168.1.103 [preauth]

Connections, that still work are those, where the server has no ECSDA auth.

Possible workarounds are:
* Disabling the ECDSA host key on the sshd_config and restart (if you have 
permission to do this):
  #HostKey /etc/ssh/ssh_host_ecdsa_key
* Downgrade the App ;)

Original comment by dammme...@googlemail.com on 31 Mar 2015 at 11:22

[GoogleCodeExporter]

Snap. Latest connectbot against Fedora 20, saved connection moans about "Host 
key changed", and lists a "Host EC fingerprint" to verify against.

Original comment by tom.chiv...@gmail.com on 1 Apr 2015 at 6:45