Passwords at Internet sites are rarely stored securely. Even if "hashed with a salt," an attacker can crack most hashing schemes using brute force compute power. Although SSL and X509 certificates protects passwords in transit to a secure web site, it doesn't protect against disclosure of passwords to malicious employees at that site, or hackers that broke into that site, an all to common occurrence.
It is therefore important that you use hard-to-guess passwords, and a different one for each site. But remembering all these passwords is virtually impossible, while writing them on a piece of paper or storing them in an unencrypted file is a bad idea. If you lose the paper or file you no longer have your passwords. If the paper or file gets stolen somebody now has your passwords.
KeyCutter fixes this problem. It uses no storage, yet is able to maintain a different, very-hard-to-guess password for each web site. The KeyCutter app can be installed on your phone or accessed through a web page.
The way it works is simple in concept: the user gives KeyCutter three pieces of information about him- or herself: a user name, a security question and answer, and a personal password or passphrase. It is important that this information is presented in the identical way everytime KeyCutter is used, down to the right capitalization. The user also provides the name or web address of the site.
KeyCutter then runs a so-called cryptographic hash function to generate a password for the site. Each time you present the same input, KeyCutter will regenerate the same output. But given the output it is virtually impossible to figure out what the input was. The more complicated your personal password or passphrase, the harder it is. Since it is the only password you will need to remember, you do not want to hold back. You can also use KeyCutter to generate different PIN codes for your various credit cards, say.
None of the input to KeyCutter is ever sent anywhere by KeyCutter. The user name and security question and answer are stored (locally) so they do not have to be re-entered each time. (Hitting Reset twice clears this storage.) KeyCutter uses this information to ensure that different users generate different output passwords even if they coincidentally use the same input password.
The input password is automatically removed from memory each time a password or PIN is generated, in order to prevent theft. The output password and destination are only displayed temporarily before being removed as well.
KeyCutter is designed and written by Robbert van Renesse at Cornell University. He first designed and implemented KeyCutter in December 1999 and deployed it on the web the next month. KeyCutter is based on so-called Cryptographic Hash Functions. Such a function y=H(x) has the property that given x it is easy to compute y, but given y it is hard to find a corresponding x. In other words, H is hard to invert. For KeyCutter, x is the concatenation of the four input fields. The destination input fields is trimmed down a bit, removing stuff like http:// and .com, and making everything lower case first.
For H, we essentially chain two cryptographic functions, HMAC-SHA256 and Bcrypt. Bcrypt takes two inputs, a 128-bit salt and a string of bytes. First we run HMAC-SHA256 on the concatenated user name, security answer, and destination, using password as the key. We use 128 bits of the 256-bit output to use as salt for Bcrypt, and remaining 128 bits are used for the other input to Bcrypt. Bcrypt generates 192 bits of output.
Using the Bcrypt output we generate a password consisting of 2 upper case characters, 2 lower case characters, 2 digits, 2 special characters, and 2 more of any kind, for a total of 10 characters. We selected 16 special characters, 8 digits (the zero and one digits are not used because they look too much like O and l), and 20 upper and lower case characters each (removing the most frequently used English characters to avoid generating dictionary words accidentally). The characters are otherwise selected pseudo-randomly based on the Bcrypt output, for a total of 38963943309312000000 different passwords (about 2^65, so using about 65 bits of the Bcrypt output).
HMAC-SHA256 is very fast and has negligible overhead compare to Bcrypt. Bcrypt takes an additional input: a work factor. The larger the work factor, the more compute-intensive Bcrypt is, and the harder it is to do a brute-force attack. KeyCutter has to run on a variety of devices, so we had to choose a relatively small number and picked 10. It takes an Intel i3-2120 (Quad Core, 3.30GHz) about 0.071 seconds to do such a computation. Given that CPU cores are not getting any faster any more, that number should hold pretty stable.
But hackers have more and more cores at their disposal. If you had a million such cores (Los Alamos National Labs is expected to have that many in about 10 years at the time of writing, November 2012), you could try about 1.4 million inputs per second. Trying 2^65 different inputs would take you about 88,000 years, or 44,000 years on average to find an input that matches a particular output.
Of course, a hacker may be smarter than trying such a simple brute force attack. It is up to you that your input fields, and particularly the input password, contains enough "entropy" so it is hard for an attacker to guess anything about the input. Remember, the destination field is known to the attacker, and the user name and birthday may be easy to guess.
So you should pick a hard input password. If you use a selection of upper case characters, lower case characters, digits, and special characters, you get about 6 bits of entropy per character, so your password should be preferably at least 11 characters long if you want the full strength of KeyCutter. Every character buys you a factor of about 64 in difficulty. If you used only 8 characters, the attacker can work 64*64*64 times faster and would need only 2 months to crack your password.
PwdHash is a Stanford project that had the same idea in 2005 (five years after KeyCutter launched on my web site). They have a very nice integration into some web browsers. It is not clear from the publication what hash function they use, but the output is immediate and is thus easy to crack with a tool like HashCracker unless you use an enormously long and random password. HashCracker is of no use against KeyCutter at this time. (There's a challenge!)
Another problem is that PwdHash creates the same passwords for users that use the same input password, and this makes it easy for an attacker to try a generated password against a large number of user accounts at a site. This is why KeyCutter asks for a user name and a security question.