Crypto-Gram

October 15, 1998

by Bruce Schneier
President
Counterpane Systems

schneier@schneier.com
http://www.counterpane.com

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

Copyright (c) 1998 by Bruce Schneier

In this issue:

Steganography: Truths and Fictions

Steganography is the science of hiding messages in messages. In the ancient world, it might mean tattooing a secret message on the shaved head of a messenger, and letting his hair grow back before sending him through enemy territory. In the computer world, it has come to mean hiding secret messages in graphics, pictures, movies, or sounds. The sender hides the message in the low-order bits of one of these file types—the quality degrades slightly, but if you do it right it will hardly be noticeable—and the receiver extracts it at the other end.

Several commercial and freeware programs offer steganography, either by themselves or as part of a complete communications security package. Here’s the rationale: If Alice wants to send Bob an e-mail message securely, she can use any of several popular e-mail encryption programs. However, an eavesdropper can intercept the message and, while he might not be able to read it, will know that Alice is sending Bob a secret message. Steganography allows Alice to communicate to Bob secretly; she can take her message and hide it in a GIF file of a pair of giraffes. When the eavesdropper intercepts the message, all he sees is a picture of two giraffes; he has no idea that Alice is sending Bob a secret message. She can even encrypt it before hiding it, for extra protection.

So far, so good. But that’s not how it really works in practice. The eavesdropper isn’t stupid; as soon as he sees the giraffe picture he’s going to get suspicious. Why would Alice send Bob a picture of two giraffes? Does Bob collect giraffes? Is he a graphic artist? Have Alice and Bob been passing this same giraffe picture back and forth for weeks on end? Do they even mention the picture?

The point of steganography is to hide the existence of the message, to hide the fact that the parties are communicating anything other than innocuous photographs. This only works when it can be used within existing communications patterns. I’ve never sent or received a GIF in my life. If someone suddenly sends me one, it won’t take a rocket scientist to realize that there’s a steganographic message hidden somewhere in it. If Alice and Bob already regularly exchange files that are suitable to hide steganographic messages, then an eavesdropper won’t know which messages—if any—contain the messages. If Alice and Bob change their communications patterns to hide the messages, it won’t work. An eavesdropper will figure it out.

This is important. I’ve seen steganography recommended for secret communications in oppressive regimes, where the simple act of sending an encrypted e-mail could be considered subversive. This is bad advice. The threat model assumes that you are under suspicion and want to look innocent in the face of an investigation. This is hard. You are going to be using a steganography program that is available to your eavesdropper. He will have a copy. He will be on the alert for steganographic messages. Don’t use the sample image that came with the program when you downloaded it; your eavesdropper will quickly recognize that one. Don’t use the same image over and over again; your eavesdropper will look for the differences between that indicate the hidden message. Don’t use an image that you’ve downloaded from the net; your eavesdropper can easily compare the image you’re sending with the reference image you downloaded. (You can assume he monitored the download, or that he searched the net and found the same image.) And you’d better have a damn good cover story to explain why you’re sending images back and forth. And that cover story should exist before you start sending steganographic messages, and afterwards. Or you haven’t really gained anything.

Steganography can also be used to hide files on your hard drive. This is also problematic. Say the secret police arrest you and start going through your hard drive. You’ve got a bunch of pornographic pictures on your hard drive, so you’ve got a decent cover story. But you’ve also got the steganographic program on your hard drive, so the secret police are suspicious. They might try to download the same pictures from the net and look for the telltale differences that indicate a hidden message. Or they might just assume that you’ve got some messages hidden somewhere. There’s some advantage here over straight encryption—at least in free countries you can argue that the police have no real evidence—but you have to think it out very carefully.

TriStrata

Over the past several months, a new company called TriStrata has been getting substantial press for a new “one-time pad” cryptography system. Most of these press reports took at face value the company’s claims about their technology and product, and did not try to analyze whether or not they were true. Counterpane Systems believes it is important to dig under the hype and figure out what the real story is behind their technology.

We reviewed the publicly available documentation on TriStrata, and found a system whose architecture is that of an early-1970s pre-public-key cryptography security system. Central servers, upon which the security of every message rests, must be kept absolutely secure; yet they run on Windows NT. These servers are all powerful, in that they can forge messages, rewrite audit logs, fake authentication, and lie about anything else in the system. Users cannot access their files unless they are connected to this server. TriStrata does not use a one-time pad at all, and none of the security proofs about a one-time pad apply to their system. Their reliance on this encryption technology forces them to use security protocols long abandoned by the rest of the security industry; in effect, ignoring the past 20 years of research into public-key cryptography and its advantages. Even their performance enhancements belie the fact that encryption is rarely the bottleneck in any communications system.

A system like TriStrata’s can be made to work within its limitations. It is certainly not the universal solution to the world’s security problems. However, there is a huge amount of hype and very little substance to the documentation. Many of the statements made are incomplete, vague, or suggest facts which cannot be true. The cryptographic claims are wild and unsubstantiated. Parts are clearly written by someone who does not understand modern cryptography, and who is not well versed in the cryptographic literature. Certain areas of the documentation give the impression that they were written with the intent to deceive the reader, but ignorance is probably a better explanation. Based on past experience with systems that made similar unsupported security claims, we are very skeptical about the security of the TriStrata system.

You can find our review at: http://www.schneier.com/tristrata.html
Press coverage: http://www.zdnet.com/pcweek/stories/news/…
See also the one-time pad FAQ at: http://www.clark.net/pub/mjr/pubs/otpfaq [link moved to http://web.ranum.com/pubs/otpfaq/]

Counterpane Systems: Featured Research

“Side Channel Cryptanalysis of Product Ciphers”

J. Kelsey, B. Schneier, D. Wagner, and C. Hall, ESORICS 98 Proceedings, Springer-Verlag, 1998, pp. 97-110.

Generalizing the work of others, we introduce the notion of side-channel cryptanalysis: cryptanalysis using implementation data. This includes timing attacks, power cryptanalysis, etc. We show how powerful these attacks are, and why they are so hard to prevent. We show concrete examples against IDEA, DES, and RC5, and then generalize our research to other ciphers.

http://www.schneier.com/paper-side-channel.html

News

The White House eased limits on crypto export. Now 56-bit DES can be exported pretty much anywhere, and stronger crypto can be more easily exported to banks, to insurance companies, to subsidiaries of U.S. corporations, and for medical and electronic commerce applications. There’s also easier rules for companies implementing key escrow (I don’t know how Private Doorbell will fare under these new rules). While this is certainly good news, I don’t think we’ve won anything big here. One, it’s always been easier to export to subsidiaries of U.S. corporations and financial institutions. Two, DES’s 56-bit key is too short for most security applications. And three, by loosening the rules for electronic commerce products, the White House has made it harder to export strong cryptography for human rights uses. The devil is in the details, though, and we won’t see the details until the new regulations are published in the late fall.
http://www.news.com/News/Item/0,4,26427,00.html
http://www.crypto.com/reuters/show.cgi?… [dead link as of 1999-08-25—for this and the next link, see http://www.cdt.org/crypto/admin/]
http://www.crypto.com/reuters/show.cgi?… [dead link as of 1999-08-25]
See CDT’s reaction at http://www.cdt.org/crypto

In yet another proof that Canada isn’t just a northern suburb of the United States, that government issued new, and relatively loose, crypto export policies. I guess that means companies like Entrust and Certicom will continue to eat the lunch of assorted U.S. corporations in the world market. If only the weather weren’t so cold….
http://www.wired.com/news/politics/0,1283,15362,00.html
http://www.news.com/News/Item/0,4,27044,00.html
More information on the policy is available at: http://strategis.ic.gc.ca/SSG/cy00001e.html [dead link as of 1999-08-23]

Watch the FBI. While everyone else is embroiled in Monica Lewinsky news, they are trying to sneak a series of draconian surveillance measures through Congress.
http://www.wired.com/news/politics/0,1283,15350,00.html

So you want to get around export controls. Here’s how the professionals do it.
http://motherjones.com/mother_jones/MJ98/…

On the WWW, things you say in haste are often recorded, and can come back to haunt you in 20 years. “‘The odd thing is, we perceive the Net as a conversation and not as public record, and it turns out to be public record to a larger extent than people are aware of,’ said Bruce Schneier, a cryptography consultant and co-editor of The Electronic Privacy Papers, a 1997 book. ‘You can easily imagine in 20 years a candidate being asked about a conversation he had in a chat room while he was in college. We’re becoming a world where everything is recorded.'”

http://search.washingtonpost.com/wp-srv/WPlate/… [dead link as of 1999-08-23; available for a fee at http://newslibrary.krmediastream.com/cgi-bin/…]

Counterpane Systems News

There are a bunch of new things on the Counterpane web site.

We’ve completed an on-line bibliography of cryptography papers on the WWW. There are over 1000 papers indexed. You can search papers by author and by keyword, and you can enter new papers. Try it out at:

http://www.schneier.com/biblio/

And there’s always new Twofish news. We’ve released two Twofish Technical Reports since we finished the main paper, and have cryptanalytic attacks against two of the other AES submissions:

http://www.schneier.com/twofish.html

And for those people who have been wanting to learn cryptanalysis but are not sure how to start, there’s a “Self-Study Course in Block-Cipher Cryptanalysis” available:

http://www.schneier.com/paper-self-study.html

The Doghouse: RapidRemote

RapidRemote (by Procomm, now owned by Quarterdeck) allows you to control one PC from a remote PC. The idea is that you can be at home or on the road, and access the computer in your office. According to the product web site, “With RapidRemote, your data and PC are constantly protected with layers of sophisticated security features such as data encryption and password protection.”

Not by a long shot.

Quarterdeck appears to have put little or no effort into the security of RapidRemote. The design allows for simple attacks on both the encryption algorithm and the authentication mechanism that allow attackers to gain complete control over the server.

Encryption: By default, RapidRemote does not encrypt its transactions. If the user enables the encryption option, RapidRemote uses the identity function in CFB mode with an eight-bit initialization vector. There is no session key. Thus, an eavesdropper only needs to try a total of 256 different IVs in order to break the security. This form of encryption is so weak that the eavesdropper could break it by hand if she felt like it; a computer could break it faster than the eavesdropper could blink.

Authentication: Authentication consists of sending an obscured (encrypted using a fixed key) username/password pair over the “encrypted” channel to the host, which compares them to entries in a local database. If RapidRemote is installed on an NT server, the NT authentication mechanism may be used instead; the username and password must correspond to an account on the machine.

Since the encryption is practically nonexistent, an eavesdropper can recover the username and password immediately. If the host is an NT server, the username and password will allow the eavesdropper to access the server by way of internet or intranet as well as by modem.

One necessary part of password-based authentication is keeping the password secret. RapidRemote fails to do this. On the client computer, there is a list of profiles that contains the usernames and passwords. In order to establish a connection, the user simply double-clicks on one of the profiles. The user is never prompted for a password. Stealing a laptop with RapidRemote installed is essentially the same as having direct access to the server.

A thief may be more interested in the password than in accessing the server by way of RapidRemote. The passwords are obscured in the profile database; however, a freeware program called Revelation (available at http://www.snadboy.com) will simply read the password out of the password edit box in the profile manager and display it.

Conclusion: RapidRemote’s security is pathetically vulnerable to attack. The encryption is practically nonexistent; a brute-force attack only requires testing 256 initialization vectors. The username and password are immediately available to an eavesdropper. A thief does not need to know the password to access the host computer, but can get it easily if he wants it. And the fact that RapidRemote claims to have security makes the program even more dangerous than one with no security at all.

http://arachnid.qdeck.com/qdeck/products/corporate/…

Memo to the Amateur Cipher Designer

Congratulations. You’ve just invented this great new cipher, and you want to do something with it. You’re new in the field; no one’s heard of you, and you don’t have any credentials as a cryptanalyst. You want to get well-known cryptographers to look at your work. What can you do?

Unfortunately, you have a tough road ahead of you. I see about two new cipher designs from amateur cryptographers every week. The odds of any of these ciphers being secure are slim. The odds of any of them being both secure and efficient are negligible. The odds of any of them being worth actual money are virtually non-existent.

Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can’t break. It’s not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. And the only way to prove that is to subject the algorithm to years of analysis by the best cryptographers around.

“The best cryptographers around” break a lot of ciphers. The academic literature is littered with the carcasses of ciphers broken by their analyses. But they’re a busy bunch; they don’t have time to break everything. How do they decide what to look at?

Ideally, cryptographers should only look at ciphers that have a reasonable chance of being secure. And since anyone can create a cipher that he believes to be secure, this means that cryptographers should only look at ciphers created by people whose opinions are worth something. No one is impressed if a random person creates an cipher he can’t break; but if one of the world’s best cryptographers creates an cipher he can’t break, now that’s worth looking at.

The real world isn’t that tidy. Cryptographers look at algorithms that are either interesting or are likely to yield publishable results. This means that they are going to look at algorithms by respected cryptographers, algorithms fielded in large public systems (e.g., cellular phones, pay-TV decoders, Microsoft products), and algorithms that are published in the academic literature. Algorithms posted to Internet newsgroups by unknowns won’t get a second glance. Neither will patented but unpublished algorithms, or proprietary algorithms embedded in obscure products.

It’s hard to get a cryptographic algorithm published. Most conferences and workshops won’t accept designs from unknowns and without extensive analysis. This may seem unfair: unknowns can’t get their ciphers published because they are unknowns, and hence no one will ever see their work. In reality, if the only “work” someone ever does is in design, then it’s probably not worth publishing. Unknowns can become knowns by publishing cryptanalyses of existing ciphers; most conferences accept these papers.

When I started writing _Applied Cryptography_, I heard the maxim that the only good algorithm designers were people who spent years analyzing existing designs. The maxim made sense, and I believed it. Over the years, as I spend more time doing design and analysis, the truth of the maxim has gotten stronger and stronger. My work on the Twofish design has made me believe this even more strongly. The cipher’s strength is not in its design; anyone could design something like that. The strength is in its analysis. We spent over 1000 man-hours analyzing Twofish, breaking simplified versions and variants, and studying modifications. And we could not have done that analysis, nor would we have had any confidence in that analysis, had not the entire design team had experience breaking many other algorithm designs.

A cryptographer friend tells the story of an amateur who kept bothering him with the cipher he invented. The cryptographer would break the cipher, the amateur would make a change to “fix” it, and the cryptographer would break it again. This exchange went on a few times until the cryptographer became fed up. When the amateur visited him to hear what the cryptographer thought, the cryptographer put three envelopes face down on the table. “In each of these envelopes is an attack against your cipher. Take one and read it. Don’t come back until you’ve discovered the other two attacks.” The amateur was never heard from again.

I don’t mean to be completely negative. People occasionally design strong ciphers. Amateur cryptographers even design strong ciphers. But if you are not known to the cryptographic community, and you expect other cryptographers to look at your work, you have to do several things:

1. Describe your cipher using standard notation. This doesn’t mean C code. There is established terminology in the literature. Learn it and use it; no one will learn your specialized terminology.

2. Compare your cipher with other designs. Most likely, it will use some ideas that have been used before. Reference them. This will make it easier for others to understand your work, and shows that you understand the literature.

3. Show why your cipher is immune against each of the major attacks known in literature. It is not good enough just to say that it is secure, you have to show why it is secure against these attacks. This requires, of course, that you not only have read the literature, but also understand it. Expect this process to take months, and result in a large heavily mathematical document. And remember, statistical tests are not very meaningful.

4. Explain why your cipher is better than existing alternatives. It makes no sense to look at something new unless it has clear advantages over the old stuff. Is it faster on Pentiums? Smaller in hardware? What? I have frequently said that, given enough rounds, pretty much anything is secure. Your design needs to have significant performance advantages. And “it can’t be broken” is not an advantage; it’s a prerequisite.

5. Publish the cipher. Experience shows that ciphers that are not published are most often very weak. Keeping the cipher secret does not improve the security once the cipher is widely used, so if your cipher has to be kept secret to be secure, it is useless anyway.

6. Don’t patent the cipher. You can’t make money selling a cipher. There are just too many good free ones. Everyone who submitted a cipher to the AES is willing to just give it away; many of the submissions are already in the public domain. If you patent your design, everyone will just use something else. And no one will analyze it for you (unless you pay them); why should they work for you for free?

7. Be patient. There are a lot of algorithms to look at right now. The AES competition has given cryptographers 15 new designs to analyze, and we have to pick a winner by Spring 2000. Any good cryptographer with spare time is poking at those designs.

If you want to design algorithms, start by breaking the ones out there. Practice by breaking algorithms that have already been broken (without peeking at the answers). Break something no one else has broken. Break another. Get your breaks published. When you have established yourself as someone who can break algorithms, then you can start designing new algorithms. Before then, no one will take you seriously.

Creating a cipher is easy. Analyzing it is hard.

See “Self-Study Course in Block Cipher Cryptanalysis”: http://www.schneier.com/paper-self-study.html

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

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

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 president of Counterpane Systems, 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 cryptography.

Counterpane Systems is a five-person consulting firm specializing in cryptography and computer security. Counterpane provides expert consulting in, design and analysis, implementation and testing, threat modeling, product research and forecasting, classes and training, intellectual property, and export consulting. Contracts range from short-term design evaluations and expert opinions to multi-year development efforts.

Sidebar photo of Bruce Schneier by Joe MacInnis.