Path: msuinfo!caen!uwm.edu!cs.utexas.edu!not-for-mail From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Algorithms Date: 11 Nov 1994 22:21:39 -0600 Organization: UTexas Mail-to-News Gateway Lines: 189 Sender: nobody@cs.utexas.edu Message-ID: <199411120422.WAA04049@pentagon.io.com> NNTP-Posting-Host: news.cs.utexas.edu In <39n23d$loq@net.auckland.ac.nz> egendorf@mail1.sas.upenn.edu (Robert Egendorf) writes: > What algorithms besides IDEA and 3xDES are extremely >difficult to break? First of all, we do *not* know that either IDEA or Triple-DES *are* difficult to break (that is, for everybody). In particular, IDEA has an internal structure which I would term "almost linear." While not strictly linear, it may be linear enough to work on, and so almost begs to be broken. Alas, this is not likely to be something one does in the odd afternoon. Any serious attack on any serious cipher is likely to be an arduous process involving a great deal of time and lots of trial and error. Success, while fun, is not very profitable. I wish I had the time to throw at it. All block ciphers are relatively-simple mechanisms which attempt to simulate a huge substitution table; this is no more than Simple Substitution on a large data value. I expect that no simple machine can do this perfectly well. Therefore, we might well have a situation where massive statistical exploration (from a new generation of computers) could lead to key- or data-bit correlations which have not yet been discovered. We commonly assume that the keysize of Triple DES is at least twice as long (has 2**56 times as many keys) as ordinary DES, and that may be. But consider the simple newspaper amusement ciphers, which are also Simple Substitution: Clearly, even three sequential cipherings through different alphabet permutations will be no harder to solve than one. (In this case we do not solve for each of the keys independently, but this probably does not matter.) Now, in a real block cipher, CBC mode will use the data space better, so the character-frequency attack on the newspaper ciphers will not work. Nevertheless, this is one example of a real attack which is *not* complicated by additional levels of ciphering. I have no reason to believe that it is the only such attack. Thus we do *not* know that Triple DES is any stronger than DES itself. >[...] >Also, Terry >Ritter posted something about an algorithm he developed. Has anyone >evaluated this? Mr. Ritter has posted the design of at least three encryption mechanisms in detail: 1) Penknife -- a 63-bit key, plus random 32-bit line key on each ciphertext line, file cipher for email. The mechanism is basically a two-level stream cipher, using both nonlinear Dynamic Substitution and conventional additive combiners, with a small nonlinearized RNG. Penknife produces only network-transportable ciphertext in ASCII lines. It can automatically skip email headers and .sigs when deciphering, or keep them with the deciphered message. Penknife is an example of an error-resilient re-originating stream cipher. 2) Cloak2 -- a 992-bit key, plus 992-bit message key, file cipher. The mechanism is a two-level nonlinear Dynamic Substitution combiner stream cipher, with 16 second-level combiners, and huge nonlinearized RNG's. The ciphertext is binary. Both of the above are commercial secret-key ciphers currently implemented for MSDOS (and which now function well under Microsoft Windows). They are not exportable. But while the ciphers proper are important, probably the major practical value of these systems lies in extensive key-management by open alias, with the ability to cleanly update keys without disturbing most users. Central key management can be important to allow a business to retain access to information for which it originally paid. And archived ciphertext under old, replaced keys can be accessed easily. 3) Fenced DES -- currently in experimental implementation. Intended to expand the width of DES (or other block cipher) and thus increase overall strength, with minimal increase in computation. For example, quad-width Fenced DES (256-bit block) ciphers faster (per byte) than Double-DES. This was done by innovating a general concept of a Block Mixing Transform which reversibly mixes data and can be efficiently scaled to virtually arbitrary size. The fast transforms are weak, thus requiring isolation; a fencing array of thirty-two 8-bit keyed substitution tables both on the data input and output provide the needed isolation. The mathematical structure of the transforms and the simple substitution layers means that we can make some fairly specific statements about avalanche, a required property of block ciphers which is normally investigated only by experiment. Of course, the keyed nature of the fencing tables does imply a substantial set-up delay, but also substantial added strength. My original proposals for the wide-block-DES project (which led to Fenced DES) were weak, ranging from not very useful, to not strong enough. Not unexpectedly, the only real analyses which I saw were directed against these weak approaches. Unfortunately, there is not much to say when you don't have an attack to discuss, so the open literature tends to accumulate ciphers of unknown strength. Of course, since there *is* *no* practical cipher *with* a proven strength, this is just part of the whole cipher game. Personally, I think if you want a block cipher with "strength," it is crucial to have a wider block than 64 bits, especially if the cipher will handle the massive real-time graphics of the near future. One low-controversy approach is Richard Outerbridge's scheme (Applied Cryptography, Fig. 8.10), although it has only a double-width block and a computation requirement (per byte) of three times DES. But let's return to: > What algorithms besides IDEA and 3xDES are extremely >difficult to break? The issue I want to bring out is: "how difficult do we need"? In the first place, ciphers do not exist in a vacuum: Ciphers can protect information, but they can only protect information which is otherwise secret. And if the secret information can be "obtained" (coerced, stolen, bribed, etc.) cheaper than "breaking" the cipher, there is probably very little point in having a stronger design. Having spent some time attacking ciphertext, I can assure you that *I* would take virtually any other alternative. However, it has recently occurred to me that some might believe in the existence of "the aliens among us." OK, suppose we assume The Grays have molecular-sized supercomputers by the liter, and so can afford to attack ciphertext itself by key-exhaustion: this would make most of our common ciphers useless. But we can make a system which should be strong enough to evade even such an attack, simply by doing what we know how to do, in grand scale: For example, I used a 992-bit key (over 10 times as *long* as an 80-bit "large enough" secret key) in my Cloak2 stream cipher, because it was a reasonably clean design without too much overhead. Since that design uses an RNG with about 37.8K (Bytes) of state, I could instead "easily" equip it to use honest 310,048-bit keys, provided we are willing to generate and keep such keys. (The user keys would be kept inside enciphered alias files, of course, but a 40K message key on a 2K message might seem a little much.) Note how much trouble we have doubling or quadrupling the block size and key space in block ciphers, and the ease with which we can expand the keyspace of a stream cipher. Generating any of 2**310,000 ciphertexts at will (instead of, say, 2**80), should make things somewhat harder for The Grays :-). Ciphering speed would be generally unchanged in the resulting cipher, which is generally not the case when we try to expand a block cipher. Of course we could use even more complex combining systems which *would* be slower (and would also isolate the RNG better), and we would also look longingly toward fast "really random" hardware. But is all this really necessary? The issue seems to be clearer for business applications: There, a cipher need be only strong enough to prevent significant losses. Even the loss of confidential information can be evaluated in terms of lost contracts or lawsuit costs. There are always losses and suits and business costs, and as long as the losses remain small, security would seem sufficient. (Of course, one does seek to avoid the proof that one's security has been weak.) Thus, in business, there may be room for a range of what we would consider to be relatively "weak" ciphers, especially if they can be made very fast and efficient. On the other hand, international banking transfers really huge amounts of money around as data. While there are checks and balances on this, it is possible to imagine some sort of terrorist attack on international funds transfers. Presumably, the NSA has acted to provide or certify acceptable systems to protect at least the US banks. We do not make every system "ultimately strong," because there *is* no "ultimate," and, eventually, we have to decide how much strength we want to pay for. Since we cannot *measure* the "strength" of a cipher, we are necessarily forced into arguing what someone else can and cannot do when they attack it. While this is not an especially strong logical position, it is all we have. --- Terry Ritter ritter@io.com