THE CODEBREAKERS
Page 34
What makes Kerckhoffs’ book great, however, is that he sought answers to the problems thrust upon cryptology by new conditions, and that the solutions he proposed were valid, well-grounded, and meritorious. The major problem was to find a system of cryptography that would fulfill the requirements of the new signal communications created by the telegraph—a problem that still commands the interest of cryptologists. While other authors simply discussed various cipher systems rather as if the science of cryptology existed in a vacuum, Kerckhoffs addressed himself directly to the issue of the day. Indeed, it inspired his book: “I have therefore thought that it would be rendering a service to the persons who are interested in the future of military cryptography … to indicate to them the principles which must guide them in the contrivance or evaluation of every cipher intended for war service.” The principles which he enunciated guide cryptologists even now.
Kerckhoffs took field ciphers as a given; far from realizing that they were creatures of the telegraph, he thought that they had existed in the 1600s. But this historical error did not affect his understanding of current conditions. In considering the problem of finding a good field cipher, he saw that any one that was practical would have to withstand the operational strains of heavy traffic. “It is necessary to distinguish carefully between a system of encipherment envisioned for a momentary exchange of letters between several isolated people and a method of cryptography intended to govern the correspondence between different army chiefs for an unlimited time,” he wrote. In that one sentence, Kerckhoffs differentiates pre-telegraphy military communications from post-. The sentence is pregnant with most of the requirements that have come to be demanded of systems of military cryptography, requirements such as simplicity, reliability, rapidity, and so on. This clear recognition of the new order constitutes Kerckhoffs’ first great contribution to cryptology.
The second was to reaffirm in a modern context the principle that only cryptanalysts can know the security of a cipher system. Others had, of course, realized this before him: Rossignol invented the two-part nomenclator upon that principle, and the English Decypherers assessed and then compiled England’s nomenclators in the 1700s. But it was forgotten after the black chambers were closed, and in any case the simple criteria for appraising the cryptanalytic resistance of a nomenclator no longer applied to the more complex cipher systems then being proposed. The inventors of these systems, instead of submitting their ciphers to the empirical verdict of cryptanalysts, sought instead to evaluate them a priori. They would calculate how many centuries it would take to run through all the combinations necessary to solve their cipher, or would argue how it was logically impossible to break through a certain interlocking feature. Kerckhoffs observed and diagnosed the phenomenon:
… I am stupefied to see our scholars and our professors teach and recommend for wartime use systems of which the most inexperienced cryptanalyst would certainly find the key in less than an hour’s time.
One can hardly explain this excess of confidence in certain ciphers except by the abandon into which the suppression of black chambers and the security of postal communications have let cryptographic studies fall; it may likewise be believed that the immoderate assertions of certain authors, no less than the complete absence of any serious work on the art of solving secret writing, have largely contributed to give currency to the most erroneous ideas about the value of our systems of cryptography.
Reacting against this, Kerckhoffs demonstrated that cryptanalysis was the only way to enlightenment in cryptography, that only by climbing the steep and thorny path of cryptanalysis could one arrive at the truth about a system of cryptography. Only solution could validly test the security of a cipher. Kerckhoffs never quite stated this in so many words, though he came close. But his whole book cries it out. La Cryptographie militaire is essentially a tract on cryptanalysis; its whole bias and emphasis is cryptanalytic. Kerckhoffs established ordeal by cryptanalysis as the only sure trial for military cryptography. It is the form of judgment which is still used.
From these two fundamental principles for selecting usable field ciphers, Kerckhoffs deduced six specific requirements: (1) the system should be, if not theoretically unbreakable, unbreakable in practice; (2) compromise of the system should not inconvenience the correspondents; (3) the key should be rememberable without notes and should be easily changeable; (4) the cryptograms should be transmissible by telegraph; (5) the apparatus or documents should be portable and operable by a single person; (6) the system should be easy, neither requiring knowledge of a long list of rules nor involving mental strain.
These requirements still comprise the ideal which military ciphers aim at. They have been rephrased, and qualities that lie implicit have been made explicit. But any modern cryptographer would be very happy if any cipher fulfilled all six.
Of course, it has never been possible to do that. There appears to be a certain incompatibility among them that makes it impossible to institute all of them at once. The requirement that is usually sacrificed is the first. Kerckhoffs argued strongly against the notion of a field cipher that would simply resist solution long enough for the orders it transmitted to be carried out. This was not enough, he said, declaring that “the secret matter in communications sent over a distance very often retains its importance beyond the day on which it was transmitted.” He was on the side of the angels, but a practical field cipher that is unbreakable was not possible in his day, nor is it today, and so military cryptography has settled for field ciphers that delay but do not defeat cryptanalysis.
Perhaps the most startling requirement, at first glance, was the second. Kerckhoffs explained that by “system” he meant “the material part of the system; tableaux, code books, or whatever mechanical apparatus may be necessary,” and not “the key proper.” Kerckhoffs here makes for the first time the distinction, now basic to cryptology, between the general system and the specific key. Why must the general system “not require secrecy,” as, for example, a codebook requires it? Why must it be “a process that … our neighbors can even copy and adopt”? Because, Kerckhoffs said, “it is not necessary to conjure up imaginary phantoms and to suspect the incorruptibility of employees or subalterns to understand that, if a system requiring secrecy were in the hands of too large a number of individuals, it could be compromised at each engagement in which one or another of them took part.” This has proved to be true, and Kerckhoffs’ second requirement has become widely accepted under a form that is sometimes called the fundamental assumption of military cryptography: that the enemy knows the general system. But he must still be unable to solve messages in it without knowing the specific key. In its modern formulation, the Kerckhoffs doctrine states that secrecy must reside solely in the keys.
Had Kerckhoffs merely published his perceptions of the problems facing post-telegraph cryptography and his prescriptions for resolving them, he would have assured a place for himself in the pantheon of cryptology. But he did more. He contributed two techniques of cryptanalysis that, while not as wrenching to the science as Kasiski’s, play roles of supreme importance in most modern solutions.
The first of these is superimposition. It constitutes the most general solution for polyalphabetic substitution systems. With few exceptions, it lays no restrictions on the type or length of keys, as does the Kasiski method, nor on the alphabets, which may be interrelated or entirely independent. It wants only several messages in the same key. The cryptanalyst must align these one above the other so that letters enciphered with the same keyletter will fall into a single column. In the simplest case, that of a running key that starts over again with each message, he can do this simply by placing all the first letters in the first column, all the second letters in the next column, and so on.
Kerckhoffs demonstrated this procedure with 13 short messages enciphered with a long key. He superimposed his first five cryptograms like this:
Now, since all these messages were enciphered with the same keytext, all the hidden plaint
ext letters in the first column were enciphered by the same keyletter, which means that they have been enciphered in the same ciphertext alphabet. Consequently, all the plaintext a’s will have the same ciphertext equivalent, all the plaintext b’s will likewise have their own unvarying ciphertext equivalent, and so on. Likewise, each ciphertext letter represents only one plaintext letter. This holds true for each column. Each column may thus be attacked as an ordinary monalphabetic substitution, just like the columns in a periodic polyalphabetic.
In cases where the key does not start over again with each message, the cryptanalyst may line up repetitions in several messages to obtain a proper superimposition.
Superimposition does not ask that the alphabet in the first column bear any relation to that in the second. Thus it suits cryptanalysts of such systems as that of C. H. C. Krohn, who published in Berlin in 1873 a dictionary of 3,200 alphabets for secret correspondence; Kerckhoffs remarked scornfully of this number that “it is at once too many and too few.” But superimposition does depend for its success on a sufficient depth of column. Kerckhoffs realized this, and used examples to show that if two columns could be found to have been enciphered with the same keyletter, their effective depth was doubled. This is of especially great value with coherent running keys, whose cipher alphabets will be brought into play with the irregular frequency that their keyletters have in plaintext. If all the columns enciphered with the cipher alphabet governed by keyletter E can be recognized, collected, and solved together, about 12 per cent of the plaintext (in an English running key) will be recovered. Identically enciphered columns could be recognized, Kerckhoffs suggested, by finding columns with similar frequency counts.
Kerckhoffs also discerned another way to extort more plaintext from a paucity of ciphertext. Unlike most techniques of cryptanalysis, which ascertain plaintext, this technique determines ciphertext letters—which are, to be sure, immediately converted into plaintext. It may therefore be considered an indirect technique, but it is one of the most powerful in the cryptanalyst’s arsenal. Kerckhoffs called it “symmetry of position.”
How it works may be seen by looking at part of a tableau with mixed alphabets:
Now, it is evident that N and E stand next to one another in every cipher alphabet of this tableau (considering the alphabets as cyclical). Similarly, N is separated from Y by an interval of 3 in every cipher alphabet. Again, R stands 6 spaces, or cells, before B in every cipher alphabet. Relations like these may be fixed between any two (or more) ciphertext letters, and they will hold for every cipher alphabet in the tableau. So if the cryptanalyst determines the linear distance between two ciphertext letters in one alphabet, and then determines one of those letters in another alphabet, he can place the second letter in the second alphabet at the known distance. This contributes a ciphertext equivalent which he did not have before and which he can decipher throughout the cryptogram to add a few grains of plaintext to further his solution.
For example, suppose that the cryptanalyst has ascertained, in solving a message based on the above tableau, that K and H represent plaintext e and n. Consequently, K and H will stand 9 places apart in the ciphertext alphabet:
Then suppose that, in another alphabet, he has discovered that ciphertext K represents plaintext i. He may immediately count 9 spaces beyond K, thus:
and insert a ciphertext H at that point. He may now decipher all the ciphertext H’s in alphabet II into plaintext r’s. If he finds that, say, plaintext e is enciphered in this alphabet by W, he will measure the distance between K and W (four spaces forward), and will insert a W four spaces before K in the first cipher-text alphabet, giving him the identity of plaintext b in that alphabet. Since the intervals between the letters remain fixed for all the cipher alphabets of this tableau, the proper identification of a few letters in a few alphabets can lead to the determination of many others.
Kerckhoffs went no further than this—a patent symmetry of position. Cryptanalysts see it when they build up skeleton tableaux in solving polyalphabetics with a normal a-to-z plaintext alphabet. But modern cryptologists have discovered that skeleton tableaux for polyalphabetics with mixed plaintext alphabets will manifest a latent symmetry of position. It enlarges the principle of linear distances to include horizontal and vertical proportions. It is a complicated technique, but an enormously valuable one. Sometimes a chain reaction of placements will reconstitute an entire tableau. More often, it will donate important ciphertext equivalents to the cryptanalyst, or will notify him that a certain assumption contradicts its rules and hence is untenable. Because of today’s extensive use of polyalphabetics with both alphabets mixed, latent symmetry of position is an indispensable tool of the modern cryptanalyst.
Finally, Kerckhoffs rounded out his work by popularizing and naming the cryptographic slide, and demonstrating its identity with the polyalphabetic tableau. He called the slide the St.-Cyr system, after the French national military academy where it was taught. A St.-Cyr slide consists of a long piece of paper or cardboard, called the stator, with an evenly spaced alphabet printed on it and with two slits cut below and to the sides of the alphabet. Through these slits runs a long strip of paper—the slide proper—on which an alphabet is printed twice.
If both alphabets are normal, the device comprises a shorthand version of the Vigenère tableau, for any given alphabet of that tableau may be reproduced by finding its keyletter in the slide alphabet and setting this under the A of the stator. The stator alphabet will represent the plaintext alphabet and the slide alphabet the cipher alphabet. The alphabets do not have to be normal; if they are mixed, the slide (a term that sometimes encompasses the entire device) will represent a tableau with mixed alphabets. Any slide may be expanded into a tableau, and any tableau that is derived from the regular interaction of two alphabets, or components, may be compressed into the more convenient St.-Cyr form. Kerckhoffs also pointed out that a cipher disk was merely a St.-Cyr slide turned round to bite its tail, and he iterated Porta’s observation that a cipher disk could be developed into an equivalent tableau. He thus joined the tableau, the cipher disk, and the St.-Cyr slide into a family of related devices that differed only in form.
Such are the many excellences of La Cryptographie militaire. It stands perhaps first among the great books of cryptology. Its incisiveness, its clarity, its solid base of scholarly research, its invaluable new techniques, but above all its maturity, its wisdom, and its vision, elevate it to that rank. Perhaps it could only have been done by a man as well-rounded and as sensitive as Kerckhoffs.
It is ironic that the most lasting work of a man whose ideals were as cosmopolitan as Kerckhoffs’ should have had nationalistic results. Yet perhaps the most immediate consequence of La Cryptographie militaire was its giving France a commanding lead in cryptology, accruing benefits that were cashed during World War I. The Ministry of War bought 300 copies. Signal officers and amateur cryptographers read it, and, in reaction, invented or reinvented systems such as the autokey to circumvent the powerful superimposition technique. A whole literature poured off the presses. France flowered in a cryptologic renaissance.
Yet the French interest in cryptology was not due purely to the intellectual challenge of the subject. Much of the impetus must have come from the smart of France’s 1870 defeat by Prussia and her desire for revenge—the same desire that drove her to build up the largest army in Europe. It is significant that while almost two dozen books and pamphlets on cryptology were published in France between 1883 and 1914, to say nothing of scores of articles, only half a dozen appeared in Germany, all third-rate except for a few superb historical studies.
Probably several factors led to this indifference. The 1870 victory may have convinced the Germans that they were doing things right and did not need to change. Germans tend to be regimented and less apt to suggest new ideas to the authorities than the more individualistic French. And Germans seem to have a predilection for working things out in advance according to theory, for erecting elaborate stru
ctures based on pure reason. They sought, by the clarity of their logic and the unshakability of their assumptions, to do in cryptography what they did in philosophy—produce the ideal system. Kerckhoffs had shown that this approach is sterile, if not actually dangerous. But the Germans persisted, confident of the superiority of anything Teutonic. Their writers occupied themselves with cryptography to the virtual neglect of cryptanalysis. The French, more pragmatic, submitted their ciphers to the harsh judgment of actual solution.
The course of French prewar cryptology may be traced in its literature. Most of the books were second-rate, unoriginal, deriving their ideas from Kerckhoffs, whom they repeatedly laud. Typical is H. Josse, a captain of artillery who is chiefly noted for condensing Kerckhoffs’ six desiderata into a single guiderule that apparently governed the selection of French field ciphers up to World War I: “Military cryptography, properly called, must employ a system requiring only pencil and paper.” Josse quoted Kerckhoffs so often that he felt it necessary to insert an apologetic “M. Kerckhoffs, whose name recurs so often in cryptography” after an especially heavy flurry of references. But four fine writers helped make French cryptology the best in the world at the time: de Viaris, Valério, Delastelle, and Bazeries.
The Marquis Gaëtan Henri Léon Viarizio di Lesegno, whose name was gallicized to de Viaris, was born February 13, 1847, at Cherbourg. His father was an artillery captain. At 19, young de Viaris entered the famed École Polytechnique as 48th—and graduated as 102nd (out of 134). He enlisted in the Navy at 21, earning his commission as ensign two years later, but serving for only four years before resigning at 25. He later became an assistant police prefect and an infantry officer.