On OpenBSD 4.2, ssh-keyscan looks like it tries for SSH1 first, rather than SSH2, which is the default[1] for OpenBSD. However, it appears not to retry the scan with SSH2 if SSH1 fails.
$ ssh-keyscan -v 127.0.0.1 debug1: match: OpenSSH_4.7 pat OpenSSH* debug1: 127.0.0.1 doesn't support ssh1 $ ssh-keyscan -v -t dsa 127.0.0.1 debug1: match: OpenSSH_4.7 pat OpenSSH* # 127.0.0.1 SSH-2.0-OpenSSH_4.7 debug1: Enabling compatibility mode for protocol 2.0 debug1: SSH2_MSG_KEXINIT sent debug1: SSH2_MSG_KEXINIT received debug1: kex: server->client aes128-cbc hmac-md5 none debug1: kex: client->server aes128-cbc hmac-md5 none debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP debug1: SSH2_MSG_KEX_DH_GEX_INIT sent debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY 127.0.0.1 ssh-dss AAAAB3NzaC1kc3MAAACB[snip] $ ssh-keyscan -v -t rsa 127.0.0.1 debug1: match: OpenSSH_4.7 pat OpenSSH* # 127.0.0.1 SSH-2.0-OpenSSH_4.7 debug1: Enabling compatibility mode for protocol 2.0 debug1: SSH2_MSG_KEXINIT sent debug1: SSH2_MSG_KEXINIT received debug1: kex: server->client aes128-cbc hmac-md5 none debug1: kex: client->server aes128-cbc hmac-md5 none debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP debug1: SSH2_MSG_KEX_DH_GEX_INIT sent debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY 127.0.0.1 ssh-rsa AAAAB3NzaC1yc2[snip] It might be time for ssh-keyscan to default to SSH2. Or if SSH1 is the first try, then at least failover to SSH2 if the server does not use SSH1. Regards, -Lars [1] From sshd_config: # Disable legacy (protocol version 1) support in the server for new # installations. In future the default will change to require explicit # activation of protocol 1