Without password ssh does not work

Question

I tried to configure without ssh b / w A with a password on B and B on A Generated public and private key using ssh-keygen -trsa on both machines. Used the ssh-copy-id utility to copy public keys from A to B , as well as from B to A

Without a password, ssh works from A to B , but not from B to A I checked the permissions of the ~ / ssh / folder and it seemed to be normal.

A .ssh folder permissions:

 -rw------- 1 root root 13530 2011-07-26 23:00 known_hosts -rw------- 1 root root 403 2011-07-27 00:35 id_rsa.pub -rw------- 1 root root 1675 2011-07-27 00:35 id_rsa -rw------- 1 root root 799 2011-07-27 00:37 authorized_keys drwxrwx--- 70 root root 4096 2011-07-27 00:37 .. drwx------ 2 root root 4096 2011-07-27 00:38 . 

B .ssh folder permissions:

 -rw------- 1 root root 884 2011-07-07 13:15 known_hosts -rw-r--r-- 1 root root 396 2011-07-27 00:15 id_rsa.pub -rw------- 1 root root 1675 2011-07-27 00:15 id_rsa -rw------- 1 root root 2545 2011-07-27 00:36 authorized_keys drwxr-xr-x 8 root root 4096 2011-07-06 19:44 .. drwx------ 2 root root 4096 2011-07-27 00:15 . 

A is ubuntu 10.04 (OpenSSH_5.3p1 Debian-3ubuntu4, OpenSSL 0.9.8k March 25, 2009) B is a debian machine (OpenSSH_5.1p1 Debian-5, OpenSSL 0.9.8g October 19, 2007)

From A :

 #ssh B 

works great.

From B :

 #ssh -vvv A ... ... debug1: SSH2_MSG_SERVICE_ACCEPT received debug2: key: /root/.ssh/identity ((nil)) debug2: key: /root/.ssh/id_rsa (0x7f1581f23a50) debug2: key: /root/.ssh/id_dsa ((nil)) debug3: Wrote 64 bytes for a total of 1127 debug1: Authentications that can continue: publickey,password debug3: start over, passed a different list publickey,password debug3: preferred gssapi-keyex,gssapi-with-mic,gssapi,publickey,keyboard-interactive,password debug3: authmethod_lookup publickey debug3: remaining preferred: keyboard-interactive,password debug3: authmethod_is_enabled publickey debug1: Next authentication method: publickey debug1: Trying private key: /root/.ssh/identity debug3: no such identity: /root/.ssh/identity debug1: Offering public key: /root/.ssh/id_rsa debug3: send_pubkey_test debug2: we sent a publickey packet, wait for reply debug3: Wrote 368 bytes for a total of 1495 debug1: Authentications that can continue: publickey,password debug1: Trying private key: /root/.ssh/id_dsa debug3: no such identity: /root/.ssh/id_dsa debug2: we did not send a packet, disable method debug3: authmethod_lookup password debug3: remaining preferred: ,password debug3: authmethod_is_enabled password debug1: Next authentication method: password root@192.168.122.1 password: 

Which essentially means that it is not authenticated using the file /root/id_rsa . I ran the ssh-add command on both machines.

I'm running out of ideas. Any help would be appreciated.