I've found the solution to a problem I had with the Santrex VPS related with SSH fingerprints and SSH error.

[ERROR]

After rebooting the Santrex VPS and trying to SSH the machine I have this error:

inedit@tpad:~$ ssh santrex  
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@  
@    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 a host key has just been changed.  
The fingerprint for the RSA key sent by the remote host is  
ea:d6:a2:5d:76:27:51:50:73:39:ac:4e:ae:d8:2a:4d.  
Please contact your system administrator.  
Add correct host key in /home/inedit/.ssh/known_hosts to get rid of
this message.  
Offending RSA key in /home/inedit/.ssh/known_hosts:6  
Password authentication is disabled to avoid man-in-the-middle
attacks.  
Keyboard-interactive authentication is disabled to avoid
man-in-the-middle attacks.

[WHY]

This error happens when you have added the fingerprint of a server to you local file ".ssh/known_hosts". Normally the fingerprint of a server never changes, and if changes the most probably is that something nasty is happening. That's why the ssh-client shows you this ugly banner and ask you to contact your system administrator. The problem here is that YOU are the system administrator.

A fingerprint changes when the public key has changed, and if the public key has changed it means that the private key has changed too. So, why this error? It seems that the host creates a new pair of keys every time you boot the system. But this is a little bit weird.

[WHERE]

In the file "vim /etc/init.d/ssh_key_hack.sh". Funny, isn't it? You have and error related with ssh and you find a file called "ssh_key_hack". The content of the file is:

#! /bin/sh  
### BEGIN INIT INFO  
# Provides:          ssh_key_hack  
# Required-Start:  
# Required-Stop:  
# Default-Start:     2 3 4 5  
# Default-Stop:      0 6  
# Short-Description: ssh keys creation.  
# Description:       Create ssh keys.  
### END INIT INFO

case "$1" in  
start|"")  
rm -f /etc/ssh/ssh_host_*  
/usr/bin/ssh-keygen -t rsa -N '' -f /etc/ssh/ssh_host_rsa_key  
/usr/bin/ssh-keygen -t dsa -N '' -f /etc/ssh/ssh_host_dsa_key  
/usr/bin/ssh-keygen -t rsa1 -N '' -f /etc/ssh/ssh_host_key  
/usr/sbin/update-rc.d ssh_key_hack.sh remove >/dev/null 2>&1  
;;  
*)  
echo "Usage: ssh_key_hack [start]" >&2  
exit 3  
;;  
esac

[WHAT]

As you can see the script deletes the old keys, create a new pair or RSA/DSA keys and tries to deactive itself, preventing being executed the next time that the computer is rebooted, but in the last step, the script fails:

jcarreras@uma:/tmp$ sudo /usr/sbin/update-rc.d ssh_key_hack.sh
remove  
update-rc.d: /etc/init.d/ssh_key_hack.sh exists during rc.d purge
(use -f to force)

[SOLUTION]

Well, running this command you just deletes this funny named script.

sudo /usr/sbin/update-rc.d -f ssh_key_hack.sh remove

You could delete the script with "rm /etc/init.d/ssh_key_hack.sh" or deactivate with a command like "rcconf".

And that's all, gentelman.

Note: Ummm... you can do exactly the same with the "dhcpv6_hack.sh" script by executing "sudo /usr/sbin/update-rc.d -f dhcpv6_hack.sh remove".

Edit: This is the end of the story.