Fall / Winter 2009
A BETTER NUTCRACKER
Ace cyber sleuths working in FSU's E-Crime Investigative Technologies Laboratory believe they may have come up with the most powerful password-breaking program ever developed.
Backed by grants from the National Institutes of Justice, the team has spent the past two years building the software that they hope will soon make it into the toolbox of every cyber-crime investigator in the country.
"Law enforcement needs a way to break passwords to find out what's on an encrypted disk," said Sudhir Aggarwal, the lab's director. "We think we have the best technique anywhere out there."
Aggarwal and his team of grad students, led by doctoral student Matt Weir, have run their password cracker in head-to-head lab tests with the leading, off-the-shelf password-cracking programs available. They say their program beats the socks off most of these, including John the Ripper, an open-source, free program that may be the most popular password cracker in use today.
In a competition whereby Ripper and the FSU program faced thousands of coded passwords to "crack" or de-code, Ripper ran out of steam after deciphering 6,000 passwords. In the same time, the FSU program crunched through 11,000 passwords and actually grew stronger the longer it ran.
Basically, what sets Aggarwal's program apart from all other password crackers is that its algorithms are based on what people actually do when they create a password, rather than what they could do-namely, create a password that is genuinely unique and thereby almost impossible to break.
Aggarwal's team was able to determine the grammatical patterns and a variety of other user habits (e.g. adding a "1," a "2" or a "3" at the end of a four-letter name) that they gleaned from analyzing over 100,000 old passwords amassed from a number of sources. One of the biggest batches they got their hands on was a list of 67,000 passwords that hackers stole from MySpace.com, for example.
Weir said this massive data set of known passwords became the focus of the research. "This was our central set of training data, which we used for building the model that is based entirely on probabilities. What are the odds, in other words, that a password will be either this or that? We assign probabilities to everything."
Unlike John the Ripper and its ilk, which rely almost solely on searching for root words based on common words or phrases-a so-called "dictionary" approach-to an approach called "brute force," which tries everything-word and number combinations, mainly-the FSU program is based on "rules" governing grammar usage that their analysis of the training set revealed.
Weir said they discovered that they could assign a probability, for example, to the odds that someone would use a four-letter versus a five-letter root word, how often these words would appear in a given set of data, the odds that each would be followed by a number, the odds that number would be a "1" or a "2", or an "11" or a "12" and so on.
"Ours is a totally novel technique for generating guesses on passwords," Aggarwal said. "The point is, we built this model from actual data not on what we think people do, but what they actually do."
In tackling a stack of coded passwords-better known as "hash" in the jargon-Aggarwal said his cracking program could generate a stupefying 34 trillion "intelligent" guesses given enough time. Even running on a laptop, the program can make over a million guesses a second.
So just how good is this new password parser? "Given enough time, we can break about 90 percent of the average passwords most people use," Aggarwal said. "This might take weeks, of course. But we can do this because most people don't go to the trouble of creating a really, really good password, mainly because they can't remember it."-F.S.
Search our Archives
