This article at Ars is a great introduction to the current state of password strength/vulnerability.
The gist is that password reuse is steadily increasing, brute force and hash attack costs are plummeting, and password composition is pretty much as bad as it always was. No big surprise at any of those trends, probably because those trends have held for the past 20 years at least, but it’s still disconcerting.
The article gives examples of several attack methods, including the trusty old dictionary attack (and not just Webster’s).
What I found really interesting was the focus on pattern analysis as a tool for reducing search space. The idea is that you can use some piece of information about a site’s user population or about the site itself to predict patterns in user-generated passwords. A site that requires one uppercase, one number, and one special character will have a different password pattern distribution than a site that requires a minimum 10 letters with no common words. Using this kind of a priori information isn’t the cool part, though…
In an attack on a large set of user generated passwords, there will always be a large percentage that will fall to easy patterns and simple dictionaries. The cool part comes from using analysis of these broken passwords to inform your attack on the ones that didn’t break. Say, for example, 10% of a password population was broken through an easy attack. Just because that 10% was easily cracked, it doesn’t mean that they are wholly dissimilar to the 90% that weren’t cracked. Both populations may have similar common patterns and only differ in length or size of their character set. If we assume that the patterns used in the easy set also describe the uncracked set, we can focus attack resources on those patterns.
Imagine playing a game of Battleship where the board is very large and you can use as many ships as you want. Play against a large number of opponents. You win some, you lose some. Look at the games you won. You can see patterns emerge in people’s tactics, how close together they place their ships, whether to clump them in groups or line them end to end, etc. The game board may be very large, but you have reasonable limits on your time to play… maybe you only want to spend 10 minutes playing any one game, but you want to win as many games as possible. If you know that the most popular pattern used by your opponents is to line their ships end to end in a long line, you will try to find a ship, then continue attacking in a line until you sink all the ships. If this attack is generally successful in 10 minute games, you may suppose that it will work even if you extend the play to 1 hour. The pattern may have been in use in the games you lost — perhaps there were simply too many ships to have sunk them all in 10 minutes. By finding the common pattern(s) in the short games, you’ve increased the chances of winning longer games without having to play many, many long games to discover the pattern.
Your computational resources are finite, just like the amount of time you have to spend playing games of Battleship. If you want to get rich hustling the underground Battleship circuit (hey, it could be a real thing), you want to win as many games as you can in a set amount of time. If you want to be a 5up3r h4ck3r, you want to crack as many passwords as you can with a set amount of computational resources.
Okay, the analogy isn’t perfect, but you get the idea.