SSH connection attempts from China show different key; is China doing a MITM attack on SSH traffic?

Question

I have a server located in the USA and SSH to it from various places around the world. When I SSH in from a computer I have never used before, I'll see something like this:

The authenticity of host 'my.usa.server.com (11.22.33.44)' can't be established.
RSA key fingerprint is xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:b8:1d:61.
Are you sure you want to continue connecting (yes/no)? 

From most places in the world, the RSA fingerprint is identical, which makes sense, because I'm always connecting to the same server:

[From a server in Sweden]

me@sweden:~$ ssh [email protected]
The authenticity of host 'my.usa.server.com (11.22.33.44)' can't be established.
RSA key fingerprint is xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:b8:1d:61.
Are you sure you want to continue connecting (yes/no)? 
me@sweden:~$

[From a server in The Netherlands]

me@nl:~$ ssh [email protected]
The authenticity of host 'my.usa.server.com (11.22.33.44)' can't be established.
RSA key fingerprint is xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:b8:1d:61.
Are you sure you want to continue connecting (yes/no)? 
me@nl:~$

[From a server in the US]

me@otherusaserver:~$ ssh [email protected]
The authenticity of host 'my.usa.server.com (11.22.33.44)' can't be established.
RSA key fingerprint is xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:b8:1d:61.
Are you sure you want to continue connecting (yes/no)? 
me@otherusaserver:~$

HOWEVER, when I try to connect from a server in China, the key fingerprint is different:

me@chinaserver:~$ ssh [email protected]
The authenticity of host 'my.usa.server.com (11.22.33.44)' can't be established.
ECDSA key fingerprint is xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:d8:0f:01.
Are you sure you want to continue connecting (yes/no)? 
me@chinaserver:~$

Notice that the key and cipher are different. It should be noted that I OWN the physical China server and the room where it is located, so I can be sure that the server hardware is secure.

Does that mean someone upstream, such as the China government or the ISP (China Telecom) is doing some sort of MITM attack?

Answer 1

See what the servers answer:

RSA key fingerprint is xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:b8:1d:61.

and:

ECDSA key fingerprint is xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:d8:0f:01.

That's not the same key type, therefore not the same key: RSA in the first case, ECDSA in the second case.

SSH servers can use several cryptographic algorithms, and indeed several keys. What algorithm will be used depends on what the client and server support, and also their order of preference. Chances are that your SSH server has both a RSA and an ECDSA key pairs, and the Chinese client happens to be configured to put ECDSA higher in its list of preferences than the other clients.

If unsure, try running the SSH client with the -vvv command-line option to see what the client and server actually send.

Answer 2

The cipher selection was the issue, so I feel a little silly for my China paranoia.

Forcing RSA with

ssh -o [email protected],[email protected],[email protected],[email protected],ssh-rsa,ssh-dss user@host

resulted in the same RSA fingerprint.