Crypto-Gram Newsletter

October 15, 1999

by Bruce Schneier
Founder and CTO
Counterpane Internet Security, Inc.
schneier@schneier.com
http://www.counterpane.com

A free monthly newsletter providing summaries, analyses, insights, and commentaries on computer security and cryptography.

Back issues are available at http://www.schneier.com. To subscribe or unsubscribe, see below.

Copyright (c) 1999 by Bruce Schneier


In this issue:


So, You Want to be a Cryptographer

One of the most frequent questions I receive via email is: "How can I become a cryptographer?" This essay is my attempt to answer the question. My answer divides into four parts -- for the high-school student, for the undergraduate, for the graduate student, and for the person employed in a related field -- although much of what I have to say overlaps.

First, what is a cryptographer? For our purposes, a cryptographer is someone who is active in the field of cryptography: someone who engages in research, writes papers, breaks algorithms and protocols, and sometimes writes his own algorithms and protocols. A cryptographer can find work as a university professor, but some large companies -- AT&T, IBM -- employ full-time cryptographers, and there are some cryptographers that work as consultants to companies that don't have full-time cryptographers on their staffs. And, of course, the NSA will snatch pretty much anyone who shows the ability to be trained as a cryptographer. The work is the same regardless: designing systems, breaking systems, doing research, publishing papers. Cryptography is a research field and it shows.

Of course, most people who implement cryptography in software and hardware products are not cryptographers. They are implementers of cryptography, security engineers. I find that most people who say they want to be cryptographers actually want to be security engineers. They want to be a person who builds secure systems that use cryptography. This essay is not really for them, although much of the advice is the same. Security engineering requires a strong understanding of cryptography, but it does not require creating new cryptography.

The short answer to "how can I become a cryptographer" is: "Get a PhD in cryptography." This is not the only way to become a cryptographer, but it is by far the easiest. The skills you learn in pursuit of the PhD are skills you will need as a cryptographer, and doors open far easier for those who have a PhD. Furthermore, the process of getting a PhD will answer the even-more-important question: "Do I want to be a cryptographer?"

Cryptography can be a specialty of mathematics. Wherever you get your degree, both mathematical and computer science training is vital. But more importantly, cryptography is a way of thinking. Elsewhere I've written about why security engineering is different from any other kind of engineering; it requires a certain kind of mentality to approach systems from an attacker's perspective. During World War II, the British found that the best cryptographers were chess players and musicians. I find that good security people are D&D players and tinkerers. The ability to find loopholes in a system, be they mathematical, systematical, or procedural, is vital to a cryptographer.

To the high school student, study mathematics and computer science. Read books on cryptography, both historical books like David Kahn's _The Codebreakers_ and modern books like my own _Applied Cryptography_. Read books about computer security: firewalls, Internet security, Windows security, whatever. The fields are closely related, and you may find that you prefer computer security to cryptography. Participate in the discussions on the sci.crypt newsgroup and the coderpunks mailing list. If you can distinguish the people in those forums who make sense from those who do not, you're well on your way. Almost certainly you will get the urge to invent new cryptographic algorithms, and will believe that they are unbreakable. Don't resist the urge; this is one of the fun parts. But resist the belief; almost certainly your creations will be breakable, and almost certainly no one will spend the time breaking them for you. You can break them yourself as you get better.

I've often been asked where to go to college as an undergraduate to study cryptography. Basically, it doesn't matter. The math education you need can be gotten from any good math department. Note: "good math department" means a place where mathematical proofs are emphasized. There are liberal arts colleges where proofs only appear in the last year or so; this is a bad idea. Some colleges offer courses in cryptography or computer security -- see my homepage for a partial list of college courses -- but in the end it really doesn't matter.

To the college student, study mathematics. Get a degree in either math or computer science, but study mathematics. Take math courses for math majors, not math courses for engineers. Learn how to think about mathematics; learn how to prove theorems. Try to take courses in number theory, complexity theory (often offered out of the computer science department), algorithms, statistics, and abstract algebra. Cryptography uses number theory, but cryptography uses ideas from many varied areas of mathematics. In fact, one of the most interesting aspects of cryptography is that the great ideas come from all over mathematics. Cryptographers need broad knowledge of mathematics; this is the only way that new connections are made and really original ideas are found.

Vital computer science courses include algorithm design, computational complexity, and theory of computation. Some colleges offer an undergraduate course in cryptography; take it. Keep reading books on cryptography: _The Handbook of Applied Cryptography_ by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, or Doug Stinson's _Cryptography: Theory and Practice_. All of these books have many, many references. If something interests you, find the reference and read it. Take computer science courses; read books about computer security. Again, chase down references if something interests you.

When choosing a graduate school, choose one that has an expertise in cryptography. Things can change quickly in the academic world so I don't want to give a list of schools (you can start with MIT and Waterloo), but they're out there. Many are outside the U.S., so be open to going to a graduate school in a different country than you're from. One way to make a list of potential graduate schools is to look for research papers that interest you. Look at where the authors teach. When you get to graduate school, your advisor will give you far more advice on becoming a cryptographer than I ever can.

And finally, advice to people who are beyond school and working. You have two options. One, you can go back to graduate school, either full or part time. Two, you can mimic the process by yourself, without benefit of a research institution or an advisor. You can read a lot; you can apprentice yourself. If you have a good mathematics background, you can teach yourself cryptography. This option is much harder, but it is possible.

No matter where in life you are, you should try to figure out what it means to be a cryptographer. Read the existing literature to get a feel for what sort of questions cryptographers ask, how they go about answering them, and what sorts of questions are still to be answered. Find problems that you can understand, and try to solve them. Don't worry that you're "reinventing the wheel" and solving things that have already been solved; that's what learning is about. I have written a "Self-Study Course in Block Cipher Cryptanalysis" that attempts to lay out problems for a cryptography student to tackle; you can try to solve problems in any area of cryptography.

Leaning to be a cryptographer is not easy, and it makes sense to question whether that is what you really want to do. Luckily, the process has many points where you can decide to change your mind. And as I said in the beginning, many people who say they want to be cryptographers actually want to be security engineers. While the requirements for a security engineer are much the same -- read books, read research papers, take classes, learn cryptography and how it's used -- a PhD is not required.

List of cryptography courses:
http://www.counterpane.com/courses.html
Self-study Course In Block Cipher Cryptanalysis:
http://www.schneier.com/paper-self-study.html


New U.S. Export Rules and Anti-Privacy Encryption Legislation

On 16 September (the day after Crypto-Gram is published...coincidence?) the Clinton Administration announced changes to its export control rules. There have been no changes yet, but if the administration actually delivers on them it will represent a reversal of their long-standing hostility towards strong encryption. But the devil is in the details, and the Clinton Administration has a long record of promising export relief and then not delivering. And there is a second part to this, a proposed legislation called the Cyberspace Electronic Security Act (CESA), that supports key escrow and has some nasty anti-privacy provisions.

Export first. The Administration proposes that "retail" encryption hardware and software of unlimited strength could be exported without a license after a "one-time technical review" and some reporting about who the products are sold to. "Custom" products will have some restrictions on sales to foreign governments and known terrorist or criminal organizations. Products with key lengths of under 64-bits would be entirely decontrolled.

Again, these changes are not in effect. The Administration has said they would be in force by December 15th. If they follow through on their promise, these new regulations will allow virtually any product to be exported more-or-less freely. Note that there is nothing about key recovery in these new regulations, and there are no artificial limits based on key length. On the other hand, still missing are regulations about cryptographic research; the Karn, Junger, and Bernstein court cases are still important.

Now for the bad news. The Administration has also proposed the CESA bill, which spells out regulations for key escrow and use of decryption as a police weapon. The bill requires third parties to disclose keys to government agents with a court order. More importantly, it states that there is "no constitutional expection of privacy" in the decrypted plaintext, and there are no provisions for "probable cause" in the bill. And more frighteningly, the bill allows the government to refuse to disclose the methods they used to recover plaintext in court. This means that the police could present decrypted plaintext in open court, but refuse to reveal to the defendant how that plaintext was obtained. This, of course, means that the defendant can have a hard time defending himself, and makes it a lot easier for the police to fabricate evidence. The ability to receive a fair trial could be at stake. And to make sure that there will be lots of recovered plaintext for the police to use, the bill authorizes $80M for an FBI Technical Support Center, designed to develop police tools for defeating computer security and encryption.

The CESA was originally even worse. There was a provision for "secret search," where the police could secretly break into people's homes and install surreptitious "recovery devices" on their computers (think Back Orifice). There were also other provisions to promote key recovery. These are gone in the final wording, but who knows if they will ever come back.

Again, all of this is proposal and none of this is official. Please don't think the deal is done, and that we've won anything. The debate over the use of encryption as a privacy tool continues.

News articles:
http://www.wired.com/news/politics/0,1283,21786,00.html
http://www.computerworld.com/home/news.nsf/CWFlash/...

Government documents:
Press release -- <http://www.pub.whitehouse.gov/uri-res/I2R?urn:pdi://...>
White House briefing -- <http://www.pub.whitehouse.gov/uri-res/I2R?urn:pdi://...>
Letter to Congress -- <http://www.pub.whitehouse.gov/uri-res/I2R?urn:pdi://...>

Analyses:
http://www.epic.org/crypto/legislation/cesa/...
http://www.epic.org/crypto/legislation/cesa/...
http://www.eff.org/91699_crypto_release.html
http://www.cdt.org/crypto/admin/...
http://www.cdt.org/crypto/CESA/cdtcesaanalysis.shtml
http://www.cdt.org/publications/pp_5.22.shtml/


Counterpane -- Featured Research


"Minimizing Bandwidth for Remote Access to Cryptographically Protected Audit Logs"

J. Kelsey and B. Schneier, Second International Workshop on the Recent Advances in Intrusion Detection (RAID '99), September 1999, to appear.

Tamperproof audit logs are an essential tool for computer forensics. We show how to build a tamperproof audit log where the amount of information exchange required to verify the entries in the audit log is greatly reduced. By making audit-log verification more efficient, this system is more suitable for implementation in low-bandwidth environments.

http://www.schneier.com/paper-auditlogs2.html


News

Now the U.K. wants backdoor access to Internet traffic, via ISPs.
http://www.theregister.co.uk/990910-000026.html And read this overview of electronic surveillance and privacy in the UK.
http://www.zdnet.com/zdnn/stories/news/...

The people at HushMail issued a response to my essay on Web-based e-mail encryption programs:
http://www.hushmail.com/bruce_comments.htm
Summary: they acknowledge the points in the Crypto-gram article, describe their physical security, outline future directions like allowing passphrase changes, point out that they explain good passphrase selection in their help system, and argue that there's no way they can be as trusted as PGP, since after all they're new and there hasn't been time for the review and refinement that PGP et al. have had. This all sounds good, and I have started to think that they may be okay after all. Then, I read a news report that has the paragraph: "'President Clinton's proposed rules to relax restrictions on exporting encryption doesn't affect us,' said HushMail Marketing Vice President and Co-Founder Jon Gilliam, 'because his proposal pertains only to 128-bit encryption,' which is (eight times less powerful than that used by HushMail). Gilliam points out that 128-bit encryption has been broken." Either the reporter or Mr. Gilliam hasn't the faintest idea what encryption is about.
http://www.internetnews.com/stocks/vcwatch/article/...

A phony email, purporting to contain a Y2K countdown attachment from Microsoft, is actually a Trojan horse virus that searches for usernames, logins, and passwords in order to send them to the author.
http://www.wired.com/news/technology/...
http://www.zdnet.com/zdnn/stories/news/...

There have been some bizarre news reports about a hand-held quantum computer able to break RSA in almost real time, supposedly developed at the Weizmann Institute in Israel. This feels very much like the movie _Sneakers_, and near as I can tell there is no truth to the rumor. There is one piece of real news that haas come out of this: the European Institute of Quantum Computing has been announced.
http://www.the-times.co.uk/news/pages/tim/99/09/29/...

A good article on privacy and business/consumer relationships:
http://www.hudson.org/American_Outlook/...

How our increased reliance on computers is eroding privacy.
http://www.technologypost.com/internet/WEEKLY/...

Electronic extortion. German and British banks are being targeted by criminals who threaten computer security.
http://www.theregister.co.uk/990920-000034.html

Richard Smith has put together a dozen or so tricks to test web anonymizers. He's found lots of problems. Read this before you trust them.
http://www.tiac.net/users/smiths/anon/anonprob.htm [link dead; try http://users.rcn.com/rms2000/anon/anonprob.htm] http://www.tiac.net/users/smiths/anon/test.htm [link dead; try http://users.rcn.com/rms2000/anon/test.htm]

The International Association for Counterterrorism and Security Professionals (yes, they really exist) had a conference this month. Sounds like a lot of scare stories, and not a lot of information.
http://www.iacsp.com/ http://www.wired.com/news/news/politics/story/... [link dead; see http://www.wirednews.com/news/print/...]

In a fabulous example of networked community cooperation, more than 300 security practitioners isolated the behavior of the Internet-wide RingZero Trojan proxy attack, found the Trojan, created defenses, and, as a result, the Russian site that was using it to collect data shut down and many sites improved their defenses against proxy attacks.
http://www.sans.org/newlook/resources/flashadv.htm

An article on online trafficking in stolen intellectual property. Interesting growth area of crime.
http://www.techweb.com/wire/story/reuters/...

This looks like a lot more rumor and innuendo than fact, but there is claim of malicious code being added into the Y2K repair process.
http://news.cnet.com/category/0-1009-200-428804.html
http://dailynews.yahoo.com/h/nm/19990930/tc/...
http://www.zdnet.com/zdnn/stories/news/...
India denies any wrongdoing.
http://news.cnet.com/category/0-1009-200-429387.html
http://www.wired.com/news/news/politics/story/...

The 9th Circuit Court of Appeals has agreed to a new hearing in the Bernstein case. This is the May 1999 ruling that said that encryption programs and their accompanying mathematical formulas are expressions of ideas and cannot be suppressed by the government.
http://www.techserver.com/noframes/story/...

Financial institutions have their own security alert network. The Financial Services Information Sharing and Analysis Center (FS/ISAC) is an organization that will allow financial institutions to track trends, share information, and obtain incident reports...all anonymously.
http://www.techserver.com/noframes/story/...

The U.S. government says: "Just say no to hacking." This is too amazing.
http://www.thestandard.com/articles/article_print/...

One of the major problems with network intrusion detection tools and vulnerability scanners is that they have different ways of naming vulnerabilities. If you use two tools, there's no easy way to compare results. To solve this problem, Mitre and others have developed a dictionary of over 300 known computer security vulnerabilities called the Common Vulnerabilities and Exposures (CVE) list.
http://www.mitre.org/news/articles_99/cve_release.shtml

The government backpedals on Fidnet.
http://www.wired.com/news/news/politics/story/...

In another distributed brute-force cracking effort, a group of 200 people (using 740 computers) cracked a 97-bit elliptic curve cryptographic key. Certicom claims that this effort is twice the effort required to crack a 512-bit RSA key, and is more evidence of the superiority of elliptic curve cryptography over conventional RSA. I'll talk about this in detail next month.
http://www.certicom.com/press/99/sept2899.htm
http://www.computerworld.com/home/news.nsf/all/...

With the popularity of DSL, cable, and other high-speed home Internet connections, more insecure computers are on the Internet than ever before. This site allows you to run a quick test to see if your computer is vulnerable to certain attacks. Passing does not mean that your computer is secure, but failing certainly means that it is insecure.
http://grc.com


Counterpane Internet Security News

Counterpane Internet Security is hiring. See http://www.counterpane.com/jobs.html for details.

Bruce Schneier will be giving a half-day tutorial on cryptography at the ACM Computers and Communications Security Conference in Singapore on 1-4 November 1999.
http://www.isi.edu/ccs99/

Bruce Schneier will be giving three seminars at the Computer Security Institute's annual conference held 15-17 November 1999 in Washington DC:
Attack Trees: Modeling Actual Attack Threats -- Monday, 2:00 pm - 3:15 pm
How to Think About Security -- Tuesday, 11:15 am - 12:30 pm Failures in Cryptographic Products -- Tuesday, 4:00 pm - 5:15 pm
http://www.gocsi.com/

A profile on Bruce Schneier appeared in USA Today. It doesn't seem to have a permanent URL, but you can find it by searching for "Bruce Schneier" at:
http://www.usatoday.com/

An interview with Schneier, on Back Orifice, appeared in Computerworld
http://www.computerworld.com/home/print.nsf/all/...
So did an article about Schneier's commentary on the NSAkey controversy:
http://www.computerworld.com/home/news.nsf/all/...

And an article on Microsoft and security quotes Schneier:
http://www.cnn.com/TECH/computing/9909/28/...


The Doghouse: AMD

AMD has something called "Magic Packet" technology that allows someone across a network to wake up a sleeping or powered-off PC. Nowhere is there any mention of security, so you can be sure someone will develop a set of hacker tools to turn on powered-off PCs across the network. Now, even turning your computer off doesn't make you secure; you need to pull the plug out of the wall.

http://www.amd.com/products/npd/overview/20212.html [link dead; see http://www.amd.com/us-en/Networking/...]


PKI Companies and their Slogans

I find this amusing. Here are the major, and minor, PKI companies and their corporate slogans. People were paid lots of money to come up with these slogans, so be suitably impressed.

ABAecom: Facilitating electronic banking and commerce over the internet

Baltimore Technologies: Global e-security

CertCo: At the root of electronic commerce

Digital Signature Trust: Creating trust in electronic commerce

Entrust: We bring trust to e-business

GTE Cybertrust: The security to be strategic

Indentrus: Trust on line

IBM/Lotus: Locate, Connect, Secure

Lockstar: Linking legacy to the future

Shym: Unlocking the power of public key

Thawte: <They don't have a slogan, but they have a mission statement in verse.>

Valicert: Enabling global private trust

Verisign: The sign of trust on the net

Xcert: Building trust on the internet


Key Length and Security

Despite what everyone else tries to tell you, cryptographic key length has almost nothing to do with security. A short key means bad security, but a long key does not mean good security.

The lock on the front door of your house has a series of pins. Each of the pins has multiple possible positions. When someone inserts a key into the lock, the pins are each moved to specific positions. If the positions dictated by the key are the ones that the lock needs to open, it does. Otherwise, it doesn't.

Most normal locks have five pins, each of which can be in one of ten different positions. That means that there are 100,000 possible keys. A burglar with a very large key ring can try every possible key, one after the other, and eventually he will get in. He had better be patient, because even if he can try a key every five seconds, it will take him an average of 69 hours to find the correct key -- and that doesn't include bathroom or meal breaks.

One day a salesman knocks on your door, and offers to sell you a new lock. His lock has six pins with twelve positions each. A burglar, he tells you, will have to try different keys for 259 days-non-stop-before he will be able to open your door. Do you feel more secure with this lock?

Probably not. No burglar would ever stand at your doorstep for 69 hours, anyway. He's more likely to pick the lock, kick the door down, break a window, or just hide in the bushes until you saunter up the front walk. A lock with more pins and positions won't make your house more secure, because the specific attack it makes more difficult -- trying every possible key -- isn't one you're particularly worried about. As long as there are enough pins to make that attack infeasible, you don't have to worry about it.

The same is true for cryptographic keys. If they are long enough, don't worry about it. And how long is "long enough" is more complicated than a simple number; it depends on the application and the amount of entropy in the keys.

Let's start at the beginning. A cryptographic key is a secret value that modifies an encryption algorithm. If Alice and Bob share a key, they can use the algorithm to communicate securely. If Eve, an eavesdropper, does not know the key, she cannot read Alice's or Bob's messages. She is forced to try and "break" the algorithm; that is, try to learn the key from just the ciphertext.

One obvious thing she can do is try every possible key, like the hypothetical burglar from the beginning of this essay. If the key is n bits long, then there are 2^n possible keys. So, if the key is 40 bits long, there are about a trillion possible keys. This would be impossibly boring for a burglar, but computers excel at impossibly boring tasks. On the average, a computer would have to try about half the possible keys before finding the correct one, so a computer capable of trying a billion keys per second would take 18 minutes to find the correct 40-bit key. The DES-breaking machine Deep Crack tried 90 billion keys per second; it could find a 56-bit DES key in an average of 4.5 days. The distributed Internet keysearch project, distributed.net (which included Deep Crack), was testing 250 billion keys per second at its peak.

All of this scales linearly. In 1996, a group of cryptographers (including myself) researched the various technologies one could use to build brute-force cryptanalytic machines, and recommended a minimal key length of 90 bits to provide security through 2016. Triple-DES has a 112-bit key, and most modern algorithms have at least a 128-bit key. Even a machine a billion times as fast as Deep Crack would take 10^15 years to try all 2^112 keys and recover the plaintext. Even assuming that Moore's law holds true for the next few hundred years, this will be secure for a long time.

So, what else is there to worry about? Why can't we just zillion-bit keys and be secure until the end of time? To answer this I need to explain about entropy.

Entropy is a measure of uncertainty. The more uncertain something is, the more entropy there is in that thing. For example, if a random person from the general population is either male or female, the variable "gender" has one bit of entropy. If a random person prefers one of the four Beatles, and each is equally likely, that corresponds to two bits of entropy. The sex of someone on a men's Olympic swimming team has no entropy; everyone is male. The entropy of the Beatles-preference at a John Lennon fan-club meeting has much less than two bits, because it is more likely that a random person will prefer John. The more certainty in the variable, the less the entropy.

The same is true for cryptographic keys. Just because an algorithm accepts 128-bit keys does not mean it has 128 bits of entropy in the key. Or, more exactly, the best way to break a given implementation of a 128-bit encryption algorithm might not be to try every possible key.

The first worry is the quality of the encryption algorithm. All of the calculations above assumed that the algorithms took the keys they were given and used them perfectly. If there are flaws in the algorithm, this reduces the entropy in the keys. For example, the A5/1 algorithm, used in European GSM cellphones, has a 64-bit key, but can be broken in the time required to brute force a 40-bit key. This means that even though the algorithm is given a cryptographic key with 64 bits of entropy, it only makes use of 40 bits of entropy in the key. You might as well use an algorithm that effectively uses a 40-bit key.

This problem is why the AES process is taking so long. The U.S. government wants to replace DES (which has a 56-bit key) with a new algorithm that accepts keys up to 256 bits. Right now there are five semi-finalists for the standard, but do any actually deliver the 256 bits of entropy it claims to? This is also why products that advertise thousand-bit keys are hard to take seriously; they don't understand how keys and entropy work.

The second worry is the source of the keys. All the key-length calculations I just made assume that each key has maximum entropy when it is generated. In other words, I assumed that each key is equally likely. This just isn't true.

Many keys are generated from passwords or passphrases. A system that accepts 10-character ASCII passwords might require 80 bits to represent, but has much less than 80 bits of entropy. High-order ASCII bytes won't appear at all, and passwords that are real words (or close to real words) are much more likely than random character strings. I've seen entropy estimates of standard English at 1.3 bits per character; passwords probably have less than 4 bits of entropy per character. This means that a 6-character passphrase is about the same as a 32-bit key, and if you want a 128-bit key you are going to need a 98-character English passphrase.

You see, a brute-force password cracking engine isn't going to try every possible key in order. It's going to try the most likely ones first, and then try the rest in some likelihood order. It will try common passwords like "password" and "1234," then the entire English dictionary, and then varied capitalitlization and extra numbers, and so on. L0phtcrack is a password-cracking program that does this; on a Pentium Pro 200 it can test a 200-entry password file against an 8 Megabyte dictionary of popular passwords in under a minute. Testing the entire 26-character alphabet space takes 26 hours, and the 36-character alphanumeric space takes about 250 hours.

This is why it is laughable when companies like Microsoft tout 128-bit encryption and then base the key on the password. (This describes pretty much all of Windows NT security.) The algorithms they use might accept a 128-bit key, but the entropy in the password is far, far less. In fact, it doesn't matter how good the cryptography is or what the key length is; weak passwords will break this system.

Some have dealt with this problem by requiring stronger and stronger passwords, but that is no longer effective. Over the past several decades, Moore's law has made it possible to brute-force larger and larger entropy keys. At the same time, there is a maximum to the entropy that the average computer user (or even the above-average computer user) is willing to remember. You can't expect him to memorize a 32-character random hexadecimal string, but that's what has to happen if he is to memorize a 128-bit key. These two numbers have crossed; password crackers can now break anything that you can reasonably expect a user to memorize. Good passwords are difficult to memorize, he will complain, but this difficulty is precisely why they are considered good.

Randomly generated keys aren't necessarily better, because now the random number generator must produce keys with maximum entropy. A flaw in the random number generator is what broke the encryption in Netscape version 1.1. While the random number generator was used to generate 128-bit keys, the maximum entropy was around 20 bits. So the algorithm was no better than if it had a 20-bit key.

Solutions exist, but they require engineering tradeoffs. Biometrics can generate better passwords, less because there is a lot of entropy in -- for example -- a fingerprint (my guess is that it is equivalent to about a 60-bit key), and more because there is no such thing as a bad fingerprint in the same way that there is a bad password. Smart cards offer a convenient way to carry about a high-entropy key, but have the restrictions associated with a physical device. And for some communications systems, public-key protocols can generate high-entropy secrets using nothing but public information. On-line verification of passwords, which prevents off-line dictionary attacks, also works in some circumstances.

This is a big deal. I see complex PKI systems where the private key is protected with a password. Almost every hard-disk encryption product bases its security on a user-remembered key. Almost all the security of Windows NT collapses because it is all built on user-remembered passwords. Even PGP falls apart if the user chooses a bad passphrase. It doesn't matter what the algorithms are or how large the keys they use; user-remembered secrets are not secure.

A Note on Public-Key Algorithms

This essay talks about symmetric algorithms (block and stream ciphers), which take arbitrary bit strings as keys. Public-key systems, which have mathematical keys such as the product of two large primes, are different. There are still brute-force attacks against public key systems, but they involve solving mathematical problems such as factoring. The group that just factored a 512-bit RSA key said that the calculation took about 2% the effort of a 56-bit keysearch. Estimates of future security for RSA keys are much harder, because you have to take into account advances in factoring mathematics as well as advances in computer speed and networking.

Conservative estimates indicate that 1024-bit keys are good enough for the next few years, and 2048-bit keys should be good enough for ten or so years. But since no one even knows if factoring is "hard," it is certainly possible that a brilliant mathematician may come along and make even these key lengths insecure.

RSA keys have, of course, much too much entropy to memorize. They are either encrypted with a passphrase and stored on the hard drive, or stored on a token such as a smart card. Sometimes they're even left out in the clear.

Key length paper:
http://www.schneier.com/paper-keylength.html


Comments from Readers

From: William Robert Night <whitenight home.com>
Subject: Back Orifice 2000
Regarding Back Orifice (BO2K). I saw source for a virus someone was passing around on IRC. It was pretty simple stuff, especially to someone who was around during the days of 2500-byte polymorphic encrypting viruses...
The virus was a shell; it contained a compressed and encrypted payload of (in this case) BO2K. There was another one that was just enough of a stub to download and install the payload silently. This was fairly simple. The devious part about this was that the payload was easily switchable. One of the options discussed was using one of the "good" remote management programs as a payload. The drawback was that they were all a bit larger, and not quite as stealthy, but the plus was that they would slip past most (if not all) virus scanners.
Struck me as fairly funny, in a morbid sort of way. BO2K is "bad" and is scanned for, but "good" software which is just as powerful isn't scanned for. (By just as powerful, if you can upload and run arbitrary programs then you can do everything BO can, if not as conveniently.)

From: "Dwight Arthur" <dwight bestweb.net>
Subject: E*Trade
You wrote: "E*Trade's password security isn't. They limit the logon password to a maximum of 6 characters, and the only choices are letters (upper and lower case are distinguished), numbers, $, and _."
I like E*Trade, I trade there. E*Trade has never asked me to agree that I will be responsible for any trades done with my password, so my opinion is that they are putting their own assets (not mine) at risk with weak security.
This is one of several factors that suggest the following business model is followed at E*Trade: Future dominance in the brokerage industry depends on maximum accumulation of "Internet accounts" and assets now. Good security is seldom convenient and often annoying, which leads to loss of some potential investors. The potential financial loss of that foregone market share may exceed the potential financial loss from impersonation through guessed or hacked passwords.
In my view, the most striking example of this comes from E*Trade's aggressive support of the new California electronic signature law. I don't have the text with me, but if I construe it correctly, if a California company plays you a soundfile that says "If you agree to our terms and conditions please make a sound at the tone, otherwise remain silent. Warning, if you make a sound it will be the same as signing your name to a contract <beep>" and then records your voice saying "no, no, wait" then the company can make a case under the law that you signed their contract using your voice as an electronic signature. Obviously you could challenge this presumed contract several ways and probably win -- but the point is that this tells us something about E*Trade's tradeoff between making it really easy to open an account, versus issues of strong authentication.

From: Matt Riben <matter acm.org>
Subject: E*Trade....Ameritrade
Think E*Trade is bad about passwords? Ameritrade allows only 4 characters: all numbers! The number is assigned to the account at creation time, and the only way to change it is by calling their 800 number. I don't even want to think about how easily someone could manipulate a human telephone operator into changing a PIN for them.

From: Neal McBurnett <nealmcb lucent.com>
Subject: Microsoft
> Two Microsoft security white papers. They're not
> great, but they do explain the Microsoft party line.
> http://officeupdate.microsoft.com/2000/... [link moved to http://office.microsoft.com/downloads/2000/o2ksec.aspx
This is really astonishing. Microsoft publishes a paper not only as a .doc file, with all the macro risks that they discuss in the paper, but they have the nerve to package it in a .exe file which the user must execute.
Then they confuse the issue by describing the .exe as a Word file, just like the author of a virus would: "The download file, O2ksec.exe, contains the Microsoft Office 2000 Macro Security white paper. This white paper is a Word *.doc file that can be opened by either Word 97 or Word 2000."
Even Microsoft's security folks can't get the packaging and language right! I hope you take advantage of opportunities in the future to point out the irony of this sort of terribly bad example.
Sigh.

CRYPTO-GRAM is a free monthly newsletter providing summaries, analyses, insights, and commentaries on computer security and cryptography.

To subscribe, visit http://www.schneier.com/crypto-gram.html or send a blank message to crypto-gram-subscribe@chaparraltree.com. To unsubscribe, visit http://www.schneier.com/crypto-gram-faq.html. Back issues are available at http://www.schneier.com.

Please feel free to forward CRYPTO-GRAM to colleagues and friends who will find it valuable. Permission is granted to reprint CRYPTO-GRAM, as long as it is reprinted in its entirety.

CRYPTO-GRAM is written by Bruce Schneier. Schneier is founder and CTO of Counterpane Internet Security Inc., the author of "Applied Cryptography," and an inventor of the Blowfish, Twofish, and Yarrow algorithms. He served on the board of the International Association for Cryptologic Research, EPIC, and VTW. He is a frequent writer and lecturer on computer security and cryptography.

Counterpane Internet Security, Inc. is a venture-funded company bringing innovative managed security solutions to the enterprise.

http://www.counterpane.com/

later issue
earlier issue
back to Crypto-Gram index

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..