January 15, 2007
by Bruce Schneier
Founder and CTO
A free monthly newsletter providing summaries, analyses, insights, and commentaries on security: computer and otherwise.
For back issues, or to subscribe, visit <http://www.schneier.com/crypto-gram.html>.
You can read this issue on the web at <http://www.schneier.com/crypto-gram-0701.html>. These same essays appear in the “Schneier on Security” blog: <http://www.schneier.com/>. An RSS feed is available.
In this issue:
- Automated Targeting System
- Surveillance Cameras Catch a Cold-Blooded Killer
- Crypto-Gram Reprints
- Auditory Eavesdropping
- Tracking Automobiles Through their Tires
- Licensing Boaters
- Wal-Mart Stays Open During Bomb Scare
- NSA Helps Microsoft with Windows Vista
- Microsoft Anti-Phishing and Small Businesses
- Not Paying Attention at the Virginia DMV
- More on the Unabomber’s Code
- BT Counterpane News
- Radio Transmitters in Canadian Coins
- Choosing Secure Passwords
- Comments from Readers
Automated Targeting System
If you’ve traveled abroad recently, you’ve been investigated. You’ve been assigned a score indicating what kind of terrorist threat you pose. That score is used by the government to determine the treatment you receive when you return to the U.S. and for other purposes as well.
Curious about your score? You can’t see it. Interested in what information was used? You can’t know that. Want to clear your name if you’ve been wrongly categorized? You can’t challenge it. Want to know what kind of rules the computer is using to judge you? That’s secret, too. So is when and how the score will be used.
U.S. customs agencies have been quietly operating this system for several years. Called Automated Targeting System, it assigns a “risk assessment” score to people entering or leaving the country, or engaging in import or export activity. This score, and the information used to derive it, can be shared with federal, state, local and even foreign governments. It can be used if you apply for a government job, grant, license, contract or other benefit. It can be shared with nongovernmental organizations and individuals in the course of an investigation. In some circumstances private contractors can get it, even those outside the country. And it will be saved for 40 years.
Little is known about this program. Its bare outlines were disclosed in the Federal Register in October. We do know that the score is partially based on details of your flight record—where you’re from, how you bought your ticket, where you’re sitting, any special meal requests—or on motor vehicle records, as well as on information from crime, watch-list and other databases.
Civil liberties groups have called the program Kafkaesque. But I have an even bigger problem with it. It’s a waste of money.
The idea of feeding a limited set of characteristics into a computer, which then somehow divines a person’s terrorist leanings, is farcical. Uncovering terrorist plots requires intelligence and investigation, not large-scale processing of everyone.
Additionally, any system like this will generate so many false alarms as to be completely unusable. In 2005 Customs & Border Protection processed 431 million people. Assuming an unrealistic model that identifies terrorists (and innocents) with 99.9% accuracy, that’s still 431,000 false alarms annually.
The number of false alarms will be much higher than that. The no-fly list is filled with inaccuracies; we’ve all read about innocent people named David Nelson who can’t fly without hours-long harassment. Airline data, too, are riddled with errors.
The odds of this program’s being implemented securely, with adequate privacy protections, are not good. Last year I participated in a government working group to assess the security and privacy of a similar program developed by the Transportation Security Administration, called Secure Flight. After five years and $100 million spent, the program still can’t achieve the simple task of matching airline passengers against terrorist watch lists.
In 2002 we learned about yet another program, called Total Information Awareness, for which the government would collect information on every American and assign him or her a terrorist risk score. Congress found the idea so abhorrent that it halted funding for the program. Two years ago, and again this year, Secure Flight was also banned by Congress until it could pass a series of tests for accuracy and privacy protection.
In fact, the Automated Targeting System is arguably illegal as well (a point several congressmen made recently); all recent Department of Homeland Security appropriations bills specifically prohibit the department from using profiling systems against persons not on a watch list.
There is something un-American about a government program that uses secret criteria to collect dossiers on innocent people and shares that information with various agencies, all without any oversight. It’s the sort of thing you’d expect from the former Soviet Union or East Germany or China. And it doesn’t make us any safer from terrorism.
Federal Register posting:
Comments from civil liberties groups:
Automated terror profiling:
Total Information Awareness:
ATS may be illegal:
This essay, without the links, was published in Forbes.
They also published a rebuttal by William Baldwin, although it doesn’t seen to rebut any of the actual points. “Here’s an odd division of labor: a corporate data consultant argues for more openness, while a journalist favors more secrecy.” It’s only odd if you don’t understand security.
Surveillance Cameras Catch a Cold-Blooded Killer
I’m in the middle of writing a long essay on the psychology of security. One of the things I’m writing about is the “availability heuristic,” which basically says that the human brain tends to assess the frequency of a class of events based on how easy it is to bring an instance of that class to mind. It explains why people tend to be afraid of the risks that are discussed in the media, or why people are afraid to fly but not afraid to drive.
One of the effects of this heuristic is that people are more persuaded by a vivid example than they are by statistics. The latter might be more useful, but the former is easier to remember.
That’s the context in which I want you to read the very gripping story about a cold-blooded killer caught by city-wide surveillance cameras.
“Federal agents showed Peterman the recordings from that morning. One camera captured McDermott, 48, getting off the bus. A man wearing a light jacket and dark pants got off the same bus, and followed a few steps behind her.
“Another camera caught them as they rounded the corner. McDermott didn’t seem to notice the man following her. Halfway down the block, the man suddenly raised his arm and shot her once in the back of the head.
“‘I’ve seen shootings incidents on video before, ‘ Peterman said, ‘but the suddenness, and that he did it for no reason at all, was really scary.'”
I can write essay after essay about the inefficacy of security cameras. I can talk about trade-offs, and the better ways to spend the money. I can cite statistics and experts and whatever I want. But—used correctly—stories like this one will do more to move public opinion than anything I can do.
Crypto-Gram is currently in its tenth year of publication. Back issues cover a variety of security-related topics, and can all be found on <http://www.schneier.com/crypto-gram-back.html>. These are a selection of articles that appeared in this calendar month in other years.
Anonymity and Accountability:
NSA and Bush’s Illegal Eavesdropping:
The Security Threat of Unchecked Presidential Power:
Diverting Aircraft and National Intelligence:
Color-coded Terrorist Threat Levels:
Militaries and Cyber-War:
A cyber Underwriters Laboratories?
Block and stream ciphers:
In the information age, surveillance isn’t just for the police. Marketers want to watch you, too: what you do, where you go, what you buy. Integrated Media Measurement, Inc. wants to know what you watch and what you listen to—wherever you are.
They do this by turning traditional ratings collection on its head. Instead of a Nielsen-like system, which monitors individual televisions in an effort to figure out who’s watching, IMMI measures individual people and tries to figure out what they’re watching (or listening to). They do this through specially designed cell phones that automatically eavesdrop on what’s going on in the room they’re in:
“The IMMI phone randomly samples 10 seconds of room audio every 30 seconds. These samples are reduced to digital signatures, which are uploaded continuously to the IMMI servers.
“IMMI also tracks all local media outlets actively broadcasting in any given designated media area (DMA). To identify media, IMMI compares the uploaded audio signatures computed by the phones with audio signatures computed on the IMMI servers monitoring TV and radio broadcasts. IMMI also maintains client-provided content files, such as commercials, promos, movies, and songs.
“By matching the signatures, IMMI couples media broadcasts with the individuals who are exposed to them. The process takes just a few seconds.
“Panel Members may sometimes delay watching or listening to a program by using satellite radio, DVRs, VCRs, or TiVo. IMMI captures these viewings with a ‘look-back’ feature that recognizes when a Panel Member is exposed to a program outside of its normal broadcast hour, and then goes back in time (roughly two weeks) to identify it.”
These cell phones are given away to test subjects, who get free service in exchange for giving up all their privacy.
The company maintains that it’s technology cannot possibly be used to eavesdrop on in-room conversations or cell phone conversations. But their phone modifications demonstrate that cell phones can be modified in other ways. Can other eavesdropping software be installed on off-the-shelf phones? Can it be done without the owner’s knowledge or consent? The potential for abuse here is enormous—maybe not by IMMI, but by someone.
Remember, the threats to privacy in the information age are not solely from government; they’re from private industry as well. And the real threat is the alliance between the two.
Tracking Automobiles Through their Tires
Automobile tires are now being outfitted with RFID transmitters:
I’ll bet anything you can track cars with them, just as you can track some joggers by their sneakers.
As I said before, the people who are designing these systems are putting “zero thought into security and privacy issues. Unless we enact some sort of broad law requiring companies to add security into these sorts of systems, companies will continue to produce devices that erode our privacy through new technologies. Not on purpose, not because they’re evil—just because it’s easier to ignore the externality than to worry about it.”
Joggers and sneakers:
The U.S. Coast Guard is talking about licensing boaters. It’s being talked about as an antiterrorism measure, in typical incoherent ways:
“The United States already has endured terrorism using small civilian craft, albeit overseas: In 2000, suicide bombers in the port of Aden, Yemen, used an inflatable boat to blow themselves up next to the U.S. Navy destroyer USS Cole, killing 17 sailors and wounding 39 others.
“Terrorism experts point to other ways small boats potentially could assist in attacks—for example, a speedboat could deposit saboteurs at the outlet pipes of a nuclear power plant, or hijackers aboard a cruise ship. In a nightmare scenario, suicide bombers in a crowded harbor could use small watercraft to detonate a tanker carrying ultra-volatile liquefied natural gas, causing a powerful explosion that could kill thousands.”
And how exactly is licensing watercraft supposed to help?
There are lots of good reasons to license boats and boaters, just as there are to license cars and drivers. But counterterrorism is not one of them.
Wal-Mart Stays Open During Bomb Scare
A Wal-Mart store in Mitchell, South Dakota receives a bomb threat. The store managers decide not to evacuate while the police search for the bomb. Presumably, they decided that the loss of revenue due to an evacuation was not worth the additional security of an evacuation:
“During the nearly two-hour search Wal-Mart officials opted not to evacuated the busy discount store even though police recomended [sic] they do so. Wal-Mart officials said the call was a hoax and not a threat.”
I think this is a good sign. It shows that people are thinking rationally about security trade-offs, and not thoughtlessly being terrorized.
Remember, though: security trade-offs are based on agenda. From the perspective of the Wal-Mart managers, the store’s revenues are the most important; most of the risks of the bomb threat are externalities.
Of course, the store employees have a different agenda—there is no upside to staying open, and only a downside due to the additional risk—and they didn’t like the decision:
Here’s one employee, quoted in the article:
“It’s right before Christmas. They were swamped with people,” she said. “To me, they endangerd [sic] the community, customers and associates. They put making a buck ahead of public safety.”
Scary story of someone who was told by his bank that he’s no longer welcome as a customer, because the bank’s computer noticed a deposit that wasn’t “normal.” This is what happens when you use computer-based profiling. Expect more of this kind of thing as computers continue to decide who is normal and who is not.
Bill Maher’s AccuTerror Forecast. Funny.
Good article on airport security and the TSA. Matt Blaze and I got some really good quotes.
By the way, people regularly chastise me for complaining about airline security but not offering any solutions. I generally send those people to the last two paragraphs of this article.
Cloning RFID passports in five minutes:
Airport security tip: don’t put your baby through the X-ray machine:
Here’s someone who climbs a fence at the Raleigh-Durham Airport, boards a Delta plane, and hangs out for a bunch of hours. Best line of the article: “‘It blows my mind that you can’t get 3.5 ounces of toothpaste on a plane,’ he said, ‘yet somebody can sneak on a plane and take a nap.'” Exactly. We’re spending millions enhancing passenger screening, and we ignore the other, less secure, paths onto airplanes. It’s idiotic, that’s what it is.
The TSA website is a fascinating place to spend some time wandering around. They have rules for handling monkeys: “TSOs have been trained to not touch the monkey during the screening process.”
And snow globes are prohibited in carry-on luggage:
“Snow globes regardless of size or amount of liquid inside, even with documentation, are prohibited in your carry-on. Please ship these items or pack them in your checked baggage.”
I get to make fun of airline security in “The New York Times.”
“The Family Guy” on airport security. Amazingly enough, this was aired before 9/11. I think it makes much better satire now.
Good essay by Matt Blaze on architecture and airport security:
The Department of Homeland Security’s own Privacy Office released a report on privacy issues with Secure Flight, the new airline passenger matching program. It’s not good, which is why the government tried to bury it by releasing it to the public the Friday before Christmas.
I’ve written about Secure Flight many times.
The DHS Privacy Office also issued a report on MATRIX: The Multistate Anti-Terrorism Information Exchange. MATRIX is a now-defunct data mining and data sharing program among federal, state, and local law enforcement agencies, one of the many data-mining programs going on in government (TIA—Total Information Awareness—being the most famous, and Tangram being the newest). The report is short, and very critical of the program’s inattention to privacy and lack of transparency. That’s probably why it too was released to the public just before Christmas, burying it in the media.
More on MATRIX:
More on data mining:
OneDOJ is yet another massive U.S. government database, designed to collect all federal law enforcement databases:
Computerizing this stuff is a good idea, but any new systems need privacy safeguards built in. We need to ensure that: 1) inaccurate data can be corrected, 2) data is deleted when it is no longer needed, especially investigative data on people who have turned out to be innocent, and 3) protections are in place to prevent abuse of the data, both by people in their official capacity and people acting unofficially or fraudulently. In our rush to computerize these records, we’re ignoring these safeguards and building systems that will make us all less secure.
US-VISIT, the program to keep better track of people coming in and out of the U.S., is running into all sorts of problems. It’s being scrapped, definitely temporarily and possibly permanently. I like the trade-off sentiment of this quote from one article: “There are a lot of good ideas and things that would make the country safer. But when you have to sit down and compare all the good ideas people have developed against each other, with a limited budget, you have to make choices that are much harder.” My guess is that the program will be completely killed by Congress in 2007.
More on US-VISIT:
The new Congress is—wisely, I should add—also unlikely to fund the 700-mile fence along the Mexican border.
I hope Congress examines the Coast Guard’s security failures and cost overruns.
Note that the article talks about serious infighting between the Coast Guard and the FBI. It would be nice if Congress spent some time on this (actually important) problem.
The U.S. government is holding an open competition to select a vendor to implement full-disk encryption on all government laptops. Certainly, encrypting everything is overkill, but it’s much easier than figuring out what to encrypt and what not to. And I really like that there is a open competition to choose which encryption program to use. It’s certainly a high-stakes competition among the vendors, but one that is likely to improve the security of all products. I’ve long said that one of the best things the government can do to improve computer security is to use its vast purchasing power to pressure vendors to improve their security. I would expect the winner to make a lot of sales outside of the contract, and for the losers to correct their deficiencies so they’ll do better next time.
I wonder if the NSA is involved in the evaluation at all, and if its analysis will be made public.
War on Terror: the board game:
Peter Gutman’s “A Cost Analysis of Windows Vista Content Protection” is fascinating reading.
The Communications Director for Montana’s Congressman Denny Rehberg solicited hackers to break into the computer system at his university and change his grades (so they would look better when he eventually ran for office, I presume). The hackers posted the email exchange instead. Very funny.
Everyone knows that writing your password on your monitor is bad security. Is it really so hard to realize that attaching your SecurID token to your computer is just as bad?
AACS (Advanced Access Content System), the copy protection used in both Blu Ray and HD DVD, might have been cracked sort of.
A review of Rudyard Kipling’s “Kim”: “Kipling packed a great deal of information and concept into his stories, and in “Kim” we find The Great Game: espionage and spying. Within the first twenty pages we have authentication by something you have, denial of service, impersonation, stealth, masquerade, role- based authorization (with ad hoc authentication by something you know), eavesdropping, and trust based on data integrity. Later on we get contingency planning against theft and cryptography with key changes.”
The book is out of copyright. Read it here:
There’s a proposal in Scotland to believe it or not issue ID cards to children to stop bullying. Seems like bullies take other kids’ meal cards, and by stopping that with ID cards bullying will magically cease. I agree with MSP Patrick Harvie’s quote at the end of the article.
A Florida judge ruled that the defeated candidate has no right to examine the source code in the voting machines that determined the winner in a disputed Congressional race.
Meanwhile, Ciber Inc., the laboratory that tested most of the nation’s electronic voting machines, has been temporarily barred from approving machines because it was found not to be following testing procedures and was unable to document that it performed required tests.
This molecular keypad lock is impressive:
The “New York Times” has a blog post on how easy it is to eavesdrop on an open Wi-Fi session. Nice to see this getting some popular attention.
How to recover numbers from blurred images:
Here’s a dumb idea: MI5 terror alerts by e-mail:
I’ve written about terror threat alerts in the UK before:
1933 article on crooked gambling technology. In every generation, criminals are near the leading edge in applying new technology to steal things.
They’re stealing the identities of our children! Is this the kind of thing that spurs legislators into action? After all, we have to protect our children.
NSA Helps Microsoft with Windows Vista
The NSA “helped” Microsoft with Windows Vista. They’re not disclosing what they did, of course, but Microsoft insiders have told me that it was nothing more than assisting with assurance testing.
But I am suspicious.
It’s called the “equities issue.” Basically, the NSA has two roles: eavesdrop on their stuff, and protect our stuff. When both sides use the same stuff—Windows Vista, for example—the agency has to decide whether to exploit vulnerabilities to eavesdrop on their stuff or close the same vulnerabilities to protect our stuff. In its partnership with Microsoft, it could have decided to go either way: to deliberately introduce vulnerabilities that it could exploit, or deliberately harden the OS to protect its own interests.
A few years ago I was ready to believe the NSA recognized we’re all safer with more secure general-purpose computers and networks, but in the post-9/11 take-the-gloves-off eavesdrop-on-everybody environment, I simply don’t trust the NSA to do the right thing.
Microsoft Anti-Phishing and Small Businesses
Microsoft has a new anti-phishing service in Internet Explorer 7 that will turn the address bar green and display the website owner’s identity when surfers visit online merchants previously approved as legitimate. So far, so good. But the service is only available to corporations: not to sole proprietorships, partnerships, or individuals.
Of course, if a merchant’s bar doesn’t turn green, it doesn’t mean that they’re bad. It’ll be white, which indicates “no information.” There are also yellow and red indications, corresponding to “suspicious” and “known fraudulent site.” But small businesses are worried that customers will be afraid to buy from non-green sites.
That’s possible, but it’s more likely that users will learn that the marker isn’t reliable and start to ignore it.
Any whitelist system like this has two sources of error. False positives, where phishers get the marker. And false negatives, where legitimate honest merchants don’t. Any system like this has to effectively deal with both.
“Phinding Phish: An Evaluation of Anti-Phishing Toolbars”, by L. Cranor, S. Egleman, J. Hong, and Y. Zhang.
Not Paying Attention at the Virginia DMV
Two men have been issued Virginia driver’s licenses, even though they were wearing outlandish disguises when they had their pictures taken at the Department of Motor Vehicles. The videos are on-line.
The Virginia DMV is now demanding that the two come back and get real pictures taken.
I never thought I would say this, but I agree with everything Michelle Malkin says on this issue:
“These guys have done the Virginia DMV—and the nation—a big favor. Many of us have tried to argue how much of a joke these agencies and our homeland security remain after 9/11—particularly the issuance of driver’s licenses (it was the Virginia DMV that issued state photo ID to several 9/11 hijackers who were aided by illegal aliens).
“But few dissertations and policy analyses drive the message home more effectively than these two damning videos.”
I honestly don’t know if she realizes that REAL ID won’t solve this kind of problem, though. Nor will it solve the problem of people getting legitimate IDs in the names of people whose identity they stole, or real IDs in fake names by bribing DMV employees.
More on the Unabomber’s Code
Last month I wrote about Ted Kaczynski’s pencil-and-paper cryptography. It seems that he invented his own cipher, which the police couldn’t crack until they found a description of the code amongst his personal papers.
The link I found was from KPIX, a CBS affiliate in the San Francisco area. Some time after writing it, I was contacted by the station and asked to comment on some other pieces of the Unabomber’s cryptography for a future story (video online).
There were five new pages of Unabomber evidence that I talked about (all available on the CBS5 website) All five pages were presented to me as being pages written by the Unabomber, but it seems pretty obvious to me that pages 4 and 5, rather than being Kaczynski’s own key, are notes written by a cryptanalyst trying to break the Unabomber’s code.
In any case, it’s all fascinating.
Last month’s entry:
BT Counterpane News
Schneier is participating on a panel on economic issues and security at an OECD Security Workshop in Washington, DC on January 31st.
Schneier is speaking on “The Psychology of Security” at the RSA Conference in San Francisco on February 6:
Schneier is speaking at the Linux World Open Solutions Summit in New York on February 14:
Schneier is speaking at the 8th Annual Privacy and Security Conference in Victoria, BC on February 15th:
DarkReading profile of Schneier:
Schneier had an op-ed published in the “Arizona Star” about wholesale surveillance:
The news hook I used was an article about the police testing a vehicle-mounted automatic license plate scanner. Unfortunately, I got the police department wrong. It’s the Arizona State Police, not the Tucson Police.
Radio Transmitters in Canadian Coins
“Canadian coins containing tiny transmitters have mysteriously turned up in the pockets of at least three American contractors who visited Canada, says a branch of the U.S. Defense Department.
“Security experts believe the miniature devices could be used to track the movements of defence industry personnel dealing in sensitive military technology.”
Sounds implausible, really. There are far easier ways to track someone than to give him something he’s going to give away the next time he buys a cup of coffee. Like, maybe, by his cell phone.
And soon after, we had an update:
“A report that some Canadian coins have been compromised by secretly embedded spy transmitters is overblown, according to a U.S. official familiar with the case.
“‘There is no story there, ‘ the official, who asked not to be named, told The Globe and Mail.
“He said that while some odd-looking Canadian coins briefly triggered suspicions in the United States, he said that the fears proved groundless: ‘We have no evidence to indicate anything connected with these coins poses a risk or danger.'”
Take your pick. Either the original story was overblown, or those involved are trying to spin the news to cover their tracks. We definitely don’t have very many facts here.
Choosing Secure Passwords
Ever since I wrote about the 34,000 MySpace passwords I analyzed, people have been asking how to choose secure passwords. There’s been a lot written on this topic over the years, but most of it seems to be based on anecdotal suggestions rather than actual analytic evidence. What follows is some serious advice.
The attack I’m evaluating against is an offline password-guessing attack. This attack assumes that the attacker either has a copy of your encrypted document, or a server’s encrypted password file, and can try passwords as fast as he can. There are instances where this attack doesn’t make sense. ATM cards, for example, are secure even though they only have a four-digit PIN, because you can’t do offline password guessing. And the police are more likely to get a warrant for your Hotmail account than to bother trying to crack your e-mail password. Your encryption program’s key-escrow system is almost certainly more vulnerable than your password, as is any “secret question” you’ve set up in case you forget your password.
Offline password guessers have gotten both fast and smart. AccessData sells Password Recovery Toolkit, or PRTK. Depending on the software it’s attacking, PRTK can test up to hundreds of thousands of passwords per second, and it tests more common passwords sooner than obscure ones.
So the security of your password depends on two things: any details of the software that slow down password guessing, and in what order programs like PRTK guess different passwords.
Some software includes routines deliberately designed to slow down password guessing. Good encryption software doesn’t use your password as the encryption key; there’s a process that converts your password into the encryption key. And the software can make this process as slow as it wants.
The results are all over the map. Microsoft Office, for example, has a simple password-to-key conversion, so PRTK can test 350,000 Microsoft Word passwords per second on a 3-GHz Pentium 4, which is a reasonably current benchmark computer. WinZip used to be even worse—well over a million guesses per second for version 7.0—but with version 9.0, the cryptosystem’s ramp-up function has been substantially increased: PRTK can only test 900 passwords per second. PGP also makes things deliberately hard for programs like PRTK, also only allowing about 900 guesses per second.
When attacking programs with deliberately slow ramp-ups, it’s important to make every guess count. A simple six-character lowercase exhaustive character attack, “aaaaaa” through “zzzzzz,” has more than 308 million combinations. And it’s generally unproductive, because the program spends most of its time testing improbable passwords like “pqzrwj.”
According to Eric Thompson of AccessData, a typical password consists of a root plus an appendage. A root isn’t necessarily a dictionary word, but it’s something pronounceable. An appendage is either a suffix (90 percent of the time) or a prefix (10 percent of the time).
So the first attack PRTK performs is to test a dictionary of about 1,000 common passwords, things like “letmein,” “password,” “123456” and so on. Then it tests them each with about 100 common suffix appendages: “1,” “4u,” “69,” “abc,” “!” and so on. Believe it or not, it recovers about 24 percent of all passwords with these 100,000 combinations.
Then, PRTK goes through a series of increasingly complex root dictionaries and appendage dictionaries. The root dictionaries include:
* Common word dictionary: 5,000 entries
* Names dictionary: 10,000 entries
* Comprehensive dictionary: 100,000 entries
* Phonetic pattern dictionary: 1/10,000 of an exhaustive character search
The phonetic pattern dictionary is interesting. It’s not really a dictionary; it’s a Markov-chain routine that generates pronounceable English-language strings of a given length. For example, PRTK can generate and test a dictionary of very pronounceable six-character strings, or just-barely pronounceable seven-character strings. They’re working on generation routines for other languages.
PRTK also runs a four-character-string exhaustive search. It runs the dictionaries with lowercase (the most common), initial uppercase (the second most common), all uppercase and final uppercase. It runs the dictionaries with common substitutions: “$” for “s,” “@” for “a,” “1” for “l” and so on. Anything that’s “leet speak” is included here, like “3” for “e.”
The appendage dictionaries include things like:
* All two-digit combinations
* All dates from 1900 to 2006
* All three-digit combinations
* All single symbols
* All single digit, plus single symbol
* All two-symbol combinations
AccessData’s secret sauce is the order in which it runs the various root and appendage dictionary combinations. The company’s research indicates that the password sweet spot is a seven- to nine-character root plus a common appendage, and that it’s much more likely for someone to choose a hard-to-guess root than an uncommon appendage.
Normally, PRTK runs on a network of computers. Password guessing is a trivially distributable task, and it can easily run in the background. A large organization like the Secret Service can easily have hundreds of computers chugging away at someone’s password. A company called Tableau is building a specialized FPGA hardware add-on to speed up PRTK for slow programs like PGP and WinZip: roughly a 150- to 300-times performance increase.
How good is all of this? Eric Thompson estimates that with a couple of weeks’ to a month’s worth of time, his software breaks 55 percent to 65 percent of all passwords. (This depends, of course, very heavily on the application.) Those results are good, but not great.
But that assumes no biographical data. Whenever it can, AccessData collects whatever personal information it can on the subject before beginning. If it can see other passwords, it can make guesses about what types of passwords the subject uses. How big a root is used? What kind of root? Does he put appendages at the end or the beginning? Does he use substitutions? ZIP codes are common appendages, so those go into the file. So do addresses, names from the address book, other passwords and any other personal information. This data ups PRTK’s success rate a bit, but more importantly it reduces the time from weeks to days or even hours.
So if you want your password to be hard to guess, you should choose something not on any of the root or appendage lists. You should mix upper and lowercase in the middle of your root. You should add numbers and symbols in the middle of your root, not as common substitutions. Or drop your appendage in the middle of your root. Or use two roots with an appendage in the middle.
Even something lower down on PRTK’s dictionary list—the seven-character phonetic pattern dictionary—together with an uncommon appendage, is not going to be guessed. Neither is a password made up of the first letters of a sentence, especially if you throw numbers and symbols in the mix. And yes, these passwords are going to be hard to remember, which is why you should use a program like the free and open-source Password Safe to store them all in. (PRTK can test only 900 Password Safe 3.0 passwords per second.)
Even so, none of this might actually matter. AccessData sells another program, Forensic Toolkit, that, among other things, scans a hard drive for every printable character string. It looks in documents, in the Registry, in e-mail, in swap files, in deleted space on the hard drive … everywhere. And it creates a dictionary from that, and feeds it into PRTK.
And PRTK breaks more than 50 percent of passwords from this dictionary alone.
What’s happening is that the Windows operating system’s memory management leaves data all over the place in the normal course of operations. You’ll type your password into a program, and it gets stored in memory somewhere. Windows swaps the page out to disk, and it becomes the tail end of some file. It gets moved to some far out portion of your hard drive, and there it’ll sit forever. Linux and Mac OS aren’t any better in this regard.
I should point out that none of this has anything to do with the encryption algorithm or the key length. A weak 40-bit algorithm doesn’t make this attack easier, and a strong 256-bit algorithm doesn’t make it harder. These attacks simulate the process of the user entering the password into the computer, so the size of the resultant key is never an issue.
For years, I have said that the easiest way to break a cryptographic product is almost never by breaking the algorithm, that almost invariably there is a programming error that allows you to bypass the mathematics and break the product. A similar thing is going on here. The easiest way to guess a password isn’t to guess it at all, but to exploit the inherent insecurity in the underlying operating system.
Analyzing 24,000 MySpace passwords:
This essay originally appeared on Wired.com.
Comments from Readers
There are hundreds of comments—many of them interesting—on these topics on my blog. Search for the story you want to comment on, and join in.
CRYPTO-GRAM is a free monthly newsletter providing summaries, analyses, insights, and commentaries on security: computer and otherwise. You can subscribe, unsubscribe, or change your address on the Web at <http://www.schneier.com/crypto-gram.html>. Back issues are also available at that URL.
Comments on CRYPTO-GRAM should be sent to firstname.lastname@example.org. Permission to print comments is assumed unless otherwise stated. Comments may be edited for length and clarity.
Please feel free to forward CRYPTO-GRAM, in whole or in part, to colleagues and friends who will find it valuable. Permission is also granted to reprint CRYPTO-GRAM, as long as it is reprinted in its entirety.
CRYPTO-GRAM is written by Bruce Schneier. Schneier is the author of the best sellers “Beyond Fear,” “Secrets and Lies,” and “Applied Cryptography,” and an inventor of the Blowfish and Twofish algorithms. He is founder and CTO of BT Counterpane, and is a member of the Board of Directors of the Electronic Privacy Information Center (EPIC). He is a frequent writer and lecturer on security topics. See <http://www.schneier.com>.
BT Counterpane is the world’s leading protector of networked information – the inventor of outsourced security monitoring and the foremost authority on effective mitigation of emerging IT threats. BT Counterpane protects networks for Fortune 1000 companies and governments world-wide. See <http://www.counterpane.com>.
Crypto-Gram is a personal newsletter. Opinions expressed are not necessarily those of BT or BT Counterpane.
Copyright (c) 2007 by Bruce Schneier.