no matching host key found

[Kyle Huggins]

I am unable to set up a ssh key between my machine and bitbucket. I think it has something to do with how the key is being generated and the cipher used, but it is unclear to me how to fix it.

the command to generate the key is:

ssh-keygen -t rsa

I place it in bitbucket and it accepts the key no problem, but when I test it out:

`Unable to negotiate with 18.205.93.2 port 22: no matching host key type found. Their offer: ssh-dss,ssh-rsa`

I've clearly specified rsa. I think it should be defaulting to rsa2. My ssh version is:

OpenSSH_7.4p1, OpenSSL 1.0.2k-fips 26 Jan 2017.

when I just do an `ssh -vvv git@bitbucket.org` I get this:

OpenSSH_7.4p1, OpenSSL 1.0.2k-fips 26 Jan 2017
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 58: Applying options for *
debug2: resolving "bitbucket.org" port 22
debug2: ssh_connect_direct: needpriv 0
debug1: Connecting to bitbucket.org [18.205.93.2] port 22.
debug1: Connection established.
debug1: identity file /home/kyleh/.ssh/id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /home/kyleh/.ssh/id_rsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/kyleh/.ssh/id_dsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/kyleh/.ssh/id_dsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/kyleh/.ssh/id_ecdsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/kyleh/.ssh/id_ecdsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/kyleh/.ssh/id_ed25519 type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/kyleh/.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 conker_1.1.31-8625750 app-131
debug1: no match: conker_1.1.31-8625750 app-131
debug2: fd 3 setting O_NONBLOCK
debug1: Authenticating to bitbucket.org:22 as 'git'
debug3: send packet: type 20
debug1: SSH2_MSG_KEXINIT sent
debug3: receive packet: type 20
debug1: SSH2_MSG_KEXINIT received
debug2: local client KEXINIT proposal
debug2: KEX algorithms: curve25519-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha256,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1,ext-info-c
debug2: host key algorithms: ssh-ed25519
debug2: ciphers ctos: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,aes192-cbc,aes256-cbc
debug2: ciphers stoc: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,aes192-cbc,aes256-cbc
debug2: MACs ctos: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: MACs stoc: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: compression ctos: none,zlib@openssh.com,zlib
debug2: compression stoc: none,zlib@openssh.com,zlib
debug2: languages ctos: 
debug2: languages stoc: 
debug2: first_kex_follows 0 
debug2: reserved 0 
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: host key algorithms: ssh-dss,ssh-rsa
debug2: ciphers ctos: aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,chacha20-poly1305@openssh.com,arcfour256,arcfour128
debug2: ciphers stoc: aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,chacha20-poly1305@openssh.com,arcfour256,arcfour128
debug2: MACs ctos: hmac-sha2-256-etm@openssh.com,hmac-sha2-256,hmac-sha1,hmac-sha1-96
debug2: MACs stoc: hmac-sha2-256-etm@openssh.com,hmac-sha2-256,hmac-sha1,hmac-sha1-96
debug2: compression ctos: none
debug2: compression stoc: none
debug2: languages ctos: 
debug2: languages stoc: 
debug2: first_kex_follows 0 
debug2: reserved 0 
debug1: kex: algorithm: curve25519-sha256@libssh.org
debug1: kex: host key algorithm: (no match)
Unable to negotiate with 18.205.93.2 port 22: no matching host key type found. Their offer: ssh-dss,ssh-rsa

I'm not quite certain why there is a disconnect, and some clarification would be helpful.

Cheers

[Ana Retamal · Accepted solution]

Hi Kyle,

Are you still experiencing this issue? If so, please double check that the SSH key was correctly saved in Bitbucket and is stored in the right location on your computer, as there are a lot of:

key_load_public: No such file or directory

If that's fine, try running the following command to see if the key s loaded into your agent:

ssh-add -L

If you're not seeing any identities, run the following command to add your private key:

ssh-add ~/.ssh/id_rsa

Once you've done the steps, try running this other command to see if Bitbucket is able to authenticate you:

ssh -Tv git@bitbucket.org

If the situation is not improving, let us know so we can continue helping you.

Best regards!
Ana

[Kyle Huggins]

So none of those things fixed it, however I did revisit the problem with a fresh set of eyes and discovered this line in my /etc/ssh/ssh_config:

Host *
HostKeyAlgorithms ssh-ed25519

Turns out that was the offending line. So to future folks, check your root config for ssh to make sure it isn't shooting you in the foot.

Cheers.

[rolfmobile99]

That's a good catch (in the /etc/ssh/ssh_config file).

This problem seems to be snagging people with the new-ish version of OpenSSH (like OpenSSH_7.4), where apparently the defaults for the host algorithm changed.

You can also use a leading "+" to add this algorithm to the list:

HostKeyAlgorithms +ssh-ed25519

Cheers,

-Rolf 

[Deleted user]

Update: Bitbucket has a support article https://confluence.atlassian.com/bitbucketserverkb/ssh-rsa-key-rejected-with-message-no-mutual-signature-algorithm-1026057701.html

I've just had this problem on my Macbook. I believe it's because OpenSSH has recently updated (I've installed it with Homebrew) and it no longer accepts RSA keys.

https://security.stackexchange.com/questions/226131/openssh-declares-ssh-rsa-deprecated-what-do-i-do-next

I had to update my ssh config to allow ssh-rsa, and to use an ed25519 key.

~/.ssh/config

Host bitbucket.org
  IdentityFile ~/.ssh/id_ed25519
  HostKeyAlgorithms +ssh-rsa

RSA is unsafe. Why doesn't Bitbucket have a safe ssh host key?

[marcusball]

I started getting the same issue today, but that SSH config change doesn't seem to be working for me. Hoping someone can find another solution.

[marcusball]

Ah, I think I found a solution. I used your SSH config change, and created a new SSH key based on this article.

Basically, creating a new key using ED25519 (`ssh-keygen -t ed25519`) and adding ssh-rsa to the HostKeyAlgorithms:

Host bitbucket.org
    User git
    IdentityFile ~/.ssh/id_ed25519
    HostKeyAlgorithms +ssh-rsa

[Deleted user]

Thanks @marcusball , I've updated my answer.

[migmolrod]

Thanks so much, @marcusball . That fixed it for me as well, using an ED25519 key here too.

[Neville Stokes]

From https://www.openssh.com/releasenotes.html:

Incompatibility is more likely when connecting to older SSH
implementations that have not been upgraded or have not closely tracked
improvements in the SSH protocol.

Does this mean that Bitbucket Cloud's ssh config needs some attention, pronto?

[nelson.cunha]

It worked. But I find this unsettling.

So, we're using an ed25519 key with a +ssh-rsa algorithm. Is that normal?

[Neville Stokes]

That's not quite right.

As I understand it, the ssh-rsa algorithm is being used to verify the Bitbucket servers in the known_hosts file, rather than being used with the new ed25519 keys to authenticate ourselves.

Still, less than ideal.

[Juraj]

Windows users that can't find the "config" file in the .ssh folder, see the workaround in the bug here:
https://jira.atlassian.com/browse/BCLOUD-21402

[Serge]

I don't know why bitbucket.org still hasn't updated their servers to use ed25519, it's been around for more than 7 years and has far better security.

Also I would say you shouldn't use ssh-add, it clutters up the ssh client but instead define your configuration in the ssh config file.

The following config will try to use ed25519 first and has a fallback to rsa for the bitbucket host only while the other two hosts ( github and gitlab ) will only use ed25519 because it is defined in the global.

Hopefully bitbucket.org decides to support ed25519 soon and you would be able to just delete the HostKeyAlgorithms and PubkeyAcceptedAlgorithms under Host bitbucket.

nano ~/.ssh/config

# SSH Host Configs
Host bitbucket *bitbucket.org
    User git
    Hostname bitbucket.org
    IdentityFile ~/.ssh/bitbucket
    HostKeyAlgorithms ssh-ed25519,ssh-rsa
    PubkeyAcceptedAlgorithms ssh-ed25519,ssh-rsa


Host github *github.com
    User git
    HostName github.com
    IdentityFile ~/.ssh/github


Host gitlab *gitlab.com
    User git
    Hostname gitlab.com
    IdentityFile ~/.ssh/gitlab


# Global SSH Configs
# Must be located at the end of file
# or it overwrites Host Configs

AddKeysToAgent no
ServerAliveInterval 15
ServerAliveCountMax 40

IdentitiesOnly yes
HostKeyAlgorithms ssh-ed25519
PubkeyAcceptedAlgorithms ssh-ed25519
PreferredAuthentications publickey

To generate the bitbucket ed25519 keys:

ssh-keygen -t ed25519 -N "" -f ~/.ssh/bitbucket

chmod 400 ~/.ssh/bitbucket ~/.ssh/bitbucket.pub

Example use:

git clone bitbucket:{account}/{repo}.git

which is the same as using

git clone git@bitbucket.org:{account}/{repo}.git