2.3 - Assessment of Modern Cryptosystems

Copyright(c), 1990, 1995 Fred Cohen - All Rights Reserved

Given a wide variety of commercially available cryptosystems, we are left with the monumental problem of determining the suitability of these systems for use in an environment. As we will see, the current state-of-the-art leaves much to be desired.

At this time, there is no comprehensive theory for establishing the credibility of a cryptosystem. Shannon's workload concept is a step in the right direction, but it leaves us with the problem of determining workload and provides no method of doing this. Cryptanalysis is usually performed by finding successively cleverer methods of attack. Since there is no feasible means of finding the optimal attack strategy against a system, we are always left with the possibility that tomorrow a clever cryptanalyst will find a very fast method of breaking the scheme we use safely today. The one exception is a system where the unicity distance is never reached, the one-time-pad.

The cryptosystem itself is only a small part of the environment which maintains cryptographic protection. The environment as a whole determines the effectiveness of cryptographic protection. The strategy normally used to make decisions is to analyze how a system works in an environment relative to other factors. We generally come up with a set of conditions under which the cryptosystem will be adequate, and then explain that we cannot make certain those conditions exist now or will exist in the future.

It is hard to overemphasize the need for an expert in the design of a cryptographic transform. History shows time and again that loss of life, limb, and fortune follow the non expert use of cryptography. There are only 3 major transforms available today that offer a reasonable degree of practical safety, and each of these can be broken if improperly used. These transforms are the one-time-pad (OTP), the data encryption standard (DES), and the Rivest, Shamir, Adleman (RSA) public-key system. We now review each in some depth.

The One-Time-Pad

• The one-time-pad (OTP) [Shannon49] is the only system to date that has been proven secure in the information theoretic sense. That is, with an arbitrary computational ability, the OTP cannot be broken. The basis of such a system is the use of a single key such that the encryption (E) of a message (M) into ciphertext (C) and its decryption (D) back into M, use the same key (K). In other words:

  D(E(M,K),K)=M

• In the OTP, K is a random sequence of sufficient length so that the sums of the lengths of all messages ever transmitted using K is less than or equal to the length of K. The reason that such a system is secure is that it uses each element of K only once, and the next element of K cannot be derived from previous elements of K.
• The problems with such a system include the distribution of K, and the fact that K must be as long as all of the messages ever to be sent. For some computer communications, this may be highly impractical, but the use of very dense ROMs makes this a practical solution to many computer to computer communications problems under the assumption that we can securely distribute and maintain the keys. Of course, if we could securely distribute the key, we could also securely distribute the messages. The only valid use remaining for the OTP is in cases where key distribution can be done at leisure, while transmission must be done in haste.
• One major variations on the OTP are systems that compress data to increase the number of bits of ciphertext per bit of key, and thus turn a one-time-pad into a many time pad. This reduces the key distribution problem.
• Another major variation is the use of pseudo-random number generation (PRNG) in place of the OTP. This is secure only so long as the PRNG is good enough to make the next bit unpredictable from all previous bits. A PRN is a number that appears to be random by all statistical measures of randomness, but that is in fact generated by a finite state machine [Knuth69] . Such a system eventually repeats keys, but it can be made to have an extremely long period, and therefore be used for transmitting a great deal of data. In addition, since the data generating the key can be relatively small in comparison to the length of the sequence generated by it, new key generating data can be exchanged relatively easily.
• Most generators of this sort are not very good, although some RSA based PRNGs are quite good as far as we can tell, and have acceptable performance for many applications. Several statistically strong generators of this sort exist [Blum82] [Knuth69] , but statistically strong systems have been successfully broken in the past. No such generator can be proven to meet the unicity distance requirements for all possible statistical measures [Knuth69] .

The Data Encryption Standard

• The Data Encryption Standard (DES) [DESDOC77] was designed by IBM to meet a government request for a high quality, low cost, high speed cryptosystem for everyday use. The DES has a sordid history, its future looks quite dim, and its origins are in systems that have all been broken, but it is a practical system for many applications because the cost of attack is thought to be quite high, and the cost of use is quite low.
• The DES is based on 16 successive rounds of diffusion and confusion, successive rounds being required because the quantity of circuitry required to implement it in fewer rounds grows exponentially with the reduction in rounds. The key size of the DES is only 56 bits, which is far too small for real protection under current technology. It is possible that 128 or 256 bit DES like implementations will soon become popular in the marketplace.
• The major variations on the DES include versions with 128 bit keys instead of 56 bit keys, and various modes of using the DES to attempt to improve its protection. Typical methods include a "cipher feedback mode", a "chaining mode", and multiple encipherment. At present there is no firm basis for the widespread belief that these techniques strengthen the system, and they may in fact weaken it considerably. There are many variations that don't preserve all of the DES properties, and in some notable cases DES like algorithms have proven to be trivially attacked. The DES has led a stormy life, is no longer supported by the NSA, and will likely fall into disuse in the next several years. It is rumored that the US government has a PC-AT program that breaks a 128 bit DES encoded message in 8 minutes, but this is impossible to independently confirm because of the shroud of secrecy maintained over cryptography.

The Rivest, Shamir, Adleman Public-Key Cryptosystem

• The only unbroken public-key cryptosystems at this time are based on the Rivest, Shamir, Adleman (RSA) public-key system [Rivest78] . In fact this system is quite easy to break from an information theoretic point of view in that all the necessary information to determine the private key is available in the public key. The protection in this system lies in the fact that noone knows how to derive a private key from a public key in a reasonable amount of time.
• To derive a private key from a public key, you would have to be able to factor the product of 2 very large primes. This problem has been under mathematical examination for several hundred years by many famous mathematicians. The best known algorithms now work in about (ln(n))**(sqrt(ln(n)/ln(ln(n)))) time (where N is the number of digits in the key). Thus a 200 decimal digit key would take about 1.2*10**23 fairly complex operations to break. This is more operations than can be performed by the fastest computer in the world (about 10**10 operations per second) in over 30,000 years.
• The key can be made as long as necessary to assure sufficient protection, so 200 digits is not a limit, and as faster computers become available, increased protection can be attained by increased key size. Several systems with very similar properties to the RSA have been shown to be insecure [Kravitz82] , and although the RSA system seems to be acceptable at this time, there is certainly no guarantee of its continued security.
• Another potential difficulty with RSA is the long time required to generate the public key, encipher messages, and decipher messages. For a 200 digit key, using the best available special purpose hardware, key generation requires several seconds, and encryption or decryption operate only at 6300 bits/second (=787 bytes/sec). The delay time cannot be easily reduced by using parallelism under current techniques.
• At least one chosen plaintext attack will work against an RSA system. If the attacker can choose text to be enciphered using the private key, the private key can be derived after only N encipherments, where N is the number of bits in the private key. The protocol used in an RSA based system must therefore make this attack infeasible. Similarly, as with any system, a playback of an old message can cause repeted interpretation if some sort of playback defense is not used.
• An additional property of the RSA public key cryptosystem is that E(D(M,Kd),Ke)=M. This feature allows digital signatures by having the signer use their private key to sign a document. By encrypting the document with the private key Kd and publishing the result, anyone with access to Ke can read the result. Since the derivation of Kd from Ke is difficult, the signature is difficult to forge. The RSA code works on blocks of symbols of sufficient length and in such a manner that the modification of ciphertext is unlikely to produce valid plaintext. Thus ciphertext attacks are not likely to allow the modification of a document in a systematic and meaningful manner.

Cryptographic transforms themselves are not adequate to lead to secure use. History shows us that any system will fall under concerted attack if it is not properly used. The key management problems pointed out earlier are only the tip of the iceberg when it comes to proper use of these systems. Furthermore, as in the case of the transforms, there is no comprehensive theory regarding how these systems are to be used. In effect, each protocol for use of a cryptographic scheme is shown to meet some set of criteria that is important to the application. At the heart of this analysis, is an expert who may or may not have enough expertise to do the job.

For any system, there is a comprehensive list of properties of interest that can be formed by taking all of the different parts of the system given in the model of how it works, and assessing which should or should not be determinable by which of the others. Each property must be evaluated in the application at hand to determine if it is important, and if it is fulfilled by the implementation.

As an example, let's take the simple model of a cryptosystem and see how complicated the analysis becomes. We start by extracting all of the elements from figure 2.8. This leaves the following list:

parties:
 A, B, T
Transforms:
 Te, Td
Keys:
 
 Ke, Kd
Forms:
 
 P,C

From this list, we can form all sets of interactions that can take place with every combination of A, B, and T knowing every possible combination of Te, Td, Ke, Kd, P, and C. This produces 2**9 possible situations, each of which must be individually analysed to determine what if any additional information can be gleaned by each party. Once this is completed, we must compare these situations to the desired set of possibilities to determine whether or not a proposed solution will work.

All of this ignores time effects, what happens if errors occur, the levels of exposure associated with particular events, how the system is to be managed to assure these properties, etc. This is only a simple case of two communicating parties and one tapper. Immagine the analysis in a situation with thousands of users, a global network, key management at and distribution to remote sites, and all of the other factors in a modern telecommunications system, and you begin to understand the problem with attaining optimal systems.

As a result of this difficulty, people have derived a set of methods that provide desirable properties. They combine these methods to provide combinations of these properties, and claim the parts are independent of each other to reduce the complexity of analysis. We will now discuss some of the methods that have been studied and what they provide in the way of desirable properties.