I just set up fail2ban on a Debian 6.0.9 and had some trouble getting it to work.
After some google research I found out that debian logs with a different time stamp to the auth.log than expected by fail2ban.
Strangely I found this problem a couple of times on google but no solution for it.
I fixed it quick and dirty by just substituting the timestamp with a wildcard in the “/etc/fail2ban/filter.d/sshd.conf”:
... failregex = ^%(__prefix_line)s(?:error: PAM: )?Authentication failure for .* from \s*$ ^%(__prefix_line)s(?:error: PAM: )?User not known to the underlying authentication module for .* from \s*$ ^%(__prefix_line)sFailed (?:password|publickey) for .* from (?: port \d*)?(?: ssh\d*)?$ ^%(__prefix_line)sROOT LOGIN REFUSED.* FROM \s*$ ^%(__prefix_line)s[iI](?:llegal|nvalid) user .* from \s*$ ^%(__prefix_line)sUser .+ from not allowed because not listed in AllowUsers$ .*authentication failure; logname=\S* uid=\S* euid=\S* tty=\S* ruser=\S* rhost=(?:\s+user=.*)?\s*$ ^%(__prefix_line)srefused connect from \S+ \(\)\s*$ ^%(__prefix_line)sAddress .* POSSIBLE BREAK-IN ATTEMPT!*\s*$ ^%(__prefix_line)sUser .+ from not allowed because none of user's groups are listed in AllowGroups\s*$ ...
with this modified line (4th from the bottom) fail2ban is now working fine for me!
If you are running ssh on a non-standard port like I am make sure to edit the [ssh] section of the “/etc/fail2ban/jail.local” config file:
... [ssh] enabled = true port = all banaction = iptables-allports filter = sshd logpath = /var/log/auth.log maxretry = 6 ...