[Next] [Up] [Previous] [Index]

Security Without Proof

This section expresses my own view of some matters which are of a highly controversial and contentious nature. Much of the debate, however, is not about whether or not the various things I advocate here are beneficial, but about the relative merits of different measures. This doesn't prevent the debate from being vigorous, as each point of view sees the measures it percieves as less beneficial, or beneficial only in theory, as very much less beneficial than those it emphasizes, and likely to lead to the neglect of those measures which it views as being of real benefit.

As noted in the previous section, the cipher system known as the one time pad, if employed correctly, makes reading your messages as difficult as guessing next week's winning lottery numbers.

The one-time pad system is not totally impractical. It requires a bit of advance effort before communications can begin. But even a floppy disk contains over a megabyte of data, which corresponds in size to the contents of an entire book. And the price of CD-R recorders has been coming down recently.

However, many people choose to employ other types of cipher systems to protect their correspondence, for reasons of convenience which are outlined below:

Another way of looking at this, and understanding why the difference between the one-time-pad and other conventional encryption is as fundamental as the distinction between public-key ciphers and conventional encryption is to examine the benefits provided by each form of encryption:

But each increase in convenience involves a cost in security.

The one-time pad comes with a mathematical proof of security, and no other cipher system has that. In fact, there is a good reason for believing that no other cipher system can have a mathematical proof of its security.

Proving whether or not an unsolved mathematical problem has a solution is like proving that a given Turing machine will halt or not without following its execution to a halt or to a simple infinite loop. There exist mathematical problems richer in complexity than any finite pre-set threshold, so such proofs are not possible.

If we intend to use a cipher system other than the one-time pad, how can we cope with the absence of a proof of security?

One way is to look for corroborating evidence of security, however incomplete it may be. For example:

Another way is to take as many precautions as one can in the use of any algorithm:

(I am particularly indebted to Terry Ritter for the third of these precautions, which I have stated here in considerably shortened and simplified form.)

Some of these precautions directly conflict with being able to obtain corroborating evidence of security. If you design your own algorithm and keep it secret, then unlike DES it won't have recieved the cryptanalytic attention of the noted researchers in the field.

But using multiple algorithms allows one to have the best of both worlds: one can use a well-respected algorithm and then also use an unknown algorithm.

In order to ensure, however, that multiple algorithms do indeed provide added strength, they have to be used properly. One algorithm can't be implemented in a way that adds redundancy to the text to be enciphered by the next algorithm. The keys used by the different algorithms have to be effectively independent, so that breaking a weak algorithm won't provide a clue to the key used by a stronger algorithm, enabling the stronger algorithm to be reversed without having to break it.

One way to make multiple keys effectively independent is to use a good one-way hash function applied to an input key to generate the key for each algorithm; the input key would be slightly modified each time it is to be hashed. However, unlike having truly independent keys, this does mean that the security of the hash function limits the security of the whole cipher system.

It is possible to use multiple public-key algorithms to each convey a piece of a session key. But one cannot cascade public-key algorithms to obtain a result of arbitrarily high complexity, the way one can with conventional symmetric-key algorithms.

[Next] [Up] [Previous] [Index]

Table of Contents
Home Page