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

The Ideal Cipher

In 1883, the most famous work by Auguste Kerckhoffs, after whom the cryptanalytic technique of superimposing multiple messages enciphered with the same running key is named, was published: La Cryptographie Militare (Military Cryptography). This book set forth six desiderata for systems of encryption.

  1. A cipher should be unbreakable. If it cannot be theoretically proven to be unbreakable, it should at least be unbreakable in practice.
  2. If the method of encipherment becomes known to one's adversary, this should not prevent one from continuing to use the cipher.
  3. It should be possible to memorize the key without having to write it down, and it should be easy to change to a different key.
  4. Messages, after being enciphered, should be in a form that can be sent by telegraph.
  5. If a cipher machine or code book or the like is involved, any such items required should be portable, and usable by one person without assistance.
  6. Enciphering or deciphering messages in the system should not cause mental strain, and should not require following a long and complicated procedure.

These six desiderata, as they are phrased, are directly applicable to pencil-and-paper ciphers. Some of the concerns they raise do not seem as important today, when the ubiquitous personal computer stands ready to assist the cryptographer.

It may be noted that I have rather heavily paraphrased Kerckhoffs in my listing of his six dicta above. The second dictum originally stated that "compromise of the system should not inconvenience the participants". While my paraphrase makes explicit the usual way in which this dictum is understood, there is at least one other way in which the users of a cryptosystem could be inconvenienced by compromise of the algorithm used.

During the Second World War, the highly-secure American cipher machine SIGABA was handled with extreme physical security. One of the reasons for this was that it was so secure that if an enemy had discovered how it worked, although that probably would not allow that adversary to begin cryptanalyzing messages encrypted on the SIGABA, it would enable the adversary to copy the principle, and thus deprive the Allies of the intelligence they had been able to obtain from solving even the highest-level German and Japanese cipher systems.

Hence, satisfying the first dictum too well caused it to fail the second dictum in a less usual manner.

In any case, as amended for the computer era, Kerckhoff's desiderata might look like this:

  1. That a cipher should be unbreakable, in practice if not in theory, needs no modification as a statement of what is desired. However, only the one-time-pad, or a cipher essentially equivalent to the one-time-pad, is known to be secure in theory at present, and there are good reasons to believe that such ciphers will remain the only ciphers that can be proven to be unbreakable. There are a number of other ciphers can be proven to be as hard to break as certain classes of difficult problems in mathematics are to solve. But what can't be proven at present (and what may possibly even remain forever unprovable) is that those "difficult problems", such as factoring the product of two large primes, will indefinitely continue to require enough time to inconvenience the cryptanalyst as new discoveries are made in mathematics.
  2. That the security of a cipher system should depend on the key and not the algorithm has become a truism in the computer era, and this one is the best-remembered of Kerckhoff's dicta. The original reason for this requirement, however, is not due to some magical distinction between "key" and "algorithm". Rather, it follows from the later conditions imposed on the key: it must be short, and easy to abandon for a new key. A cryptographic algorithm can meet neither of those conditions. Hence, it should not be part of the key, because then the key would be bulky and hard to change. However, there is also a fundamental distinction between key and algorithm which, even if Kerchoff considered it when he wrote this desideratum, was not likely to have been one of the major considerations behind it, although it relates to the first desideratum, and which is generally used today as the main rationale for this requirement. Unlike a key, an algorithm can be studied and analyzed by experts to determine if it is likely to be secure. An algorithm that you have invented yourself and kept secret has not had the opportunity for such review.
  3. With today's computer technology, that allows a cipher with a key 56 bits in length, as used with DES, to be easily broken by brute force (by merely trying every possible key) it would appear that a dictum advocating that keys should be short is entirely obsolete. But if we rephrase the requirement to indicate the reasons behind it, we find that the concern is still valid. The secret key, on which the security of one's messages depends, should not be of a size (or form) that prevents it from being handled, stored, and exchanged in ways that effectively protect it from compromise. And it may also be noted that public-key cryptography, which allows the two participants to avoid having to exchange their private keys, and which allows them to use a fresh session key for each message, contributes to the ease of meeting this requirement. And on the other hand, the one-time-pad may require the exchange of keys at an inconvenient time, once the available key is exhausted.
  4. Enciphered messages should be in a form suitable to transmission by means of whatever communications medium is intended to be used, or convenient to use. This may mean the Internet or a fiber-optic link instead of the telegraph, but the principle remains sound.
  5. In order for a cipher to satisfy the first rule, it seems impossible to avoid having to use a piece of apparatus for encipherment, the digital computer. Computers certainly do exist that are portable and which are easily used by one person today. As apparatus can also cause problems by arousing suspicion, it would be an advantage in this area if one's cipher could be carried out with the aid of a computer program in BASIC that one could type in from memory.
  6. Again, it seems that for a cipher to remain unbreakable by today's standards, the algorithm used would have to be intricate and complicated. However, it is also true that we now have computers to do all the hard work. One of the reasons that a cipher should not be too complicated is to avoid problems caused by error in the encipherment of messages. Hence, this dictum could be considered to recommend that ciphers with unfavorable error-propagation characteristics should be avoided, since transmission errors can also make it necessary to retransmit a message. And this relates more directly to the cipher itself than to simply note that any encryption program, like any other computer program, should have a good user interface.

Thus, I claim that all six of Kerckhoffs' desiderata, not just those whose relevance is most often acknowledged at the present time, still retain at least some degree of importance, when correctly understood. But it is true that the ones regarded as obsolete have retained less of their importance as stated, although the reasons behind them remain valid in a different form.

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

Table of Contents
Home Page