Password Expiration

One common bit of advice with respect to security is to require frequent password changes.  This "best practice" has persisted for decades despite some prominent criticism.  But, is password expiration actually helpful or not?

Are there benefits?

Password expiration has a negligible effect on limiting or preventing malicious behavior.  The ability to steal passwords often implies privileged access to your systems or network.  If the attacker has administrator rights, access to the password database or the ability to sniff traffic on your network, he can install a backdoor or continuously steal passwords in order to avoid the expiration window.  That’s assuming he even needs continued access to accomplish his goal.  If the attacker only needs short-term access, which is often the case, password expiration is irrelevant.

A note on password math

The number of possible passwords with a character set of size C and a password length x is C^x.  For instance, with mixed case alphanumeric passwords we have a character set that has 62 possible characters: 26 lower case letters, 26 upper case letters and 10 numbers (26 + 26 + 10 = 62).  If a password is 8 characters long, there are 62⁸ = 62 ∙ 62 ∙ 62 ∙ 62 ∙ 62 ∙ 62 ∙ 62 ∙ 62 possible combinations.

If there are P possible passwords and we can guess G passwords per second, then it will take us P ÷ G seconds to guess all possible passwords.  Since there are 86,400 seconds in a day, the number of days that it will take us is P ÷ (G ∙ 86,400) and the number of years is P ÷ (G ∙ 86,400 ∙ 365).

The number of guesses that an attacker can make per second depends mostly on the password hashing algorithm.  For a fast algorithm like MD5, a reasonable cracking speed is several billion guesses per second.  For bcrypt or scrypt, a reasonable speed might be from a few hundred to a few thousand guesses per second. 

Example:

Number of possible 8 character mixed-case alphanumeric passwords = 62⁸ = 218,340,105,584,896

Seconds to guess all possible passwords (1 billion per second) = 62⁸ ÷ 1,000,000,000 = 218,340 seconds.

Days to guess all possible passwords = 218,340 ÷  86400 = 2.523 days.

Years to guess all possible = 2.523 ÷ 365 = .007 years

Salted vs Unsalted

A lot of people seem to think that it's okay to use something like salted SHA-1, without any key stretching, as a password hash.  The following graphic shows how many guesses an attacker would be able to make per user on a daily or monthly basis assuming that he can make either one thousand or one billion guesses per second.  One thousand guesses per second indicates a password hash such as bcrypt or PBKDF2 that includes stretching to slow down the hash.  One billion guesses per second is a reasonable estimate for a single iteration of MD5 or SHA-1 (depending on your hardware) .

Click for full-size

It should be obvious that salting is not enough.  Even with a site that has 10 million users, an attacker can make millions of guesses per user per day against salted SHA-1* or MD5. A strong password hash literally makes password cracking a million times harder.  If an attacker can only guess a handful of passwords per day, per user, then any user with a password that isn't his name, username, or on one of the worst passwords lists is probably going to be okay.  There is some safety in numbers.

If an attacker targets a single account, he can still make millions of guesses per day, even with a strong password hash.  There is no safety in numbers once the attacker is focused on you.  Pick good passwords.

* I used SHA-1 as an example because it's common.  The SHA-2 family are stronger cryptographic hashes, but they don't provide any significant benefit beyond SHA-1 for password hashing.

Edit: I'd like to point out that, for simplicity, these numbers do not factor in the number of passwords that are actually cracked along the way.

Edit #2: I expanded the graphic to include user counts of 10k, 100k, and 10M.  Thank you Solar Designer for the suggestion.

Password Basics

This post is a brief introduction to passwords.  All of my other posts assume some prerequisite knowledge that may make them inaccessible.  If you already know about password cracking, hash functions, salting, and stretching, you can probably skip this post or perhaps just skim it.  If those concepts are new to you, you're in the right place.

Please post any questions you have in the comments.  I will try to answer questions and/or update this post as required.

Most operating systems and web applications authenticate people using passwords.  In order for this to work, the server (or application) has to store some information that will allow it to validate the password.  One way to accomplish this would be to just store the passwords in plain text, but this would be a big problem if the password file or database was ever stolen. The solution most systems use is to hash the passwords.

Password Complexity Requirements

The issue of password complexity came up at work today so I put together a small spreadsheet detailing how long it would take to crack unsalted passwords of a given length and how many passwords per day or year an attacker could expect to recover in an offline attack.  I assumed that there are 10k users and that an attacker can guess 20 billion passwords per second.  The speed estimate implies that the attacker is using a  GPU-based password crackers such as CryptoHaze or oclHashCat and that the underlying hash is something fast like MD4 (Windows) or MD5 (many websites).  Here's what the numbers look like:

Click so you can read it...

I highlighted the lengths/complexities that would yield less than one password per day for an attacker.  That's a pretty arbitrary requirement, but it seemed like an okay minimum.  Your requirements may vary.

The numbers indicate that passwords should be at least 10-12 characters long (depending on the character set), but they also assume truly random passwords.  Since people do not actually pick random passwords, I'd add at least two to three characters which brings us up to 13-15 characters (again, depending on the character set).  In order to avoid the increased support costs and general discontent that is likely to arise from requiring 15 character passwords, it's probably a much better idea to adopt a stronger password hash and/or two-factor authentication instead.  With scrypt, bcrypt, or PBKDF2 (and reasonable cost values), seven and eight character passwords start to look pretty good again. 

Understanding RSA

This is a explanation of RSA that I wrote about a year ago for a discrete math class.  I've shared this a few times so I'm posting it here in hopes it will be useful to others. Please post comments if something is unclear or if you think you've found a mistake.

Background

A key is a number that can be used with a cryptographic algorithm to encrypt or decrypt a message.  In symmetric cryptosystems (AES, DES, RC5, etc) the same key is used for encryption and decryption.  In asymmetric cryptosystems like RSA, there are two keys: one key is used to encrypt while another is used to decrypt.

A user's public key is used to encrypt messages intended for that user.  The user can decrypt those messages using his private key but an attacker with only knowledge of his public key cannot decrypt the message.  This allows the user to share the encryption key publicly for anyone that might want to send him a secret message (hence “public”).  The user must keep his decryption key secret (private).  

Learning Cryptography

Cryptography can be a difficult subject to learn.  Until recently, there were only a few books available and, even now, most of them aren't well-suited to self-study for anyone who doesn't already have a strong math background.  Cryptography is a mathematical field.  If you want to be cryptographer, you will have to learn probability, number theory, abstract algebra, etc.  But, those aren't strict prerequisites to learning basic cryptography so you can study those areas as you go along.

I became interested in cryptography in the late 1990s after reading Schneier's Applied Cryptography, but I had other interests, responsibilities, etc. so I never went very far with it.  Recently, I've been trying to take my skills to a higher level and I've found several resources that are helpful to me.  Those are outlined here.

Building PyCrypto on Amazon EC2

I setup a new AMI Linux instance in the EC2 cloud today primarily for playing around with Python and possibly building some small web apps.  Shortly after firing up the instance, I tried to build and install PyCrypto and ran into some problems.  It was a bit of an adventure.  Here's how I got it working:

Is IDS effective?

Network intrusion detection systems are a popularly considered as a crucial component of network defenses and fit well (in concept) with the idea of defense in depth.  One of the common arguments in favor of IDS, which I first read from Richard Bejtlich, is that "prevention eventually fails."   The argument is persuasive and it seems that we should have some sort of monitoring or detection in place to help us discover when an attack has penetrated or evaded our defenses.  Unfortunately, it's not clear that IDS accomplishes that goal.

In the physical world, the benefit of combining detection with prevention seems more clear.  A fence with razor wire will deter a casual intruder or pedestrian from wandering onto a property, but a fence can be cut or climbed even with razor wire.  We could built a stronger or higher barrier, perhaps a large steel wall, but this is expensive.  It's more cost effective to install motion sensors, alarms, and cameras to alert security staff if someone violates the perimeter.  This does not analogize well to network security.

Blame the management

I'm not the first person to say this, but I really can't stress it enough: security starts with management.  No matter how smart or well-intentioned the employees are, management has to drive security.  Without management support and pressure, individual efforts lack consistency, security measures don't align properly with the business, and, perhaps most important, the incentives are all wrong.  And, when an organization fails at security, it's management's fault.

Optimizing NTLM brute-force

For this post, I'll assume that you're familiar with NT password hashes and/or MD4.  This is based on a paper I wrote in 1998 but did not publish.  I mentioned it in my 2004 article on password protection but it didn't really fit there.

The NT Dialect/NTLM hash in Windows uses the MD4 algorithm.  Password input is treated as Unicode when it is hashed so ASCII characters are converted to 16-bits ('A' = 0x41 = 0x0041).

The MD4 algorithm consists of 48 steps which turn a 512-bit input into a 128-bit output.
MD4 pads all inputs to a multiple of 512 bits, though it can iterate over several
512-bit blocks if necessary.When passwords are 13 characters long or less, the inputs to steps 46-48 are null. An attacker can use this information to reverse the last three steps of any password hash he or she is trying to crack. Subsequently, the attacker
only needs to compute the first 45 steps for each password tried. This results in a
speedup of about 6.25%.