Remote host identification has changed - How do I know if it's an attack or not?

Question

When connecting using SSH to a shared hosting provider I'm regularly using, I got this message today:

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 [xyz.example.com]:2222 is 2b:6b:ec:d3:c0:fe:fb:40:11:fe:4b:73:03:17:6b:89. Please contact your system administrator. Add correct host key in C:\Users\Example.ssh\known_hosts to get rid of this message. Do you want to delete the old key and insert the new key?

I clicked "No", because I have no idea if it's a legitimate change or an actual attack.

How would I find out? The hosting provider is using CPanel, if it helps.

Clarification due to "possible duplicate"

I've seen many similar questions asked here and on StackOverflow, but all of the answers seem to explain how to make the "annoying" warning go away, not how to actually make sure that you're not connecting to a man in the middle. If I wanted to make it go away, I could just click "OK".

I'm asking "How do I know if it's an attack or a legitimate change?", not "How do I make the warning go away?".

Answer 1

You did the right thing, don't connect if you don't know what happened, that is exactly what the warning is for. This message would absolutely appear if an attack was taking place. If it wasn't it could also appear if something else has changed.

You need to investigate what caused the change before drawing a conclusion.

If you can login in an alternative way (i.e. via cpanel?) check the SSH daemon configuration for the keys it is using [/etc/ssh/ssh_host_*], the configuration could have changed and the order of the host keys presented could have changed, thus showing a different one, check the date of change of host key files, try to find the fingerprint of the stored key files and compare to the value you have, etc. Has the IP address changed since you last connected?

Try to connect to the host using a completely different network (e.g. tethered to a smartphone as opposed to using the local wifi?), see if the same happens.