Reusable Security

CCS Paper Part #2: Password Entropy

2010-10-30T14:27:00.000-07:00

This is part #2 in a (mumble, cough, mumble) part serious of posts discussing the results published in the paper I co-authored on the effectiveness of passwords security metrics. Part #1 can be found here.

I received a lot of insightful comments on the paper since my last post, (one of the benefits of having a slow update schedule), and one thing that stands out is people really like the idea of password entropy. Here’s a good example:

“As to entropy, I think it would actually be a good measure of password complexity, but unfortunately there's no way to compute it directly. We would need a password database comparable in size (or preferably much larger than) the entire password space in order to be able to do that. Since we can't possibly have that (there are not that many passwords in the world), we can't compute the entropy - we can only try to estimate it in various ways (likely poor)”

First of all I want to thank everyone for their input and support as I really appreciate it. This is one of the few cases though where I’m going to have to disagree with most of you. In fact, as conceited as it sounds, my main takeaway has been that I've done a poor job of making my argument, (or I’m wrong which is always a possibility). So the end result is another post on the exciting topic of password entropy ;)

When I first started writing this post, I began with a long description on the history of Shannon Entropy, how it’s used, and what it measures. I then proceeded to delete what I had written since it was really long, boring, and quite honestly not that helpful. All you need to know is:

Claude Shannon was a smart dude.
No seriously, he was amazing; He literally wrote the first book on modern code-breaking techniques.
Shannon entropy is a very powerful tool used to measure information entropy/ information leakage.
Another way of describing Shannon entropy is that it attempts to quantify how much information is unknown about a random variable.
It’s been effectively used for many different tasks; from proving one time pads secure, to estimating the limits of data compression.
Despite the similar sounding names, information entropy and guessing entropy are not the same thing.
Yes, I’m actually saying that knowing how random a variable is doesn’t tell you how likely it is for someone to guess it in N number of guesses, (with the exception of the boundary cases where the variable is always known – aka the coin is always heads- or when the variable has an even distribution – aka a perfectly fair coin flip).

Ok, I’ll add one more completely unnecessary side note about Shannon Entropy. Ask a crypto guy, (or gal), if the Shannon entropy of a message encrypted with a truly random and properly applied one time pad is equal to the size of the key. If they say “yes”, point and laugh at them. The entropy is equal to that of original message silly!

Hey, do you know how hard it is to make an entropy related joke? I’m trying here…

Anyways, to calculate the entropy of a variable you need to have a fairly accurate estimate of the underlying probabilities of each possible outcome. For example a trick coin may land heads 70% of the time, and tails the other 30%. The resulting Shannon entropy is just a summation of the probability of each event multiplied by the log2 of its probability, (and then multiplied by -1 to make it a positive value). Aka:

So the Shannon entropy of the above trick coin would be -(.7 x log2(.7) + .3 x log2(.3)) which is equal to 0.8812 bits. A completely fair coin flip’s entropy would be equal to 1.0. In addition, the total entropy of different independent variables is additive. This means the entropy of flipping the trick coin and then the fair coin would be .8812 + 1.0 = 1.8812 bits worth of entropy.

I probably should have put a disclaimer above to say that you can live a perfectly happy life without understanding how entropy is calculated.

The problem is that while the Shannon entropy of a system is determined using the probability of the different outcomes, the final entropy measurement does not tell you about the underlying probability distribution. People try to pretend it does though, which is where they get into trouble. Here is a picture, (and a gratuitous South Park reference), that I used in my CCS presentation to describe NIST’s approach to using Shannon entropy in the SP800-63 document:

Basically they take a Shannon entropy value, assume the underlying probability distribution is even, and go from there. Why this is an issue is that when it comes to human generated passwords, the underlying probability distribution is most assuredly not evenly distributed. People really like picking “password1”, but there is always that one joker out there that picks a password like “WN%)vA0pnwe**”. That’s what I’m trying to say when I show this graph:

The problem is not that the Shannon value is wrong. It’s that an even probability distribution is assumed. To put it another way, unless you can figure out a method to model the success of a realistic password cracking session using just a straight line, you’re in trouble.

Let me make this point in another way. A lot of people get hung up on the fact that calculating the underlying probability distribution of a password set is a hard problem. So I want to take a step back and show you this holds true even if that is not the case.

For an experiment, I went ahead and designed a variable that has 100 possible values that occur at various probabilities, (thanks Excel). This means I know exactly what the underlying probability distribution is. This also means I’m able to calculate the exact Shannon entropy as well. The below graph shows the expected guessing success rate against one such variable compared to the expected guessing success generated by assuming the underlying Shannon entropy had an even distribution.

Now tell me again what useful information the Shannon entropy value tells the defender about the resistance of this variable to a guessing attack? What’s worse is the graph below that shows 3 different probability distributions that have approximately the same entropy, (I didn’t feel like playing around with Excel for a couple of extra hours to generate the EXACT same entropy; This is a blog and not a research paper after-all).

These three variables have very different resistance to cracking attacks, even though their entropy values are essentially the same. If I want to get really fancy, I can even design the variables in such a way that the variable with a higher Shannon entropy value is actually MORE vulnerable to a shorter cracking session.

This all comes back to my original point that the Shannon entropy doesn’t provide “actionable” information to a defender when it comes to selecting a password policy. Even if you were able to perfectly calculate the Shannon entropy of a password set, the resulting value still wouldn’t tell you how secure you were against a password cracking session. What you really want to know as a defender is the underlying probably distribution of those passwords instead. That's something I've been working on, but I’ll leave my group’s attempts to calculate that for another post, (hint, most password cracking rule-sets attempt to model the underlying probability distribution because they want to crack passwords as quickly as possible).

New Paper on Password Security Metrics

2010-10-07T07:23:00.000-07:00

I'm in Chicago at the ACM CCS conference, and the paper I presented there: "Testing Metrics for Password Creation Policies by Attacking Large Sets of Revealed Passwords", is now available online.

Since I had the paper and presentation approved through my company's public release office I was given permission to blog about this subject while the larger issue of my blog is still going through the proper channels. Because of that I'm going to limit my next couple of posts to this subject rather than talking about the CCS conference as a whole, but let me quickly point you to the amazing paper "The Security of Modern Password Expiration: An Algorithmic Framework and Empirical Analysis", written by Yinqian Zhang, Fabian Monrose and Michael Reiter. In short, they managed to obtain a great dataset, their techniques were innovative and sound, and there's some really good analysis on how effective password expiration policies really are, (spoiler: forcing users to change their password every six months isn't very useful).

I'd like to first start by acknowledging the other authors who contributed to the "Testing Password Creation Metrics..." paper.

Dr. Sudhir Aggarwal - Florida State University: My major professor, who spent I don't know how many hours helping walk me through the subtle intricacies of information entropy.
Michael Collins - Redjack LLC: Another data driven researcher, and much cooler than me since he uses GNUPlot instead of Excel ;)
Henry Stern - Cisco IronPort: He was the driving force behind getting this paper written. It was over lunch at the Microsoft Digital Crime Consortium, (it's a conference to combat cybercrime, and not a group of people from Microsoft looking to commit digital crime like the name implies...), that the framework for this paper was laid out.

As for the contents of the paper, I'm planning on breaking the discussion about it down into several different posts, with this post here being more of an overview.

When writing this paper, we really had two main goals:

How does the NIST model of password entropy as defined in SP800-63 hold up when exposed to real password datasets and realistic attacks?
How much security is actually provided by typical password creation policies, (aka minimum length, character requirements, blacklists)?

Based on our results, we then looked at the direction we would like password creation policies move to in the future. This ended up with us suggesting how to turn our probabilistic password cracker around, and instead use it as part of a password creation strategy that allows people to create passwords however they like, as long as the probability of the resulting password remains low.

Of all that, I feel our analysis of the NIST password entropy model is actually the most important part of the paper. I know it sounds like an esoteric inside baseball subject, but the use of NIST's password entropy model has a widespread impact on all of us. This is because it provides the theoretical underpinning for most password creation policies out there. Don't take my word for how widespread the use of it is. Check out the Wikipedia article on password strength, (or better yet, read the discussion page) for yourself.

Our findings were that the NIST model of password entropy does not match up with real world password usage or password cracking attacks. If that wasn't controversial enough, we then made the even more substantial claim that the current use of Shannon Entropy to model the security provided by human generated passwords at best provides no actionable information to the defender. At worse, it leads to a defender having an overly optimistic view of the security provided by their password creation policies while at the same time resulting in overly burdensome requirements for the end users.

Getting in front of a room full of crypto experts and telling them that Shannon Entropy wasn't useful to evaluate the security of password creation policies and "We REALLY need to STOP using it", was a bit of a gut clenching moment. That's because the idea of information entropy is fairly central to the evaluation of most cryptographic algorithms. I would have never done it except for the fact that we have a lot of data backing this assertion up. The reason we are making the broader point is because it's tempting to dismiss the flaws in the NIST model by saying that NIST just estimated the entropy of human generated passwords wrong. For example, if you juggle the constants around or perhaps look at word entropy vs character entropy, things will work out. Our point though is not that you can't come up with a fairly accurate Shannon entropy model of human generated passwords. You most assuredly can. It's just that it's not apparent how such a model can provide "actionable information". In addition, the way we currently use Shannon Entropy in evaluating password security policies is fundamentally flawed.

This subject really does require another blog post, but before I head back to Boston I wanted to leave you with one of the graphs from our paper that demonstrates what I'm talking about:

The above graph shows cracking sessions run against passwords that met different minimum length password creation requirements, (aka must be at least seven characters long). The NIST estimated cracking speed is based on the calculated NIST entropy of passwords created under a seven character minimum password creation policy. You may notice that it overestimates the security of the creation policy over shorter cracking sessions, but at the same time doesn't model longer cracking sessions either. This is what I keep on saying that it doesn't provide "actionable intelligence", (third time and counting). When we say "password entropy" what we really want to know is the Guessing Entropy of a policy. Unfortunately, as a community, we keep using Shannon entropy instead. Guessing entropy and Shannon entropy are two very different concepts, but unfortunately there doesn't exist a very good way of calculating the guessing entropy, while calculating the Shannon entropy of a set of text is well documented. This is part of the reason why people keep trying to use Shannon entropy instead.

So I guess I should end this post by saying, if any of this sounds interesting please read the paper ;)

Quick Status Update

2010-09-10T17:56:00.000-07:00

This is just a quick post to let you know that I for once have a valid excuse for not updating this blog in a timely manner. I actually found a job! Thanks to everyone who offered help, recommendations and encouragements. The only catch is that right now it's being decided if I have to run my posts through our public release office or not. Don't worry, this blog is not going away regardless of the decision.. It might just gain a few unwilling readers ;)

As to my new company, I'm going to keep that a bit of an open secret. This blog reflects my personal views. I certainly don't speak for them, and I plan on avoiding any topics that have to do with my day job, (Don't worry, I'm not doing any password cracking there).

Once again thanks, and I'll resume posting once I get the OK and can update this blog while complying with company policies. I just want to make sure I handle this situation the right way.

Defcon Crack Me if You Can Competition

2010-07-28T10:39:00.000-07:00

I'd be remiss if I didn't spend a little time talking about the "Crack Me if you Can" competition at Defcon. It's really been amazing the amount of interest that this contest is drumming up. People are excited; it seems like everyone is refining their mangling rules, putting together new wordlists, and finishing up various password cracking tools. The impact that this is having on the password cracking community as a whole is hard to overstate. Needless to say, I'm a fan of that, and I have a ton of respect for Minga and the folks at KoreLogic for putting this together.

I'll be participating, though I certainly don't plan on winning. What I'm really looking forward to though is the chance to meet with everyone else and learn what other people are doing. I'm hoping this turns into an event like the lockpicking village with the contest being almost besides the point. Of course I might be saying that because I'm going to get creamed as well...

Since I've had a few people ask me about the competition itself, here's my two cents. My biggest concern is that the passwords we will be cracking aren't real. This isn't a criticism. There's no way you could run this competition with real corporate passwords, (well, legally that is...). It's just something to keep in mind. What will be interesting though is applying the techniques learned from the winner, (part of the rules are that you have to disclose your cracking techniques), to other datasets as they become available. That's why I have this blog. I might not be the best password cracker out there, but I can certainly run other people's attacks and plot the results on Excel ;)

If I had to hazard a guess, here's some predictions of mine about the contest:

1) Most passwords will be based on relatively common dictionary words. Way more so than you would find normally.

2) Most of the cracking will center around applying the correct mangling rules. Yes there will be the 'Dictionary123' words, but I expect most 'high score' passwords will have less common rules such as 'xD1ct1onaryx'.

3)There will probably be some LANMAN passwords, so bring your rainbow tables.

4) I expect there to be so many NTLM passwords that rainbow tables for them won't be cost effective.

5) I'll be interested to see if they have any 'exotic' password hashes. WinRAR, TrueCrypt, etc.

6) It'll be a ton of fun ;)

I'll see you guys there.

Protecting Physical Documents

2010-07-03T18:08:00.000-07:00

The above picture is of my Subaru Baja. Sometime last night, someone broke my back window, and stole almost everything from my car, (they apparently did not like my music; btw Punk is not dead). Normally this would be a costly annoyance, but in this case I'm in the process of moving and finding a new job. While most of my stuff is sitting safely in a storage locker, I still had several boxes of various items stored in my back seat, including unfortunately my "to-go" bag.

My to-go bag contained all of my important possessions that I planned on grabbing if my house was in the process of burning down. For example, it contained two thumb drives with backups of all of my work plus assorted other documents. I'm not worried about them though since I used TrueCrypt. Good luck cracking those, which BTW, is the reason I love TrueCrypt. What I am concerned about though is that my social security card, my passport, my birth certificate, my extra banking checks, and a whole lot of other important paper documents were also taken. Visualize everything you don't want to be stolen and you have a pretty good idea of what was in that bag.

Of course the next question is "Why the Hell did you leave such important documents in your car?" My response is, laziness and a poor threat model. I needed several of those documents when getting a job. A drivers license by itself doesn't cut it, as you need at least two other forms of ID. Rather than grab those two documents out of my bag and leave the rest in the storage locker I grabbed the whole thing in case there was anything else I needed. Normally I also wouldn't leave it in my truck if I was planning on going somewhere sketchy, but I was parking in a well lit hotel parking lot, and quite simply I had my hands full hauling my bag of clothes, my suit and my computer bag into my room. Darned if I wanted to make a second trip back down to my car. What's worse though is I rationalized it away by saying that at least my car was locked, unlike my hotel room where any of the housekeeping staff could access it during my stay; Plus my car's never been broken into before... The reason that's worse is because I didn't simply forget my bag; I realized it might be a problem and then actively convinced myself that, "No, everything really is ok".

I have to confess that this is a difficult post for me to write. I was counseled by several friends never to mention this incident to anyone, (besides the cops and other officials of course). Their comments were along the lines of "You're looking for a security job, and you just had your life stolen because you left it in the back of a car. Even I wouldn't hire you now!" Of course that was said in jest, but the concern is real.

I'm willing to take that risk though for several reasons. First of all I'm really angry, both at the person who did this and myself. Actually mostly at myself which is seriously messed up. By talking about this incident hopefully I can gain a bit more control over the situation. Second, I'm a big fan of disclosure. If the above description doesn't sound like a typical computer attack, let me rewrite it for you:

The attacker performed an SQL injection attack against subaru_bajas_rule.com. After gaining access to the database they downloaded the user's social security number, banking information, and other personally identifiable information. Afterwards the attacker performed a 'drop table users' destroying the local copy of the data. When the site administrator was asked about this, he responded that knew SQL injection attacks were common, but he never expected to be targeted by one. As for the reason why the user data was accessible, the administrator admitted the site was in the process of transitioning to a new forum software, and that if the attack happened a week later when the new forum software was in place, this wouldn't have been a problem.

I've always felt that security incidents can happen to anyone, and what's important is to focus on the remediation, and use them as a learning tool to make sure the same attack doesn't happen again. That's one nice thing about having a blog, I'm on record on saying much the same thing when talking about the ZF0 attack, so at least this isn't a new found belief I came to after finding myself completely 0wned ;)

So in the spirit of full disclosure I wanted to talk about this attack in a public forum where hopefully it will benefit other people, and if someone doesn't want to hire me because I'm not perfect, well at least they found out now. So on to a more detailed analysis of the attack:

Only items in the back seat were stolen. Since there was so much stuff it looks like the attacker grabbed what they could, and then left without doing a full search of the car. I just was really unlucky that everything I cared about was in the back seat.
When this happened, my car was parked at the far end of the parking lot, since I'd rather walk than squeeze into a small spot. This was a serious mistake considering all of the stuff I had in my car.
While there was a night watchman, he did not notice the attack. Likewise there were no sensors collecting forensically useful data, (aka cameras, and the thief did not leave any useable fingerprints).
I'm much too focused on digital issues. The fact that I bothered to encrypt my electronic documents and the store them with paper documents that are way more valuable to an attacker shows a serious lack of priorities and/or threat modeling. I'm not saying don't encrypt your files, but simply that I should have taken the same care with my other documents and locked them up in my hotel room safe.
The mindset, "Just because something bad hasn't happened to me in the past means it won't happen to me in the future" is very hard to avoid.
I really hope all that is happening right now is some 16 year old kid is trying to use my passport to buy booze. That being said, I need to plan for much more serious scenarios, hence closing my old bank account rather than just canceling my checks, signing up to a credit check service, etc.
Dealing with issues like this on a holiday weekend is extremely difficult. Canceling my old bank account and moving it to a new one was particularly stressful since I had a couple of hours to do it before the bank closed for the long weekend. Likewise, I will have to wait till Tuesday to have my car window replaced. Of course, cyberattacks never happen during a holiday...
Security policies are important, but what's more important is enforcement of those policies. You really do need some force from on high telling people, "Yes, it is a pain to take a second trip down to your car, but you are going to do it anyway".
Storing all of your valuables in one place has advantages and disadvantages. I still don't know if the idea of a to-go bag was a fundamentally bad idea, but I certainly should have "checked out" my two forms of id from it rather than taking the whole thing.
What makes a fiasco is a cascade of multiple smaller mistakes/failures occurring together. Whether we are talking about the BP oil spill, or a horribly hilarious Peter Pan play, serious problems often are not the result of just one thing going wrong, but several poor decisions.
Combined with my comments in the previous paragraphs, it's really easy to analyze all of the stuff that I did wrong after the fact. The problem is it all of my decisions seemed so reasonable at the time. On the other hand, you can't live a perfectly secure life. What I'm wrestling with right now is how to re-evaluate my personal threat models and learn from this incident without letting it ruin my life.

Well, that about does it for now. Hopefully I can get back to the focus of this blog, the academic study of password cracking techniques, soon. This whole real life security thing can be pretty annoying...

Carders.cc - General Observations and Updates - Part 3

2010-05-31T01:27:00.000-07:00

Digging into this data is like watching an episode of Lost. Whenever it seems like one question gets answered, about ten other questions pop up.

Before I get into details, I want to start with a comment Per Thorsheim sent me as to what other password cracking programs support salted sha1 hashes:

The sha1(lowercase_username.password_guess) is at least supported by these:
Extreme GPU Bruteforcer (www.insidepro.com) hashcat and oclhashcat (cpu/gpu respectively) www.hashcat.net

I'm kicking myself for not thinking about hashcat, since it's a extremely powerful password cracker; plus it's free. Unfortunately the GPU version doesn't support the salted sha1 hash type, but even the non-gpu version is quite nice.

As for InsidePro, it also is very good, though it does cost some money. I've had a license-free version of questionable origin offered to me before, but I turned that down. Legality aside, installing pirated software given to you by shady people at a hacker conference would just be stupid...

Also, I've been talking to Ron Bowes over at the excellent skullsecurity blog, and he and some other people are hard at work cracking the passwords. It sounds like they have some serious hardware behind the effort, so expect to see something posted on his site about that in the near future.

OK, now onto the analysis:

First of all, I'm downgrading my opinion of the skill showed by the hackers in their password cracking attack. What I didn't realize before was the extent that the users of carders.cc had been compromised previously. Just about all of the non-trivial passwords that were cracked appear in publicly available input dictionaries which are based on passwords cracked from user submitted hashes - aka hashkiller, insidepro, etc. Please note, I'm not saying they were script kiddies. The attackers were able to target the salted sha1 hash, and they knew where to get some good input dictionaries. It's just that they are not some uber-l33t password crackers, and anyone else using those input dictionaries could crack the same number of passwords in a couple of hours.

What this also means is we might be able to figure out which input dictionaries the attackers were using by looking at the hashes they cracked, vs. what the input dictionary would crack. To demonstrate this, below is a Venn diagram of what an input dictionary the attackers used would look like:

For example, there is a good chance the attackers used the InsidePro Big dictionary, since it cracks the same 598 passwords from the carders.cc list that the attackers cracked. Add in a couple of the other publicly available input dictionaries, and you get real close to the 920 total passwords they managed to crack. To put this in perspective, I've so far managed to crack 62%, (compared to the 53% that the hackers cracked), of the salted Sha1 passwords on my laptop using basic dictionaries with almost no mangling rules. I fully expect other people to blow past that mark.

Next up, initial thoughts about the carders.cc database:

What I really need to do is load all of the tables into my own database so I can do quick SQL queries, vs. manually going through the data by hand. That being said there are a few things that stick out:

There's a lot of userids/password hashes in the carders_smf_members table that did not appear in the write-up.
The MD5 hash is salted, but at least the salt is also available in the carders_smf_members table. The hash itself is a vBulletin3 hash type, MD5(MD5(Password).Salt). Both John the Ripper and Hashcat support this hash type.
I'm not sure if the IP addresses stored in the table are accurate or not, since it looks like the site admins tried to obscure it in the webserver logs, but if they are, the database stores the last two ip addresses used.
Other interesting fields include date joined, number of posts, karma level, last login date, etc.
The above doesn't even begin to get into all of the data contained in the actual posts themselves...

That about it for this update. Let me leave you with one last fact that Ron found out:

Another interesting factoid:

Last MD5 password: 2010-01-10 21:54:01

First SHA1 password: 2010-01-10 22:40:16

So it was on January 10, 2010, later in the evening (in CDT) that they upgraded from vBulletin 3 to SMF.
*shrug* the more you know!

Carders.cc - Analysis of Password Cracking Techniques - Part 2

2010-05-26T18:34:00.000-07:00

So I figure I probably should get around to looking at the passwords in this list, since password cracking techniques are the focus of this blog...

First though, a real quick definition. I needed to decide what to call the various parties involved in this whole shenanigans. For example, when I'm talking about the 'hackers', am I referring to the people collecting stolen credit card data who belonged to the board, or the people who hacked carders.cc? Likewise, if I use the term criminals, that could refer to both groups as well. Therefore, in my blog posts I'm going to use the following terms to refer to the two groups:

Carders/Users: The people who belonged to the board. Normally I would also use the term 'victims', but I don't want to honor them with that title.
Hackers/Attackers: The people who broke into the forum and posted the data online.

Ok, now that we have that out of the way, the rest of this post is going to be broken up into four parts:

Executive Summary
Brief Description of the Password List
General Observations
Setting Up a Password Cracker to Target Salted Sha1 Hashes

More in-depth analysis will have to wait till later since I need more time to go through the data. Also, I'm moving up to the D.C. area in a week to look for a job/start interviewing, so large scale password cracking sessions are not really feasible for me to perform right now.

-BTW, if you have a job opening please feel free to contact me.

Finally, I apologize but this post is going to be a bit more haphazard then the above outline implies, simply because it's hard to talk about one aspect of this dataset without discussing other aspects as well.

Executive Summary:

Carders.cc, on online forum for the buying and selling of stolen bank and credit card data, was broken into sometime before May 5th by vigilante hackers. On May 18th, the hackers then posted data about the users to various file sharing sites, (pastebin, rapidshare), which included IP addresses, usernames, e-mail addresses, and all of the saved forum posts. More significant to this report, the attackers also posted the users' password hashes along with the plaintext passwords that the attackers had managed to crack. These passwords and password hashes provide significant data for researchers. From this data, we now know that cyber-criminals often select weak passwords. Furthermore, by analyzing these passwords we can develop better password cracking techniques that target the specific type of users, (criminals), whom law enforcement is the most interested in. This is an improvement from some of the other disclosed password datasets which were gathered from the general public. In addition, by looking at the passwords the attackers managed to crack, along with the passwords they failed to crack, we can gain a better understanding of the capabilities and techniques employed by hacker groups in real life attacks. This hacker group in particular appears to be quite proficient in password cracking techniques, possessing both the tools to attack salted SHA1 password hashes, and the ability to crack close to 53% of the passwords in the dataset.

Brief Description of the Password List(s):

The first thing that stands out is there are actually two lists of passwords present in the attacker's write-up, though all of the password hashes are mixed together.

List 1)

Contains 1737 salted Sha1 password hashes using the following format:

Sha1(username.password)

This is the list that the attackers talked about and the list they attempted to crack passwords from. Of all the salted Sha1 password hashes, the attackers cracked 920 of them, (around 53%), during the course of an approximately two week period.

List 2)

Contains 2036 "one hundred and twenty eight bit" password hashes of unknown origin. Due to their length, the base password hash is most likely MD4 or MD5. It is unknown if the attackers knew of the existence of these separate hashes since they did not mention the second hashing function in their writeup or crack any of the passwords from this list. I've run some quick tests and these hashes do not appear to be a single round of MD4 or MD5, but probably instead are salted in some manner, and/or use multiple rounds of MD4/5. If a salt that was not the username was used, then it probably will be infeasible to crack very many of the passwords due to the salt not being included in the writeup. A few of the passwords might still be vulnerable though since the salt may be short enough to be brute-forced along with the guesses.

So the next question is, why were there two separate types of password hashes? The most likely explanation is that at some point in the past, the site administrators switched over to a new forum software, or upgraded their security settings. The old users were left with the original password hash, and users who joined up afterwards were assigned the newer password hash. The exact same thing happened when phpbb.com was hacked, leaving users who hadn't logged into the site recently, exposed with only a simple MD5 hash protecting their password vs. the tougher phpbb3 hash.

The interesting thing is that in this case, a user's hash probably was not changed to the new format when they logged into the site. This can be seen by comparing the user's hash type to the IP addresses I talked about earlier. Of the 960 username/IP address combinations, 47 of the users had their password stored as the unknown hash, and 726 had their passwords stored as a salted Sha1 hash. You might notice that these two numbers did not add up to 960. There were 187 usernames that appeared in the IP logs but did not appear in either list of password hashes. I need to look into this more, but many of them might represent incorrect login attempts. A second option is the attackers may not have released all of the user password hashes, instead choosing to keep several for themselves to aid in future hacking attacks. I should probably analyze the forum posts to confirm if the hash type correlates to when the users became active, and if any of the users with missing password hashes actually posted previously on the forum.

Why yes, this is my "brief" description...

General Observations:

Observation 1) The attackers are very proficient in password cracking techniques

Level of Confidence: High
Discussion: The fact that the attacker could even target the salted Sha1 password hashes speaks to their competence. Most major password crackers, (Cain&Able, John the Ripper, L0phtcrack, etc), do not natively support that salt/hash combination. While John the Ripper has extensive support for a generic MD5 hashing function, where it is very easy to modify it to support all sorts of weird hash/salt combinations, that functionality has not yet been ported over to support Sha1 as well. So either they developed their own password cracker/workaround, (which isn't as hard as you might think, as I'll discuss later), or they had access to a less well known password cracker that supported that hash.

Question: Does anyone know of any password cracking program that does support Sha(username.password)?

In addition, since the passwords were salted with a unique salt per hash, this negates many common attacks like rainbow tables. Also, I don't know of any online password cracking site that supports this hash format, since they can't use hash lookup tables either. This means the attackers had to crack all of the password hashes themselves instead of relying on community resources.

Next, the fact they cracked 53% of the password hashes in a two week period speaks highly of the attacker's skills. To put this in perspective, in the phpbb.com attack, the attacker had submitted unsalted MD5 password hashes to an online cracker and only managed to crack 24% of the passwords. In that case, while the hacker might have been very skilled in webpage attacks, they were pretty much at the script kiddie level when it came to cracking the passwords. While 53% might not sound that much more impressive, there is the fact that in the carders.cc case, the hashes were salted with a unique salt. The 'unique' part is important since it means an attacker has to hash each guess independently against each target hash they are trying to crack.

For example, imagine a typical cracking session taking one hour to complete. If an attacker was attempting to crack three thousand unsalted password hashes, then it would take them one hour to run all of their guesses against the entire list. On the other hand, if those password hashes used a unique salt, the same attack would then take three thousand hours, or roughly four months. That's a big difference. Assuming the attackers spent two weeks attempting to crack all 1737 salted Sha1 password hashes, that would mean the guesses they could make in their attack would be equivalent to a 11 minute cracking session against unsalted Sha1 passwords. Even assuming they cracked 50% of the password almost immediately, their cracking session would still be only equivalent to around 20 minutes of attacking unsalted hashes. In conclusion: cracking 53% of close to two thousand salted password hashes in a two week period is fairly impressive.

Observation 2) The Attackers did not user John the Ripper's Incremental mode to brute force guesses.

Level of Confidence: High
Discussion: When I ran JtR's incremental mode, using the default charset 'All', against the list, I almost immediately cracked a new password. Over a longer running session, I managed to crack even more.

Observation 3) The Attackers brute forced digits

Level of Confidence: ~~Low/Medium~~ Very Low
Edit March 28th 2001: I've since managed to crack the password '37721010'. It appears that most of the longer digit based passwords that the attackers had cracked were publicly available in lists of previously cracked password. I'm leaving my original discussion post up for posterity.
Discussion: I have not yet been able to crack any all-digit passwords that the attackers did not crack. Likewise, the attackers cracked several passwords such as '19930720', where unless the attacker has outside information, or had run across that password earlier, it is unlikely to be cracked by any form of attack besides brute force.

Observation 4) The Attackers did not brute force alpha passwords longer than five characters long

Level of Confidence: High
Discussion: I have since managed to crack several passwords that were four lowercase characters long followed by two digits. Likewise I managed to crack several passwords that were six characters long all lowercase.

Observation 5) The attackers may have used knowledge from previous attacks to aid their password cracking sessions

Level of Confidence: Medium
Discussion: Let's be honest, this isn't their first time at the rodeo. It's doubtful that carders.cc is the first blackhat site these attackers have compromised. As we've seen from the ZF0 attacks, just because a website supports a tech-savy audience, doesn't mean it stores their passwords securely. And as we all know, people re-use passwords ... a lot. It's quite possible that the attackers used passwords cracked from previous sites to in turn crack some of the passwords in the carders.cc set. For example, one of the cracked passwords was 'Nadia2312'. An unsalted MD5 hash of that same password was cracked via the Hashkiller site's project Opencrack, on February 1st, 2010. While it could be a coincidence, I'd also like to point out that Hashkiller is a German based website. Other plaintext passwords in the list such as '123456r12', and '01724776692' also show up as being cracked by HashKiller and InsidePro in 2009. Note, this may just imply that the attackers used custom input dictionaries from these sites, and did not actually submit the original password hashes to them.

Setting Up a Password Cracker to Target Salted Sha1 Hashes

As I mentioned previously: I'm sure there's already a password cracking program out there that can target salted Sha1 hashes, but I don't know of it. Not to be deterred, I quickly modified an old password cracking program I had written a while ago to support the hash, (note I could have modified John the Ripper instead, but I'll get to that in a bit). The hardest part was I didn't realize that when you added the username as the salt, you had to lowercase the entire thing. That's a couple of hours of my life I'd like back...

So testing this on my Mac laptop I expected to be able to make around 1000 guesses a second against the entire set of 1737 password hashes. I based this guess on benchmarking unsalted Sha1 hashes using John the Ripper, which gave me around 7,000,000 guesses a second. This would give me a maximum of 4029 guesses a second against the salted hashes. Throw in the overhead required to apply the salt plus my general programing sloppiness, and 1000 guesses a second sounded like a good number. So you can imagine my surprise when i was only ended up making around 80 guesses a second. Something's not right here...

Well it turned out, the problem was I had used the OpenSSL implementation of the Sha1 hashing algorithm which is really slow compared to the version in John the Ripper. Rather than trying to jury rig it into my old password cracker, I then decided to work with John the Ripper instead, which is what I should have done in the first place.

Since I'm a bit ~~lazy~~ goal oriented, I didn't bother to modify John the Ripper's source code though. I was able to get away with this since the hashing algorithm only uses one round of Sha1. Let's look at the hashing algorithm again:

Sha1(lowercase_username.password_guess)

The simplest way to do this would be to create a rule in JtR that would insert the username first. Such a rule would look like:

A0"alice"

Which would insert Alice in front of all of your password guesses. Since we have close to two thousand usernames we are talking about though, that could get annoying having to create a rule for each one. This calls for the use of one of my favorite programs, Awk.

Awk, (and its sister Sed), is one of the best programs out there for quickly parsing and modifying files. It's also very useful for creating word mangling rules on the fly for use in a password cracking session in conjunction with JtR's stdin option. In that way, I sometimes use it much like MiddleChild, and in retrospect, I could easily have written MiddleChild in awk instead. For example I can create guesses using John the Ripper, pipe them into an awk script, and then pipe them back into John the Ripper where the guess will actually be hashed and compared against the target hashes. The above JtR rule could then be replaced with:

./john -wordlist=passwords.lst -session=cracking1 -rules -stdout | awk '{print "alice" $0}' | ./john -stdin -format=raw-sha1

The advantage of this approach is that 'alice' will be automatically inserted in front of all the guesses/rules that the first instance of John the Ripper is generating. But wait, don't we still have close to two thousand usernames we have to do this for? That would be one nasty command line. Luckily an Awk script can be run from a file with the -f option. And how do we create that file with all 1737 usernames? Well with Awk of course! The original format that the hashes were saved to in the carders.cc writeup was:

username:hash:plaintext:e-mail

Simply cat that file into Awk using the following command will create your Awk script for you.

cat carders_hashes.txt | awk -F : '{print"{print \"" tolower($1) "\"$0}"}' > awk_add_usernames.txt

The -F tells it to use the ':' as a seperator and the tolower() option lowercases the usernames. To run this whole thing just type:

./john -wordlist=passwords.lst -session=cracking1 -rules -stdout | awk -f awk_add_usernames.txt | ./john -stdin -format=raw-sha1

Using this setup, now I'm getting around 2,300 guesses a second which is much more respectable. There certainly is room for improvement though. First of all, John compares each hashed guess against all of the target hashes, instead of only the hash which the salt belongs too. Also, you have to clean up the cracked hashes file afterwards to remove the username from the plaintext password. But did I mention it works? As Miles said in the Lost finale, "I don't believe in a lot of things, but I do believe in duct tape!"

Well, that about does it for now. Next up, analysis of the cracked passwords.

Carders.cc - Analysis of E-mail Addresses

2010-05-25T15:00:00.000-07:00

I just wanted to point everyone over to Cedric Pernet's bog where he did an amazing job analyzing the e-mail addresses that the carders had used. You can view his work at the following link:

http://bl0g.cedricpernet.net/post/2010/05/20/Fraudsters-e-mail-addresses

It shouldn't come as a surprise, but just because someone is a cybercriminal doesn't mean they are smart.

Also, if you or anyone you know is doing research into this, feel free to forward me the links. I only found Cedric's blog on a reference in another post on page 8 of a Google search I did, (aka I stumbled on it by pure luck). Thanks!

Carders.cc Hacked - Initial Analysis of IP addresses

2010-05-23T13:58:00.000-07:00

As the title says, Carders.cc, a German forum for the buying and selling of stolen credit cards was hacked and a ton of information was posted publicly online. For a more detailed description, I highly recommend reading the always excellent Brian Krebs writeup on the incident.

I'm going to skip right past my feelings on the subject. The short version is, while part of me is laughing inside, I tend to think such vigilante justice is often counter-productive. I just wish people like that could work with the system because by doing so you can sometimes achieve spectacular results.

Instead I'm going to focus on the data itself and what it can tell us from a research perspective. So far I've managed to download the writeup of the attack, which also includes IP addresses, usernames, e-mail addresses, and password hashes. I'm also currently in the process of downloading what I think is the listing of all the private messages, though it may just turn out to be viruses and fail. BTW, that's why I love VMWare. Edit: It's legit, and wow. It's going to take me a while to sort through/make sense of that data. Expect a post on that later. Google translate, don't fail me now!

As a word of warning, just about everything in this post falls into the category of WAG. While I try to create these guesses with the data I have available, please take everything I say here with a grain of salt. The uncertainty level is HIGH.

First of all, here is a picture of the writeup so you can all enjoy the ASCII art:

So what do we know? From the file timestamps in the writeup, the site was probably compromised sometime around May 5th, (though of course the initial attack could have occurred earlier.) The pastebin copy I downloaded was uploaded on May 18th, so this gives us a general timeframe which will be useful when we start talking about the password cracking that went on.

Question: Does anyone know where/how the attack was initially publicized? Was it a site defacement, posting in a rival forum, etc?

Before I get sidetracked talking about password cracking the hackers did, let's look at those IP addresses collected from the various users of the forum. These IP addresses were only collected for the users who logged on to carders.cc between May 11th and 12th. Starting out, the simplest thing to do was to run a basic GOIP lookup on the countries associated with them. The results can be viewed in the following graph:

As you can see, it really was a mostly German based forum. Not a big surprise I know, but it's nice to see where everyone is coming from. The next thing I wanted to look into was how many duplicate IP addresses there were. This would imply a forum goer was using multiple usernames, or a common proxy that several of the carders were connecting through.

Of the 960 published IP addresses:

819 of them were unique
25 of them were associated with two user accounts
10 of them were associated with three user accounts
3 of them were associated with four user accounts
2 of them were associated with five user accounts
1 of them was associated with seven user accounts
1 was associated with eight user accounts
1 was associated with eleven user accounts
1 was associated with thirteen user accounts

Thirteen user accounts to one IP address? As the Germans would say: "That's a Bingo". The IP address in question, 92.241.164.47, has been previously detected by Project Honeypot as a prolific Russian based Mail, and Blog spam sever. It's on most IP blacklists by now, so I guess they also use it as an anonymous proxy sever to keep their revenue stream up. The other heavily used IP addresses showed similar characteristics. What I found particularly interesting was the following pastebin link I stumbled across when Google searching those IP addresses. It was posted on February 28th, and contained three of the proxy servers that the carders used.

The IP address I have the most questions about though was 193.105.134.54, which is a Swedish IP where eight of the users connected from. I couldn't find any past abuse originating from that site. When looking at the user-accounts/e-mail addresses associated with those IP addresses, another interesting thing popped up. The user "Risking", didn't have an associated password hash/user account listed in the writeup. My guess is that the hackers dumped the hashes fairly early on, (probably around May 5th), but didn't figure out how to grab the IP logs until May 11th. In that time the user Risking probably created a new account.

So we know some of the users were smart enough to use proxy servers. How about Tor? Downloading a list of all of the known Tor routers was fairly easy, so all that remained was to compare them to the IP addresses in the writeup. All in all, there were 20 unique IP addresses that matched known Tor IP addresses. That's actually a lot lower than I expected. Of course the question then is, how were a majority of users connecting to the site? Smaller proxy servers? Public cyber-cafes? Starbucks? Their neighbors wireless? Were they really dumb enough to connect from their home accounts? I don't know the answer to that, but hopefully someone with more experience investigating blackhat forums will post their analysis/experiences on the subject.

So that about does it for IP addresses today. The database containing all of the downloaded messages looks like it also contains IP addresses too so I might revisit this subject soon. The next topic: An analysis of the hacker's password cracking attacks against carders.cc.

They'll Let Anyone Graduate: My Password Cracking Dissertation

2010-05-12T13:16:00.000-07:00

You've all heard me complain/stress out about writing my dissertation, so now that it's done of course I'm going to post it online. My PhD. dissertation, "Using Probabilistic Techniques to Aid in Password Cracking Attacks" is available for download from my tools page here.

A lot of it is going to look fairly familiar if you've seen my talks or been reading this blog, which makes sense since my dissertation is a summary of what I've been up to for the last three years. Here's a quick breakdown of what's in it:

Chapter 1:

Overview + background info
The need for password cracking
General terms and techniques
Obtaining the datasets, and basic statistics about the datasets
A quick survey of common password hashes and popular password cracking tools

Chapter 2:

Brute Force Attacks
95% of it I've talked about on this blog before
The remaining 5%, which I really should post an entry on, is a comparison of a targeted brute force attack against a pure Markov attack. The targeted attack uses the tool I previously released, MiddleChild.

Chapter 3:

Dictionary Based Attacks
Summary of some of the custom dictionaries I've created plus tools. Most of the tools are available in various places on my tools webpage.
Mostly this chapter focuses on the use of a customized edit distance metric for evaluating the effectiveness of input dictionaries, which is something that I've found incredibly useful.
Being a total of nine pages long, this is the chapter I feel is the most incomplete. It's also why I'm glad I have a blog so I can rectify that shortcoming over the next couple of months with additional posts ;)

Chapter 4:

Dictionary based Rainbow Tables
For the complete AV experience, a video of me talking about this at Shmoocon is available here.
Quick note: I've since figured out that the higher number of collisions caused by the dictionary tables was due to the fact that I was comparing them to "perfect tables", aka ones where all of the merging chains had been removed. If I remove merging chains from the dictionary tables, they perform just as well, collision wise. The fact that I didn't realize this when I was running the tests is a bit embarrassing. #facepalm
I have a bunch of ideas on how to further improve my tables, such as adding targeted brute force support, (with Markov Models!!), and enhancing the basic dictionary attacks with more advanced word mangling rules and multiple dictionaries. Implementing those is very high on my todo list.

Chapter 5:

Using probabilistic context free grammars for password cracking
Instead of focusing on the word mangling rules, focus on the probabilities instead
The result is a password cracker that can be trained on previously disclosed passwords and generates highly targeted guesses
This is the heart and soul of my dissertation and the reason why I graduated. If you only read one chapter this should be it.
Why should you care: It cracks more passwords with fewer guesses. What's not to like?

Chapter 6:

A critique of NIST's use of entropy as a password strength measurement
Essentially a very rough draft of the paper I submitted to the ACM CCS conference on the effectiveness of different password creation policies. I started running the tests/writing this section about two weeks before I defended, so I've collected a lot of data since this chapter was finished.

Sot that's about it for three years worth of work. It's a bit humbling I have to admit, since there's still a ton of stuff I still want to look into/implement. Luckily, just because I graduated doesn't mean I have to stop my research. Here's looking forward to the future.

E-mail Address Change

2010-05-12T13:11:00.000-07:00

Since I'm graduating, I was informed that I might not be able to keep my weir@cs.fsu.edu e-mail address. I'm trying to see what I can do to hold onto it, but for the time being I'd recommend e-mailing me at reusablesec@gmail.com.

Optimizing JtR's Single Mode Follow Up

2010-04-24T18:50:00.000-07:00

Over at the John the Ripper mailing list, (I'm sure you already belong to it right?!), SolarDesigner, the creator of JtR, raised the following question about the re-ordered Single Mode rule-set I released last night.

It is not clear whether you have full (or any) separation between your training and test sets when you re-order the rules. (You do say that you have such separation for your "UnLock" test, but that's another one.) In other words, the improvement from "Original Single Rules" to "Edited Single Version 2" that you've demonstrated might be partially attributable to you training (re-ordering) the rules on the same set that you later test them on.

It's a valid question and it's something I've worried about myself. Referring back to my original post:

For the target set, the RockYou list seemed like an obvious choice. I actually used a subset of the RockYou list of one million passwords I designated for training purposes, (that way I'm not testing/training against the same passwords).

I should have written more about my methodology. Basically the RockYou set represents a huge number of passwords, (over 32 million of them). One of my concerns though has always been over-training my password cracking techniques. As Solar pointed out, you can easily create a highly optimized set of rules that crack one set of passwords extremely well, but performs poorly against everything else. To avoid that, and to get the most use out of the RockYou list, I decided to follow typical machine learning practices and split the list up into one million chunks of passwords. To ensure the same password doesn't end up in different lists, I first randomized the full list by using the GNU shuf tool, and then divided the list into 32 sub-lists containing one million passwords each. I refer to these as the Rockyou1-32 lists. So far I have designated five the sub-lists as test lists, RockYou_test1-5, and five of the sub-lists as training lists, Rockyou_training28-32. I've been assigning them at the end of the spectrum and moving my way to the middle so I don't get confused which one I used for training vs. testing. The remaining lists I'm saving for future tests, so that way I don't "taint" them with my experiments.

Still, since some users had multiple accounts on RockYou due to the way it was set up, it's highly possible, (if not almost certain in some cases), that different passwords from the same user might appear in both a training and a test set. That's also why I would love to get my hands on the original list that included usernames so I can make sure that this doesn't happen. Since there is bound to be some "cross-pollination" though, it's a very valid concern that tests trained on one of the RockYou training sets, and tested against one of the RockYou test sets contain unfair knowledge and don't accurately represent real password cracking attacks.

All the experiments I've run so far have indicated that the above isn't a major problem, but rather than take my word for it, Fig 4.1 shows another round of tests comparing the original single rule-set vs. the reordered rule-set I released the other night. The input dictionary remains the same, (dic-0294), but this time they are both attacking the phpbb.com list.

Figure 4.1:

In the above test, the rearranged version on the Single rule-set performed better, but this time to a much lesser degree. I then ran the both of the attacks against 33k passwords from the MySpace password testing list, (considering the MySpace list was the first set of real passwords I collected, it also was split into a training and test list each containing around 33K passwords). The results of those cracking sessions can be seen in Fig 4.2.

Figure 4.2:

This time the results are much more dramatic over the first 500 million guesses, with the modified ruleset performing significantly better. So now we've seen against three different sets of English website passwords, (the RockYou_test1 list, the PhpBB.com list, and the MySpace test list), that the re-ordering of the single mode mangling rules cracked as many, if not more passwords over the first 500 million guesses compared to the original rule-set.

If you are interested in downloading the modified rule-set, you can still grab it here. To use it, just enter the command line option "rules=Modified_Single".

Optimizing John the Ripper's "Single" Mode for Dictionary Attacks

2010-04-22T19:00:00.000-07:00

While I've been doing a lot of analysis, I figure it's been a while since I actually released anything. That obviously needs to change. As one small step in the right direction, I decided to optimize John the Ripper's "Single" mode word mangling rules for use in normal dictionary based attacks. If you don't want to read through the rest of this post on my methodology, you can grab the new rule-set right here. To make use of it in a cracking session, simply enter the flag:

-rules=Modified_Single

For a more detailed explanation on what I did, please read on.

The Problem:

First of all, did you know that starting with John the Ripper version 1.7.4 you can have multiple rulesets in the same john.conf config file? Also SolarDesigner added a several new mangling rules, (such as the ability to insert/append whole strings), and increased the speed at which the mangling rules generate guesses. I know the current 1.7.5 branch is still not considered the stable version, but if you are using John the Ripper, I highly recommend upgrading to it.

Perhaps the biggest change from a research perspective was that the single mode ruleset can now be used with normal dictionary based attacks. Let me back up and quickly summarize John the Ripper's three default modes:

Single Mode: Originally designed to only work with the GECOS field information, (mostly just the username + full name of the individuals who the password hashes belong to); Think of it as a dictionary attack with a large number of word mangling rules but a very small dictionary. This is the default first attack that John the Ripper runs.
WordList Mode: Your typical dictionary based attack. The default John the Ripper mangling rules were designed to finish very quickly, so they are highly optimized, but only produce a limited number of guesses, (on average around 40 guesses a word -not a scientific number, but more of a general guesstimate). This is the default second attack that John the Ripper runs.
Incremental Mode: An "intelligent" brute force attack. What John the Ripper falls back on if nothing else works.

One problem I've always had in my research was finding an "honest" comparison when evaluating dictionary based attacks. In the professional password cracking industry, people are very reluctant to disclose their custom mangling rules. That pretty much left me with just John the Ripper's default wordlist mode. The problem was, even with a larger input dictionary, the default rules don't generate very many guesses, (For example, there is no rule that will try all two digit numbers at the end of a password guess). This made comparisons against longer cracking sessions quite difficult since I didn't have anything to compare my methods against. While I could always design a longer set of mangling rules myself, that becomes a little "iffy" from a research perspective. Aka how do people know that I put forth an honest effort to make a fair set of mangling rules vs intentionally creating mangling rules that perform horribly in order to make my own cracking techniques look better. Single mode helps solve this problem since now I can model longer password cracking sessions against an "industry standard attack".

This also helps a majority of the users of John the Ripper who don't want to create their own word mangling rules. Since for simple password hashes such as MD5, the time it takes for the default wordlist mode to finish generally is measured in minutes, (if not seconds), depending on the input dictionary, the ability to use single mode rules allows people to run more extensive dictionary based attacks before they are forced to fall back to incremental mode.

The problem is that the single mode ruleset was designed to work with usernames, not dictionary words. This means the order in which it tries guesses is not tailored to most input dictionaries. As an example of that check out Fig 1.1 of a password cracking session using the single mode rule-set and the dic-0294 input dictionary, (around 860k words), run against a list of one million passwords selected from the RockYou dataset divided by minimum password length. Note: The cracking session was limited to 1 billion guesses.

Figure 1.1:

BTW, you'll probably be seeing this graph in a later post as well...

The thing that really stands out is that the cracking session looks like a series of steps. What this means is that some effective mangling rules are not being tried until later in the password cracking session. While this still isn't a huge deal if fast hashes like MD5 are being attacked, it does become an issue if more computationally expensive hashes are targeted. In short, you want to front-load your cracking session to crack as many passwords as quickly as possible.

The Solution:

Basically, I set out a modest goal for myself. Reorder the Single mode rules to make for a more optimized dictionary based cracking attack.

The first problem was identifying how effective each mangling rule was. To do this I inserted a new mangling rule after each mangling rule in JtR's single ruleset. That rule is as follows:

A0"THISISABENCHMARK!!"'I

All it does is delete whatever word that was supposed to be printed from the input dictionary and outputs "THISISABENCHMARK!!" That way I can easily tell when a new rule is started. Admittedly, depending on the size of the dictionary, several million of these debug lines may be printed but that's easy to deal with.

After that is was simple a matter of modifying my verification program to take input from John the Ripper, and keep track of 1) How many passwords each rule cracked, and 2) How many guesses each rule generated. This lead to a passwords cracked per guess metric:

passwords_cracked_per_guess = (#_of_password_cracked) / (#_of_guesses)

In the future I'll probably normalize the equation so the metric is independent of the number of passwords in the training set being attacked. For now though it doesn't really matter. One other minor point: I reset the password list with each new rule. That way a single rule won't mark the same password being cracked twice, but if two different rules would crack a password, they both get credit for it.

After that, the next question was which input dictionaries and password sets should I tailor it to. As you can imagine, both of those choices can make a fairly large impact on which rules are considered the most effective. For the target set, the RockYou list seemed like an obvious choice. I actually used a subset of the RockYou list of one million passwords I designated for training purposes, (that way I'm not testing/training against the same passwords). For the input dictionary I was very tempted to use one of my custom ones, but I actually settled on using dic-0294 instead since that's readily available and most likely represents the type of dictionary a majority of people are going to use.

After that it was pretty straightforward. Run my cracking session against the training set, evaluate how effective each rule was, and then re-order the rules. The results of using the reordered rules when cracking one million test passwords, (different from the training passwords), from the RockYou list can be seen in Fig 2.1.

Figure 2.1:

So as the results show, while the modified version of the single rules starts out slightly better, the original version cracks more passwords in the first one billion guesses .... Wait, What!! That wasn't supposed to happen.

While eventually both rule-sets will crack the exact same number of passwords, I certainly expected the modified version to perform much better over a majority of the cracking session. At first I thought it might be some differences in the training/test password sets, but quickly discarded that idea as one million passwords should be enough for the law of large numbers to come into effect. Looking into it more I quickly discovered that the problem was with my replacing cracked passwords between each different rule when calculating the passwords cracked per guess. The way that the rules and the input dictionary interacted creates a huge number of duplicate guesses. For example, both 'password', and 'Password' are in dic-0294. Therefore the guesses 'Password', 'Password1', 'Password2', etc are created twice, once when trying the words with no capitalization, and once when the first letter is capitalized.

Duplicate guesses are a fact of life when performing most dictionary attacks. While there are ways to minimize them, the benefits of having a pre-mangled input dictionary can sometimes be quite high since it can allow you to crack passwords with context sensitive mangling rules, such as 'passWord', much faster. The reason I'm writing about the above test, (vs. just sweeping it under the rug), is I feel even a failed test can provide a lot, if not more, information than a successful test. That's why I love science.

So the next step was to re-run my calculations, but this time without performing replacement of cracked passwords between different rules. Ideally I should have done this several times, (re-ordering the rules, and recalculating their effectiveness), until a local maximum was reached, but I was lazy and just did it once. The results of running these re-ordered rules andt the original single rule-set against the RockYou test list can be seen in Fig 2.2:

Figure 2.2:

OK, this time the results turned out how I expected it to, with the modified rule-set performing as well as or better than the original single rules. That being said, I think this highlights how much credit should go to SolarDesigner for his work creating the original Single rule-set, since the improvement, while noticeable in the first 500 million guesses, was not overly dramatic. To improve the cracking effectiveness even more, changes would need to be made to the individual rules, vs. just re-ordering them.

As a preview of the probabilistic password cracker I've been working on, currently called UnLock (though I'm desperately looking for a new name since that sounds a bit presumptuous), Fig 3.1 shows it attacking the RockYou test list using the same input dictionary dic-0294. Also, since UnLock allows you create rules by training it on disclosed password lists, I trained this attack on the MySpace password set, which actually wasn't ideal since MySpace required users to include one non-lowercase letter in their password.

Figure 3.1:

Finally, I'll talk about this more later when I write a post on using modified edit distance to evaluate input dictionaries, but the estimated maximum number of passwords possible for Dic-0294 to crack when compared against the RockYou training list was 60.59%. An attacker would achieve that if they tried every combination of case-mangling rules, common letter replacements, combining two words, and appending/pre-pending numbers + special characters. Aka '7123PaS$w0rd$@12' would be included, even though no real life cracking session would likely every create that guess.

State of the Blog: April Edition

2010-04-05T14:42:00.000-07:00

*Comic courtesy of http://www.phdcomics.com/

Well, it looks like after three years of work, I did it. I'm still putting some last minute touches on my dissertation but once that's finalized I'll post a copy. The crazy thing is that after going through all of that, I'm actually more motivated to do research.

So that leads us to this blog. Don't worry, it's not going away. In fact one of my prerequisites for any new job I get is that I need to be allowed to keep on updating here. As far as posts go, I'm going to be shifting away from brute force attacks and start talking about dictionary attacks instead. I know, I've maintained this blog for over a year and I'm only getting to that now...

Let me explain:

1) I'm lazy

2) My main area of study has been designing new ways to represent how people create passwords using probabilistic context free grammars. At it's heart this approach is an improvement to standard dictionary based attacks, though I'm currently expanding it to incorporate brute force attacks as well. What it really is though is a fundamentally different way of looking at a password cracking attack compared to traditional rule based methods. This has lead to a bit of a problem when talking about traditional dictionary attacks though. Creating a new 10,000 rule John the Ripper config file just doesn't hold that much appeal to me -ed note: yes it does. Ok, what I should say is that it's hard for me to put my full heart into that when all my experiences using probabilistic grammars have been so superior. The issue though is that I've been struggling with a way to convey why they're useful beyond the fact that they can crack more passwords with fewer guesses than traditional methods. Hmm, actually that might work...

Probabilistic Context Free Grammars: More passwords cracked - Fewer Guesses

You can see an older version of it here, though currently that's about a year out of date. Refer to point #1 above. What I really need to do is clean up a newer version and post it online. Right now it's full of debugging code, the user interface is almost non-existent, and the case-mangling algorithm looks like it was written by the lead developer of Windows ME. But it does crack passwords.

I expect the next couple posts will probably follow along the lines of:

A survey of existing dictionary based attacks available in current password cracking tools
Optimizing JtR's single mode rules for longer password cracking sessions
Using Edit Distance to reverse mangle passwords
The limits of rule based attacks - Alt title: 2 million rule config files are a real pain
Releasing a new version of my JtR config generator - Only one year after I said I would. Refer to point #1 above
Probabilistic password cracking

That doesn't include all of the other topics I might post about depending on my mood. For example, I really tempted to do a detailed write-up of all the cloud based password cracking options available. Interesting times.

Paper Keys and Me Wearing the Dunce Hat

2010-03-19T22:40:00.000-07:00

When I said you could ignore this blog for the next couple of weeks, little did I realize how true that would be. I know this is the internet where no-one is ever wrong, but I'd like to retract some of the statements I made in the previous post about Safeberg's use of paper keys. As I said before, I won't always be right, but I will try to correct myself when I am proven wrong.

My real failure was that I didn't take the time to perform the proper research. That's why I wasn't planning on posting anything in the first place. But then I saw pictures like the one below, and just about every, "Someone is BSing me" alarm I had went off. Hence the angry post.

While some of the underlying points I made were factually correct, I had in my mind that Safeberg was selling standard file encryption software like Truecrypt. Instead they provide file storage and recovery. That's a pretty big misunderstanding on my part. The reason why that makes a difference is the threat models they fall under, and the people who would end up using them.

With normal file encryption the main worries are A) I lost my laptop, or B) The cops kicked down my door and took my laptop. With file backup though, your major worries are a hacker compromising Safeburg's website and grabbing your files, or a hacker breaking into your account and downloading your files. As for the userbases, well with file encryption you're talking about reasonable tech savvy people, or enterprise users who can be trained. With file backup, you're including the general public.

The important thing to remember is that since Safeburg is using PKI, not only are they encrypting your files, but they are encrypting them in a way that only you have access to the key to decrypt them. That's huge. Aka if Safeburg's website gets completely p0wned, an attacker still can't decypt your files. Also, even if an attacker guesses the password to your account, they don't have the private key to decrypt any of the files they download.

As I stated in my original post though, this security is provided by the use of PKI, and public/private keys themselves. It doesn't make you any more secure though if the key is stored on a USB drive or piece of paper. That's where I forgot that everyone is not like me, (and trust me, that's a very good thing). For instance, here is a picture of me grabbing up a couple of items I could store a private key on that I had lying around my desk:

Note, the above doesn't include an old palm phone my roommate was going to throw away, my voice recorder, my slide clicker, or about 10 other usb drives I've picked up over the years. Also, I just wear my defcon speaker badge around all the time. There's no way you could store a private key on it ;)

Most people don't have a modded defcon badge or for that matter a spare usb drive. Even if they do, how many people do you think would accidently save the key to their harddrive instead? People don't understand computers. But just about everyone understands paper records. That means from a usability standpoint, paper keys make a whole lot of sense.

I want to stress the part about PKI again. For file backup, encryption is useless if you give Safeberg the key. If an attacker breaks into their site, then they will also have access to the key. If they break into your account, then they can use the stored key to decrypt your files. The security comes from keeping the key to yourself. Also, the key has to be stored separately from the user's computer. This isn't a security feature so much as the fact that you're backing up your files at a remote site specifically because you are worried your computer is going to die on you. Therefore from what I can tell Safeberg really seems to be on the right track with this, and I should not have called what they were doing snake oil. The worst I can say is their marketing department stretches the truth a bit, but then, so does everyone else.

Paper Keys and Tinfoil Hats

2010-03-03T17:43:00.000-08:00

I know I said I wasn't going to post anything, but then I saw this craziness on slashdot and like other bad ideas I just have to share it.

For those of you who don't want to click on the link, (smart move), a short summary is that a company called Safeberg is marketing file encryption software where the private RSA key is stored on a printed out piece of paper. To decrypt your files, you just take a picture of the key with your web-cam and their software will turn it back into a digital key. You can see a YouTube video they produced about it here. No seriously, this is a real product...

How do I know this is snake oil?

It's using zany solutions to something that's not a problem
They spend all their time talking about key length

First, let's back up and talk about file encryption. I've written a proof of concept password cracker for TrueCrypt encrypted files, and I'm currently working with another graduate student to implement it using GPU processors, so this is a topic that interests me a lot.

With most file encryption software, there actually are two keys used to encrypt your files. The first key is a symmetric key used to encrypt/decrypt files with algorithms like AES, Twofish, etc. This is the key you are generating when you spend a couple minutes moving your mouse all over the screen when setting up a TrueCrypt container. Symmetric encryption algorithms are almost always used due to the speed/computation power required to encrypt and decrypt large files. In Safeberg's product they actually use a 192 bit AES key.

The second key is used to encrypt the file header for the encrypted files. The file header contains a lot of important informations, (such as file length, information about the individual files, checksums, etc), which is depended on the encryption product being used. The encrypted file header also contains the previously mentioned file encryption key. When a user decrypts the file-header, the encryption program extracts the file encryption key and then uses that to decrypt the actual files. There's a couple of reasons why these two keys are separate:

First, this allows a user to easily change their password, or specify a new public/private key pair. If only one key was used, then when a user changes their password all the files would have to be re-encrypted. That would really be a pain for applications like full hard drive encryption. With two keys though, when a user changes their password all the program needs to do is recreate the encrypted file header.

Second, having two keys allows for an administrative recovery key. Basically a second copy of the file-header is stored but encrypted with a master administrative key. That way the user can change their password; the user doesn't have to tell their sys-admin about their password; but when the user forgets their password the files can be recovered. This feature is VERY important in a corporate setting.

The file-header can actually be encrypted in many different ways. If a human-generated password is used, that password is then hashed, and the resulting hash is then used as the key for the symmetric encryption algorithm. For example TrueCrypt uses the PBKDF2 framework available in RSA's PKCS #5 v2.0 standard to hash a user's password and turn it into an AES, TwoFish or Serpent key. Asymmetric encryption can also be used to decrypt the file encryption key. In this case, the file encryption key is stored in something resembling a certificate, but in this case the certificate is encrypted with the public key. That way the user can decrypt the certificate when they enter in their private key. This method is used by default both by Microsoft's BitLocker, and apparently Safeberg's product as well. TrueCrypt and PGP can also use asymmetric keys.

I'm not going to go into the whole human-generated password vs. public/private key debate. It's sufficient to say they both have their advantages/disadvantages. Luke O'Conner has a couple of great posts on using human-generated passwords to generate symmetric encryption keys here and here if you are interested. What is relevant to this post though, is that if a private key is used, it needs to be stored on some sort of media separate from the encrypted files. Traditionally this is a usb thumbdrive, but smart-cards are another popular option. All Safeberg is doing is storing the private key on a piece of paper instead. This isn't rocket science since you can represent a 4096 private key using a string of 683 characters composed of lower/upper/digits+2 special characters. This post is already over 4,500 characters at this point so this could be my clever private key right here ;).

The question then becomes, how much safer are you using a piece of paper to store your private key vs a usb drive? This is where my imagination fails me. Short of some crazy spy situation, "I print the key as a pattern on the inside of my shirt so the border guard doesn't suspect a thing" I can't think of a single use-case where printing the key out on a piece of paper would provide you any additional security. And that's why this idea is physically hurting my brain. At least with a usb, it is easy to encrypt it was a human-generated password so now you have two-factor authentication:

Something you know -the password
Something you have -the private key on the USB drive

Also, it's been my experience when people start talking about weird/zany things like printing out keys on paper, they often forget to focus on the fundamentals when it comes to file encryption. For example, how do they store the file encryption key in memory? How do they ensure the file encryption key isn't saved in a page-file? Well, you get the idea. Their product may actually be secure, but I wouldn't trust it without it going through a lot of independent testing beforehand. In short, snake-oil.

Edit: I just viewed this video and apparently their products mostly focus on encrypting online file backups. Now I'm really curious about what other online backup companies do... Also upon further reflection I might have been a bit too harsh since while paper keys might not be a security feature, they could be a very strong usability feature. That being said, since they are marketing it as a security feature I'm going to leave the above post as is.

Just a FYI

2010-03-01T19:19:00.000-08:00

I apologize for the lack of actual posts. Right now I'm facing several fairly strict deadlines when it comes to graduating, so you probably can ignore this blog for the next two weeks or so. I know, it's annoying for me too because from real life spies caught on camera, to a new WPA attack, there's a few things to blog about...

For now though, it's LoLcats and funny comics 24/7

Netscape won't save you now...

2010-02-17T03:08:00.000-08:00

Click on the image to get the full comic, or better yet check it out at its original location. Courtesy of http://www.overcompensating.com/

Spies, Buried Treasure, and Crypto: What More Do You Want?

2010-02-12T11:59:00.000-08:00

Wired has a very interesting article talking about the FBI's investigation into the case of Brian Regan, who tried to sell a bunch of classified documents to foreign governments. Here is a link.

The most interesting thing that I took from the article is that either A) The NSA was unable to crack a simple Caesar Cipher (ROT25), or B) they just didn't bother to share the results with the FBI after claiming to make no progress. Honestly I don't know which option would be better...

Even More Markov Modeling: What's in a Probability?

2010-02-10T15:45:00.000-08:00

I've twice gotten into heated debates, (and I remember the count since I still find it weird that I've gotten into arguments about this), that there is no universal letter frequency probability values for the English language. Both times I stumbled into this argument by answering the question, "So, do passwords match letter frequency analysis of the English language as a whole", by replying, "Well, it depends on what training set you use to calculate the probabilities of the English language, but for the most part, yes". In reality I should have just said, "For the most part yes..."

Letter frequency analysis, and its big brother Markov models, depend entirely on their training sets. This means while different training sets may share common characteristics, there is no one LFA, or Markov set of probabilities that perfectly model the English, (or any other), language. But what about those tables Wikipedia posted? Well, they are based on a study in 1948 by Herbert Zim, who analyzed several American books like Moby Dick, along with a collection of poetry. It was a fairly impressive effort considering he didn't use a computer so I really feel sorry for his graduate students at the time. Reading Moby Dick is hard enough without having to keep count of the number of times the letter "i" is used.

For whatever reason, Moby Dick is still one of the most popular training sets of the English language today. For examples of that, check out these intro to cryptography lecture slides from both Stanford and Colombia University. The question is, does Moby Dick represent the English language as a whole? Well if you compare it to Twitter posts, you are probably going to notice some differences. I may be out on a limb here, but I'm going to guess that Melville didn't use as many emoticons and tinyurl's as your average Twitter user ;)

The next response then is to collect as many examples of English literature as possible and analyze the entire set as a whole. Poetry, novels, wikipedia posts, Webster's dictionary, web pages - they all go into the pot. The problem then is that the target set you are really interested in might get buried under all other chaff. On a side note concerning that last link: the ladders must be an attractive site to hackers. A huge collection of personal information, including passwords, resumes, job history, e-mail addresses, etc, of people who are earning 100k, and are slightly gullible. No, that's not worth anything....

So finally to the reason of this post. The same caveat that there is no universal best set of probabilities to use also applies to password cracking. This means there is no .chr probability file for John the Ripper's incremental mode, (or .stat file for Markov mode), that is the best for all situations. That's why it's great that Minga released a custom .chr file trained on the RockYou password set. The original post he made on the John the Ripper mailing list can be found here, and the most updated copy of the .chr file can be downloaded from his website here. John the Ripper's default incremental .chr file was originally trained on mostly Unix passwords. What Minga's custom .chr file does is provide us with a probability set that is targeted against web site users. The question then becomes, how effective is using the RockYou .chr file against other website passwords? Oh, boy it's time to make some new graphs ;)

Test 2.1: Testing various .chr files using John the Ripper's Incremental mode against a subset of the RockYou password list

Full disclaimer: This test is not fair! You almost never want to train/test against the same dataset. It's like stealing the teacher's answer key the night before a big test. That being said, I was interested in just how much of an improvement an attacker would receive by training and testing against the same set. Also, Minga actually created two .chr files. The first one was not trained on duplicate passwords, (aka '123456' was only counted once). The second set, (which is the one now available for download), did count duplicate passwords, (so '123456' appeared several thousand times in the training set). That can have a dramatic impact on the resulting probabilities. I figured this test might demonstrate which approach is better and if so, by how much.

As far as the actual test construction goes, I selected a random subset, (using the GNU shuf command), of one million passwords. This was to add some randomness into the test set so it wasn't an exact duplicate of the full RockYou list. I then ran the original non-duplicate Rockyou list, (Minga_RockYou1), the second RockYou list trained on duplicates, (Minga_RockYou2), John the Ripper's default All incremental mode, (Default_All), and a training set based on passwords from the Phpbb list, (Phpbb) for one billion guesses each to see how many passwords they cracked. I selected the 'All' subset for the default attack even though "Alnum" would perform better over the first billion guesses simply because the RockYou and Phpbb .chr files included uppercase, and special characters. If I find the time, I might create some special .chr files using those datasets that only include lowercase letters and numbers in the future and then re-run these tests.

Results:

Analysis: As expected, the second publicly available Rockyou .chr file available from Minga performed the best. I decided to to add some additional data to the graph since total passwords cracked tends to leave out the fact that as a password cracking session goes on, it takes many, more guesses to crack each additional password. Aka, cracking 42% of the test set represents a much larger accomplishment than cracking 40% of the set. To that end, I added vertical lines representing when each of the other modes cracked as many passwords as JtR's default mode. As you can see, the PhpBB trained attack cracked the same number of passwords with less than half of the guesses the Default mode required.

Test 2.2: Testing various .chr files using John the Ripper's Incremental mode against the PhpBB.com list

Same attack setup as last time, but now we are attacking the phpbb.com list that was released about a year ago. Once again, since the phpbb .chr file was trained on this list, it's not a fair test, but at least we can see how the RockYou trained .chr file fares against JtR's Default .chr file. Also, I'm only using the more recent RockYou list since it performs better than the first version.

Results:

Analysis: As expected, the phpbb training did the best. What's notable though was that the RockYou trained attack also performed significantly better than John the Ripper's default probabilities. Combined with the previous test, this implies that the passwords from the two different sets share a lot in common, and that they also differ from Unix passwords. This leads us to the next test...

Test 2.3: Testing various .chr files using John the Ripper's Incremental mode against the Faithwriter's list

Faithwriter's was a Christian website that stored its passwords in plain text, and was broken into and publicly posted online by the 4chan Anonymous crowd. Let's see how it does using the same three training sets from the previous test.

Results:

Analysis: Wow, it looks like web-based passwords do share a lot in common. This was the first fair test where the test set was completely separate from all three training sets. Once again, the Phpbb, and RockYou trained attacks continued to outperform the default JtR trained attack. It's interesting to note that the RockYou set did the best, so there are differences between web-using groups. I would imagine that the Phpbb users tended to skew older and more computer literate, (it was a development website for the Phpbb forum software), than the RockYou users. This isn't a knock against the FaithWriter's users, but I'm just pointing out that bloggers, (from the RockYou set), and writers, (from the FaithWriters set), might share similar characteristics.

Test 2.4: Testing various .chr files using John the Ripper's Incremental mode against the MySpace list

To end this post up, I figured I might as well run the attacks against the grandfather of all disclosed password lists, the MySpace list that showed up a few years ago. This list was the result of a rather clever phishing attack where the attacker failed to password protect their drop-box, (ironic, I know). What makes this list special is that it was one of the first publicly disclosed password lists and you still see it mentioned a lot in password analysis papers. More importantly, since the RockYou list included MySpace users, this seems like the very definition of an overlapping user-base. Aka, if you are attacking a MySpace user, how much of an improvement should you expect to get using the RockYou probabilities, vs. the Default or Phpbb probabilities?

Results:

Analysis: At first glance it may appear that all of the training sets did poorly, but it's important to note that MySpace has a password creation policy, (at the time of the attack, passwords had to be at least six characters long and have one non-lowercase alpha symbol), and there is a lot of non-passwords in the list due to people telling the phisher what they really thought about him/her. Therefor you wouldn't expect a brute-force style attack to perform as well. As you can see though, the RockYou trained attack performed significantly better than both of the other attacks.

Conclusion/Notes: What I really need to do is run some additional tests since I feel that the current slate of tests above unfairly shows the default John the Ripper probabilities in a bad light. What would be nice would be to run the same attacks against passwords from computer log-ins, (both Windows and Unix/Linux). I would expect the default John the Ripper .chr files to perform much better in that case. The problem is I don't have very many passwords like that due to the nature of my research, (I collect passwords that are disclosed publicly online). Basically I have more MD5's, Sha1, Phpbb3, and Vbulletin hashes than I know what to do with, a couple of LanMan, (old Windows Login hashes), and a very small scattering of other password hashes, (NTLM, Cisco, Crypt3, etc). I've been archiving posts from hashcracking forums so the next step is to sift through them for examples of other log-ins. They won't be part of some nice data-set, but it will give us a better idea of how people create passwords for a computer log-in vs. a website log-in.

In conclusion, if you are auditing website passwords, you should probably use the .chr file Minga provided when you run an incremental attack using John the Ripper.

Shmoocon Bound

2010-02-05T01:59:00.001-08:00

Leaving sunny, warm Florida for DC. What am I thinking... Ah, yah Shmoocon. I'll probably be wearing my FSU hat if anyone wants to grab a few drinks, (I know the picture on the side of the blog isn't very good for identification purposes).

Out of Context Graph Challenge #1

2010-01-30T21:02:00.000-08:00

I'm struggling with the best way to graph some new data I just analyzed based on the RockYou list. Since I'm also too lazy to write up a full post on it right now, I thought I might as well throw it out as a challenge to the five or so people who read this blog. I'll buy a beer for the first person who can correctly state what the following graph shows.

The beer is redeemable at any conference I happen to meet you at, (For example: Shmoocon). Here are a few hints:

It is based on a subset of one million passwords from the RockYou set
It has to deal with a project I am working on
There is one word you MUST include in your submission for it to be valid

Answers will only be accepted in the comments. This contest will run until someone gets it right or I actually get around to writing a post on this. Imaginary bonus points are applied if you have any suggestions on a better way to graph the data.

More Analysis of the Rockyou Password List - Strong Passwords

2010-01-26T17:50:00.000-08:00

So it's been an interesting last couple of days. First of all, it's a bit amazing how popular the Rockyou list has become after it was mentioned in the New York Times article. While I'm not going to provide a link, let's be honest, if you can't find it, you are not looking. The thing that keeps going through my head is that we may have just narrowly missed having a black swan event, (Ok, Mr. O'Conner just posted about those in his blog so the term is stuck in my head, even though I'm using it wrong.) Can you imagine what would have happened if the public RockYou list had contained e-mail addresses? While lists of this size have been distributed before, (and black hats have been able to obtain the whole list + email addresses), I really don't know what a public disclosure of a list this size containing e-mail addresses and passwords would be like. It probably won't lead to an internet apocalypse, but we would have people looking up friends/co-workers. The 4chan crowd, and associated griefers would of course get involved. How would sites deal with locking accounts/resetting passwords? When the Hotmail + various other passwords were leaked back in October, e-bay/webmail providers/etc had a hard time dealing with even 30k leaked passwords. Will secret questions be enough to re-verify people? What if the secret question answers from the hacked site are disclosed as well?

As I was joking with someone else, "Does the security of the Internet really depend on Facebook not getting completely 0wned?"

Ok, the above is overly pessimistic - but an event like this is going to happen, and I feel we as a security community need to start planning how we're going to respond instead of just making stuff up as we go along. I certainly hope Microsoft/Google/Banking websites/etc, have a coherent plan on what to do anyway.

So enough doom and gloom, on with the analysis. I was shooting e-mails back and forth today with Per Thorsheim about the Rockyou dataset and we both pretty much agreed that as great as 32 million passwords sounds, it's very hard to draw conclusions from the set since we know so little about it. In fact, he has a good writeup of the problem plus analysis of Imperva's white-paper which he posted here.

Basically the list gives us 32 million values. Are these values real passwords? Well there's numerous URL's included in the list, (several that are over 100 characters long and contain search strings for Rockyou applications). In fact, I just did a search using awk and came up with 684 passwords that were longer than 100 characters. Should we count those as legitimate passwords? How about 484 passwords that were only 1 character long? How many of the passwords are from the same person? What password policies were in place at the different sites? Why am I asking so many questions in this post?

So yah, I'm struggling to make sense of it all. Now on to some answers instead of more questions. Per wrote:

Regarding your own analysis of the RockYou password list as well as the analysis done by others, what strikes me is the "negativity" of the results. I had a long chat with a colleague/friend of mine who is also assisting me in my various analysis, and we agreed that we wanted to know a little more about the positive parts of the RockYou list..

He then went on to ask some specific questions. Once again I have to agree with him. The interesting part of this list isn't that thousands of people used '123456' as their password. We already knew that. The tougher passwords, now that's interesting.

Q) What's the longest password found? (# characters)

A) As I mentioned, that's hard to say since there's a lot of really long values in the list that probably aren't passwords as we consider them in the traditional sense. Excluding passwords with non-ascii characters, (they gave awk a bit of a problem since it counted them as two or more characters), I found 27,337 passwords that were longer than 21 characters long. Glancing through the results, most of them appeared real. I'll get more into their composition in the next question.

Q) What's the most complex password found? (all character groups, randomness, length etc)

A vast majority of what would be considered complex passwords turn out to be e-mail addresses. Some of them are even mangled, such as alice@example.com123. In other news, people still apparently hate using spaces in passphrases as well, (or more likely they don't realize they can use spaces). That all being said, very few of the passwords would meet a corporate password requirement, aka >8 characters, containing an uppercase/lowercase/special/digit. That's to be expected since I doubt any of the sites that rockyou collected the passwords for enforced such a requirement.

Q) Percentage of passwords longer than 8?

A hair over 30% of the passwords were longer than eight characters long. This is actually worse than the hotmail dataset where close to 40% of the passwords were longer than eight characters. That can probably be explained by the high number of rockyou only accounts in the list, (heck, 'rockyou' was the #8th ranked password). I don't know about you, but I certainly wouldn't use my A-game password there.

There still are a couple other questions I haven't had a chance to answer, but they will have to wait for another blog post.

New York Times Article

2010-01-24T15:40:00.000-08:00

When I was interviewed a week and a half ago by a reporter from the New York Times about the Rockyou hack, I honestly never expected for it to end up on the front page of the newspaper, but there you go. As a friend mentioned though, it doesn't really count since it's below the fold ;)

While I'm ecstatic about being quoted, there are a few things I wish could have been changed. Just saying that makes me feel like the guy who won the million dollar lottery, but is annoyed that he didn't get the 10 million jackpot. That being said, I have a blog, and this is the internet so I might as well complain away ;) First of all, I feel the need to explain my quote. Here is an excerpt from my conversation with the reporter:

Matt's Brain: "Don't say anything stupid. Don't say anything stupid. Don't say anything stupid..."

Reporter: "I take it this is the largest password list ever stolen right?"

Me: "Well, it's the largest one ever publicly disclosed. There's been a lot of larger or similar sized databreaches in the past."

Reporter: "But this is like the mother load for you guys?"

Me: "Yes this was the mother load.'

Matt's Brain: "Doh!!! I hope he doesn't use that..."

I'm sure the reason I wasn't quoted further is because A) I'm just a college student, B) I tend to be a bit overly verbose as you may have noticed... and C) What I was saying didn't fit into the narrative he was trying to tell.

I completely agree with the reporter on part A, and B. If you have a choice of quoting the CTO of a security company or a college student, you go with the CTO. My suspicions about Part C requires further explanation.

Throughout the entire interview the reporter tried multiple times to get me to criticize users for picking weak passwords. I refused to do that because quite honestly I don't blame the users. This may be a little controversial, but for a majority of users and a majority of accounts, password strength does not matter. Let's be honest: while everyone loves to talk about online attacks, (where the attacker is trying to guess the user's password to gain access to their account), online attacks generally are too expensive, (from a time/resources perspective), to perform on all but the most valuable accounts. Online attacks are something you have to worry about if you are well known, it is a corporate account, or you hosting a publicly available server, (for the last example, one of my old co-workers got 0wned by it), but the average user doesn't have to worry about that. Phishing attacks and malware/keystroke loggers are much more prevalent threats, and the reason they are is because they can be highly automated by the attacker, (aka cheap), and they don't depend on the user picking a weak password. Aka, I could have a 50 character passphrase, but if my computer is infected by the zeusbot and is recording all my keystrokes, it doesn't matter.

Likewise, this Rockyou list shows another reason why we shouldn't blame the users. The list was all in plaintext. I don't have to crack anything. This gets to the heart of my argument. I'm not saying everyone should start using '123456' as their password. What I am saying is that the security of the system is much more dependent on the user recognizing other threats, (such as that fake security e-mail asking them to re-verify all their info), and for sites to practice better security, (hashing the lists with a salt, having a password blacklist, limiting online guesses, etc). We tend as a security community to get caught up on the fact that users pick bad passwords. What we need to do as a community is to move on and say what are we going to do about that.

At the end of the interview the reporter asked if I had anything else to say, which I responded, "If there is anything people should know, it is the importance to have at least two passwords. You can't expect people to remember a different password for every site, but this Rockyou hack demonstrates, you should use a different password for your bank/webmail vs. the password you use on facebook and other social networking sites." I'm happy the reporter phrased this much better and included it in the article. That's also the reason why only the passwords, (and not the e-mail addresses), were publicly disclosed. The passwords by themselves are not that valuable to an attacker. The passwords + e-mail address are since they allow an attacker to quickly compromise many more accounts. I'm not just making this up. In the original forum postings the attacker essentially said, "These passwords are free, but if you want the e-mail address you'll have to pay me a lot of money."

Considering my writeup is longer than the entire NYT's article, once again I'm not surprised I wasn't quoted more ;) If you disagree with me please let me let me know since as my last post pointed out, I certainly can be wrong.

One last thing. I've been getting a whole lot of e-mails from people asking me to send them a copy of the Rockyou list. Please don't take this personally, but I can't determine from an e-mail if you are a legitimate white-hat security researcher or a script-kiddie, (ok some are fairly easy to pick out as script-kiddies, but identifying the good guys is much harder to do). The answer is almost certainly going to be no.

Analysis of 10k Hotmail Passwords Part 6: Markov Model Showdown 2 - The Rematch

2010-01-24T13:07:00.000-08:00

I know, soon my titles will get so long I won't be able to fit them into a Twitter post. It was all I could do to leave off a tagline such as "Revenge of the Incremental Mode."

I just received an e-mail from SolarDesigner, the creator of John the Ripper, who promptly set me straight on a few points about how the incremental attack works. I'm going to break down the e-mail into two parts. The first part is as follows:

Matt,
In your very interesting blog post at:
http://reusablesec.blogspot.com/2009/11/analysis-of-10k-hotmail-passwords-part.html

you made some incorrect statements/guesses about the incremental mode:

"Unfortunatly it doesn't take into account the previous trigraphs that appeared before it,"

Not true.

"(except when calculating the overall probability)."

No idea what you mean here.

"For example, if the first trigraph is "auq", the next trigraph's probability isn't increased if it starts with a 'u',"

Actually, if the first trigraph is "auq", then as far as inc.c is concerned the next trigraph starts with "uq", and there's one letter to be determined.

"(even though 'u' almost always follows 'q')."

If "u" commonly follows "uq" at that character position in passwords of that length in the training set, then it will be tried by JtR early on.

"Therefore, the incremental attack doesn't measure the conditional probability between the third and fourth letter, and the sixth and seventh letter of a password guess."

That's not true. It treats trigraphs at all positions in the same way. It also has special handling for the first and the second character position, before the first trigraph can be formed, but then it just proceeds with overlapping trigraphs till the full length is reached.

"The biggest advantage of using the incremental attack is that it creates highly optimized guesses while still retaining the ability to eventually cover the entire key-space if you give it enough time."

Right, and that's probably the cause of the difference you're seeing as well. This ability is achieved by having the same number of character indices possible for each character position. This works great early on, but it might be suboptimal after a while - where it might make sense to try, say, 50 different character indices for a certain position, but only 10 for another one. This is cured to a limited extent with the "cracking order" table (which includes not only the length and the character count, but also the "fixed character index" position number), but perhaps further improvement in this area is desired.

I think you could hack inc.c such that you'd achieve results similar to those of the Markov mode. Specifically, drop expand() and adjust inc_key_loop() to remove the assumption that characters exist for all indices. It'd be tricky to skip those incomplete-info indices quickly, though - but in terms of the first 1G guesses produced (if you don't care how much time it'd take to produce those), I think you'd achieve results very similar to Markov's.

I'm very happy I was corrected about this, and I have modified my previous post to be less wrong. The original copy of my post can still be found in the comments since I do occasionally try to practice some journalistic ethics. Also, if I ever say anything else that doesn't match up with reality, please let me know. I'd rather be shown to be wrong than to remain ignorant. That's why I have a blog with comments and an e-mail address on the side ;)

Now onto the second portion of SolarDesigner's e-mail:

Another related thought I had:
When you compare Incremental vs. Markov (or the like), you could want to run through --single and at least a small wordlist such as password.lst with rules first. That would reflect the real-world case those modes need to be optimized for. It's certainly what I was optimizing for. I had slightly different revisions of the incremental mode early on that would happen to crack more passwords sooner when run with empty john.pot, but would work worse after single and wordlist w/rules; I rejected those revisions (never released).

I don't expect this change in your testing to affect your results in a major way (I pointed out another likely cause for the difference you've observed above), yet this is something for you to try next time (for both modes, indeed).

Similarly, when you compare different wordlists and different wordlist rulesets, it makes sense to do so after having run --single first (keep and reuse the same john.pot with after-single results). Again, this is what I had in mind when experimenting with the default wordlist ruleset (over 10 years ago).

That's a good point, which of course leads us to more tests:

Test 9: Testing JtR's Markov and Incremental Modes After a Simple Dictionary Attack

Unfortunately I'm not going to run --single mode first for this test. As a quick explanation, single mode uses the username/e-mail addresses/related information as a very small targeted input dictionary and then runs a large number of advanced word mangling rules against the password set. By default, this is the first attack that John the Ripper runs during a password cracking session. The reason I'm not going to run it is that I don't store the user information with the password sets I analyze. This isn't because of some secret l33t password cracking technique, but instead due to the fact that I'm trying to remain ethical and respect the privacy of the people in these lists. While I will look at username/password info initially when I get a new list so I can get a better handle on how the list is structured, I separate the info as soon as possible. That's because I don't want to know that bob@yahoo.com's password is 'Ihatemyboss'. In short, I'd rather penalize my cracking techniques than deal with those issues. I might grab the original list and run a -single attack in the future since as SolarDesigner points out, that is very useful information, but right now it's just too much of a hassle, which is the way I meant it to be.

So that disclaimer aside, the next question is how I should run my dictionary attack. To keep things simple, for this first test I used the default John the Ripper ruleset and the default passwords.lst wordlist. With that dictionary/rule combo, I ended up cracking 512 passwords from the Hotmail dataset using just 139k guesses. What can I say? It's a small input dictionary and JtR's default rules are highly targeted, (aka they are designed to finish quickly). Also, most of the Hotmail passwords are Spanish/Portuguese, and passwords.lst is and English dictionary. I'll get more into that once I finally write that post I've been promising you about dictionary attacks on this list. Just for comparison, below is a graph representing the passwords cracked using a dictionary attack, vs an incremental attack and a Markov attack as detailed in Test 8 from my previous post. Aka, both of the brute force attacks were trained on the Phpbb password set, and the Markov attack used a limit of 215 with a maximum of 8 characters.

Results Part 1:

Analysis Part 1: It shouldn't come as a surprise that the dictionary attack performed better. As I stated previously there were a lot of factors that kept it from performing as well as it would against an English based password list, (the main one being it helps to use a dictionary targeted against the language of the set. It's a complicated concept I know). That being said, notice the sharp drop off in passwords cracked. That shows the dictionary attack was able to crack a lot of passwords using no mangling rules, or just adding '1' to the end of the guess. That's partially an artifact of the dictionary, as it has many common password pre-mangled in it, such as "abc123", and the fact that many people didn't use any mangling rules to create their passwords. That's actually one of the nice things about the dictionary passwords.lst since having pre-mangled passwords in the dictionary helps the attacker crack the easiest passwords quicker. Oh, and for the Markov mode, no I didn't forget to add it to the graph. It only cracked 4 passwords in the first 140k guesses since I didn't re-target it for the smaller cracking session. As I said before, depending on how you set the limit size it takes a while to catch up to other cracking methods.

Results Part 2: Ok, so after running the dictionary attack, I then re-ran the Markov and Incremental attacks as described previously on the uncracked passwords. Here are the results - Note, I attributed the 512 passwords previously cracked to both of them:

Analysis Part 2: Well, the results are pretty much the same. This is to be expected since the dictionary attack only cracked 512 passwords, (aka the largest possible improvement would occur if all of those passwords were guesses that Markov mode tried, but Incremental mode didn't. Even that would only help Incremental mode catch up by 512 passwords). In fact, most of the passwords that were cracked in the dictionary attack would also have been cracked in the Markov/Incremental attacks given 1 billion guesses. By this I mean the Dictionary attack only cracked 28 passwords the Markov attack didn't, and 4 passwords the Incremental mode didn't. Please note, this isn't a knock against dictionary based attacks. What a dictionary attack lets you do is crack those passwords much, much sooner, which is the reason why I included the previous graph in part 1. That leads us to the next test...

Test 10: Testing JtR's Markov and Incremental Modes After a Longer Dictionary Attack

Everything pretty much stays the same as the previous test, except that I ran the hotmail list through multiple dictionaries first using John the Ripper's default rule sets. The dictionaries include the previously mentioned passwords.lst, along with dic-0294, the Spanish wordlist off of John the Ripper's ftp site, and a Spanish and Portuguese wordlist gathered off of wiktionary, (this isn't Sebastian Raveou's one though I'll get to a specialized dictionary he provided me in a later post).

Results: I'm not going to include a graph of the dictionary attack since I was lazy and didn't bother to merge the dictionaries and remove duplicate words, (I just ran each one through independently). All together they cracked 2,104 passwords from the Hotmail set. Once that was done I re-ran the Markov and Incremental mode attacks against the list. Here are the results:

Analysis: Once again, the results look pretty much the same, though this time the dictionary attack cracked many more passwords that were not cracked during the brute force attacks. In fact, this run raised the success rate of the dictionary attack + Markov mode to slightly more than 50% of the total set cracked.

Coming Up: I know interest is mostly focused on the Rockyou list right now, but I do want to continue with the Hotmail list simply because combined with all the previous analysis, I think we're getting a better view of the effectiveness of different password cracking techniques. Aka, when I finally get around to doing a write-up on dictionary based attacks you will be able to compare it to all the previous brute force methods I've looked at. Don't worry, I'll still cover the Rockyou list. It's just that I might be switching between the two lists for the next couple of posts.

From the "That's Just Not Cool" Department

2010-01-22T20:36:00.000-08:00

So it looks like a spammer managed to modify the Hackers for Charity webpage so they could put all their fake drug medication links into it. Hint, view source-code and then scroll down to the very bottom.

This does lead to some interesting observations though:

The person who did this has no idea about the webpage they were hacking. If it was a targeted hit, (think ZF0), they probably would have done some visible defacing. If it is someone just looking to make money, there's no way they would knowingly tangle with all the heat that is probably going to be coming their way soon.
Web page security is really hard. Over the last 6 months we've seen a large number of people in the security field have their webpages get hacked. Heck, even the NSA's main webpage was defaced.
What does this say about the white-hat security community? As a member of that community this drives home the point that humility is important in this line of work.

I expect that the Hackers for Charity webpage will be fixed soon so if anyone is interested in doing some additional analysis, here are two of the spammer links, (they all pretty much are the same). I also have the entire webpage source-code available on request. Note, I changed the http to hxxp, and the www to aaa to avoid further helping the links advance their Google ranking.

hxxp://aaa.oaregion3.org/events/old_files/_vti_cnf/general/buy-acomplia-online-no-prescription.html
-- Buy Acomplia Online no Prescription
hxxp://aaa.oaregion3.org/events/old_files/_vti_cnf/general/take-acomplia-cheap.html
-- Take Acomplia Cheap

Now back to writing the post I was planning to put up here...

State of The Blog: 2010

2010-01-17T23:27:00.000-08:00

I know most people normally do this at the beginning of January, but like so much else I'm running behind ;) What I really wanted to do was give you readers, (all 10 or so of you now), an update on where I'm at, my goals for the following 6 months, and why my update schedule might be kind of wacky.

Goal 1: Graduate

Yes, I have been researching password cracking since August 2007, and as much as I love college, it's time to move on to the real world. Or I hope it's time, as I still have that pesky dissertation to write. Getting that done is my #1 priority right now, and to be honest I don't know how that will impact this blog. The dissertation itself will mostly cover my work developing a probabilistic password cracker, though I'll also be covering some of my other tools such as my dictionary based rainbow tables. I'm a little ashamed I haven't posted more about my probabilistic password cracker here since I've become a true believer in it. It's just that I've kind of enjoyed using this blog as an excuse to research other things, (there's only so much time I can spend talking about parsing grammars). With every addition I make to it, it gets meaner and nastier, and quite honestly I need to take the time to clean up the latest version and post it online. Here is a quick rundown of using a probabilistic approach:

This is a way to create password guesses. Aka, it works against salted hashes and full hard-drive encryption. It's not a rainbow table, and instead is designed to work with traditional password cracking tools.
Instead of using standard word mangling rules, it assigns probabilities to the various ways people create passwords. These range from dictionary words, ('password' is more common than 'zebra'), word mangling rules, (people tend to uppercase the first letter), specific replacements/additions, (aka dates are very common), etc. It even takes into account the password length, (aka people generally make passwords between 6 and 8 characters long).
It then uses these probabilities to create very fine grained word mangling rules on the fly based on probability order. By fine grained, I mean it will literally create millions of rules if you give it the chance.
The algorithm it uses is very fast, and extremely parallelizable, which is necessary for a password cracker.
Because of this, it becomes conceptually easy to create a customized attack profile for an individual target, (or group). You can create a custom dictionary for them based on kids names, important dates, files found on their computer, and then just give those values a higher probability. If there's a password creation policy for the site? No problem, just exclude rules that don't meet it, and/or only train the password cracker on similar passwords that meet those rules. The main problem going forward with all of this has been developing the GUI believe it or not.
I'm currently adding support for brute force as well, (hence my focus on brute force techniques over the last couple of posts). This way it will automatically switch between limited brute force and dictionary based attacks depending on the current probability of the guess it is working on.

I've been running it in head to head comparisons against existing password crackers, and it has been beating the socks off of them. In short, it generally will crack more passwords with less guesses than existing methods.

Goal 2: Get Some Work Done with Pass-Phrases

This actually was the original goal of my research. The main problem up till now is I haven't had many examples of pass-phrases, (beyond the 'AliceLovesJoe' variety). With the RockYou list though, that has changed, and I look forward to adding support for pass-phrases to my probabilistic cracker. There's a couple of attack methods I plan to test, ranging from a mad-libs approach to using pass-phrase input dictionaries.

Goal 3: Finish Up Some of These Dangling Posts

Going through my archives, there's a horrible amount of posts where I started talking about something, such as the ZFO dataset gathered from people in the security community, and never got around to posting any follow-ups. I realize that's something I need to change.

Goal 4: Work on a GPU Assisted Password Cracker

Most of the work is being done by another graduate student, which means this actually might get done and be relatively bug free. I'm very excited about this, as it will help move a lot of my research from the theoretical to actual implementation where it will help law enforcement officials. We're using OpenCL right now, (I know CUDA currently is faster, but OpenCL is much more portable), and we're initially targeting TrueCrypt, (though hopefully once we get the basic framework finished we can add additional encryption types).

Goal 5: No More Public Speaking for the Next Six Months

I really need to focus on actually doing stuff vs. talking about it. I'm also cutting down on the conferences I'm attending, though I'm making an exception for Shmoocon since I love that one. BTW, anyone interested in doing the Ghost in the Shellcode competition? My hacking skills are really lame, but I still love hacking competitions.

Goal 6: Finish up my Paper on NIST's use of Password Entropy

An academic publication on the investigation of the effectiveness of using entropy to justify password creation policies. While I have a lot of preliminary data already, I don't want to spoil my objectivity by posting my initial conclusions quite yet. The hardest part is the fact that password entropy is used as an average value across the entire password set, so finding the best way to fairly map the effectiveness of a real attack against it is tricky. Aka if following NIST's calculations it would take an attacker two years to crack a password via an online attack, but I find that an attacker could crack 5% of the passwords in an hour, what does that mean exactly?

Conclusion:

It should be an interesting year ;)

A Quick Preview

2010-01-10T17:23:00.000-08:00

There's been a bunch of requests about this, so I thought I'd post a couple of screenshots of something I've been working on over the holiday break.

The RockYou 32 Million Password List Top 100

2009-12-29T01:41:00.000-08:00

But first, a quick responses to one of the previous comments, (since it really did merit a front-page post).

Tfcx posted:

The initial vulnerability was posted 29th November on a hacking forum called darkc0de here: http://forum.darkc0de.com/index.php?action=vthread&forum=11&topic=13082

Thanks, as that really helps narrow down the timeframe, (and reading that post and related posts was interesting if a bit depressing). The hack itself appears pretty straightforward once you see it, (like most things once the solution is presented to you it's easy, but finding it in the first place is hard). I'm still interested in the hacker Igigi, and have been tossing about all sorts of theories; but I'll refrain from posting them here since they are all pure WAGs right now.

Now on to the main topic: Per Thorsheim wrote:

I would like to see a comparison of Twitters 370 banned passwords against the top 370 or so passwords stolen from rockyou (http://www.techcrunch.com/2009/12/27/twitter-banned-passwords/)

Happy to oblige! To start things off, here are the top 100 most frequently used passwords from the RockYou list. I then bolded any of the passwords that did not appear in Twitter's blacklist. As a side note: Yes I do realize I need to modify my website code to allow support for expandable post summaries. Wow do I ever miss Livejournal...

Rank | Num of Occurrences | Password

--------------------------------------------------------------

1 290729 123456

2 79076 12345

3 76789 123456789

4 59462 password

5 49952 iloveyou

6 33291 princess

7 21725 1234567

8 20901 rockyou

9 20553 12345678

10 16648 abc123

11 16227 nicole

12 15308 daniel

13 15163 babygirl

14 14726 monkey

15 14331 lovely

16 14103 jessica

17 13984 654321

18 13981 michael

19 13488 ashley

20 13456 qwerty

21 13272 111111

22 13134 iloveu

23 13028 000000

24 12714 michelle

25 11761 tigger

26 11489 sunshine

27 11289 chocolate

28 11112 password1

29 10836 soccer

30 10755 anthony

31 10731 friends

32 10560 butterfly

33 10547 purple

34 10508 angel

35 10167 jordan

36 9764 liverpool

37 9708 justin

38 9704 loveme

39 9610 fuckyou

40 9516 123123

41 9462 football

42 9310 secret

43 9153 andrea

44 9053 carlos

45 8976 jennifer

46 8960 joshua

47 8756 bubbles

48 8676 1234567890

49 8667 superman

50 8631 hannah

51 8537 amanda

52 8499 loveyou

53 8462 pretty

54 8404 basketball

55 8360 andrew

56 8310 angels

57 8285 tweety

58 8269 flower

59 8025 playboy

60 7901 hello

61 7866 elizabeth

62 7792 hottie

63 7766 tinkerbell

64 7735 charlie

65 7717 samantha

66 7654 barbie

67 7645 chelsea

68 7564 lovers

69 7536 teamo

70 7518 jasmine

71 7500 brandon

72 7419 666666

73 7333 shadow

74 7301 melissa

75 7241 eminem

76 7222 matthew

77 7206 robert

78 7148 danielle

79 7116 forever

80 6979 family

81 6775 jonathan

82 6658 987654321

83 6653 computer

84 6647 whatever

85 6598 dragon

86 6570 vanessa

87 6554 cookie

88 6547 naruto

89 6501 summer

90 6420 sweety

91 6390 spongebob

92 6320 joseph

93 6272 junior

94 6215 softball

95 6131 taylor

96 6111 yellow

97 6080 daniela

98 6079 lauren

99 6068 mickey

100 6027 princesa

Analysis: I'm hesitant to post the top 370 passwords due to privacy concerns, (also 100 is such a nice round number), but I figure this should give a good overview of the coverage of the 370 passwords that are blacklisted by Twitter. A grand total of 38 of the top 100 passwords did not appear in the Twitter blacklist. That actually really surprised me, as I expected the Twitter blacklist to perform better. So I guess what I'm trying to say is good question ;)

Just to save everyone from the math, if an attacker tried the top 100 passwords as guesses, they would have been able to crack 1,483,668 passwords from the dataset, or 4.5% of the total passwords. If the Twitter blacklist had been in place, and the attacker still tried the same 100 guesses, they would have only cracked 475,046 passwords, or 1.4% of the total passwords. So a blacklisting approach certainly can help against online password attacks, (where the attacker is severally limited in the number of guesses they can make). That being said, the Twitter list probably shouldn't be considered the gold standard as there are a lot of improvements that can be made to it.

Well, that's one question down. Keep them coming!

RockYou Hacked: 32 Million, (yes that's Million), Passwords Stolen

2009-12-24T09:53:00.000-08:00

As the title implies, the popular Facebook and MySpace game/widget maker RockYou was hacked, with the hack becoming public last week Tuesday, December 15th. What's worse is that RockYou stored all of their passwords in the clear, (no hashing), so 32 million plaintext passwords were stolen. I've been doing some digging into this so I can add something to the conversation, but for a great general overview I highly recommend reading TechCrunch's writeup.

First of all, if you have ever used the following social networking applications, you probably should change your password ... like right now.

Slideshow
Uploadphoto
Photofx
Glittertext
Funnotes
Countdown
Superhug
Myspace layouts
Stickers
Superwall
Pieces of flair
Speedracing
Likeness
Hugme
Birthday cards

Yup, that's why we're talking about 32 million user accounts, (though in all fairness, many of those user accounts are almost certainly duplicates created by the same person).

One day after the attack became public, the hacker gave an interview over at readwriteweb talking about password security in general. He, (I'm going to assume he's a guy since the nickname he gave was Tom), basically said around 30% of all websites still store user credentials in plain text. He also said the most important thing users can do is choose different passwords for different sites since they can't rely on those sites to protect them.

I'll certainly agree with that. I'll also agree that Rockyou should be held responsible for A) Not storing passwords securely, and more importantly B) Trying to cover up the hack after the fact. When Rockyou tried to downplay the impact of the hack, (by claiming it only affected some of their older programs), it was really a sleezeball move. That being said, I can't condone the Hacker, (Tom), either, since his behavior is unacceptable. It's one thing to point out a vulnerability. It's another thing to exploit it.

Probably the most interesting part of the interview was that they referred to the hacker's blog. Apparently he also goes by the handle 'igigi'. I guess that sounds better than Tom ;) As far as I can tell, he choose igigi because that's what ancient Sumerians called angels. Either that or he's really into plus sized clothing. Now is it just me, or is it weird that someone actively hacking into websites is giving interviews and keeping a blog?

The thing is, igigi probably wasn't the first person to hack into RockYou. According to Imperva, an internet security company, they originally discovered the exploit being talked about on a hacking forum about a week earlier, and several of the webmail accounts associated with those logins have since been flagged as being hijacked by spammers. Looking at igigi's blog, his first entry was December 6th 2009. I guess what I'm trying to say is there's a definite possibility that he stumbled upon an exploit that someone else had posted and decided to cash in on some fame. Either that or he isn't as white/grey hat as he claims to be. RockYou is the only English site he's claimed to hack; All of the other sites have been Slovakian or Czechian which gives you an idea of where he's from, (and/or which forums he reads). I did some additional searches and I haven't been able to find any trace of igigi before December, though my ability to do research into the other sites he's hacked has been limited because Google's Czech to English translator leaves a lot to be desired.

All this is just a run-up to the news that on Monday igigi posted the entire password list, minus the usernames and e-mail addresses. The original rapidshare links no longer work, (or I wouldn't have posted a link to his blog), but the list certainly is still out there on the net if you know where to look. Just a warning though, there are also some copies of it that contain nothing but viruses and fail. Here's a hint, if the list claims to be a self-extracting executable, don't click on it...

Dealing with such a large list has had its own challenges, (though I certainly can't complain). Even opening it with vi takes about a minute, and for searches I've resorted to catting it into grep. I've also discovered that I probably should have used some more efficient algorithms in a couple of my analysis tools.

Here are some of the basic statistics:

Total Plaintext Values Parsed: 32,603,387
Average Password Length of Parsed Passwords: 7.88
Average Complexity Level of Parsed Passwords: 1.94
Percentage of Passwords that have an uppercase character: 05.94%
Percentage of Passwords that have a special character: 03.42%
Percentage of Passwords that have a digit: 54.02%
Percentage of Passwords that only have lower characters: 41.68%

Overall Letter Frequency Analysis:

ae1ionrls02tm3c98dy54hu6b7kgpjvfwzAxEIOLRNSTMqC.DBYH_!UPKGJ-* @VFWZ#/X$à,¸\&+=Q?)(';%"]Ã~:[^

First Letter Frequency Analysis:

sm1cba0pljdtrk2hgfniew39v45o8y76MzSBACJLquDPTxRKGHNFIEW*VOY#Z@!Q($.UXà-_<~[/+,;="`?&%Ã:^

Last Letter Frequency Analysis:

1ae326sn5794y08roltdihgmukzc!pxwbA.fEj*SNYOvRLqDT@IHM$?KG)U_-ZC+#PXB/,WJ]%;F'~=V`^\&Q"> (:

Quick Analysis:

The first thing that stands out is that many of the passwords don't meet RockYou's password policy. RockYou requires users to create a password between 5 and 15 characters, and passwords cannot contain special characters. With this dataset though, 78,404 passwords were less than five characters long, and 258,835 passwords were longer than fifteen characters long. As already mentioned, 3.42% of the passwords also contained a special character. This seems to imply that a lot of RockYou's applications use a different password creation policy. Since many of the widgets manage Facebook/MySpace info, it's a fair bet that they require the user to enter their Facebook/MySpace password which is what we're seeing in this dataset.

Well, it's Christmas Eve, so I'm going to leave further analysis till later. As a Christmas/Hanukah/Seasonal present I would really appreciate for you guys to let me know in the comments or via e-mail what you would be interested in finding out about this list. That way I can focus on what's useful to you vs. just posting random statistics like I did above ;)

Google Wave Invite

2009-12-01T09:49:00.000-08:00

I've been playing around with Google Wave, and received a couple of extra invites to the free beta. If you are interested, let me know and I'll send one your way.

My short review: It looks like one of those tools where it takes a lot of work to gain any benefit from it. That being said, if you are collaborating with a lot of people on several different projects it has real potential.

Biometrics Are Not Going to Save Us - Or Get Used to Your Password

2009-11-27T14:29:00.000-08:00

Abstract:

It generally is taken as common wisdom that one day, everyone is going to switch to biometrics so we can finally get rid of those pesky passwords. This post is an attempt to stave off that future. This isn't because I'm in the password cracking business, (I'm sure horse-buggy salesmen thought that cars were a poor substitute as well). Instead it's because biometrics are a really bad solution. In fact, over the long run, biometrics will make it even easier for an attacker to break your authentication schemes. The rest of this post is an attempt to explain why this is the case, along with some other reasons why you probably shouldn't go out and buy that thumbprint reader quite yet.

If Biometrics Are So Bad, Why Do People Still Like Them:

Let's face it, passwords suck. This is a blog pretty much devoted to password cracking. I'm aware of the fact that they suck. Passwords are a pain to use, a pain to remember, and pain to make secure. Who doesn't want to get rid of them? At the same time, biometrics seem like the perfect solution. Just about everyone has something to scan, (we'll make a special use case for the double amputee). You won't forget them. You won't leave them at home. User's can't share them. Oh, and with all that fancy equipment, how's a hacker supposed to break it? In addition, it's an authentication scheme that everyone understands. Try to explain public key cryptography to someone, and all you'll get are blank stares. Everyone knows about fingerprints and iris scans. Heck, we use biometrics every day to distinguish between people like Bob and Alice, (though please stop staring at Alice's chest and calling it an authentication scheme...) So why shouldn't we use biometrics with computers to authenticate people?

Identification, not Authentication:

If you've ever had to suffer through a CISSP prep course, you'll probably remember the instructor droning on about the IAA triad, (Identification, Authentication, and Authorization). The thing is, keeping those three ideas separate really is important, since they perform different jobs. Identification is a way to keep multiple users distinct, and as a statement of who you think that person might be - "Hey that looks like Alice". Authentication is where you verify someone's identity - "Hey that is Alice because she knows the secret codeword". Biometrics are extremely useful for identification. Yes, you heard me right - I'm a fan of biometrics when it comes to identifying people in certain cases. It's using biometrics as a form of authentication that I have a problem with.

My very first internship back in 1997 was working on the National Automated Fingerprint Identification System. It was one of the best summers of my life. From moments such as, "Wait these fingerprints were taken from someone who died in the tub and laid there for three weeks - Ewww", to having to pass through an almost "Get Smart" level of security when going to work, it was amazingly fun. Beyond that though, I gained respect and a better understanding of how biometrics like fingerprints can be useful, (though I also obtained a better understanding of false positives). It's not just law enforcement where biometrics as a form of identification is used. From all accounts, biometric identification has also proven vital to supporting our troops in Iraq and Afghanistan. So I want to state for the record I'm not against using biometrics. As I'll go into much more details in the later sections though, due to certain inherent weaknesses, biometrics perform very poorly when used for authentication in computer systems. In short, biometrics for authentication = fail.

The Number #1 Reason Why Biometrics Fail - It's all Digital:

It's easy to get carried away talking about the lack of false positives, liveness sensors, or the inability to duplicate the blood vessels at the back of an eye when discussing the security of biometrics. In reality, very rarely does any of that matter since they are all factors of the biometric sensor itself. This is important. If you can bypass the sensor, then all you are dealing with is a digital representation of the data. Probably the best example of this was the excellent Defcon 15 talk by Zac Franken - "Biometric and Token Based Access Control Systems: Are you protected by two screws and a plastic cover? Probably". In it, he demonstrated grabbing biometric "signatures" from devices and then replaying those signatures to allow him access. It's a lot like a pass-the-hash attack but easier. This gets even worse for remote authentication, where the sensor is completely out of the control of the defender. Now, a defender can try to make the sensor harder to bypass, for example by using some form of trusted computing, but this is a tough battle to fight. Let me put it this way: If we had trusted computing down pat, no-one would be able to jailbreak their I-Phones...

The fact that an attacker is dealing with a digital representation of a biometric signature means the type of biometric measurement, (fingerprint, iris, voice, etc), they are attacking generally doesn't make a difference. The one caveat I want to mention though is that the type of signature can impact the ability to perform guessing attacks. As I'll explain later though, that becomes largely irrelevant as biometric authentication becomes more prevalent.

My Mother Always Said, "Don't Use Your Online Banking Password Everywhere":

I think we all agree that password reuse is a real problem. When singles.org was hacked, some of the 4chan'ers tried the disclosed e-mail/passwords on facebook, and then proceeded to create a lot of embarrassing fake posts. Some of those posts are hilarious; until you realize that this happened to real people. I think we can all agree - using the same password for your online bank account and every other site is a bad idea. But what about biometric signatures? I only have ten fingers. What happens when a site that has a copy of my biometric signature gets hacked? Now an attacker has a digital copy of my fingerprint. That can't be good...

The sad fact is that biometric authentication is only somewhat effective as long as it is a nitch market. The second everyone starts using it, you fingerprint/iris-scan/whatever will get disclosed. I wish I was exaggerating, but if that wasn't the case, we wouldn't have any problems with password reuse either. Heck I know my password has been stolen at least once when a gaming website I used to play on was broken into. In reality, my password probably has been stolen more than that, (the Cain&Able forum may have been hacked, the FSU Alumni database was broken into a couple of years ago, etc). Since a biometric signature is digital and can be used in a replay attack, the user needs to have at least the option to select different forms of authentication across different sites.

This is Going to Hurt - Lack of Revocation in Biometric Authentication

This dovetails with the previous point. What happens when a hacker gets your biometric signature? You can't change your fingerprints, (well you can, but it'll probably be fairly painful). How do you stop someone from logging in if they have your password and you can't choose a new one? That's not a rhetorical question. I really don't know the answer to it, and I don't think anyone else does either. In short, even if there is a form of biometric authentication where it is hard/impossible to guess someone's signature, it really doesn't matter because if it achieves widespread deployment your signature is going to get disclosed.

I Was Framed - Lack of Attribution, But Don't Count on the Jury Knowing That:

There's a lot of privacy issues with using biometrics, but I'm going to skip over that. It's not that the privacy issues are unimportant, but that they can lead into conversations/arguments that wildly diverge from the subject at hand. Instead, let me ask you this question. If you were on a jury, would you convict someone if the only evidence against them was fingerprints and/or DNA samples? I hope the answer is no, but I think a vast majority of people would say yes. What happens to Bob when Alice uses his biometric signature to break into the server room and trashes the place? As much as we want them too, biometrics don't provide attribution on their own, and this fact can be used by an attacker to frame someone.

Trusting Fuzzy Hashing to Encrypt Your Harddrive - This Is Going To End Well:

The great thing about passwords is if you don't enter them in exactly, they don't work. Ok, you might not think it's great when you spent ten minutes trying to log in only to find that caps lock was on, but from a cryptographic standpoint it's really nice. You might have some trouble decrypting your AES256 encrypted hard-drive if your password is constantly changing. To combat that, something called fuzzy hashing has been proposed. What fuzzy hashing attempts to do is return the exact same output hash even when the input values are changing slightly from time to time. This fuzzy hash can then be used as the key for your encryption algorithm. The problem is that current fuzzy hashing techniques aren't that good, and have been shown to have multiple problems that make them extremely vulnerable to guessing attacks, (the attacker only needs to get close). In fact, here are two papers on this very subject: 1, 2. Even if that wasn't the case, good luck trying to keep the cops from obtaining your fingerprint. That's actually one of the fundamental flaws with biometrics. Since they are based on something you are, instead of something you know, it becomes very hard to keep them secret. At least with a RSA key, you can hide it under the floorboards.

Finally, fuzzy hashes may not be able to take into account drastic changes in someone's biometric signature. If you cut your finger, do you have to wait for it to heal before you can decrypt your hard-drive? In short, biometrics and encryption don't play very well with each other.

Conclusion:

There were quite a few additional arguments I could have made, (hey I didn't even mention this Mythbusters episode), but I'm probably beating a dead horse by now. It's actually gotten to the point where I'm not even a fan of using biometrics as one-half of a two factor authentication setup. It's not that they don't provide some additional security, but that there are better solutions out there. No form of authentication is perfect, but I'm fairly well convinced that biometrics are not the way to go. I hoped this post proved convincing, and if not, please use the comments section below as I'm always open to new ideas.

Analysis of 10k Hotmail Passwords Part 5: Markov Model Showdown

2009-11-24T13:18:00.000-08:00

Don't worry; I'm still not done with this data-set. A little over a week ago I received an e-mail from Ilya Sokolov, saying:

If I'm getting the numbers right from your graphs - you've got around 3k hashes bruteforced in about 1G guesses. Assuming you used --incremental mode of John, right? I guess you should try --markov too :)

How right he is. Ilya went on to send some statistics my way, so I truly do appreciate e-mails like this. Before I talk about the results, first let me back up and spend a little time talking about the incremental and markov modes in John the Ripper. Aren't they both Markov based attacks?

--Ed Note: The following description of how the incremental attack works has been updated since I was incorrect about how JtR used trigraphs. A copy of the original incorrect description can be found in the comments.

Well surprisingly yes they are, though they go about it in different ways. The --incremental option actually models the probability of trigraphs appearing. In this case a trigraph represents a three character long string, such as "abc". Another way to say this is that JtR uses trigraphs to represent second order Markov probabilities, aka the probability of 'c' given 'ab'. There's special code handling the first two characters, (since they don't have two characters before them), but after that John the Ripper select each successive character based on the previous characters. Therefore, for the guess 'abcdef', it would create the trigraphs 'abc', 'bcd', 'cde', and 'def', and assign a final probability to the guess based on those four different trigraphs. In addition, the probability of a trigraph is also dependent on where it shows up in the password. In this way, the --incremental attack also takes into account factors such as numbers often show up at the end of a password, and uppercase letters usually are at the front. Pretty nice, right? The only downside is that it doesn't generate these guesses in true probability order. I'm still a little fuzzy on some of it, but the incremental mode does make some shortcuts so it can cover the entire keyspace, while still being able to generate a large number of guesses quickly.

I know; Way to much info - especially since this is just my understanding of how it works. I need to spend more time looking at the code to make sure the above is actually correct. The biggest advantage of using the incremental attack is that it creates highly optimized guesses while still retaining the ability to eventually cover the entire key-space if you give it enough time. Aka it will eventually try guesses like 'bD359sl'. Also it is blazingly fast.

The --markov mode on the other hand takes a different approach. First of all, if you haven't noticed this option in your copy of John the Ripper, that is because it was added as a third party patch, (though it's currently part of the jumbo patch set). Personally I haven't used it that much since it full out segfaults on Intel based macs, which I generally use as my development/testing platform. That being said, after running some comparative tests on my Linux box at the lab, (I use that one for my long term password cracking sessions), I've really become a believer in it. However, using the markov mode is a little bit tricky.

Unlike incremental mode, the markov mode does not use trigraphs. Instead it starts with the highest probability starting letter, (in the default stats file this is a 'c'), and then appends the most probable following character. It repeats this until it hits the probability threshold specified, or it reaches 12 characters long, in which case it outputs a password guess. The attack then goes to the last character of the previous guess and changes it to the second most probable value, and outputs another guess. You can probably see where this is going as it cycles through printing out all the possible guesses that meet the probability threshold specified. There are a lot of advantages to this approach. For example, it can attack passwords up to twelve characters long. The downsides of this approach is that it doesn't create guesses in probability order which the incremental attack does. Therefore, as we will see, if you set a high threshold the markov mode starts to resemble a letter frequency analysis attack. Finally, because of this, the markov mode won't cover the entire key-space, (aka, it won't crack the password '3Nw!lswp'). The last point isn't as important as it may seem though, since in all likelihood due to time constraints, (aka you only have several months to crack a password if that), you simply don't have enough time to cover the entire key-space even using incremental mode. In short, you want to do the best that you can with the limited number of guesses you can make.

So that was a really long introduction before we even talked about any results ;) Let's see how the incremental and markov options fare against some real passwords!

Test 6: Trying the default -incremental and -markov modes against the Hotmail password set

For the first test, I wanted to run both the -incremental and -markov modes against the Hotmail password set using their default settings. The one tricky part was to set the limit for the markov attack. In the readme file for the patch, it actually goes into quite a bit of detail on how to select a proper limit. Really all I did was run the included program 'genmkvpwd', and select a limit that would cause the attack to generate slightly more than one billion guesses. This turned out to be the value '214' for the limit.

Results: So here are the results. As always, you can click on the graph to get a slightly larger version. The Y-axis is the number of passwords cracked. Sorry, I didn't realize I forgot to add that until I was proof-reading this and I didn't feel like re-uploading the graphs.

-ed note: I know; It certainly doesn't look like I proof-read these posts ;)

Analysis: As you can see, the Markov mode started out slow, but finished strong, cracking 786 more passwords than the Incremental attack. As far as I can tell, the reason why it did so well near the end was that the markov mode started trying password guesses that began with numbers, which was very common in the hotmail dataset. Also, since the probability of a guess starting with a number was so low according to the default rule-set, it only tried very probable guesses following a number.

Another thing I'd like to point out: Due to the way it creates guesses, for the most part the Markov mode cracks passwords at a fairly fixed rate; while the Incremental mode is much more front-loaded. I'd like to caution you against extending the Markov mode's line though, as it has finished just about every password guess within the limit that I set. That actually leads us to the next test...

Test 7: Setting Different Limits for a Markov Based Attack

So the next question of course is, "How does the limit affect Markov based attacks?" That's a pretty easy one to solve. All I needed to do was run it with several different limits and graph the results. I also included the Incremental results for a comparison.

Results:

Analysis: See what I mean about not being able to continue a predictive line on the number of passwords that using JtR in Markov mode will crack? When using a limit of 200, it created slightly more than 250 million guesses and then finished. If we run the same attack using a limit of 214, it will create almost four times as many guesses, but it only cracks 148 more passwords. If we increase the limit to 250, it will generate roughly 46 billion guesses; But if you refer back to some of the previous tests, even a pure brute force attack performs significantly better in the first billion guesses. Don't worry though, as the Markov attack will catch up with brute force, (and then exceed it by a large margin), if you let it run long enough.

What this shows is that you really do need to spend the time to tailor your attacks using Markov mode to the resources you expect to spend cracking the password list you are attacking. One good option is you can split your attack up into multiple parts, where you try all the guesses using a very low limit, and then increase the limit and run the attack again. There is an option in the latest build of the patch to exclude guesses made previously. This can save you time since you don't have to re-hash guesses you made already. There is a slight performance hit by using this approach though as it will make a guess, realize that it made the guess before and reject it, before moving on to the next guess. Still, this can be very useful, especially when attacking salted hashes, as it makes a huge performance improvement to crack as many hashes as possible as soon as possible, (since each hash you are cracking greatly adds to the cracking time).

Test 8: Comparing Incremental and Markov Modes When Trained on the Same Password Set

Now, all of the previous tests are fairly nice, but there is the worry that we are comparing apples and oranges. I mean, both the default Markov and Incremental modes were trained on different password sets, and that can have a huge impact on their cracking ability. For example, the Markov mode was trained primarily on French passwords, and the Incremental attack was mostly trained on English passwords. That's one nice thing about being in the password cracking research business though; I certainly have a lot of passwords to use for my own training set ;)

For this test, I trained both the Incremental and Markov modes on the same set of disclosed passwords from the phpbb.com list that I had previously cracked. In technical terms, I created a new .chr and new stats file for both attacks. As I previously mentioned in part 4 of the writeup, the phpbb.com list isn't ideal for this attack since it is primarily composed of English passwords, while this list is mostly Spanish/Portuguese, but that doesn't matter for this test. What does matter is both attacks are being trained on the same list, and they have to deal with the same limitations. In addition, I ran the Markov attack twice. The first time I allowed it to attack passwords up to 12 characters long. The second time I limited it to only attack passwords up to 8 characters long, (and I assigned it a higher limit so it would generate roughly the same number of guesses). This way we can better compare it against JtR's incremental mode which only tries guesses up to 8 characters long. So, let's see how this turned out:

Results:

Analysis: Yup, the Markov mode still cracks more passwords than JtR's Incremental mode. Still, there were a couple of things that surprised me about these results. First of all, the phpbb.com list made a much better training list than using the default .chr and stat files. The Markov attack cracked 540 more passwords using the same number of guesses when it was trained on the phpbb list. The Incremental attack also got off to a much faster start, though in the end it cracked 17 less passwords than the Incremental attack using the default alphanum character set. This isn't exactly a fair comparison though since I didn't bother to filter the training set to only include lowercase letters and numbers.; Aka it actually is using pretty much the entire keyboard. In that case, it performs much better than using JtR's Incremental mode using the 'All' .chr file, and it cracked 333 more passwords overall.

The second thing that surprised me was that limiting the maximum password guess size didn't really have much of an effect on the number of passwords cracked using the Markov mode. This shouldn't have surprised me that much, since it didn't make that many guesses longer than eight characters long, (the probability of those guesses would be very low), but still it helps to see that on a graph.

Future Work: Whew, and here I thought I'd be done with this data-set by now. I still have a few miscellaneous tests I want to run using brute force style methods believe it or not. And then I need to get around to posting my results with dictionary based attacks. Oh ,then there are the topics that I've been meaning to post on for a while. They range from going over other datasets, (such as the ZF0 one), to the vulnerability of World of Warcraft accounts to password disclosure attacks, (and what Blizzard is doing about it). It should be fun ;)

Installing John the Ripper Version 1.7.3.4 Tutorial

2009-11-16T18:13:00.000-08:00

I just upgraded to the newest version of John the Ripper so I decided to make a tutorial out of my experience, (with screen-shots), since it was a fairly time consuming ordeal. It's mostly focused on installing John the Ripper on a Mac OSX Snow Leopard, but you should be able to use most of it when installing it to various flavors of Linux as well. Besides going over the base install, I also tried to cover:

Which patches to install, where to find them, and how to apply them
Picking the right build options
Modifying the Makefile so it actually will install on Snow Leopard
Modifying the code so you can use incremental attacks against passwords longer than eight characters long

You can find it on my tools page, or by clicking on this link.

Defcon 17 Videos Posted Online

2009-11-15T14:20:00.000-08:00

The title says it all. You can get all of the videos here. Just a warning, I may have used some inappropriate language in my talk on password cracking, so you might not want to watch it in front of small children.

Also, my writeup of a couple of the talks can be found here, and here if you are having trouble deciding what to watch.

Analysis of 10k Hotmail Passwords - Even More Brute Force

2009-10-29T13:58:00.001-07:00

A reader asked me through e-mail how much better John the Ripper's Markov models were compared to pure brute force or letter frequency analysis. I knew there was a reason why I put my e-mail address on the side of this blog. That's a great question, since while I'd always had more success with Markov models vs letter frequency analysis, (and certainly brute force), I had never measured the difference before. What type of researcher am I? I better fix that, so let's check it out.

Test 4: Markov Models vs. Letter Frequency Analysis vs. Pure Brute Force

So in this test I reused the data collected previously in Test 1 using JtR's -incremental mode targeting lowercase letters and numbers, (a-z0-9). I then used the popular tool crunch to run both the brute force and letter frequency analysis, (which I'm going to call LFA), attacks since JtR doesn't support pure brute force, (well there is a bit of a hack, but crunch is easier). For the pure brute force attack I ran:

./crunch 6 8 abcdefghijklmnopqrstuvwxyz0123456789

In short, I'm creating brute force guesses between 6 and 8 characters long containing a-z0-9, starting with aaaaaa and theoretically ending with 99999999, (in this run it never finished all of the six character long words). This is also the default character set that the popular password cracker Cain&Able uses.

For the LFA attack, I then ran it using the numbers based on my analysis of the phpbb.com password list. As we'll see, you can do better if you base your LFA on analysis of Spanish/Portuguese passwords, but I don't have another dataset of Spanish/Portuguese passwords so this is the best I can do without cheating. The command I used was:

./crunch 6 8 smp1abctdkjlhrfgnw2ei0ov3q457z968yux

A couple of notes. I used the first character LFA charset since crunch increments it's values from right to left; aka it will try 01, 02, 03, 04 etc. This means using the above character set, it will initially crack all the words starting with 's', then move on to words starting with a 'm' and so on. When there is no password creation policy, (aka users aren't forced to include numbers in their passwords), this is slightly better than password crackers such as Cain&Able who increment their values from left to right, aka 10, 20, 30, 40 ... The reason for this is because people are slightly more predicable in how they start words/passwords, vs how the end them. For example, from the phpbb.com dataset, over 51% of the users choose one of top ten characters to start their passwords. Likewise, 46% of users choose one of top ten characters to end their passwords. It's not a big difference, but every little bit helps. If there is a password creation policy though, this quickly falls apart, and it's vastly more preferable to use a left to right approach since people almost always put numbers/special characters at the end of their passwords. For example, just the number '1' appears 21% of the time at the end of stronger passwords.

Also, the more astute, (and/or skeptical), readers might notice the order I'm using is slightly different from the one I published before. That's because I've cracked more passwords from the phpbb.com dataset, (I'm nearly up to 98% of the total set cracked), so I've updated some of my statistics. That's another thing I need to get around to posting up here...

Results: Note, you can click on the image for a bigger version of it.

Analysis: The first thing that stands out is that my letter frequency analysis percentages are way off. I actually do worse initially then if I had chosen a pure brute force approach. I know it's cheating, but going back to my original analysis of the hotmail list, and comparing it to the phpbb list, you get the following:

Hotmail list: a1mbc2sp0lterdjfgn3hi6k759vo48ywzuqx
Phpbb list : smp1abctdkjlhrfgnw2ei0ov3q457z968yux

Looking at this, the best choice you could have done was to start with the letter 'a' which is coincidentally what the pure brute force approach did. The reason for the huge bump in the LFA attack around the 220 million guess mark is because it hit the '1' as the first character, followed by an 'a' which was about the equivalent of a perfect storm since people started their passwords with a number, followed by the actual word they were using. Even with my probabilities being off though, LFA still beat out pure brute force, so if you aren't at least using that, well I don't know what more I can say to convince you. That being said, this really shows how superior using Markov models is to both attacks, with the alphanumeric Markov attack cracking more than twice the amount of passwords that the LFA did. I'd also like to point out that if you look at the first several million guesses, a Markov based attack performs so much better than LFA it's ridiculous.

Test 5: LFA and Brute Force Attacks Against Different Length Passwords

The next question is how do LFA and Brute Force attacks perform as the password gets longer. As I said before, the above test only shows them attacking 6 character long passwords. What happens when we bump up the length to 7 or 8 characters minimum. To simulate this, I once again used crunch with the above settings except for increasing the minimum size guesses allowed. I also used the phpbb LFA probabilities, since I hate training and testing on the same dataset, (also I had already run the tests before I graphed out the results and realized how off those probabilities were...)

Results:

Analysis: I didn't even bother to put the eight character one up there since it was pretty boring. If I'm generous the pure brute force attack would crack one eight character long password, (it took slightly more than one billion guesses to do so), and the LFA attack would crack two. This shows though that while increasing the character set quickly makes brute force and LFA attacks infeasible, which is what you'll see in all the literature, even longer passwords are vulnerable against Markov model based attacks. One way to increase the effectiveness of LFA style attacks is to not try the full alpha numeric character set, (aka drop qxz etc). That's another test I'll try to run later. Even so, once again this shows that Markov models are the way to go. I'd like to point out too, that JtR's Markov model attack almost certainly would perform better if trained against similar passwords. That's another test I'll need to run ... after Halloween weekend.

A Quick Note on Time Required: I think it's important to state that these test runs are extremely short since I didn't want to run each for an entire day just to get a few more data points. My update schedule is already too slow ;) To give you a better idea how long it would take to bruteforce the entire key space here is some numbers I ran using Cain&Able. Note, Cain&Able is much slower than JtR, but it has a really nice time estimator, so please consider these numbers a worst case scenario.

Computer Specs:
2.4 Ghz Core Duo
3 Gigs of Ram
NVIDEA GeForce 8800 GTS
Windows 7 - 64 bit

-All tests were run against cracking plain MD5 hashes

Alpha-Numeric passwords: a-z0-9

6 character: 14 minutes
7 characters: 8 hours
8 characters: 12 days

The Entire US Keyboard

6 characters: 3 days
7 characters: 272 days
8 characters: 71 years

Oh, and keep sending me ideas, either via e-mail or in the comments of these posts.

Analysis of 10k Hotmail Passwords Part 3 - Brute Force

2009-10-18T16:53:00.000-07:00

As promised, let's see how these Hotmail passwords would fare in a real password cracking attack. This post will cover brute force attacks, and I'll make a later post going over the effectiveness of dictionary based attacks. As always, if there is any further attacks/analysis you would like to see run against these passwords, please let me know in the comments.

Test 1: John the Ripper Incremental Modes

The first test I wanted to run was to use John the Ripper's brute force attack, (aka -incremental). As I mentioned in a previous post, JtR's incremental attack is very powerful and probably as close to an "industry" standard as you will find. For this test, I ran JtR's four different built-in incremental modes, (All, Alpha, Digits, Alnum), against the password set, and let each one run for one billion guesses. While in a real password cracking attack, the attacker would probably run their attacks much longer, (aka try trillions of guesses), I figured a run of one billion guesses was enough to give people a general idea of the effectiveness of these attacks. Since the minimum password requirement for Hotmail passwords required legitimate passwords to be at least six characters long, I modified my JtR config file so it would only try guesses of six characters or more. Also, since the built in brute force attack in JtR won't try passwords longer than eight characters long, for the Digits only attack I ran it through Middle Child to add two digits to the end of each guess. This is because JtR would only make one-hundred million guesses otherwise, (aka all digits between 0 and 99,999,999.) I know I can patch JtR to try longer guesses, but I'm lazy.

Character Set of Each Attack Type:

Alpha: a-z, all lowercase
Alnum:a-z 0-9, all lowercase
Digits:0-9
All:a-z A-Z 0-9 and keyboard characters such as !@#$%

Results:

Analysis: As you can see, bruteforcing lowercase characters and numbers was the most effective strategy, cracking a hair over 30% of the passwords. It shouldn't be surprising that it did better than the "All" attack since less than 10% of the passwords contained an uppercase character or a special character. By including those in your attack you drastically increase the search space you are attacking. It's only the fact that JtR's Markov models are so good that the "All" attack remains competitive.

It may appear that the digits attack stopped cracking passwords after around 300 Million guesses, but the truth is that it was running out of passwords to crack. After 1 billion guesses, there were 36 passwords that contained only numbers that hadn't been cracked. This also shows how weak numeric passwords can be, (since there are only ten digits vs. 26 letters).

Test 2: Running a longer cracking session

Next I wanted to try the "All", and the "Alpha Numeric" attacks again, but let them run much longer. In this case I let them run for 25 billion guesses. This took a while even without having to do any hashing just because JtR had to spend time generating the guesses, I had to check/record those guesses, (and I was running it on my laptop).

Results:

Analysis: I think this shows fairly dramatically how front-loaded a password cracking session can be. An attacker will initially see very good results, but after the easiest passwords are cracked it requires many more guesses to crack successive passwords. It almost looks like a logarithmic function. Near the end it was taking over fifty million guesses to crack each additional password. Even if that rate remains constant, (in real life it almost certainly will get worse), you're looking at having to make over 56 billion guesses total to crack 50% of the Hotmail passwords using the Alpha Numeric character set.

Test 3: Effectiveness of password length against brute force attacks

One person wondered in the comments about how password length affects dictionary based password cracking attacks. I'll get to that question in a later post, but I figured I should run some tests to demonstrate how minimum password length requirements can drastically increase the cost of brute force attacks. For this test, I ran John the Ripper's -incremental mode several times, using the Alphanumeric character set. Each session I modified the config file so it would only attempt to crack passwords of a specified length, from 6 to 8 characters long. The results of this, (measuring percentage of passwords of that length cracked), can be seen below.

Results:

Analysis: Quite honestly, if your password is six characters or less, chances are,it's going to be cracked in under a billion guesses. Please note, none of the attacks will ever reach 100% of the passwords cracked since I'm only bruteforcing lowercase letters and numbers, (and there are a few passwords that used uppercase letters and symbols). Once again, we see that cracking 30% of the passwords is fairly easy even when the password length is longer, but as the attacker tries to start cracking 40-50+ of the passwords the effort required really starts to ramp up. This also shows that the minimum password requirement should be at least seven characters long to defend against any sort of offline password cracking attack.

One interesting thing that is hard to see on the graph is that I only needed 31 thousand guesses to crack 5% of the six character long passwords. I needed 60 thousand guesses to crack 5% of the seven character long passwords. Finally I needed 536 thousand guesses to crack 5% of the eight character long passwords. The reason why I'm pointing this out is to look at the password's resistance to an online attack, (aka where the attacker does not have the password hash and is trying to log into the system). Now admittedly in most online attacks the attacker is almost certainly going to use a dictionary attack vs. brute force. That being said, it was surprising that seven character long passwords only took twice as many guesses to hit that 5% mark, and the difficulty level didn't really ramp up until eight character long passwords were required.

Up Next: Dictionary Based Attacks! If there are any dictionaries you would like to see me use, please let me know, either via e-mail or in the comments. (Yes, I'll run the Wiki dictionary). As a quick preview, most of my input dictionaries have been performing horribly since they aren't targeting Spanish/Portuguese/French speakers, and the foreign language dictionaries I've found online have been ... lacking in quality. What I'm going to do is start building a custom dictionary based on these passwords to use in future research, (I've had great success with that when attacking Finnish and Swedish passwords), but that's not really an option here for obvious reasons. "Hey look, I cracked 100% of the passwords using an input dictionary created from those passwords!"

Analysis of 10k Hotmail Passwords Part 2

2009-10-17T23:58:00.000-07:00

There's been a lot of discussion and analysis of this list on various other sites over the last week. That's actually why I'm so interested in it. It isn't the size. Ten thousand passwords aren't that hard to come across on the net, (as scary as that is). The nice thing though is this password list is becoming sort of a common data-set anyone can work on. This keeps us researchers honest, (If I mess up my analysis someone can easily call me on it), and it gives us a way test competing password cracking techniques in a public environment.

First off, I'd like to give Google, E-Bay, and Facebook credit for how they handled this. All three sites suspended user accounts which appeared on the list, (and in the additional 20k list which I'll get to in a second), pending user verification. I don't know the amount of hoops that a user will have to go through to reactivate their accounts, but this step was necessary to protect them. Unfortunately, according to this writeup, Microsoft didn't lock several of the Swedish Hotmail accounts that appeared in the 20k list, (perhaps international .live accounts are handled by a different internal group in Microsoft), and Yahoo did an even worse job. Oh, and apparently the Yahoo accounts were filled with password reset messages, as thieves used the yahoo accounts to compromise other online accounts belonging to those users.

As to the additional 20k list, I finally managed to grab a hold of it. Looking through it, it's fairly obvious that the list was collected via a different attack, and probably was posted online by a different hacker. It just happened to be another list that was posted around the same time on pastebin. I'm going to delay doing analysis of it for now, and focus on the Hotmail list to keep things simple. Later on, once I figure out what tests/analysis proves to be the most useful to people, I'll run them on the 20k list and perhaps show some head-to-head comparisons with the Hotmail, phpbb.com, webhosting talk, myspace, etc lists.

So on to the analysis. As promised, here is a graphical breakdown of the password lengths, with the longest password being 30 characters long, (though that looks like it may have been a typo by the user, since they typed their password in three times with a varying degree of 'o's after it. The actual password was probably 17 characters long). On a side note, I really should put all of this in a pdf whitepaper, since the graphs are fairly hard to read here.

As you can sort of see, (once again, I'm sorry about the blurriness and size), 80% of the passwords fell between 6 and 10 characters long. Manually looking at the invalid passwords, (the ones which were blank and/or less than six characters long), I saw that most of the e-mail addresses associated with them also had an entry containing a valid password, (at least six characters long). I didn't check the whole list, (I do sometimes try to have a life), but I saw 50 invalid passwords that matched a valid username/password combo, and 31 examples where I couldn't match an invalid login attempt to a valid username/password. The 31 unmatched invalid username/password combos almost certainly overstates the case, since for most of those they might have also typed their username in wrong as well. Aka the username listed could be 'bob@hotmail.com', but while there were no other login attempts with 'bob@hotmail.com' there would be several accounts for 'bob.lastname@hotmail.com', 'bob.lastname2@hotmail.com', etc. I also saw similar results for people who typed in their e-mail address wrong, (such a bob@homail.com). All this is just a longer way of saying that there probably was some form of authentication in the collection of this password list. Either they were collected via a keystroke logger, or the phishing site attempted to log into Microsoft's servers using the entered credentials and presented the results to the user.

So the next question is how would these passwords fare in a real password cracking attack? Well, it's late and I need to get some sleep so that will have to wait till part 3 of this writeup.

Analysis of Hotmail Passwords by Other People

2009-10-07T19:46:00.000-07:00

As the title implies, there have been a few other people who have commented on this dataset.

Link:

Acunetix's Statistics From 10,000 Leaked Hotmail Passwords:

Comments:

At first I was a bit worried because their numbers didn't match up with mine. It wasn't until later that I realized all of their analysis was only on unique passwords. Aka if three people used the password "monkey123," they would only use that password once when generating their statistics. I disagree with some of their conclusions, but it's certainly worth a read since I can be wrong.

Link:

The Insecurity of Password Security

Comments:

The above post was written as a response to Acunetix's analysis, and I think it brings up some good points on how we need to stop blaming the user for not having some 14 character complex password for every single website they go to. There are some details that once again I don't fully agree with, (I'm much more accepting of people writing their passwords down), but it's a good read. I completely agree that the most important thing is to have three classes of passwords, one that you use everywhere, one for medium sensitive sites, (such as Facebook), and (at least) one strong password for your e-mail and online banking. The simple fact is that phishing and password disclosure, (such as one of the sites being hacked), is a much bigger danger to users then password cracking attacks.

Link:

Analysis of Hotmail Users' Passwords

Comments:

This one is in Russian, (You can use Babblefish if you want), and it's quite good. It has some excellent graphs. In fact, I'm probably going to steal his idea and make some graphs of my own in a followup post since they convey the information a lot better than raw numbers. Another nice thing he did was exclude all the invalid passwords, (such as passwords that didn't meet hotmail's password creation policy), in his analysis. The best graph was him comparing the hotmail passwords to two other Russian password datasets. In short, this was a really good writeup.

10k Hotmail Passwords

2009-10-06T16:56:00.000-07:00

Ed note: Ok, I probably should update the title to "30k E-mail Passwords". That teaches me to take my time writing these posts ;) An updated article talking about the additional passwords floating around can be found here. All of the below only deals with the initial 10K passwords that were posted originally, since I haven't been able to find the second 20k list yet. According to Google, there's a third list as well. It's still unknown at this point if all the lists are related or not.

So as some of you may have heard, a little over 10,000 hotmail e-mail account/password combinations were publicly posted online around October 1st, with the first news report about it surfacing around October 5th. First off, I'd like to give special thanks to Steve Gadd and Ilya Sokolov for alerting me about this dataset. I'm always open to any help I can get.

Luckily I managed to snag a copy of the list before it was deleted from Google cache, though I've seen some other copies floating around. The site where it was posted on, pastebin.com, has since been taken down by the owner due to the large amount of attention, (and traffic), it has received over the incident. It's also been mentioned that pastebin is putting filters in place to prevent this from happening again. If they look through their old archives though, I think they will be surprised to find that pastebin has been one of the primary sites for distributing passwords for a while. Just about every password cracking forum I've gone to I've seen people posting their password lists, (both the raw hashes, and the cracked passwords), on pastebin. That's because most forum software won't allow you to add several thousand lines of hashes into a single post. Also pastebin's original goal, of providing a way for developers to easily distribute and modify code, makes it real easy for several people to update a huge list of password hashes with the ones they have cracked. I'm not blaming pastebin for this. It's just interesting to me how many technologies can have a dual use.

The passwords posted only cover a small range of users. Specifically the list only covers users who e-mail addresses fell into the range ara*** to bla***. It should go without saying then that this is only a small sample of the entire list that the attacker collected. While I don't know how the list was first discovered, my guess is that this list was posted online by the attacker who was trying to sell the entire list, and used this snippet to prove they actually had the goods. Looking at some of the other e-mail lists I've collected through my research, that range, (ara-bla), constitutes around 4% of all the total e-mail addresses. This means that the 10k sample probably represents around a 250k password set. Note, I based this on primarily English e-mail addresses, and the list mostly contains Spanish/Portuguese/French users so this number may be wildly off. That number sounds about right though, since 250k would make a nice round number to sell off in one chunk, (the attacker probably has collected many more passwords and is saving the extra for a different sale).

It's important to realize how valuable your webmail account is. Once someone's e-mail account is compromised, you can take over every other web account they own. Banks, Paypal, Facebook, Twitter, amazon.com, the list goes on and on. That's because every other site relies on your e-mail account to send a reset password to if you forget your current one. An attacker doesn't even need to know which online bank someone uses. All they need to do is just go to all of the online banks, enter in the compromised e-mail address and click "I forgot my password". A couple of minutes later, the bank that the user has an account with will e-mail a new password to the compromised account. I wish I could say I'm exaggerating the problem, but your e-mail address is the key to your whole online existence.

So the next question is: how did the attacker get the e-mail addresses/passwords in the first place? It wasn't from Microsoft, that's for sure. I'm very confident about this due to numerous reasons, (invalid e-mail accounts, several gmail accounts being in the list, blank passwords, and passwords that didn't meet the minimum password requirements, etc). That means that this list was either collected through a phishing attack, or through malicious software, (keystroke loggers), installed on users computers. Luckily, it's looking more and more like it was from a phishing attack, which means that Microsoft's quick efforts to disable the accounts and alert the users will pay off. If it was a keystroke logger, (And by keystroke logger I mean software set to harvest passwords), most of the users would reset their passwords only to have them stolen again. I originally suspected that this was due to infected computers, simply because there weren't any vigilante posts that you normally see due to phishing attacks. Aka passwords such as "F**K YOU, YOU F**KING HACKERS!!!" As Mr. Gadd pointed out to me though, one of the usernames was

still can not believe this, tell me whether you think is real

The lack of vigilante posts though seems to point to the fact that if this was a phishing scheme, it was a very convincing one. Upon doing some further research, it looks like this list may have been collected from a MSN Instant Messenger scam. I'm still a little weak on the details, but the short answer is that the scam site would send out e-mails saying that they could discover who had blocked you on your instant messenger client. The user would then go to the website and log in using their Microsoft account ,(supposedly so the site could run it's tests to see who was ignoring you). The scammers would then send out the same advertisement to everyone in the user's address book, saying that the e-mail was from them. There are some other details as well that I'm fairly foggy on, (they would try to sell the user some free software, and have the user send them a SMS message so they could split the profit of the SMS message with the phone company).

As a clarification, the only reasons I suspect that the above phishing attack and this password list might be related, is that the first public comment about this list that I can find appeared in a discussion about that scam on October 2nd, and the list mainly contains Microsoft e-mail addresses. There's a very high chance these various scams might not be related.

So on to the analysis:

Total Passwords: 9,845 - This number excludes all the e-mail addresses that had blank passwords
Average Password Length: 8.7 characters long
Percentage that contained an UPPERCASE letter: 7.2%
Percentage that contained a special, (aka !@#$), character: 5.2%
Percentage that contained a digit: 51.7%
Percentage that only contained lowercase letters: 43.3%
Percentage that only contained digits: 17.6%
Percentage the started with a digit, (aka '1password'): 25.0%
Percentage that ended with a digit, (aka 'password1'): 44.1%
Percentage that started with a special character: 0.5%
Percentage that ended with a special character: 2.2%
Percentage that started with an uppercase letter: 6.1%

Letter Frequency Analysis:

Note, for some reason I can't get a couple of the characters to display correctly on my Mac so I'm cutting off several of the non-ascii ones that are only used once or twice:

Overall letter frequency analysis:

aeoi1r0ln2st9mc83765u4dbpghyvfkjAzEIOxRLwSNq.MTC_DB-UP*G@H/ZYF+VJK,\$&X!Q=W?'#")(%^][}< {`>

First character, letter frequency analysis:

a1mbc2sp0lterdjfgn3hi6k759vo48yAwMzBSCuqPLExJRTFDGNV*HOZYKI\W@/-+(.$U&?Q^[,#

Last character, letter frequency analysis:

aos01326e57849nrilydzmtuAhbO.gck*SxpfE@+LvjNRw_-I?/$q!ZX)YKH"UPMDCB#GF'&%}T,]\VJ(

Short Analysis:

Overall, the passwords in this list were fairly strong considering Microsoft only had a weak password creation policy in place, (the password had to be at least six characters long). What was also surprising was the number of passwords that only contained numbers. -See, I told you it would be a short analysis. I'll try to post a more detailed analysis, (such as nationality/language breakdown, effectiveness of input dictionaries, etc), later.

Cracking Passwords with Middle Child

2009-10-06T00:06:00.000-07:00

Yup, it's been a month since my last post. Believe it or not, I've actually been fairly busy, both in working on my probabilistic password cracker, and writing up several research papers. That doesn't even begin to get into the stacks of disclosed passwords I've managed to accumulate but I still need to do some analysis of. Of course it's fairly hard to complain about having too many passwords to crack/analyze. It's sort of like having too many girls ask you out. It's a good problem to have.

Wow, after rereading the last couple of sentences, I really need to get my priorities in order ;)

On that off-topic note though, I figured I should actually make some more of my tools available to the public rather than just boring everyone by talking about crypto. Middle Child is a tool designed to aid in targeted brute force password cracking attacks.

The short summary is that I love using John the Ripper's -incremental mode which incorporates the most sophisticated Markov modeling I've yet to see in a password cracker. JtR uses 2nd order Markov models, (where it models the probability of three letter triplets appearing), and it actually keeps separate probability information for different length words, (aka the probability matrix it uses for a 5 letter word is different from the one it uses for an 8 letter word). To better illustrate this, below are the first 10 guesses JtR will create when running a brute force attack, (using only a lower alpha key-set):

bara
sandy
shanda
sandall
starless
dog
bony
bool
boon
stark

As you can see, it looks a lot like a dictionary attack, but it's actually using brute force. The advantage is that if you let it run long enough it will completely cover the keyspace. For example, it will eventually try unlikely guesses such as 'zqzqqqzz' which a normal dictionary attack will never try. The problem is, while Markov models are very efficient at generating guesses that look like human generated words, they still can have trouble cracking any halfway decent password, (due to time constraints). Middle Child is an attempt to apply additional logic to JtR's -incremental option to more efficiently attack stronger passwords.

-Ed note: Yes that is the "short" summary...

So what is the additional logic that Middle Child uses? Mostly just basic modeling of how people create passwords. For example, people often put numbers at the end of a password, and if they bother to hit the shift key, capitalize the first letter. Another optimization is if users incorporate special characters and numbers into their passwords, they generally use a special character followed by a number and not the other way around. Really all Middle Child does is apply word mangling rules to brute force guesses. By applying these rules to the password guess as a whole, it allows an attacker to target what are traditionally considered stronger passwords using a brute force attack. This is important since most input dictionaries will generally only crack around 30-50% of an average password set even in a best case scenario. That number isn't made up, (like 74% of all statistics...). If you are interested, check out my Defcon16 slides for a further explanation of how I came up with that 30-50% range. Note, I haven't tried to run the numbers again with Sebastien Raveau's humongous wikipedia wordlist yet since it was so large it broke my parsing tool.

Ok, back on track: Now admittedly when you start to use multiple input dictionaries you can achieve better results, (especially input dictionaries created from previously cracked passwords), but after a certain point that starts to resemble brute force as well. I guess what I'm trying to say is that brute force attacks still play a very important role in password cracking. It just means you have to be smart about how you go about using brute force style attacks.

Now, I've actually gotten into arguments over whether this can still be called a brute force attack, (since I'm using Markov models and word mangling rules). Can you say, "Nerd fight"? My response is anything that doesn't use an input dictionary technically is a brute force attack. Personally I like the term "Targeted brute force attacks", though I've seen people call it "Indexed attacks" as well. In the end, it is what it is, and I find it useful so I don't care if you call it a brute force attack or not. I've posted before about how troublesome it is that the password cracking field doesn't have standard definitions...

You can get the tool, (along with some more info and a short user's guide), here.

For the love of one time pads, or Why we still mess up crypto

2009-09-03T21:45:00.000-07:00

I know, "Oh great, another crypto post". I'll try to get back to talking about password cracking next week, (as I have a bunch of stuff I'm just polishing up right now). Also, I'm still trying to reply to all of the e-mails I've received since Defcon so if I haven't gotten back to you yet, I apologize and I'm working on it.

Well, on with the show. Bruce Schneier reposted a writeup from another blog by Steve Bellovian, (it's like Twitter), that talked about the history of one time pads, (which I'll refer to as OTPs). More to the point, why you should generally avoid using them, and instead use standard cryptography, (RSA, AES, etc). This certainly isn't news. In fact Bruce has been writing about it since 2002. I have to say I enjoyed it simply since it introduced me to Bellovian's blog which is really good. This post isn't about OTPs though, despite the title and the fact that I'll be talking about them a bit. What interests me more is how the security community as a whole deals with cryptography.

People love OTPs since they are the only crypto algorithm that has a valid mathematical proof that shows they are unbreakable. I'll spare you the long proof, but it has to deal with the fact that every single bit is encrypted with its own key. Aka even if you know 99.9% of the plaintext message, it doesn't help you when trying to decrypt the other 0.1% since the encryption of the known 99.9% has no bearing on the encryption of the unknown 0.1%. Letter frequency analysis, machine cryptanalysis, known plaintext attacks, quantum computers; all these prove worthless against a properly implemented OTP.

The problem is, everything I just said depends on the assumptions in the proof being true in real life. Another way to say it is that the cow really needs to be a sphere. The two biggest assumptions are that

The key has to be truly random, and

The key must only be used once.

If either one of these is not true, OTPs become subject to attack, just like any other form of cryptography.

We've been using OTPs since at least 1917. The fact is we still have a hard time getting them right. Our random number generators turn out to be not so random. People reuse keys because key distribution is a major problem. Multiple groups share the same key. With the defender shipping out so much key material, some of it gets intercepted. The list goes on and on. After a certain point, you need to stop blaming the users, and instead try to come up with an alternate solution.

As of when I'm writing this, there are currently 37 comments in Bruce's original thread. Of these comments, there were 29 different posters. Going through the comments trying to figure out if they were pro-OTPs or not, I came up with 15 people supporting the use of OTPs, 10 people against their use, and 4 people I couldn't classify. (On a side note, going through numbers like this is why I'm so far behind on my e-mail...). Of the 15 people supporting OTPs, two came up with their own mathematical functions to create random numbers, and 4 people suggested that key size doesn't matter as storage space becomes cheaper. The very first comment turned out be my favorite:

"I think that there is a bias against OTP among cryptographers because OTP takes a problem that you need a cryptographer to solve -- message security -- and turns it into a problem that you don't need a cryptographer to solve -- key distribution. Cryptographers do not like approaches to problems that make them irrelevant."

Snark aside, I think the above comment brings up a lot of good points, though not the ones the poster intended. People have a tendency to get fixated on the crypto algorithm used. You can see a good depiction of it in this xkcd comic, (another reason why xkcd rocks). In reality, very rarely is the crypto algorithm the weak link. That's why I'm into password cracking. Quite simply, there is no way I'm going to crack AES. Heck 3DES is beyond me. Attacking the user though is something I can do. Likewise, in my last overlong post, I mentioned that I didn't trust RC4 encryption. This isn't because RC4 itself is broken, (in fact it can be very strong), but that implementing it correctly is almost impossible. Key exchange, key storage, identification, authentication, modes of operation, (ECB anyone?!); these are the areas where crypto implementations run into problems. Referencing the above comment again, the poster is mostly right. Most cryptographers don't like OTPs because while they solve the problem of encryption algorithm, we already have a lot of good solutions for that already, (let me mention AES again). Why cryptographers caution against using OTPs is because they are the absolute worst algorithm to use when it comes to key exchange, and key exchange is a much harder problem. Heck, public key cryptography was invented specifically to deal with the fact that key exchange can be too difficult even for block cyphers like AES.

I could go more into the implementation problems with OTPs, (Sysadmin analogy: It's like trying to maintain the patch level of servers all over the world when the servers don't have internet access), but I want to get back to talking about the security community. Your typical programmer should not have to worry about designing their own crypto protocols, (aka how the crypto algorithm, key exchange, authentication, etc all go together). The fact that many programmers still have to, is a failure on our part. Furthermore, we as a security community need to become less fixated on the encryption algorithms, and instead look at the crypto protocols instead. Saying that you use AES is like saying the car you are trying to sell me has wheels. Yes, it's a good and necessary starting point, but there's a lot of other requirements that would be good to know before I make a purchase. That's why I like IPSec. I hear that one word, and I can be fairly certain that the encryption protocol the program is using is solid, since IPSec not only deals with the encryption algorithm, but all the other stuff as well. Yes, there are issues where people allow "aggressive mode," (don't do that), but for the most part, if you don't set IPSec up securely it doesn't work. Also, the fact that there are multiple libraries, which have been vetted, available for it means that programers don't have to worry about coding it up themselves.

One last thing: to those who say OTPs are useful for spies since they don't require a computer to encrypt/decrypt a message. Let me point out that the last time I flew on an airplane I had a grand total of four different computational devices on me. The era where carrying around an Ipod made you suspicious has passed. Carrying around a code booklet filled with random numbers on the other hand...

WPA not cracked yet

2009-08-27T23:55:00.000-07:00

I'll admit, when I heard that WPA, (specifically implementations using TKIP), was cracked, my first reaction was "It's about time." This does not stem from some deep held desire to obtain free internet access from my neighbors, but instead from the fact that TKIP use RC4. It's extremely hard to implement RC4 correctly. So much so, that in general I don't trust any encryption algorithm that uses a stream cipher vs. a block cipher, (for the crypto purists, yes block ciphers essentially become stream ciphers when put in CFB mode, but that's also when problems tend to occur).

I guess what I'm trying to say is I'm inclined to take a dire view of WPA's security. That being said, when headlines like "Wi-Fi Code Cracked in Minute" appears on the front page of Yahoo, (bad grammar and all), I really feel the need to post something. Regardless though, please understand, if you are still using WPA in TKIP mode you should at least start thinking about upgrading to WPA2, or WPA using AES. Even if this particular attack doesn't prove weaponizable, chances are another attack later on down the line will.

So disclaimers aside, and with all the doom and gloom I already posted, what's my problem with the Yahoo article? Well, it's the simple fact that the current attack doesn't break WPA in a practical sense yet. Now I admit, I'm not an expert when it comes to wireless encryption protocols. I consider myself more of a hobbyist, ~~but I did stay at a Holiday Inn last night~~. I mean I did actually read the academic paper describing the attack details. Also my initial job after graduating from college, (the first time), was attacking wireless networks so this is a topic near and dear to my heart. Oh, and while I'm talking myself up, some of my Master's research involved attacking Ad-hoc networks which tend to use wireless protocols. I guess what I'm trying to say is that while this post may sound like I know what I'm talking about, chances are there are major flaws in my understanding of the attack and it's implications so please feel free to correct me.

The attack described is a refinement of the ChopChop attack applied to WPA that was originally discovered by Martin Beck and Erik Tews. There's a couple of things to note about this attack that limit its usefulness in real world situations.

It doesn't disclose/recover/discover, or whatever word you want to use, the encryption key. What this means is an attacker can't use this attack to figure out your password, hop on your network and start reading your e-mail or download random pictures of scantily clad individuals.
While this attack does allow the attacker to decrypt encrypted packets, even with the refinements proposed, it is not an entirely offline attack. It still needs to use an authorized user, (access point, and/or client), as an oracle. This means an attacker can't just collect the encrypted data, and then go home and spend the next year decrypting it on some botnet/computer in their mom's basement. Essentially they have a limited time window to decrypt the packets, and the limiting factor is not how fast their computer is, but the amount of data that is leaked via error messages sent by the defender. The reason that the original attack took so long was that if an attacker sends more than one packet with a bad Message Integrity Check within 60 seconds, the AP would drop the connection. Thus it would take a minimum of 11 minutes to make 12 submissions to the AP. Those 12 error messages would be enough for the attacker to decode 2 byes of data. Similarly, packet injection takes around 5 minutes to execute, with three of those minutes taken up by submitting four different packets to obtain specific error messages.
Continuing on point #2, in general most implementations of WPA are smart enough to realize that if someone is still trying to submit the same packet after 11 minutes, something is wrong. Or more to the point, WPA uses has a counter, (called the TKIP Sequence Counter or TSC) so when the actual client sends more data, the AP will no longer try to decrypt older packets. Beck and Tews get around this by attacking certain WPA implementations that allow multiple channels for QoS where the WPA implementation isn't smart enough to increment the TSC counter on all of them. One of the main improvements proposed by Ohigashi and Morii is to perform a true MITM attack where the client only talks to the attacker, not to the access point. Thus when the attacker wants to decrypt two bytes from a packet, they simply DoS the client for around 15 minutes. Needless to say, while this may be useful to decode an Arp packet at 3:00am in the morning, employing this attack when a user is online, and you know, sending interesting data, might be noticed. This is further complicated by point #4.
The attacker has to know EVERY byte in the packet they are attacking with the exception of the byte or two of information they are trying to discover. Essentially the attacker conducts a known plaintext attack by constructing every possible packet that could be created by those two unknown bytes of information and then uses the error messages from the Access Point to identify which one is the correct packet. What this means is an attacker can't use this attack to decode the first two bytes of someone's telnet login password since they don't know what the rest of the password is. That's also why you see these papers talk about decoding and injecting Arp packets. Essentially what they are assuming is that they know the first three octets of defender's IP address, (such as 192.168.0.x), and so they are only trying to decode the last octet, (the 'x'), for both the access point and the client. Conveniently that is only two bytes of information. Since it's an Arp packet, the mac address information is already known, (it's not encrypted by WPA), and the attacker can figure out what the rest of the packet will look like. Now from my reading of both the original paper and this new one, there is nothing stopping the attacker from attempting to guess what more than two bytes are. Well, except for the fact that the attack would then require several hours to several years to decrypt 4-5 bytes from a single message. I would expect that after the first week of the DoS attack someone would at least try to reboot the router, not to mention the automatic idle timeouts ;)
Finally, the "1 minute" time everyone is talking about only applies to injecting forged arp packets into the network, (it still takes around 11-15 minutes to decode a packet with the new attack). They achieved a speedup from the 4-5 minutes it took Beck/Tews attack to inject an arp packet by designing a way to forge the packet without having to contact the access point to verify if the packet is valid. Basically, instead of making sure their packet will be accepted, they just say "F*** it! Lets send it anyway. There's a 37 percent chance it will get accepted!). Then there's the fact that I have a hard time coming up with a non-DoS attack that involves injecting an Arp packet when the attacker doesn't have an authorized computer on the network, (otherwise why are they bothering to try and attack WPA in the first place). The only thing I can think of is framing someone else for Arp spoofing. Oh and the DoS attack isn't that useful since in order to pull it off, you have to already be able to perform a DoS attack, (though in all fairness you could perform a DoS attack against some other computer on the same Layer-2 network besides the client you are currently attacking).

Now I want to stress, this is good research that Ohigashi and Morrii are doing, and it almost certainly will lead to more potent attacks. Likewise, their paper is honest about what they are doing and the limitations of their attack. It's just that people see the words "WPA packet injection" and "Less than 1 minute," and automatically assume that WPA is as weak as WEP. Or as the Yahoo article puts it,

"The second generation of Wi-Fi security systems has now been broken as badly as its notoriously insecure predecessor"

It's just not true. As I said at the beginning of the post, if you are using WPA you should change to WPA2, but your neighbor's kid isn't going to be using your wireless anytime soon.

Defcon Roundoup Part II

2009-08-18T23:26:00.000-07:00

Saturday:

Started out at Hacker vs. Disasters, but I bailed on the first speaker and instead went to the talk by Joe Grand on hacking parking meters. It just further reinforced my belief that society functions because there are not many talented bad guys. Or I should say, the effort to hack these systems outweighs the cost of using them legitimately. Still the ability to frame other people is scary. Also, you can buy ANYTHING on E-Bay.

Then went back to Hacker vs. Disasters to see Renderman talk. Didn't learn much but had a great time. Favorite quote: "Most people will be absolutly useless in a disaster. Actually that's not true. They are mostly made of meat..."

Of course I went to the Mythbusters talk. I was blown away by how good a speaker Adam Savage was, along with the great topic "Failure". Like everything else in his life, Adam's failures truely were epic, and I think they need to show a copy of that speach to every kid in Intermediate/High School. It's an important lesson that failure is normal, and you can bounce back from it.

PLA Information Warefare Development Timeline. Quick disclaimer, I've worked with the person who gave this talk, (and I found it hillarious that he originally used his name but later decided to use his handle instead). The talk itself was jam packed with information, though I had a hard time being engaged by most of it. Quite honestly I'm not shocked that another country would A) Develop military plans to fight the US. and B) Develop information warfare capabilties. It would almost be the height of irresponsability if they didn't. This first half of the talk dealt with the rise of China's IW program, (along with the development of certain kinetic military capabilities). I really would have liked to stay around for the second half, but I needed to see the next talk since it corrolates with some of my research.

Sniff Keystokes With Lasers/Voltmeters: I am in awe of these guys presenting ability. They could talk about the weather and I'd show up. Just check out this video they created to demonstrate one possible use of their research. From a practical standpoint, the ability to read PS/2 keyboards via signal leakage into the ground wire was really scary. It was something that I hadn't even considered before, (and honestly would have gone "That's impossible", if someone would have suggested it). I wouldn't be surprised if the laser exploit gets deployed at next year's Defcon CTF.

I am Walking Through a City Made of Glass: This talk once again focused on the Chinese hacking scene, but was slightly more useful to me since it covered the non-state affiliated Chinese hacker groups. It was refreshing to finally hear someone say that in addition to the attacks coming from home-grown Chinese hacking groups, other countries/groups are buying Chinese botnets/proxies to launch their attacks from.

And that was it for Saturday, (I spent the rest of the day wanding the CTF room, Vendor booths, etc).

Sunday:

I was freaking out about my talk, so I wasn't the best audience member. That being said, here is what I went to

Down the Rabbit Hole: This talk, (or at least the same title), has been given before at several other conferences, but I've always managed to miss it. It was fairly good, though as I said before I had a hard time concentrating.

Hack the Textbook: I feel sorry for the presenters since it's hard to make a website that rates and corrects computer books sound interesting. That being said, this project has the potential to help the secuirty industy more than any of the other talks given this weekend. We need to teach people how to write secure code, and if it takes off, this project has a good chance of helping people do that.

Unmasking You: This was a solid talk, and some of the user fingerprinting was really nasty. I don't know how much these attacks are going to show up in the wild though.

Search and Seizure Explained: A solid talk going over the different search and seizure laws. I hope I will never need to know the legal requirements that need to be met before a body cavity search can be performed on me when I'm crossing the border. Of course, that's one of those pieces of information where you REALLY need to know it if the situation arises.

And that was it for me. The rest of the time I spent in the CTF room and the speaker ready room. As for my talk? I don't remember most of it, though I think it went well. My demo didn't crash which was the big thing ;) I had a real good group of people show up for Q/A afterwards, and I apologize since I was still hyped up on adrenaline from the talk. That's why I have to practice my talk a million times before I give it, but once I get off script, (aka Q/A), pretty much all everyone got was a direct stream of consciousness feed from me laced with a healty dose of profanity.

That was it for Vegas. I had a drink with some of the people, hopped on a cab with one of the Shmoo guys before the closing ceremonies were finished, and then spent the next two weeks googling my name trying to figure out what people thought of the talk ;)

I hope to see everyone at Defcon 18!

Blog Spammers

2009-08-11T21:28:00.000-07:00

Well, it looks like I've had my first tangle with blog spammers. If I deleted any legitimate posts that offered strong, but completely abstract, praise for this site along with a signature full of links, I apologize.

Defcon 17 Roundup

2009-08-10T19:15:00.001-07:00

It hardly seems like Defcon 17 was only a week ago. Right now it alternately feels like I just got back from it, or it happened a million years ago. Ok, I admit it. That link has nothing to do with this post, defcon, or even the idea of "a million years ago", but I stumbled across it in my Google search for something more appropriate and I thought I should share. Librarian hackers: need I say more?

As I was saying, Defcon 17 occurred at some point in the past. I won't detail the parties that went on, though there were a few. The exception I will mention is the Toxic BBQ which was held on Thursday. Having skipped it the last two years due to various reasons, most of which involved the words "108 degrees", "outside", "off-site", and "laziness", I was truly amazed at how fun this event was. It also was the one event where you could relax, drink a few beers, (making sure to drink plenty of water as well - let me reference that 108 degrees again), and talk to people without music blasting in the background. All in all, I'm going to make sure I don't miss it next year.

Now on to the actual talks, which supposedly are the reason why everyone goes to Defcon in the first place.

Thursday:

I arrived too late to see any of these, but I heard good things about "Effective Information Security Career Planning", and "Hardware black Magic - Building Devices with FPGAs". I really wish I could have attended the FPGA talk since as you can imagine there are a few ways that can help my research.

Friday:

Talks I attended:

Beckstrom's Law: I saw Rob Beckstrom speak at last year's Defcon panel "Meet the Feds", and I have to admit that I didn't have a very high opinion of him. Later when reading about his resignation from the post of Cyber-security chief I had to re-examine my previous evaluation as a lot of the points he made were very good. That being said, I managed to sit through about 10 minutes of this talk before I had to walk out. Between him promoting his book, explaining what DNS is, and warning us he might use "math", I realized he must have forgotten that he was giving this talk to Defcon attendees and not your typical office boardroom. That's a shame too since I looked at his slides afterwards, (the ones on the CD, not the ones he used), and there was a lot of good stuff in them. The problem he was covering is extremely important, and I think everyone agrees that the way we currently value networks and computer security falls into "pick some numbers that sound right." That's not acceptable and it's good to see someone trying to do something about it. I think in the future I need to focus on what Beckstrom writes, and skip any of his live talks.
Asymmetric Defense: How to Fight off the NSA Red Team with Five People or Less: As the name implies, this talk detailed how the US Merchant Marine Academy goes about participating in NSA's Cyber Defense Exercise with a limited budget. It was a good talk, and one that I would recommend browsing through when it becomes available online. It also annoyed people from the other service academies to no end which was amusing as well.
More Tricks for Defeating SSL: This was THE talk of Defcon. I'm sure you've heard about it already so I don't need to go into details. What made this talk amazing was not only did Moxie completely break SSL; not only did he do it a way that was totally l33t, (Pascal strings?!); not only did he show some scary attacks with it like completely owning any computer that was running Firefox, but he gave a great presentation as well. When he showed the blurry code segment and asked us to find the bug, (hint it's the part with all the nested If statements), I was blown away by his ability to convey this information to the crowd.
The Year in Computer Crime Cases: Yay EFF. The most interesting part was hearing about the problems they had trying to set up a secure war-room at Defcon last year.
Defcon Security Jam 2: I eventually ditched this talk and went to grab some lunch. I think part of the problem was the general setup of this hybrid talk/panel session. It wasn't bad, but eating food was a better use of my time.
Computer and Internet Security Law - A Year in Review: Of the three "law" talks I went to, this one was the best. It really helped explain some of the reasoning behind certain rulings, such as why the cops can obtain a warrant and force you to open up a keyed safe, but they can't force you to open up a combination safe. In that case, it's all about attribution: aka if you know the combo, the safe is probably yours. With a key though, all the cops can "prove" is you knew where the key was. Yah, laws are weird.
Malware Freak Show: I wasn't able to get into Johnny Long's talk so I went to this one instead. Looking back, it just goes to show that it's good that life doesn't always work out the way you want it to. I always wondered what computer security measures casinos use. Now I have a better idea, and I was shocked to find out that in at least one case the casino did such a poor job.
Fragging Game Servers: I love to hear Bruce Potter talk, so it was entertaining, but he and Logan really needed another two to four months of work before this presentation should have seen the light of day. I feel sympathy for them as I've been in a similar situation myself. Most people don't realize it, but with these talks you need to submit a proposal around four months before the actual conference itself. This means the presenter usually has to make a few educated guesses about where they will be when the conference rolls around. Sometime those guesses don't match up with reality.
Something about Network Security: So of course I had to go to the Kaminsky talk. I originally was going to see the talk by Travis Goodspeed, since I'm just blown away by his work, but with all the craziness of the zf0 hack I wanted to see what Kaminsky's reaction to it was. Pretty much everyone took the view of "but for the grace of god go I", with Dan being hacked. I have to admit, it wouldn't take much to completely 0wn me so reassessing my security setup is certainly on my to-do list when I get back to Tallahassee. The talk itself wasn't his best, but a lot of that can be attributed to Moxie covering much of it earlier. In short, it was a tough week for Dan, though my opinion of him hasn't been diminished at all.

And that was my Friday. I'll leave Saturday and Sunday for a later post.

EliteHackers Data-set

2009-07-29T13:55:00.000-07:00

If you haven't already heard, ZF0 just released their 5th installment of hacking the hackers, and boy is it a doozy. I was almost expecting to see my username/password show up there since it looks like the Cain&Able forum was hacked about a month ago. Still Mitnick, Kaminsky, and several other high profile hackers were completely 0wned.

I downloaded the data dump and have been perusing through it. Coming in at whopping 400+ pages long, it will make good reading on the airplane. Of course the part that really interested me was their coverage of cracking user passwords from the Elitehackers.org website. Apparently they grabbed around 24 thousand password hashes from the site and managed to crack 43% of them, (of course they assigned it a N00b score of 87% since they multiplied it by x2 to make it look better. I guess it's like assigning a "proof" to describe the alcohol content of liqueur). That being said, since they were salted hashes, that's pretty good. Unfortunately ZF0 only posted 1,000 of the cracked passwords and almost no un-cracked hashes which will make analysis of the set tricky; Kind of like reading a mystery novel told from the point of view of an untrustworthy narrator. That being said there should be enough data to be able to make some educated guesses about their actual attack pattern and input dictionaries they were using.

It should be an interesting Defcon. I'll post more on this when I have a chance.

Defcon 17

2009-07-28T21:14:00.000-07:00

Just packing everything up and getting ready to head to Vegas. I'll be closing out the conference 4PM Sunday with my talk:

Cracking 400,000 Passwords, or How to Explain to Your Roommate Why the Power Bill is a Little High

Remember when phpbb.com was hacked in January and over 300,000 usernames and passwords were disclosed? Don't worry though, the hacker only tried to crack a third of them, (dealing with big password lists is a pain), and of those he/she only broke 24%. Of course the cracked password weren't very surprising. Yes, we already know people use "password123". What's interesting though is figuring out what the other 76% of the users were doing. In this talk I'll discuss some of my experiences cracking passwords, from dealing with large password lists, (95% of the phpbb.com list cracked so far), salted lists, (Web Hosting Talk), and individual passwords, (TrueCrypt is a pain). I'll also be releasing the tools and scripts I've developed along the way.

The talk itself is going to mostly focus on what these attacks mean to the defender and some of the different optimizations an attacker can use to increase their chances of cracking passwords given limited resources. Hopefully it should be a fairly fun talk. A preview copy of my slide deck can be found here.

Pass-Phrase Input Dictionary

2009-07-19T20:06:00.000-07:00

I could write some elaborate five thousand word post about this, but the following is fairly self explanatory. I created an input dictionary of all the phrases in wikiquotes for use in cracking pass-phrases. You can download it off my tools site here. The final wordlist has around 187k phrases in it. I limited the phrases to a maximum size of 140 characters since anything longer than a twitter quote probably won't be used in real life. On that note, anyone have any good ideas how to spider all the twitter postings?

A couple of things: First of all I only used the primary quotes, not the derivations, since it's fairly hard to automatically parse them out without bringing in a ton of garbage as well. Second, talking about garbage, I'm parsing user generated data so there are still some "artifacts" in the wordlist. Third, I left capitalization and punctuation in the actual quotes. If anyone wants a list with those removed please let me know. Also if you want a list that only contains the first letter of every word, I can do that as well. Enjoy.

Keyboard Dictionaries

2009-07-17T18:39:00.000-07:00

By far the most popular download from my dictionary based rainbow tables has been the input dictionary I created based on keyboard combos. It's been downloaded close to 2000 times which means about 1995 more people have downloaded it than read this blog ;) So of course I'm looking to improve on it. The original dictionary was created thanks to an abundance of free time and my own personal lack of carpal tunnel syndrom as I typed each entry into it. The problem of course was that I've since found out that there were many keyboard combos that I missed.

So that's why God, (or at least Solar Designer), created external moduals for John the Ripper. One of them simulates a keyboard layout so if you type

./john -stdout -external=keyboard

It will start to output different strings based on how close the keys are on your actual keyboard. Me being the lazy person I am of course decided to pipe the output of that into a file to create a new and improved "keyboard dictionary". The problem is I left it running and after a while started to wonder why it hadn't stopped. Checking on it, I found that the file it had been creating filled up over 18 gigs of disk space. That's not acceptable.

I really don't have anything else to offer right now, but I just wanted to give you a status update and let you know it's a problem I'm working on ;)

Using online password crackers

2009-06-24T20:48:00.000-07:00

Online password crackers are extremely popular and it's easy to see why. Instead of having to go through the trouble of cracking the password yourself, why don't you just submit it to someone else who has gigabytes, (to terabytes), of pre-calculated hashes to crack it for you. Just as a warning though, there are some privacy concerns when using these sites, (what? You don't think they store the hashes that are submitted to them?).

According to www.hashkiller.com, which keeps track of the effectiveness of these sites, (quick disclaimer: recently the reporting mechanism seems to be having issues), most of these sites crack around 20 to 40% of the passwords submitted to them which is fairly good, (actually really good since most of them rely on quick lookups in pre-generated tables). This statistic matches what I've seen both from my own testing and looking at other people's results, (aka the person who attacked phpbb.com submitted some of the passwords to one of the sites and cracked around 24% of them according to the textfile he/she posted online).

Recently I've been playing around with md5-utils, (available here), which is a program that will submit your password hashes to 33, (as of right now), different online password crackers. The advantage of course is that as a group online password crackers do very well. Where I've really found it useful though is as a sanity check on my own work. Aka as I posted before, I've cracked 90% of the phpbb.com list, but when I submitted a small subsection of the passwords I haven't cracked yet using md5-util I quickly found out that I needed to spend more time brute-forcing passwords that only contained uppercase letters and numbers, (I knew that was popular and even mentioned it back in my Shmoocon08 talk but for some reason I had forgotten that. Probably because I had associated it with LANMAN hashes.) People really hate hitting the shift key.

The main problem with md5-utils is that it is very "polite" in that it will only submit one hash at a time and it takes several minutes to check it. This means running even several hundred hashes though it takes a while. It would be fairly trivial to crank it up a notch, but I've been hesitant to do so since I like to live my life by the rule, "Don't be a jerk" and I don't want to hammer the online cracking sites with requests.

Now for some trivia. One password that md5-utils cracked was "HPw2207!@#" (without the quotes of course). Looking at it I was really impressed. Ok the "!@#" is fairly easy since it just is a keyboard combo, but to make a rule try three letters, (the first two capitalized), followed by four random numbers and then a keyboard combo of symbols is pretty impressive. It certainly wasn't pure brute force, that's for sure. So of course I decided to do a google search to see if HPw2207 might actually mean something.

No, not Laura Croft. Look at the bottom right corner of the screen. Yup, the person had used the label on their monitor, HP2207, as their base password and then just added !@# to the end. I'm sure that's also how their password was cracked, aka in one of the input dictionaries someone has, they've probably listed out all the computer monitor types. Hey, I found it amusing plus it gives me a chance to post tomb raider pictures to this blog ;)

Site News Update

2009-06-14T09:58:00.000-07:00

As stated in the previous post, I'm in the middle of creating a new site to hold all the tools, custom dictionaries, and research papers I'm working on. It's fairly bare bones right now but I'm plugging away at it. Expect the layout to change quite a bit. I'd recommend only linking to the main page for the next month just because I'm still juggling around which pages should go where.
I'm making the change since everyone ,(including me), hated the old googlepages site. The new site also allows comments so if you want to talk about a specific tool, file a bug report, or make a request please do. My one worry is hosting space, (aka some of these dictionaries and the rainbow tables in particular are large), but I'll cross that bridge when I get to it.

The new site can be acessed from the link in the sidebar to the right or by going to

http://sites.google.com/site/reusablesec/

Cracking Web Hosting Talk

2009-06-12T06:29:00.000-07:00

I'm working on completely redoing my tools page so hopefully I'll be able to start posting some new dictionaries, password cracking programs and scripts sometime this weekend. Enough site news, on to the post!

I've talked previously about cracking password lists from phpbb.com and the finnish78k list. Now I would like to discuss another list that I've been working on. Back in March, a site called "Web Hosting Talk" was compromised via a flaw in their backup server. The attacker then distributed a list containing user information, (usernames, e-mail addresses, and password hashes), to several file sharing sites.

I wasn't able to obtain a copy of this list, (and trust me, I tried), but I'm actually pretty happy about that as it means WHT was able to yank most copies of it offline quickly. What I wasn't happy about was the "advice" WHT gave their users regarding changing their passwords...

"Passwords are hashed with salt. It would be an unprecedented event to reverse engineer our passwords. I change my password periodically though, so maybe today is a good day for that."

That's like saying, "The building is on fire, but I can't imagine it burning down. Occasionally when there is a fire burning out of control I go outside. This might be a good time for you to grab some lunch, or whatever..."

Now there are a couple of things they could have done.

A) Force users to change their passwords when they logged on again

B) If the user logs on to the site from a different IP address then they normally do, prompt them with a "secret" question, or send them an e-mail with a new password. <--More secure, but a pain in the butt from a system admin side of things

C) Warn users they need to not only change their password, but change it on other sites they may have used it on <-Yah it's bad PR, but it's necessary

Honestly for a site like WHT, they probably should have gone with both options A and C, as B might have been overkill for the value of the site, (aka someone could log on a make a couple of posts or read private messages, but it's not like they store financial or medical data ... at least for a user to see).

So if I wasn't able to find that list, what have I been cracking? Well, when WHT reopened they apparently missed a backdoor the attacker had left in their system. About a week or two after the initial attack the hacker released another list containing all the user data. This time though the attacker also included Credit Card numbers, expiration dates, and the CCV number on the back, (which online retailers are not supposed to store). That's the list I actually stumbled upon. Full disclosure: when I found out I had downloaded stolen CC info I deleted those files as quickly as possible and had visions of FBI agents kicking down my door for the next week. Luckily the user info was stored in a different file.

The list contained 202111 unique user/password combos. The attacker also included a file talking about the attack which contained one very interesting fact, (among all the swearing and racist comments). In the time between the initial attack and the most recent one, only 1348 users, (counting system administrators), changed their password. That's less than 1% or the userbase (0.6% to be precise). To put this in perspective, according to the link above the list also included 2,218 credit cards, (the site was storing 9,561 credit cards but the hacker kept the rest of them to him or herself).

Assuming that this password hash was "impossible to reverse engineer" this wouldn't be a problem. The question of course was, how true is that statement? The first step was to find out what forum software WHT uses. A quick Google search revealed they use vBulletin. The next step was to figure out the function that was used to hash the passwords. Once again Google provided me with the answer:

MD5(MD5(Password).Salt)

Modifying the password cracker that I had used previously to attack phpbb.com's passwords, (I'll try to post it this weekend), I was ready to go. Of course, how should I test it? I mean WHT could have changed the hashing function to make it almost impossible to figure out. I could spend days/weeks trying to crack those passwords only to find out I was hashing it wrong... So I loaded up the password list and entered the guess "password" since I guarantee that a site with 200k+ users and no password creation policy at least one of the users is going to pick "password".

And .... nothing.

I didn't crack a single one. Feeling slightly less smug, I tried "Password123!", "password123", "monkey", "football", well you get the idea. Still nothing. At this point I was feeling really sheepish and had all sorts of scenarios going through my head. A couple of days later though I realized that the problem was I wasn't converting the first hash of the guess to its ASCII representation before rehashing it. Once I made that change, I reloaded all the password hashes, crossed my fingers and tried "password" again.

Yup, that did it. Watching several hundred cracked hashes flash across the screen was a sight to see. I had accomplished the "unimaginable" and reverse engineered their password hash using only Google and my horrible programming skills. Of course since then I've found out that I wasn't the only one. There already exists a 3rd party patch for John the Ripper. Also, over at hashkiller.com, there is an entire forum devoted to cracking vbulletin and other forum hashes.

All I can think of is the image to the right. "Unimaginable! I do not think that word means what you think it means..."

Of course, once I started to launch my actual attack reality set in. But this post grows long and it's a Friday night so that will be left for another day ;)

In which a milestone is reached..

2009-06-11T10:53:00.000-07:00

I think I've made as many posts this month as I have readers ;) I just want to remind the four or five of you that your input really matters to me. If there is something you want me to look into or you disagree with a post, please let me know.

Rule #31 of Hacking: Bypass the Crypto

2009-06-11T08:19:00.000-07:00

It's a story as old as time. A webmail company says their security is unbreakable. They give out their CEO's username/password and offer a $10,000 reward to anyone who can break into his account. Guess how this ends? Despite the predictable outcome, this story has been really interesting to me, not only for the issues it brings up but how the security community has been reacting to it.

I think security contests can be a good strategy for a company. That being said, it really matters how they approach it. Google's take on it with their Native Client hacking contest was spot on. Not only did they get a lot of positive buzz, but they also attracted some of the smartest hackers out there to compete for only $8,192. You normally can't even get a CISSP to give you a Nessus scan for that type of money. The reason for this of course is that hackers don't do it for the money, but for the challenge and bragging rights.

Looking at other such events, a couple rules of thumb to holding a successful hacking challenge seem to come to mind.

1) Don't ever use the words, "un-hackable", "un-breakable", or "perfect". You need to approach these competitions with a healthy dose of realism and the knowledge that your security system probably will fail.

2) Treat the participants with respect. Bring them into the process and take the time to actually listen to them. You want them to feel like they are part of the team making a better product. If this doesn't happen then they will instead write posts talking about how you "don't get it".

3) On the other-hand, you can put so many rules and restrictions on the contest that it becomes almost impossible to win. Of course this is not ideal as you don't actually test the security of your system and this approach should only be used for marketing reasons. Normally this only works with abstract problems like with the Bodacion challenge where you can control everything. Otherwise you get hacked and just look dumb when you claim you weren't really hacked. Also, most security professionals will avoid your product like the plague but then again, we generally are not the ones buying this type of stuff.

Now about the merits of StrongWebMail's particular product:

They claim to be the most secure webmail service out there. For a nominal fee, when you attempt to log on to their site they will then call your phone for confirmation. While I haven't seen the details on their exact protocol, (nor do I want to spend $5 to start an account), I think I can safely say they call you after you typed your first password in successfully. If not, forget denial of service, think denial of sleep as someone brute-forces your account at 2am in the morning...

The thing is, the authentication mechanism doesn't matter much when you can bypass it. StrongWebMail's back-end website had several XSS vulnerabilities that apparently were trivial to exploit. This means that in a targeted attack you would be safer off using yahoo's webmail. That being said, I do have to admit that StrongWebMail is more secure against conventional password attacks. This isn't trivial. When singles.org was hacked their password list was leaked. The 4chan crowd then got ahold of it and proceeded to try those passwords on other accounts associated with the e-mail addresses provided to the site. Since people often use the same password for all their accounts, webmail accounts were hacked. Horrid e-mails were sent out to family and friends. The same goes for paypal accounts, facebook accounts, amazon.com accounts... well you get the idea.

It really comes down to what you are trying to protect against. Personally I advise just using a unique password for your e-mail account. That way you get the back-end security of google or yahoo for free, but also are resistant to the above attack. Yes I know, remembering different passwords is hard which is why I normally have different classes of passwords. My bank password is different from my mail password, but I use the same password for many of my other less important accounts. Oh, and write your password down. If someone is willing to sort through and read all the papers in your filling cabinet, they probably already stole your computer, (robber), or installed a keystoke logger, (government or a really smart robber).

Please don't take this as a knock against two factor authentication. Two factor authentication really raises the bar for a hacking attack to be successful. By using two factor authentication, it moves the security requirement away from the user having to select a strong password. That's huge. It also often forces an attacker to time their attack to coincide with the user logging into the site, (though CSRF and other attacks can get around this). That being said, StrongWebMail's approach is pure overkill. A much better implementation is this free I-Phone app made by Blizzard for World of Warcraft. Sure there are security implications, (what if they hack your I-phone?), but at that point we're getting into, "you're screwed already" territory.

So in conclusion: Don't ever believe in perfect security.

ASCII Art in Password Cracking

2009-06-03T12:11:00.000-07:00

Just a quick warning but almost all the links presented here are NSFW, (more from an embarrassment factor due to ascii representations of male and female genitalia).

As pointed out in the comments of this post not all passwords are created from dictionary words or pass-phrases. One other way of creating a password is to use ascii art instead. For example:

/><{{{{"> --fish

///\oo/\\\ --spider

d[ o_0 ]b --robot

You get the idea. Of course the most common ascii art used is that of the male genitalia. I'll spare you the examples of that on the front page of this blog ;)

The question then is what is the best way to attack these passwords? My gut feeling is that a standard dictionary based approach is the way to go, but instead of input words you can use a wordlist full of ascii art instead. To test this I googled various terms such as "ascii penis", "ascii porn", "one line ascii art", along with some actual pictures of said ascii art to collect as many examples as possible. One a side note, I hate to envision what Google thinks of me based on my browsing history...

What I found is that most people used variations of common "construction" techniques of their ascii pictures. For example the shaft is usually either '=' or '-'. There are common heads, bases, depictions of sperm, and depictions of what said ejaculation is landing on. I then threw all of this into a script and had it output all the possible different combinations. The end result is a little over 3 million examples of NSFW ascii art for use in password cracking. You can get a copy of the wordlist here. In all likelihood it's the largest collection of ascii porn on the internet. That's exactly what I thought I would be creating when I decided to go for my PhD. Sigh, at least it's better than frog fluffing, (a reference to the movie beerfest).

The list is rather large since I included a lot of options that probably won't be used in real life, such as 'p' to represent someone with only one ball, (people on the internet are inventive, what can I say). Also spacing added quite a bit to it since in password cracking the spaces used/not used do make a difference. If you have any examples I missed please post them in the comments of the site where I'm hosting the wordlist as I'd rather avoid getting my inbox filled with depictions of ascii penises and vaginas.

The next step is to create another wordlist containing "normal" ascii art such as hearts, frogs, etc. Once I have that done I'll post that as well.

One final note. Despite all the joking, I seriously considered not writing this post or making this wordlist available since I do like to maintain a shred of dignity, professionalism, etc. The thing is, people actually create passwords this way so something like this wordlist is needed by the community. I'd really appreciate it though if you kept this post off of digg, slashdot, don't submit it for an ignobel award, etc so it stays "in-house".