Slashdot Mirror
How Would Crypto Back Doors Work?
frantzdb writes "We've been hearing about adding crypto back doors for the govement to snoop on us, but how would they work? Would there be one key that could be cracked opening up all such traffic? Also, how would/does the government know wether a bitstream is random bits, or encrypted data?"
They could never work.
The simple reason is that as long as there is an algorithm that cannot be penetrated, either by force or by escrow, that algorithm can hide data. On this, at least, the cat is out of the bag.
One of the more likely scenarios which could possibly keep criminals away from data while allowing governments to have access would be an agreement worldwide on a data-encryption standard that included key-escrow. Likely this would be implemented with a large database of registered keys rather than a "skeleton key" approach simply because the "skeleton key" would be a ridiculously easy target. Of course, this whole scenario cannot work for catching dissidents and criminals, and therefore cannot serve the purpose of fighting terrorists.
The reason is that under any reasonable key-escrow scheme a government would be required to show evidence before using the person's key to find the data. This works fine for average citizens who only use the mandated encryption standard, but, Surprise! When the government uses the key of terrorist Tim to decode his messages, they find that not only did he use the mandated scheme, but he also encrypted his data with his own scheme, which, of course, is unbreakable with current technology. Terrorist Tim wins in two ways here, not only did his data remain secure, but he also managed to waste a large amount of the government's time and resources.
The fact that this is even being proposed shows the ignorance of technology rampant in Congress. I live in NH, maybe I'll write a letter to Senator Gregg.
"He's more machine now than man, twisted and evil."
Making crypto 'safe' with a back door effectively makes it useless. Why would anyone in their right mind use a cryptographic algorithm knowing that a perfect stranger has a 'backdoor pass' to their information? The whole point of crypto is to only allow the intended recipient to view the secret information.
This idea would weaken any cipher that this idea is applied to. Why? Simple. Key recovery in a datastream you haven't ever seen before depends basically on one of 2 things: Brute force, and a little ingenuity. If you know that the cipher has a 'universal backdoor' then each stream encrypted with the cipher will be that much easier to crack -- because the streams will have to be somewhat similar.
What happens when the wrong people get the 'back door' key? You don't think that someone dangerous is going to somehow either recover the key manually, or steal it? Think again. A 'back door' key (or set of keys) of this scope would be too good to pass up. Why bother attempting to recover a key that unlocks one stream, when you can unlock a whole set of streams?
The cat's already out of the bag Why would somebody who really wants to keep information secret use a cipher that didn't keep it secret -- especially when there are so many good ciphers (RC4, Twofish, etc.) that don't have a backdoor? In short -- this is a braindead thought process that will lead the U.S. straight into another disaster.
Simply, that the only way to prove that something was encrypted "legally" would be to automatically break it, all of it, as it passes through various communications channels.
But this is too large of a job for just one person, or a (fiscally feasible) number of people, as much traffic may not pass through a central point. Machines will have to do it automatically, and there will ave to be many o them. Who will make the machines? How will they guarantee that the backdoor isn't released? What if the machines themselves take a walk?
Steganography would be the only way around this, by hiding an encrypted snippet well enough that it doesn't look encrypted. What if someone posts a badly-encoded GIF of their cat on their personal page, and the so-called "Stego detectors" pick it up. Of course, the "message" isn't there. Therefore it can't be decrypted, and they will be flagged as a criminal... scary prospect.
As the technology progresses, only poorly done stego and innocent media would be caught. It's already possible to encode messages to be indecipherable from quantization noise by any theoretically possible system.
-- Insert witty one-liner here. --
If you're talking about public key cryptography or some form of key exchange protocol (such as what happens with PGP, SSL, and the like), then, yes, there'll be more than one key that can decrypt the message. PGP already allows you to encrypt a message to more than one recipient; a simple solution would be to require all software to always encrypt to Uncle Sam's key in addition to the intended recipients.
The other solution is to weaken the encryption algorithm in some way. There are very subtle approaches, but the simplest is to limit the length of the key. A 40-bit key takes half as long to crack with brute force as a 41-bit key, and a 42-bit key takes twice as long again (all else being equal). If you have an application that uses 128-bit keys, it could be ``dumbed down'' to a 40-bit key by forcing all keys to start with 88 zeroes (or some other known pattern).
How to get people to use such software when there's a wealth of reliable strong cryptographic software readily available is left as an exercise to the reader.
Most encrypted streams have header information to make identifaction easy for the recipient. If you've ever gotten PGP-signed or -encrypted email, you've seen ``BEGIN PGP MESSAGE'' or some such at the top.
You could, of course, remove all such identification. If the encryption method is strong, what remains is provably indistinguishable from pure noise. If the recipient adds the identifaction back--if she puts ``BEGIN PGP MESSAGE'' before the bits--the result can be fed to the decryption proces without trouble.
But how many people send random bitstreams to each other? Somebody doing so would stand out like a sore thumb against the usual traffic of ASCII.
The most commonly accepted solution is steganography, the art of hiding secrets in plain sight. ``All the twenty clever kings'' could mean ``attack'' if you were to just look at the first letter of every word. Common modern methods of steganography include encoding the message in the low-order bits of a JPEG, but the field is still young and many techniques a bit crude. If ``they'' are already looking at you, ``they'' will have a good chance of finding the message.
As always, Bruce Scnhier's Applied Cryptography is a wonderful resource.
b&
All but God can prove this sentence true.
This is a long post (for me)... It basically contains the majority of a letter that I sent to my representative and senators... It basically states a number of reasons that I think this proposal is inoperable. I encourage all of you to contact your elected representatives as well.
0 0.html) that "Sen. Judd Gregg (R-New Hampshire) called for a global prohibition on encryption products without back doors for government surveillance."
Adam/Zwack
As I feared when I first saw the attack on the World Trade Center, it has been reported (http://www.wired.com/news/politics/0,1283,46816,
Media reports have made it appear that Osama Bin Laden may have used encryption, but it is more likely that he relied on a lack of technology. According to the media, Bin Laden held face-to-face meetings in a private room rather than trusting that the communications channel was not intercepted. One journalist who has met him had some newspapers with him and Bin Laden is reported to have pounced on them and read them as he was so out of touch with the outside world.
Even if there is a ban on encryption products, older encryption products already exist without those back doors. Writing encryption software is not too complicated (Applied Cryptography is about $40) and terrorists and criminals are not going to worry about breaking yet another law. So who would this effect? Criminals? No. Terrorists? No. Penry, The Mild Mannered Janitor? Could Be.
Anyone can do a little research and find out that there are other techniques that cannot be legislated against that are just as effective for secret communications.
Ronald Rivest, one of America's foremost cryptographers published a paper in 1998 called "Chaffing and Winnowing: Confidentiality without Encryption." (http://theory.lcs.mit.edu/~rivest/chaffing.txt) In it he describes a method for plain text communication which does not rely on encryption to hide the message. He then goes on to add more twists to the method, which mean that if someone demanded the actual message you could give them a completely false, and presumably inoffensive, message.
If that wasn't enough to make legislation on encryption pointless, then steganography, the practice of hiding one message inside another, could be used either independently or with "Chaffing and Winnowing". It is possible for messages to be hidden within pictures, movies, sound files and even Stream of Consciousness-like poems easily. The sophistication of some of the programs is astounding. One program (http://www.outguess.org/) actually performs a statistical analysis on the image first to ensure that in hiding the message it does not modify the image too much.
There are numerous other non-technological techniques that could make this law pointless. For example, the terrorists could choose a book, say Hamlet, and spell out their message with the words or letters in that book. A message like "42 23 17 65" is not going to mean much to anyone until they know that in a specific edition of a specific book they should read the twenty third word on page 42, the 65th word on page seventeen... and so on.
They could use a simple code where phrases mean certain things. So "I went to see the new production of Oscar Wilde's Importance of Being Earnest" might mean "The birthday cake arrives tomorrow". As long as only the parties involved know the code phrases, and their meanings this kind of communication is impossible to break.
If encryption software without back doors is outlawed, what will terrorists do? If they're paranoid they'll use illegal encryption to encrypt a code phrase, hide it in an image, and then mix it with several completely innocent, and some totally random streams using chaffing techniques.
That way, by the time the NSA have worked out which streams contain real messages, figured out that one or more of the images contains a steganographically hidden message and broken the encryption on it, they will have wasted weeks in order to get a perfectly normal sentence that isn't going to mean anything to them anyway.
In that same period of time, several companies who are obeying the law and not using encryption will have had their company secrets stolen by other companies, as they couldn't encrypt confidential messages between two of their office. The French Secret Service was known to pass trade secrets to French companies when the French government was strictly controlling encryption. Add to that the many completely innocent uses of encryption for security and confidentiality: communicating with banks, logging on to remote servers, protecting medical records, implementing Virtual Private Networks and so on. Banning encryption that the government can't decode is more likely to cause harm to the law abiding citizen than it is to stop or reduce terrorist or criminal activities.
In short, any attempt to regulate the free flow of ideas, whether encrypted or unencrypted is only going to hinder law abiding citizens, and effectively punish them, without providing any additional safety. Remember that these highjackings were very low tech, no computers were hacked, no high technology weapons were used, just people armed with knives and the willingness to die.
-- Under/Overrated is meta-moderation, and therefore is Redundant.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)