warning: remote host identification has changed!

Hello,

I am getting this message occasionally. How big is the chance that it is
really a man-in-the-middle attack?

The first time I got this error, I have deleted the offending line in
the $HOME/.ssh/known_hosts file, and just retried. The authentication
using the authorized_keys file was also not working, so I entered the
root password.

After the same happened again a few minutes later, I became suspicious
and created a new ssh key and root password.

But now the same happens again: I get the following message, but not
always. It happens to work ~10 times or minutes in a row, and then I get
the error message a few times, without any recognizable pattern, and
from the same shell.

It seems to start working again after I try the same from a different user on my local machine.

--------------------8<-------------------------
rup@sempron:~/cvs/homepages/schachtner> ssh root@www
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
89:b8:08:03:f3:02:d0:2f:5a:e3:7c:c3:eb:ef:8d:7e.
Please contact your system administrator.
Add correct host key in /localhome/rup/.ssh/known_hosts to get rid of this message.
Offending key in /localhome/rup/.ssh/known_hosts:4
RSA host key for www has changed and you have requested strict checking.
Host key verification failed.
rup@sempron:~/cvs/homepages/schachtner> ssh root@www
Last login: Wed Mar 19 09:48:45 2008 from wdsl-80-73-127-53.wcli.deg.net
Have a lot of fun...
h68390:~ # exit
logout
Connection to www closed.
--------------------8<-------------------------

What is really surprising is that the key fingerprint displayed in the
message is identical with the one I got when creating the key.



.