ssh refusing connection with message "no hostkey alg"

My SSH connections worked well, but from last week SSH from my laptop to my board refusing connection. I can make a SSH connection from the board to laptop, but not vice-versa. I tried that with my user and root user and had same issue.

My Laptop is an Ubuntu 12.10 and my board is a Debian 6.

Here is the verbose output of SSH:

danialbehzadi@danial-HP:~$ ssh -v 192.168.1.2
OpenSSH_5.2p1, OpenSSL 1.0.1c 10 May 2012
debug1: Reading configuration data /usr/local/etc/ssh_config
debug1: Connecting to 192.168.1.2 [192.168.1.2] port 22.
debug1: Connection established.
debug1: identity file /home/danialbehzadi/.ssh/identity type -1
debug1: identity file /home/danialbehzadi/.ssh/id_rsa type 1
debug1: identity file /home/danialbehzadi/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.0p1 Debian-4
debug1: match: OpenSSH_6.0p1 Debian-4 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.2
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
no hostkey alg

2 Answers

I made new rsa and dsa keys on the board and it went OK:

~# ssh-keygen -t rsa -f /etc/ssh/ssh_host_rsa_key
~# ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key

[root@server ~]# ls -la /etc/ssh/ssh_host_*

-rw-------. 1 root root 668 Jun 25 00:03 /etc/ssh/ssh_host_dsa_key
-rw-r--r--. 1 root root 609 Jun 25 00:03 /etc/ssh/ssh_host_dsa_key.pub
-rw-r-----. 1 root ssh_keys 227 Dec 14 2018 /etc/ssh/ssh_host_ecdsa_key
-rw-r--r--. 1 root root 162 Dec 14 2018 /etc/ssh/ssh_host_ecdsa_key.pub
-rw-r-----. 1 root ssh_keys 387 Dec 14 2018 /etc/ssh/ssh_host_ed25519_key
-rw-r--r--. 1 root root 82 Dec 14 2018 /etc/ssh/ssh_host_ed25519_key.pub
-rw-------. 1 root root 963 Apr 18 2011 /etc/ssh/ssh_host_key
-rw-r--r--. 1 root root 627 Apr 18 2011 /etc/ssh/ssh_host_key.pub
-rw-------. 1 root root 1679 Jun 25 00:02 /etc/ssh/ssh_host_rsa_key
-rw-r--r--. 1 root root 401 Jun 25 00:02 /etc/ssh/ssh_host_rsa_key.pub

make sure file ssh_host_* mode is 644 and 600 like this