Posts

Hashing fast and slow: GPUs and 1Password

The net is atwitter with discussion of Jeremi Gosney’s specially crafted machine with 25 GPUs that can test hundreds of billions of passwords per second using hashcat, a password cracking system. Password crackers, like hashcat, look at the cryptographic hashes of user passwords and repeatedly make guesses to try to find a password that works. 1Password has been designed to resist automated password cracking attempts exactly because we anticipated developments like this.

Don’t get freaked out by the numbers

Windows XPFirst and foremost the reports of 348 billion passwords per second is specifically about passwords stored in the LM format used on Windows XP, exploiting the notorious design flaws and limitations LM hashes. (If you are still running Windows XP; and particularly if you are running NT, 2000 or 2003 domain controllers, please, please upgrade.) The hundreds of billions of  passwords per second reached against those hashes does not mean that passwords stored in other formats can be cracked that quickly.

By the way, this isn’t the only important news about password security to come out this year’s excellent Passwords12 conference. I couldn’t quite make it there this year, but I will talk about other developments from it in coming weeks. Today, all eyes are on GPUs guessing billions of passwords per second.

Slow and Fast Hashing

Typically when a password is “stored” on a system that you log into it is not the password itself, but instead it is a cryptographic hash of the password. I’ve written about some of the ways that password  can be hashed before. HashcatThese can roughly be divided into two categories: slow hashes and fast hashes. Slow hashes are specifically designed to slow down the kinds of attacks we are discussing.

Your 1Password Master Password is processed using the slow hashing system known as PBKDF2. 1Password’s use of PBKDF2 and your use of a good Master Password keep your data resistant from password crackers such as John the Ripper and hashcat if you chose a good Master Password.

Defending against future threats

There are several lessons from this. Gosney’s work does reflect real innovation and a breakthrough, but it isn’t an unexpected breakthrough. People who keep an eye on these things – and we do keep an eye on these things – expected something like this within the next couple of years.

We need to design systems that work against plausible future threats, not just against current threats. This is what we have always tried to do with 1Password.

Lessons and actions

  1. Your 1Password Master Password and your 1Password data remain safe, we designed the Agile Keychain format from the beginning to resist crackers like this. But it is also important for people to select strong, memorable, Master Passwords.
  2. It is more important than ever to have unique passwords for each site and service. As password cracking gets easier, the risks of using the same password on multiple sites increases. This is because if password hashes are stolen from one site, attackers have a better chance of discovering the password from the hash. Once they have that, they can try the same password on other sites.
  3. When using 1Password’s Strong Password Generator, try to create passwords that are at least 20 characters long.

Back to the Future

Gosney slow hash chartI’ve talked (well even boasted, I suppose) about how our earlier design decisions are protecting 1Password users today. But we have to look at what design decisions we make today will do for 1Password users half a decade from now.

Gosney’s machine can also be used against slow hashes, including PBKDF2 passwords. You can read more (and see cool pictures) of the design of Grosney’s hashcatting machine in the conference presentation slides (PDF).

Furthermore PBKDF2 was not designed to specifically impair parallel processing. But because GPUs have unusual and restricted ways of addressing memory, it is possible to design systems that make parallel processing using GPUs slower. This leaves a number of questions that we continue to look at.

  1. Do we need to change anything at all in anticipation of even more powerful machines tuned toward PBKDF2? (We don’t yet Password Based Key Derivation Function diagramhave estimates on how many passwords per second this system could try against a 1Password data file.)
  2. If we do need to change things, when do we need those changes need to be in place?
  3. Should we look at more parallel and GPU resistant alternatives to PBKDF2, such as scrypt?
  4. Should we look at tinkering with options within PBKDF2 to make it more resistant to GPUs working in parallel?

These are not new questions. We are always asking ourselves these and other questions in order to keep your 1Password data secure and protected, both now and in the future.

[Updated 2012-12-06 15:50 UTC. Updated to correctly explain that Gosney's system is not limited to LM hashes. Thanks to Jeremi Grosney, Solar Designer, and others who pointed out my error. I have also taken the opportunity to add more clarifications and links to background throughout.]

Credit card numbers, checksums, and hashes. The story of a robocall scam

Sample Bank of America debit cardAs  Lívia and I were out walking Molly and Patty on Monday evening, I received a telephone call from an unknown number.

I decided to answer the phone anyway, and I was greeted by a recorded voice telling me that my Bank of America debit card beginning with 4217 has been limited and whether I would like to revalidate it.

I don’t have a Bank of America debit card (though I did many years ago), and I know US rules bar most calls that begin with recorded messages, otherwise known as “robocalls.”  I also know that the first few digits of credit card and debit card numbers indicate the card issuer and so are not secret if you know that it is a card issued by a particular bank. It would be easy for a scammer to appear to know my card number. Once I got home, I was able to confirm that 4217 is, indeed, how most Bank of America debit card numbers begin.

Naturally I pressed 1 to “revalidate” my card (not-so-sidenote: you should not try this at home. Indeed, you really should just hang up when you get such calls). I wanted to see how this scam proceeded. At this point I was told a few more details explaining that my card beginning with 4217 needed to be revalidated because of a internal security failure and that I should press 1 to continue. I pressed 1 again.

I was then asked to enter my Bank of America debit card number. Unfortunately, I was not able to construct a number off of the top of my head that would pass their validation check.
While I knew it should begin with 4127 (thanks to the robocall), I did not know at the time that the next two digits should be between 64, 65, or 66 for Bank of America. I did know that the last digit of the sixteen digit number should be calculable from the preceding 15 digits by the Luhn checksum algorithm. But I couldn’t recall the details of the algorithm at the time, and I certainly would not have been able to construct something on the fly quickly enough to enter a “valid” number.

As a consequence, I wasn’t able to get past the “enter your debit card number” step, and so never learned what other information they would ask for, such as my Social Security Number, billing address, or PIN. But it is a safe bet that those would have been requested at some point. Those of course, would have been easier to fabricate as they have no quick validation system.

Checksums

The Luhn checksum is not some super secret security feature, it was a simple system designed to identify errors when exchanging credit card numbers in common use. At best, it can play a minor role in basic security checks to weed out those who just try random numbers.

The system is designed to catch common errors. If one digit of the 15 digits is entered incorrectly the checksum will fail. For example if the correct number is 4217 6601 2345 6784 (here 4 is the checksum) then if the number is given as 4217 6681 2345 6784, where the “0” has been mistyped as an” 8″, the check digit will be 7, and so  4217 6681 2345 6784, with a “4” as the last digit, will not validate.

Some people accidentally type “2435” instead of “2345”, swapping the “3” and the “4”. It happens to the best of us, and it’s another example of the the type of errors the Luhn system can catch.

Not all checksums are cryptographic hashes

1P logo in AESCheck digits of this sort, where the checksum is just one digit long, have properties that make them poorly suited for cryptographic purposes. The most obvious is that they are too small. That is, the check digit can only be one of ten possibilities—0 through 9. Put another way, there is a pretty much a 1 in 10 chance that two numbers will have the same check digit.

When two numbers result in the same checksum, we have a “collision”. If it is feasible to create two numbers that have the same check digit, the system is not collision resistant.

If we also have one number that has a particular checksum then we can easily construct another number that yields the same checksum. So the Luhn algorithm isn’t second-preimage resistant. The difference between collision resistance and second-preimage resistance is subtle. For collision resistance, the problem is “find two numbers whose checksums collide.” For second-preimage resistance, the problem is “here is a number m, now go and find another number that has the same checksum as m.”

It is also the case that if we have a checksum, we can easily construct a number that shares the same checksum. If you give me a checksum of “5”, I can construct a 15 digit number that has 5 as its checksum. That is, it is possible to work backwards from the checksum to an original. Hence, this checksum system is not preimage resistant. Functions that are preimage resistant are sometimes called “one way functions”.

The obvious reason why the Luhn algorithm fails to be preimage resistant, second-preimage resistant, and collision resistant is because it is just one digit. There just isn’t anything you can do when you only have one digit (about 3 bits) with which to work. But there are other reasons as well. I won’t discuss them at all, other than to say that the Luhn algorithm doesn’t have those three properties because it was never designed to.

Resistance is necessary

Cryptographic hash functions, however, are used for more than just checking for accidental errors in data entry or data transmission. This means they do need to be one way functions (preimage resistant); they need to be second-preimage resistant; and they really should be collision resistant.

We’ve discussed how preimage resistance is one of several essential properties of proper treatment of passwords on servers. We’ve also discussed how second-preimage resistance plays a vital role in network security. Over the next few posts I will be talking about how hash functions are used for data integrity checks and specifically for authenticated encryption. Authenticated encryption will play a big role in our next data format.

A fine night for a scam

I am relieved to say that both Patty and Molly did not really mind that I spent the remainder of our walk talking about the nature of the scam; how the criminals’ knowledge of the issuer number on a card can easily fool a target; and, of course, on the difference between checksums and cryptographic hashes. Lívia did not seem quite as complacent as the dogs. “The difference between us, Jeff,” she said, “is that I get really annoyed when something like that happens; but you seem to be really enjoying yourself.”

A few notes about robocalls

Robocalls are a lot like email spam:

  1. The caller ID number is easily counterfeited. You cannot rely on it to trace the source of the call
  2. “Press N to be removed from our list” is a lot like the “unsubscribe” button in email spam. Sure there may the the rare case where it is genuine, but usually it is just used to confirm that the spam/call reaches a real person who, to at least some extent, trusts the message. It’s a great way to get yourself added to more lists

As I write this, the US Federal Trade Commission is hosting a summit on robocalls. There should be more information at that site in coming days and weeks.

Correction October 22, 2012: I incorrectly suggested above that the Luhn algorithm will catch all single transcription errors involving the replacement of one digit with another and all cases where adjacent distinct digits are transposed. I was wrong. The ISBN checksum has these properties, but the Luhn Algorithm used for credit cards does not. The crucial difference revolves around the fact that the ISBN-10 system uses a prime modulus (11), while the Luhn system uses a composite modulus (10). This is also why the check digit for ISBN numbers can sometimes be “X”. The check digit there works out to be a number from 0 through 10, but “X” is used to indicate 10.

I should have spotted this instantly when I looked at the Luhn algorithm, but it required a different path for me to learn of my error. Today is a student holiday in our school district, and so I assigned my daughter the task of proving that the Luhn system will have the properties that I claimed it had. She quickly constructed some counter-examples, where changing an individual digit leads to the same check digit.