Password Arithmetic

Here's a tool that claims to be able to break Notes ID passwords. Now before you start thinking that this tool breaks the encryption of the Notes ID file, and therefore the whole basis of Notes and Domino's PKI-based security is blown away, please take a close look at what they claim. They do not in any way, shape, or form break encryption. The foundations of Notes and Domino are as secure as ever.

What they do is use brute-force attacks to guess the password. No level of encryption will ever prevent this type of attack from being able to succeed. This is why password quality is so important.

Let me justify this claim a bit. Imagine that I'm a military commander, and I have the best encryption system in the world. My keys are 4096 bits long, the world's best cryptologists have ascertained that the algorithms are sound, and their calculations have established that the fastest computers in the world will take 42 million years to do an exhaustive search of encryption keys to decrypt a single message. The problem, however, is that I have just a two word vocabulary. Every single one of my messages either says "Attack", or "Retreat". And what makes this a huge problem is that my enemy knows this. Now, if I send just one message, it may indeed take my enemy 42 million years to decrypt it; but what if I send two messages? On the assumption that my enemy will observe my army's behavior after I send the first message, it should take him no time at all to decrypt my second message because it will either be exactly the same as my first message, or it will be different -- and those two possibilities exhaust my vocabulary.

Back to passwords. If there's a way to test a password -- and of course there is -- then there's a way to test lots of passwords. If there's a limited vocabulary of passwords, then you can test them all. It simply takes time. The product linked above claims to be able to test 1,000,000 passwords per minute. At that rate, it can go through a very large dictionary and then systematically try likely nonsense passwords until it succeeds, and if your password is weak it will succed very quickly. Take a look at the following table:

Password Type	N. Combinations	Avg. Time To Guess
6 character lower case letters or digits	36^6 = 2176782336	18.1 hours
6 character mixed case letters or digits	62^6 = 56800235584	19.72 days
8 character lower case letters or digits	36^8 = 2821109907456	2.6 years
8 character mixed case letters or digits	62^8 = 218340105584896	2.07 centuries
2 English words with a digit in between	10*(5000^2) = 250000000	2.08 hours
3 English words with digits in between	100*(5000^3) = 12500000000000	11.9 years

As you can see, password quality matters a lot. If someone knows that users are required to have six character passwords, and he knows that most people use all lower case letters and occasional digits in their passwords, then at the rate of 1,000,000 attempts per hour the attacker can expect to succeed against any given user password in just a bit over 18 hours. Even worse, if your standard recommendation to users is to pick two English words and separate them by a digit -- which I hate to admit is exactly what I used to recommend -- then an attacker who is aware of that recommendation will probably succeed in just over two hours. That assumes a 5,000 word English vocabulary, which is far less than the actual number of words in the English language, but it may in fact be pretty generous as far as the selection of words that real users will probably pick from!

Given the speed with which an attacker might be able to make a brute force attack against weak passwords, it is prudent to recommend -- to require, actually -- password standards that will stand up to attack. Eight character passwords consisting of a mixture of upper and lower case letters and digits are plenty strong. So are three word passwords, with the words separated by digits. The latter is a bit much to type, and not all that much easier to remember than an eight character mixed case alphanumeric.

Bear in mind, while I started by discussing a tool that guesses Notes ID passwords, this really applies to any type of password. Take a look at all the links on the right hand side of that product's page, and you can see that the company offers products for lots of different types of password.

Addendum: More about passwords here.

Addendum 2: I've seen claims of 10 million passwords per minute for some tools, and a billion passwords a minute for zip file passwords, but no such claims for anything related to cracking Notes ID passwords. While dividing the times given above by ten may be prudent, I don't think that dividing them by 1000 is realistic. Even so, extending the above table out to cover the case four words separated by three random digits shows that it would still be plenty strong: requiring an average time of 595 years to crack even at the rate of a billion tries per second.