SSH login via IPv6 successfull while using IPv4 to the same host yields “Permission denied”-Collection of common programming errors

I’m currently stumped by a strange problem. I have a dual stack host to which I want to SSH. If I connect via IPv6 everything works like expected

datenwolf@foo ~/ > ssh -6 bar.example.com
Password:

datenwolf@bar ~/ >

However when doing the same via IPv4 it fails

datenwolf@foo ~/ > ssh -4 bar.example.com
Password:
Permission denied (publickey,keyboard-interactive).

datenwolf@foo ~/ >

Excerpt from /var/log/sshd for the failing login

Apr 24 16:34:03 [sshd] SSH: Server;Ltype: Version;Remote: www.xxx.yyy.zzz-38427;Protocol: 2.0;Client: OpenSSH_5.9p1 Debian-5ubuntu1
Apr 24 16:34:03 [sshd] SSH: Server;Ltype: Kex;Remote: www.xxx.yyy.zzz-38427;Enc: aes128-ctr;MAC: hmac-md5;Comp: none [preauth]
Apr 24 16:34:04 [sshd] SSH: Server;Ltype: Authname;Remote: www.xxx.yyy.zzz-38427;Name: wolfgangd [preauth]
Apr 24 16:34:07 [sshd] pam_access(sshd:account): access denied for user `datenwolf' from `foo.example.com'
Apr 24 16:34:07 [sshd] error: PAM: User account has expired for datenwolf from foo.example.com
Apr 24 16:34:07 [sshd] Connection closed by www.xxx.yyy.zzz [preauth]

Of course the account did not expire and I can perfectly log in via IPv6. Using Google I found various reports on the log messages but none of them matched my problem (in the sense that applying the proposed solutions didn’t work for my case).

I’m pretty much out of ideas here.

Update

/var/log/sshd for successfull IPv6 login on the very same target machine:

Apr 24 16:56:42 [sshd] SSH: Server;Ltype: Version;Remote: 2001:x:x:x:x:x:x:x-46025;Protocol: 2.0;Client: OpenSSH_5.9p1 Debian-5ubuntu1
Apr 24 16:56:42 [sshd] SSH: Server;Ltype: Kex;Remote: 2001:x:x:x:x:x:x:x-46025;Enc: aes128-ctr;MAC: hmac-md5;Comp: none [preauth]
Apr 24 16:56:43 [sshd] SSH: Server;Ltype: Authname;Remote: 2001:x:x:x:x:x:x:x-46025;Name: datenwolf [preauth]
Apr 24 16:56:47 [sshd] Accepted keyboard-interactive/pam for datenwolf from 2001:x:x:x:x:x:x:x port 46025 ssh2
Apr 24 16:56:47 [sshd] pam_unix(sshd:session): session opened for user datenwolf by (uid=0)

I tried logging in from various machines all the same result: IPv6 works, IPv4 doesn’t.

Update 2

For reference this are the used IP tables. Note that these are battle tested, i.e. they are in use for several years now and were not changed recently. Remote login via IPv4 did work with them.

IPv4 iptables:

Chain INPUT (policy ACCEPT 2144 packets, 336K bytes)
 pkts bytes target     prot opt in     out     source               destination         
  132 20762 fail2ban-SSH  tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:22
  12M   14G ACCEPT     all  --  ppp0   *       0.0.0.0/0            0.0.0.0/0            ctstate RELATED,ESTABLISHED
 3111 95984 ACCEPT     icmp --  ppp0   *       0.0.0.0/0            0.0.0.0/0           
18692 1123K ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:22
    2   112 ACCEPT     udp  --  *      *       0.0.0.0/0            0.0.0.0/0            udp dpt:1194
    0     0 ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:1194
 4633  288K ACCEPT     udp  --  *      *       0.0.0.0/0            0.0.0.0/0            udp dpts:6880:6899
 2826  154K ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpts:6880:6899
    4   160 ACCEPT     udp  --  *      *       0.0.0.0/0            0.0.0.0/0            udp dpt:123
    0     0 ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:123
44165 3069K REJECT     all  --  ppp0   *       0.0.0.0/0            0.0.0.0/0            reject-with icmp-port-unreachable

Chain FORWARD (policy ACCEPT 48032 packets, 44M bytes)
 pkts bytes target     prot opt in     out     source               destination         
    0     0 REJECT     udp  --  *      *       0.0.0.0/0            0.0.0.0/0            udp dpt:631 reject-with icmp-port-unreachable
    0     0 REJECT     udp  --  *      *       0.0.0.0/0            0.0.0.0/0            udp dpt:515 reject-with icmp-port-unreachable
    0     0 REJECT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:631 reject-with icmp-port-unreachable
    0     0 REJECT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:515 reject-with icmp-port-unreachable
    0     0 REJECT     all  --  ppp0   ppp0    0.0.0.0/0            0.0.0.0/0            reject-with icmp-port-unreachable
 133K 8347K TCPMSS     tcp  --  *      ppp0    0.0.0.0/0            0.0.0.0/0            tcp flags:0x06/0x02 TCPMSS clamp to PMTU

Chain OUTPUT (policy ACCEPT 14378 packets, 2172K bytes)
 pkts bytes target     prot opt in     out     source               destination         

Chain fail2ban-SSH (1 references)
 pkts bytes target     prot opt in     out     source               destination         
  132 20762 RETURN     all  --  *      *       0.0.0.0/0            0.0.0.0/0 

IPv6 ip6tables

Chain INPUT (policy DROP 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination         
    0     0 DROP       all      *      *       ::/0                 ::/0                 rt type:0 segsleft:0
 484K   86M ACCEPT     icmpv6   *      *       ::/0                 ::/0                
 105K 7943K ACCEPT     tcp      *      *       ::/0                 ::/0                 tcp dpt:22
    0     0 ACCEPT     udp      *      *       ::/0                 ::/0                 udp dpt:1194
    0     0 ACCEPT     tcp      *      *       ::/0                 ::/0                 tcp dpt:1194
    0     0 ACCEPT     udp      *      *       ::/0                 ::/0                 udp dpts:6880:6899
    0     0 ACCEPT     tcp      *      *       ::/0                 ::/0                 tcp dpts:6880:6899
    0     0 ACCEPT     tcp      *      *       ::/0                 ::/0                 tcp dpt:123
    0     0 ACCEPT     udp      *      *       ::/0                 ::/0                 udp dpt:123
    0     0 ACCEPT     all      ppp0,sixxs *       ::/0                 ::/0                 ctstate RELATED,ESTABLISHED
4164K  466M ACCEPT     all      !ppp0,sixxs *       ::/0                 ::/0                
    0     0 REJECT     all      *      *       ::/0                 ::/0                 reject-with icmp6-port-unreachable

Chain FORWARD (policy DROP 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination         
    0     0 DROP       all      *      *       ::/0                 ::/0                 rt type:0 segsleft:0
 2864  311K ACCEPT     icmpv6   *      *       ::/0                 ::/0                
    0     0 REJECT     tcp      *      *       ::/0                 ::/0                 multiport ports 631 reject-with icmp6-port-unreachable
    0     0 REJECT     udp      *      *       ::/0                 ::/0                 multiport ports 631 reject-with icmp6-port-unreachable
    0     0 REJECT     tcp      *      *       ::/0                 ::/0                 multiport ports 515 reject-with icmp6-port-unreachable
    0     0 REJECT     udp      *      *       ::/0                 ::/0                 multiport ports 515 reject-with icmp6-port-unreachable
    0     0 REJECT     all      ppp0,sixxs ppp0,sixxs  ::/0                 ::/0                 reject-with icmp6-port-unreachable
    0     0 accept_with_pmtu_clamp  tcp      ppp0,sixxs *      !2001:x:x::/48   2001:x:x::/48   tcp dpt:22
  18M   14G accept_with_pmtu_clamp  all      *      *       ::/0                 ::/0                 ctstate RELATED,ESTABLISHED
65503 5289K accept_with_pmtu_clamp  all      !ppp0,sixxs *       ::/0                 ::/0                
    0     0 REJECT     all      *      *       ::/0                 ::/0                 reject-with icmp6-port-unreachable

Chain OUTPUT (policy ACCEPT 8099K packets, 11G bytes)
 pkts bytes target     prot opt in     out     source               destination         
    0     0 DROP       all      *      *       ::/0                 ::/0                 rt type:0 segsleft:0

Chain accept_with_pmtu_clamp (3 references)
 pkts bytes target     prot opt in     out     source               destination         
    0     0 TCPMSS     tcp      *      ppp0,sixxs  ::/0                 ::/0                 tcp flags:0x06/0x02 TCPMSS clamp to PMTU
  18M   14G ACCEPT     all      *      *       ::/0                 ::/0 

Update 3

This is /etc/sshd/sshd_config of the system I try connect to, stripped of all comments:

Port 22
ListenAddress 0.0.0.0
ListenAddress ::

PubkeyAuthentication yes
PasswordAuthentication no
UsePAM yes

AllowAgentForwarding yes
AllowTcpForwarding yes
X11Forwarding yes
X11DisplayOffset 10
X11UseLocalhost yes
PrintMotd no
PrintLastLog no
UseDNS yes

Subsystem       sftp    /usr/lib64/misc/sftp-server