When I ssh to a server - let's call it x.x.x.x - over one network, Network A, I get a message that the remote host identification has changed.
If I use one of two other networks - call them Network B and Network C - to connect to x.x.x.x, I don't get the message.
That is, for the same IP address of x.x.x.x, Network A is giving back a different remote host identification than Network B and Network C.
So my theory is that since Network B and Network C agree, they are correct, and Network A must be giving me the wrong key somehow.
Network A gives the same results over Wi-Fi or ethernet. Network B is my home Wi-Fi and Network C is a mobile hotspot Wi-Fi.
I've rebooted Network A's router, but the different remote host identification persists.
Does this indicate a MITM attack? Is there anything else it could be? What are the next steps?
And to be clear, the problem is not just that it has updated. If I switch my known_hosts to contain the key that network A expects, it works, but then network B and C don't work, and vice versa. That is, they are currently expecting different keys.