Why is MBP 10.12 using an ECDSA key instead of my RSA key?

Question

This question might belong to the Ask Different community but I'll ask here since this is more of a unix question.

I'm using a MBP running OSX 10.12.4. In my terminal window, when I ssh to localhost, it's using a "ECDSA key". I had setup an RSA key from before so I don't know why it's trying to use an ECDSA key. I don't even know what ECDSA is and I didn't knowingly setup a key with this algorithm. If I try to connect to another server, it's using my RSA without problems.

This is the output when I try to ssh to localhost:

$ ssh localhost
The authenticity of host 'localhost (::1)' can't be established.
ECDSA key fingerprint is SHA256:1234567.
Are you sure you want to continue connecting (yes/no)? no
Host key verification failed.

This is the output when I try to ssh to a remote server:

ssh hostname.domainname.com
The authenticity of host 'hostname.domainname.com (10.10.10.10)' can't be established.
RSA key fingerprint is SHA256:abcdefg. 
   (yes, the fingerprint different from ECDSA key above)
Are you sure you want to continue connecting (yes/no)?

I had setup a local single node hadoop cluster that worked before but something happened where I now can't startup the cluster b/c I can't ssh to localhost. I deleted any entries in my known_hosts file that mentioned 127.0.0.1 or localhost but I'm still having trouble. In my .ssh/config file, I don't make any mention to ECDSA.

How do I make my laptop stop using ECDSA when sshing into localhost? How did I end up using ECDSA anyway? Any help is appreciated.

EDIT #2: When I run ssh -v localhost, I see some interesting messages. Hopefully someone can help me decode what this is saying b/c it doesn't make sense to me. My id_rsa file is present but it says it's not:

$ ssh -v localhost
OpenSSH_7.4p1, LibreSSL 2.5.0
debug1: Reading configuration data /Users/first.last/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 53: Applying options for *
debug1: Connecting to localhost [::1] port 22.
debug1: Connection established.
debug1: identity file /Users/first.last/.ssh/id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/first.last/.ssh/id_rsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/first.last/.ssh/id_dsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/first.last/.ssh/id_dsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/first.last/.ssh/id_ecdsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/first.last/.ssh/id_ecdsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/first.last/.ssh/id_ed25519 type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/first.last/.ssh/id_ed25519-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_7.4
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.4
debug1: match: OpenSSH_7.4 pat OpenSSH* compat 0x04000000
debug1: Authenticating to localhost:22 as 'first.last'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: curve25519-sha256
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: [email protected] MAC: <implicit> compression: none
debug1: kex: client->server cipher: [email protected] MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:Zg4yEz5WCZVbQEutpAM5zRw+Tk+2gUGFtSYOSTsVfTU
debug1: Host 'localhost' is known and matches the ECDSA host key.
debug1: Found key in /Users/first.last/.ssh/known_hosts:75
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519,ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521>
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /Users/first.last/.ssh/id_rsa
debug1: Server accepts key: pkalg ssh-rsa blen 279
Authentication failed.
$ 

Contents of my .ssh dir is as follows, so I don't know what the OS is smoking when it says id_rsa is not present, unless the permissions are somehow messing me up:

authorized_keys*  id_rsa            config*
id_rsa.pub*       known_hosts*

Answer 1

I think you're confusing host keys with user keys. When you SSH to a host, the host authenticates itself to you with its host key, and then you authenticate yourself to the host with your user key.

Macs have always generated their host keys themselves. Recent versions of macOS have upgraded from RSA host keys to ECDSA host keys because Elliptic Curve cryptography is considered more secure than RSA. RSA's security rests on the fact that no one has found an easy way to factor the products of large prime numbers. Unfortunately no one has proven that it's irreducibly hard, either. I believe that elliptic curve cryptography is provably hard.

While you're removing references to localhost and 127.0.0.1 from known_hosts, also remove any entries for ::1, which is the IPv6 equivalent of 127.0.0.1.

You don't need to downgrade your Mac's SSH host key from ECDSA to RSA to make SSHing into localhost work. Just type "yes" once when SSHing into localhost and its ECDSA host key will be stored in your known_hosts file.