die@frog.UUCP (Dave Emery) (10/27/84)
<eat this> As someone unversed in cryptology I'd like to ask what may seem like a dumb question, does anybody know whether DES has *actually* been broken ? One hears much speculation about "NSA trap doors" and such, and discussion of some work which suggests the effective key length may be slightly shorter than 56 bits, but I am unaware of any account at all of someone having actually derived a method (short of brute force) of breaking DES encoded messages with only approximately (or partially) known plaintext, or even of obtaining the key given a large plaintext and it's equivalent ciphertext (even for block encipherment with a fixed key). Does anybody know of published or unpublished work that establishes a method of breaking DES in a reasonable amount of real time per key other than brute force milling on gigantic arrays of special processors ? Which leads to my second question, how secure should one assume something enciphered under DES really is ? Does current technology permit organizations with the resources of a say a large corporation (or even the mafia) (many millions to spend, but not billions) to break DES using more or less available hardware (large arrays of chips (standard or semi/full custom) or perhaps fast array processors such as the Cray machines) in under a few months per key ? When will we reach this point if we are not already there ? What impact does using double encipherment (DES-DES) or all the various variations (such as cipher chaining or feedback) of using the text being enciphered to permutate an initial key have on security ? I've heard it said that double encipherment doesn't help much ... why is this so ? Is it ever possible to break a DES class cipher without possessing any plaintext/cipher text pairs at all, by using statistical approaches based on knowlage of the properties of the plaintext being transmitted ? -- ---- David I. Emery Charles River Data Systems 983 Concord St. Framingham, MA 01701 Tel: (617) 626-1102 uucp: ...!decvax!frog!die
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (10/31/84)
> does anybody know whether DES has *actually* been broken ? I have not personally heard that it has, but ... > One hears much speculation about "NSA trap doors" and such, and > discussion of some work which suggests the effective key length may be > slightly shorter than 56 bits, but I am unaware of any account at all of > someone having actually derived a method (short of brute force) of breaking > DES encoded messages with only approximately (or partially) known plaintext, > or even of obtaining the key given a large plaintext and it's equivalent > ciphertext (even for block encipherment with a fixed key). ... I do know in general terms how I would go about breaking it, given the time, facilities, and motivation for doing so. Although a brute-force approach is guaranteed to work, in reality such an approach is not usually taken. Rather, one exploits the internal mathematical structure of the encryption system, which is always there and which has comparatively few parameters. The DES is somewhat more complicated than the cryptanalyst would really like, but its general characteristics are such that, given sufficient ciphertext encrypted by a single key, it is theoretically possible to break the system with far fewer resources than a brute-force key search would require. Known-plaintext approach ("crib dragging") can help considerably but it is not essential. > Does anybody know of published or unpublished work that establishes > a method of breaking DES in a reasonable amount of real time per key other > than brute force milling on gigantic arrays of special processors ? Because the NSA has a virtual monopoly on cryptography in this country (ASA, NSG, AFSA, CIA, etc. have their own operations but they are technically subservient to NSA), it is likely that any such work would be classified. I no longer subscribe to the NSA Technical Journal but it made fascinating reading, being one of the few places where this type of work is published to reach a (comparatively) wide audience. Most issues of the NSA Technical Journal were classified, to various degrees. > Which leads to my second question, how secure should one assume > something enciphered under DES really is ? I personally would assume that a technically competent cryptographic agency would be able to routinely read traffic so encrypted if it had some motivation to do so, and that amateurs could not. I would not stake human lives on its security. > Does current technology permit organizations with the resources > of a say a large corporation (or even the mafia) (many millions to spend, but > not billions) to break DES using more or less available hardware (large arrays > of chips (standard or semi/full custom) or perhaps fast array processors such > as the Cray machines) in under a few months per key ? When will we reach this > point if we are not already there ? Yes, if one had tens of millions to spend on equipment, brute-force hardware could be set up; this has been descibed in the open literature. The trouble with doing this is, as soon as word gets out that this has been done, the DES could be re-engineered to (for example) double its key size, which would force one to spend many times the original investment to retool the brute-force DES-breaking apparatus. In contrast, a clever approach would scale much more reasonably with key size. > What impact does using double encipherment (DES-DES) or all the > various variations (such as cipher chaining or feedback) of using the text > being enciphered to permutate an initial key have on security ? I've heard > it said that double encipherment doesn't help much ... why is this so ? In general, multiple encipherment does not do as much to make the cryptanalyst's job tougher as one might think. It normally does add somewhat to the task, but if you adopt an information-theoretic outlook you can see that no more than 56 bits more need to be found for double DES encryption than for single encryption. This will at least double the work (under typical assumptions), but the required computation is not necessarily very great anyway so this is no big deal. Under a brute-force approach, the work might go up by a factor of 2^56, which would be hopelessly expensive. By the way, it often happens that iteration of an encipherment system is equivalent to a single use of the system with a different effective key (the obvious example is simple substitution). > Is it ever possible to break a DES class cipher without possessing > any plaintext/cipher text pairs at all, by using statistical approaches > based on knowlage of the properties of the plaintext being transmitted ? Definitely. Known-plaintext is desirable but algebraic/statistical analysis can be applied (often in conjunction with whatever other knowledge is available). The most accessible desciption of such methods is probably the original unabridged edition of David Kahn's "The Codbreakers", although techniques have progressed far beyond those he discusses. In fact, unless the underlying plaintext is strictly random (which in practice it never would be), considerable progress can be made without a priori knowledge of its statistics. One inherent limitation to statistical techniques is that there is only a certain probability of being able to break a given message with them, and the odds of doing so depend on the structure of the encryption system, the length of the key, the plaintext statistics, and the amount of plaintext. If one has a good handle on the statistics, he can estimate how frequently (as a function of text traffic) one needs to change the key for a given system to ensure that there is little chance of statistical approaches being able to break out the message. I haven't computed this for the DES but I am sure someone has; I wonder what the DES unicity distance really is. I bet it is less than people generally realize. P.S. If anyone from the NSA wants to give me a hard time about this discussion, let me remark that everything I have said can be obtained from unclassified sources. I think it is to the general benefit of everyone except perhaps the cryptographic agencies to work toward demonstrably secure cryptosystems for commercial use.
chongo@nsc.UUCP (Landon C. Noll) (11/04/84)
> P.S. If anyone from the NSA wants to give me a hard time about > this discussion, let me remark that everything I have said can be > obtained from unclassified sources. I think it is to the general > benefit of everyone except perhaps the cryptographic agencies to > work toward demonstrably secure cryptosystems for commercial use. Folks who know about the multi-speak one goes through to say: "I neither confirm, nor deny, nor to admit that public comment should, or should have not been said for national security reasons." can understand why people smell a rat in the DES system. The NSA would not admit to the fact that the DES has a trapdoor (so they can read the other guys messages in case they use it), NOR would the NSA admit that the DES is very secure (in case the other guys actually fear that the NSA did have a trapdoor and thus not use it while domestic traffic is secure from the other guys). On the other hand, the NSA might act in such a way as to indirectly admit the truth (the other guys think the NSA wants to fake them out, so they reject the truth), or indirectly give out dis-information (the other guys suspect a double-switch so...). Anyway you get the idea.. [Note: the term: other guys is used as a generic term] The net sum of the above kind of system is: "If in doubt, don't count on it going your way. If dealing with security, then doubt. Therefore don't count on it!" This rule need not apply to encryption of your christmas wish list to mommy, but it might be useful for sending your all your money over a wire. Then again of you always encrypt everything, you wont forget to encrypt things of value, nor will you call attention to an secure message when you need one! But then again if you encrypt everything, you might call attention to youself to such a degree that the other guys try to break all your messages! I think it would be good for the NSA to come out with some testable justification of the DES system. Maybe the folks at arrowwan.UUCP might like to comment or help clear the air on this, but I am not going to wait until they do. Last, let me refer readers to the President's letter on the Communications of the ACM for the past 3 years in regards to the damage National Security has done to research. There is a price paid for National Security, and there is a value gained by it. Discussions about the net result are best done on net.politics. chongo <the text of this article is actually encrypted> /\??/\ -- "Don't blame me, I voted for Mondale!" John Alton 85'