Lessons from the S.C. breach

In October, the South Carolina Department of Revenue discovered that it had been breached and contacted Mandiant to assist in the investigation and response.  All told, millions of social security numbers and hundreds of thousands of bank/credit card numbers had been stolen.

In November, Mandiant published their findings.  This is exciting.  All we usually get is a news article lacking in technical detail.  This we can actually learn from.

My goal in this blog post is to explore what, in hindsight, the S.C. Department of Revenue could or should have done better. Please read the Mandiant report before you move on.

Lessons from the CCSF debacle

In January 2012, some fairly sensational news stories were published about a major data breach at City College of San Francisco.  According to the early reports, tens of thousands of student records may have been compromised.  Even more interesting, the reports said that some systems may have been infected for over a decade and that there were connections to China and Russia.  While the reports were interesting, they were short on details and I hoped to eventually read more after the school had some time to sort things out.

In May, the CTO of CCSF was suspended at least in part for his reaction to the breach.  The Guardsman, CCSF's newspaper, published a series of articles that described controversy within CCSF over the handling of the breach, the CTO's management and accusations that the breach was a false alarm.

The CTO's tenure sounds like it was a disaster.  It's also full of lessons for IT and security managers.

Wrapping up 2012

I've been really busy lately so I haven't blogged much.  Things are coming together pretty well here at the end of 2012.  Here's what's happening with me.

This summer, I won a free trip to Fishnet Security's iSWAT training event in Las Vegas through The Ethical Hacker Network.  I decided to take the CISSP review course.  I've been meaning to take the CISSP exam for a while, but it's been hard to find time to study since I'm working and in school full-time.  There were only three of us in class, but it worked out really well.  Instead of sitting in rows and listening to the instructor drone on for hours, we sat around a conference table and actually discussed things as we went over them.  Many of the discussions went well past what we needed for the exam, but I enjoyed the hell out of it.  It's not often that I get to spend an entire day talking about security.

My only complaint is that Fishnet was supposed to reimburse me for the CISSP exam (it was part of the package).  I was told a month ago that my reimbursement was being processed, but I haven't heard back and I haven't received anything.

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%.

How to fail at cryptography

In my last post, I discussed the number 2¹²⁸ and explained why it’s not possible to brute-force 2¹²⁸ possible keys.  Does this mean that we can use 128-bit cipher like AES with confidence?  Not quite.  Brute-force against AES with 128-bit or larger keys is impossible with any non-quantum computer we will build for the foreseeable future, but that’s only one avenue of attack.  In practice, cryptosystems are broken in a variety of ways.  Sometimes, the algorithm is flawed.  Other times, the algorithm is sound but the implementation is bad.
 

This post attempts to explain, at a high level, some of the technical vulnerabilities that exist in real-world cryptosystems.  I hope that it will help developers, IT and security people gain a basic understanding of the difficulties that exist and give them some ideas of what to look for in code reviews, testing, or product selection.  I also hope to make clear why writing your own implementation is usually a bad idea.  For more information, check out the book Cryptography Engineering and Matthew Green’s blog.  For a look at management/business failures, check out Ross Anderson's  Why Cryptosystems Fail.

Book Review: The Block Cipher Companion

A few months ago I picked up a new book called The Block Cipher Companion by Lars Knudsen and Matthew J.B. Robshaw.  Shortly thereafter, I posted a review on ethicalhacker.net.  I am reposting that review here.

The book is aimed at practioners and aspiring researchers in block cipher cryptography.  It is very well-written and accessible (for a cryptography book).  I've been interested in cryptography since Applied Crypto came out when I was in high school so I was very excited to finally see a dedicated book on block ciphers. 

How big is 2**128?

Most cryptographic algorithms deal with numbers that are 128 bits or larger.  A 128-bit number has 2¹²⁸ possible values, but how big is 2¹²⁸?  Most people realize that it’s a “big number” but don’t comprehend exactly how big.  Who can blame them?  Outside of a few disciplines such as cryptography and astrophysics, most people will never encounter a number this large.  

It’s important to understand this, however, because it tells us what is and is not possible in cryptography.  Conversely, a number of inaccurate statements about cryptography arise because of a poor understanding of this quantity.  For instance, many articles I’ve read recently claim that it is possible to use rainbow tables even for password hashing algorithms with a 128-bit salt.  Others have claimed that it is or will be possible to brute-force 128-bit keys.  To understand the problem with these claims, let’s figure out just how big this number is.

Sorry about the mess.

Sorry about not truncating my posts earlier.  Math I'm good at; visual design, not so much.

Everything should be much more readable now.

An Introduction to Password Protection

In June 2004, I published an article on password protection in ;login:.  The article discusses the history and basic concepts behind the password protection measures used in Unix and Windows.  Parts of it are out of date (e.g. the password length recommendations), but the technical parts hold up fairly well as an introduction to password security.  It also provides lots of references for further reading.

Disclaimer: I no longer stand by some of the advice I gave at the end of the article.  Password aging and expiration, for instance, are worthless.  Read it for the technical bits, but skip the ending.

The article is online here.

Passwords: Attacks and Threats

People throw around a lot of advice about password security, but we don't often talk about what we're trying to accomplish.  The purpose of this post is to flesh out some of the questions we should be asking to determine who the potential attackers are and what attacks we are trying to prevent.  This allows us to consider if and why we would want to implement defenses such as password salting and stretching, two-factor authentication, time delay, password expiration, and account lockouts. 

At a basic level, a password is used to secure access to an account so let's assume there is a corresponding threat that someone would try to get into that account.  But, we need to get more detailed than this.  Who would try to get into account (i.e. the threat actor)?  Why?  Would they be happy with any account or just a specific one like root or Administrator?  Does the attacker need to crack a large number of accounts or will he be satisfied with just a few?  Would the attacker be likely to use an online attack or an offline attack?

How long should passwords be?

There's a lot of advice thrown around about what the actual password requirements should be, but most organizations do not stop to consider what the goals of those requirements are.  In this post, I throw some numbers around to determine minimum password lengths for different security requirements and hashing algorithms.  The minimum lengths can get a bit silly, but this is why we need to use strong password hashes and should use two-factor authentication when practical.

The first consideration is whether the organization wants to prevent offline cracking attempts or just online attacks. Online password guessing is easier to stop. With even a short temporary lockout (five seconds is sufficient), the passwords do not need to be that strong: five characters with a reasonable complexity requirement should be sufficient. With a 5 second lockout, you can guess 17,280 passwords per day per user. At that rate, it would take 145 years to exhaust the password space assuming five character, mixed-case, alphanumeric passwords.

Rainbow Tables Not Considered Harmful

Since the LinkedIn password dump was posted online a couple of weeks ago, there's been a lot of discussion about hashing algorithms, salts, and, of course, rainbow tables.  Rainbow tables were described in Phillipe Oechslin's 2003 paper Making a Faster Cryptanalytical Time-Memory Trade-Off and are a type of lookup table for password hashes that only require a fraction of the storage needed for a naive lookup.  You might, for instance, only store 1/2000 hashes. 

Rainbow tables seemed like a pretty big deal at the time.  Rather than an attacker brute-forcing passwords every time he needs to crack some hashes, an attacker can make tables ahead of time so that he will only have to perform a relatively quick lookup operation later.  This is way more efficient than brute force if the attacker is dealing with unsalted password hashes from relatively small sites (thousands of users or less). 

Today, rainbow tables don't seem like such a big deal after all.

Passwords Matter

This is in response to a Tenable blog post "Do Passwords Matter?"  I have several issues with the post that I address here.

Password Salts

When discussing password cracking, the post says "A 'salt' will help slow down this process a little."  Actually, salts slow down the process a lot.  It's still no more difficult to brute-force an individual user, but it becomes insanely hard to brute force all of the accounts for a large set of hashes (e.g. the 6million+ hashes dumped from LinkedIn).  With salts, it's six million times harder to crack six million passwords than to crack one.  Salts also prevent rainbow tables and other precomputation attacks completely.  The Tenable post points out that developers sometimes implement salts incorrectly.  That's really beside the point.  Just because some developers get it wrong doesn't mean the others should stop trying to get it right.