Openssh fails with 'key_verify failed for server_host_key'

[elvisdieguez]

I really need a solution to this problem and would appreciate any help. Here is the output of ssh (I've removed IPs and URLs):

ssh -l XXXX xxx.xxx.xxx -v
OpenSSH_3.6.1p2, SSH protocols 1.5/2.0, OpenSSL 0x009060af
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Rhosts Authentication disabled, originating port will not be trusted.
debug1: Connecting to xxx.xxx.xxx [xxx.xxx.xxx.xxx] port 22.
debug1: Connection established.
debug1: identity file /home/edieguez/.ssh/identity type -1
debug1: identity file /home/edieguez/.ssh/id_rsa type 1
debug1: identity file /home/edieguez/.ssh/id_dsa type 2
debug1: Remote protocol version 2.0, remote software version OpenSSH_3.5p1
debug1: match: OpenSSH_3.5p1 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_3.6.1p2
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 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
debug1: Host 'xxx.xxx.xxx' is known and matches the RSA host key.
debug1: Found key in /home/edieguez/.ssh/known_hosts:1
RSA_public_decrypt failed: error:0407006A:rsa routines:RSA_padding_check_PKCS1_type_1:block type is not 01
debug1: ssh_rsa_verify: signature incorrect
key_verify failed for server_host_key
debug1: Calling cleanup 0x8062570(0x0)


Now I've tried some of the fixes posted in other threads about this problem but none have worked. I am using OpenSSL-0.9.6j and I've tried recompiling with -O2 optimization, removing the known_hosts file and connecting with protocol 1 (this fails as the remote server only accepts protocol 2). Help!!

[jimlynch11]

try to just remove the .ssh directory from your home directory, and then logging in again...iv had similar problems in the past and this has effectively wiped everything out and started over from scratch

[elvisdieguez]

I've tried this but it doesn't fix the problem either. Thanks for replying though.