I have client connecting to server over the internet (WCF).
To calculate the hash to save in the DB I currently use:
var hash = BCrypt.HashPassword(password, 13);
To verify it I do:
var isApproved = BCrypt.Verify(passwordFromUser, hashFromDatabase);
Generation of the hash must be calculation-intensive, true. But the verification too must be intensive ?
There is no secure but quicker way to verify the user (it's being done on the server) ?
Yes, verification must be intensive. Indeed, it's much more important that the verification is intensive than the original generation. (It's hard to see how you'd have cheap generation and costly verification, but that would be okay.)
The point is that if it's cheap to verify a password, then an attacker can check lots of passwords quickly. If you make verifying each guess costly, however, it becomes much less feasible to apply brute force to cracking a password.
Even though the verification is relatively expensive, it's still unlikely to be a very significant cost in the operation of a normal application, unless you're under attack (at which point you don't want to be verifying things quickly). If you're getting enough legitimate login attempts to cause your server to break into any kind of sweat, that suggests you've got enough users that you can probably afford to scale out somewhat...
The verification must be computationally intensive, so when the passwords database is stolen it's expensive to recover the passwords by quickly checking lots of them, as explained by Jon Skeet.
However, in normal operation when a client connects to your server over the Internet, you can prevent an attacker from checking lots of passwords simply by rate-limiting the authentication attempts from the client. In this case, it's a bit undesirable that the server needs to perform the expensive verification since the server is the 'good guy'.
Have a look at the Salted Challenge Response Authentication Mechanism (SCRAM), which provides a mechanism where the verification is split between the client and the server, and the client lifts the heavy part.
