The problem is that, if you do proper hash stretching on the server, the server must do a fairly expensive operation before rejecting an incorrect password. This means that brute force password guessing is a denial-of-service attack and the best that you can do is throttle login attempts somehow.
A simple CAPTCHA is a good option for this; asking the solution to simple math problem will confound most bot herders and allow to prioritize actual users' requests ahead of a bot horde. This has to be site-wide, not per-user, however and is probably best accompanied by an explanation that the server is under high load due to password-guessing attacks and solving the CAPTCHA will get your request priority. Tarpit requests that lack a CAPTCHA solution until they timeout, if you can.
A large botnet can produce a very diffuse attack, somewhat reducing the effectiveness of filtering by IP address, and storing IP addresses raises privacy concerns, but if your users' accounts are linked to real-world identities anyway (for example, you are running a paid service) the privacy concerns are less severe and you may want to store commonly-used IP addresses per-user and give priority to logins originating from IP addresses or IP address blocks that a user has previously used. Associating processing priority with how many logins have been seen from the same IP address could result in login attempts from password-guessing bots being demoted to "idle" priority and taking perhaps minutes while actual users see quick logins in less than a second.
Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
Want more info? How to link or
or How to display code and escape characters
are good places to start.