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.