fail2ban and denyhosts constantly ban me on Ubuntu

I believe I've seen someone say that some of those apps will count failed key logins as a brute force attempt. Do you have an ssh-agent running with keys in it? Connecting with that set will offer every key in turn before falling back to password, so that might be why. Try setting sshd's log level higher, and check fail2ban/denyhost logs.

Edit: here is the original source that tipped me off, with a way to fix it.

please review the following links:

• http://denyhosts.sourceforge.net/faq.html#3_9
• http://denyhosts.sourceforge.net/faq.html#3_19
• http://denyhosts.sourceforge.net/faq.html#allowed

if you wanted to scrap the whole fail2ban, and denyhosts idea, do as Nathan Powell below says, change from port 22 to something more obscure

also a few more ideas:

1. iptables: the following example will drop incoming connections which make more than 2 connection attempts upon port 22 within ten minutes:

   iptables -I INPUT -p tcp --dport 22 -i eth0 -m state --state NEW 
            -m recent --set
   
   iptables -I INPUT -p tcp --dport 22 -i eth0 -m state --state NEW
            -m recent --update --seconds 60 --hitcount 4 -j DROP
   

2. key-based login

3. port knocker (knockd)