New SSH key pairs can not be resolved

Question

I have removed the complete know_hosts and config as well as public keys and private keys under the folder ~/.ssh/. I also removed all public keys in github. Then I generated a new ed25519 key pair. Wenn I added the new generated ed25519 public key to github, and try to connect to the github.

The authenticity of host can't be established.
ECDSA key fingerprint is SHA256:h41sMp7TPyRt9NnlOcuOt41O+rAgV1FsJzc/+Iy1yyY.
Are you sure you want to continue connecting (yes/no/[fingerprint])?
Host key verification failed

I noticed the SHA256 fingerprint of my generated key is inconsistent with ECDSA key fingerprint. I assume that the ECDSA key fingerprint is the one I used previously. However, the complete ssh folder contains only ed25519 key pairs. What could be the problem?

Answer 1

This is actually not a problem as such: since you deleted your known_hosts file, SSH client's memory of previous connections to Github is gone, and now it behaves as if you're connecting to Github for the first time. So it cannot automatically use Github's host key saved in known_hosts to verify the supposed "Github" is the same server as before, and not an imposter. This fingerprint is of the remote host's SSH host key which is not affected by anything you did locally.

Now, to verify that you are connecting to a real Github and not to a fake one, you would have to verify the fingerprint yourself and answer yes to the question, or just copy&paste the fingerprint you got from another source (like this webpage of GitHub.com).

After the fingerprint is successfully verified (or you just answer yes to choose to trust it), the actual remote host's public key will be saved to your known_hosts file, and on next connections the verification will happen automatically again.

However, I note that the fingerprint you are seeing does not actually match GitHub.com's SSH public host key fingerprints. Either you are connecting to your own private GitHub instance, or there is a man-in-the-middle between you and the real GitHub.com.

The authentication with your ed25519 key pair has not even started yet: first the remote host key is checked to see if the remote host is already known (and if so, it's used to verify the remote host's identity) and only after that is successfully done (or the user has explicitly chosen to trust the remote host), SSH will start the process of authenticating you to the remote host.