By William Hugh Murray
From: WHMurray@DOCKMASTER.NCSC.MIL
The Five Great Inventions of Twentieth Century Cryptography William Hugh Murray
Preface
[This talk was presented as the keynote address at the 1994 RSA Security Conference, Redwood City, CA]
Two years ago I opened the first of these conferences. Jim Bidzos invited me to "kick it off;" nothing so formal as a "keynote." While I wore this same suit, I just sort of got up here to shoot the breeze with a few of my friends and colleagues. No notes, just sort of "off-the-cuff." He did not even tell me how long I could talk. As far as I know there were no reporters present; nothing that I said got me in trouble. After the morning session was over, Jim hosted a lunch for some of the speakers and panelists. Whit Diffie sat beside me, with his notes, and began to quiz me on my sources and authorities for my comments. He even told me that some of my best stories were apocryphal (though he conceded me the points that I made with them). Well, I see the same friends, but there are far more colleagues. The program is more formal, Diffie still has his pad and pencil, the press is here, my remarks are styled as a "keynote," they are sufficiently arguable that I need to choose my words very carefully, and I have a fixed time to end. Prudence suggests that I use notes. Introduction Cryptography, the art of secret communication, is almost as old as writing. Indeed, it has been suggested that, at least for a while, writing itself was a relative secret. Certainly it was esoteric and its use was reserved to an initiated elite. Cryptography and recording and communicating technologies have played leap frog through the pages of history. It is my thesis that both have changed so radically during the nineteenth and twentieth centuries as to constitute a new era. On the recording and communicating side we have photography, telegraphy, telephony, radio, phonography, cinema, television, and telecommunications.hy, telephony, radio, cinema, television, and the computer. Collectively, and even individually, these technologies constitute a dramatic change in our ability to make a mark across time and space. We have seen a similar advance in our ability to conceal those records and messages from all but a chosen few. Modern cryptography has its origins between the two great wars of the twentieth century. .It was driven as much by the use of radio on the battlefield as by any other single influence, but there are an infinite number of important recording and communicating applications that simply cannot be done in clear text. While more sparingly used and less well known, the advances in cryptography have been no less dramatic than those in recording and communications. I propose to consider five inventions of the twentieth century that have defined modern cryptography and that set it apart from ancient or traditional cryptography. The impact of these technologies has been to simplify the use of codes, reduce their cost, and increase by orders of magnitude the cost to a cryptanalyst of recovering information protected by the codes. What constitutes an invention or sets it apart from other inventions is somewhat arbitrary. Some of the inventions that I propose to discuss could be considered as a group of other inventions; the members of the group might or might not be significant by themselves. I have limited myself to a discussion of inventions rather than accomplishments, and to cryptography rather than to cryptanalysis. Many of the accomplishments of the century have been in cryptanalysis and may have been greater than the inventions in cryptography. However, greatness is in the eye of the beholder. Certainly all the inventions have not been limited to cryptography. For example, if cryptanalysts did not invent the modern computer, they certainly gave it a major boost. They have lived to see the advantage that it provides shift, with its scale, from them to the cryptographer. Automated Encoding and Decoding Modern cryptography begins in 1917 with the invention by Gilbert S. Vernam, an employee of the American Telephone & Telegraph Company, of the Vernam System. Vernam used two paper tape readers, one for the message and the other for the key. He added the two (bit-wise and modulo 2) to produce the ciphertext. Moreover, he used the standard information technology of his day to automate the encoding and decoding of information. Modern cryptography is automatic. Translation from plaintext to ciphertext and back again is performed automatically, that is by a machine or automaton. While there may be a separate step, the conversion from one code to the other is done by a machine rather than by a person. Today that conversion can be done by almost any single user computer. With appropriate controls and for some applications it can be done in a multi-user computer. Before computers, this encoding was done in special purpose machines. The Enigma and Purple machines were both early and famous examples of such machines. The requirement to manually convert from natural language to secret codes has always been a limitation. It tended to limit both the amount of traffic encrypted and the complexity of the encoding schemes used. Therefore, encryption machines of any kind increase the complexity and effectiveness of the codes available. At one level, the modern computer can be viewed as a general purpose code conversion machine. That is, it converts information called input into a new representation called output. The relationship between the input and the output can be simple or complex, obvious or obscure, public or secret, and reversible or irreversible. If the conversion is complex, obscure, secret, and reversible, then the computer can be viewed as an encryption machine. But for want of a small amount of readily available software, all of the hundred million general purpose computers in the world are encryption engines of immense power. At some price in performance, the relationship between input and output can be arbitrarily complex and obscure and thus arbitrarily effective in concealing the meaning of the output. The cost of computer performance has been falling steadily and rapidly for fifty years. It has now become so cheap that most capacity is not used for the convenience of having it ready when it is wanted. The result is that the use of secret codes can be viewed as almost free. So cheap is automatic coding and encoding that some applications do it by default and globally, concealing it completely from the user. Since the difference in cost between public codes and secret codes is vanishing and can be paid in a currency, computer cycles, that might otherwise be wasted, secret codes can be used by default. Independent Long Key Variable The major weakness of Vernam's system was that it required so much key material. This was compensated for by Lyman Morehouse who used two key tapes of 1000 and 999 characters, about eight feet each in length, in combination to produce an effective key tape of 999,000 characters, effectively 8000 feet in length. Morehouse had used a long key. Modern cryptography is tailored to a particular use by a key variable, or simply a key. The key is a large integer that tailors the behavior of the standard algorithm and makes it generate a cipher that is specific to that number. The requirement for secrecy is limited to this number. The problem of protecting the data reduces to the simpler one of protecting the key. Access to the cleartext requires access to the combination of the ciphertext, the base mechanism, usually a computer and a program, and the key. Since the rest are readily available, the efficiency of any use depends upon the fact that it is more expensive or difficult to obtain the key than to obtain the protected data by other means. All other things being equal, the longer the key, the more secure the mechanism. Key length is a trade off against the complexity and the secrecy of the algorithm. The longer the key, the simpler and more obvious can be the mechanism or algorithm. If the key is as long as the message, statistically random in appearance, and used only once (one-time pad), then such a simple and obvious mechanism as modulo addition will still provide effective security. For practical reasons, short keys and more complex mechanisms are preferred. Complexity Based Cryptography (The Data Encryption Standard) In May 1973 the US National Bureau of Standards advertised in the Federal Register for a proposal for an encryption mechanism to be employed as a standard mechanism for all of the needs of the civilian sectors of the government. The ad stated that the successful proposal would be for a mechanism that would be secure for at least five years in spite of the fact that the mechanism would be public and published. The resulting Data Encryption Standard was proposed by the IBM Corporation. It was invented by a team led by Walter Tuchman and was based upon a concept originated by Horst Feistel of IBM's Yorktown Research Laboratory. This mechanism, which can be implemented on a chip and completely described in a few 8.5"X11'' pages, changed the nature of cryptography forever. The security of modern encryption mechanisms like the DES is rooted in their complexity rather than in their secrecy. While traditional encryption relied upon the secrecy of the mechanism to conceal the meaning of the message, these modern mechanisms employ standard and public algorithms. These mechanisms are standard in the sense that they are of known strength or have a known cost of attack. However, the trade-off is that their effectiveness can not, must not, depend upon their secrecy. Rather, it relies upon the complexity of the mechanism. The complexity of modern ciphers is such that they can be effective even though most of their mechanism is public. The most well known, trusted, and widely used of all modern ciphers is the Data Encryption Standard. Because of the intended breadth and duration of the use of this cipher, the sponsors specified that it should be assumed to be public. Its effectiveness should rely upon the secrecy only of the key (see the next section). It has been public for more than fifteen years, but its effectiveness is such that trying all possible keys with known plain and cipher text is still the cheapest practical attack. [The DES belongs to a class of ciphers known as Feistel ciphers. These ciphers are also known as block product ciphers. They are called block ciphers because they operate on a fixed length block of bits or characters. They are called product ciphers because they employ both substitution and transposition.] Automatic Key Management The same key must exist at both ends of the communication. Historically, keys were distributed by a separate channel or path than the one by which the encrypted traffic passed. The initial distribution and installation of the keys must be done in such a way as not to disclose them to the adversary. When this is done manually, it represents a significant opportunity for the compromise of the system. Because they were attempting to combine cryptography and computing in a novel manner, Tuchman and his team understood this problem very well. The products that they based upon the DES algorithm addressed it, in part, by automating the generation, distribution, installation, storage, control, and timely changing of the keys. Their elegant system is described in two papers published in the IBM Systems Journal Vol. 17(2) pp. 106-125 (1978) and covered by a number of fundamental patents based upon it. [While NSA had automated some key management operations, and while Rosenblum was awarded a patent for a "key distribution center," these were ad hoc. This work is the first that describes and implements a complete and integrated automatic system.] The impact of this concept on the effectiveness, efficiency, and ease of application of modern cryptography is immense. However, it may also the the least understood and appreciated. For example, much of the analysis of the strength of the DES is made in the context of the primitive DES. However, the DES rarely appears as a primitive. Instead it appears in implementations which use it in such a way as to compensate for its inherent limitations. For example, automatic generation of the keys avoids the use of weak or trivial keys. (the DES has four known weak keys and four semiweak keys.) Since automatic key management systems permit so many keys, they also reduce the exposure to "known plaintext" attacks. History suggests that codes are most often broken because the user fails to apply them with the necessary rigor and discipline, particularly when choosing, distributing, and installing keys. Automating of these steps provides much of the necessary discipline and rigor. Automatic key distribution and installation increases the effectiveness by protecting the keys from disclosure during distribution, and by making the system resistant to the insertion of keys known to attackers. When keys are installed manually they become known to the human agent who installs them. He is in a position to provide a copy of the key to others. To the extent that this agent is vulnerable to coercion or bribery, the system is weakened by this knowledge. Therefore, the system may be strengthened by automatic mechanisms which provide the agent with beneficial use of the key without granting him knowledge of it. For example, systems available from IBM and Motorola provide for the key to be distributed in smartcards and automatically installed in the target machine. The key can be encrypted in the smartcard or destroyed by the installation process. In either case, the agent can use it, but cannot copy it or give it to another. Just as the use of automata for encoding and decoding reduces the cost and inconvenience of using secret codes, the use of automata for key management reduces the cost and inconvenience of changing the keys frequently. By changing the key frequently, e.g., for each, file, session, message, or transaction, the value to an adversary of obtaining a key is reduced, and the effectiveness of the mechanism is improved. One way of looking at automated key management is that it increases the effective length of the key, or makes it approach the length of the data protected. Asymmetric Key Cryptography However, even though most of the key management can be automated, most such systems require some prearrangement. In any-to-any communications in a large open population, this requirement can quickly become overwhelming. For example, in a population of two hundred people, the number of key pairs and secret exchanges would be in the thousands with many opportunities for keys to be compromised. Moreover, with traditional keys, the initial distribution of keys must be done in such a way as to maintain their secrecy, practically impossible in a large population. These problems are addressed, in part, by public key, or asymmetric key, cryptography. This mechanism was proposed by Whitfield Diffee, Martin Hellman, and Ralph Merkle. It may be the single most innovative idea in modern cryptography. The best known and most widely used implementation is the RSA algorithm invented by Ronald Rivest, Adi Shamir, and Leonard Adelman. [In this mechanism the key has two parts, only one of which must be kept secret. The two parts have the special property that what is encrypted with one can only be decrypted with the other. One half of the key-pair, called the private key, is kept secret and is used only by its owner. The other half, called the public key, is published and is used by all parties that want to communicate with the private key owner. It can be published and does not need to be distributed secretly. Since the public key, by definition, is available to anyone, then anyone can send a message to the owner that only he can read.] With a minimum of pre-arrangement, this function provides the logical analog of an envelope that can only be opened by one person. The larger the communicating population, and the more hostile the environment, the greater is its advantage over symmetric key cryptography. This concealment from all but the intended recipient is the traditional use of cryptography. However, asymmetric key cryptography has another use. A message encrypted using the private key can be read by anyone with access to the public key, but it could only have been encrypted by the owner of the corresponding private key. This use is analogous to a digital signature. It provides confidence that the message originates where it appears to have originated. Since if even a bit of the message is changed it will not decrypt properly, this mechanism also provides confidence that the message has not been either maliciously or accidentally altered. In part, this is also true as between the two parties to a message that is sent using symmetric key cryptography. That is, the recipient of the message knows with a high degree of confidence that it originated with the other holder of the key; he knows it, but he cannot prove it to another. However, with asymmetric key cryptography, he can demonstrate it to a third party. If the owner of the key pair has acknowledged the public part of the key to the third party, then he cannot plausibly deny any message that can be decrypted with it. [The concept of the digital signature is such a novel concept as to easily qualify as an invention on its own. However, it is so closely bound in origin and literature to asymmetric key cryptography that I elect to simply treat them as one.] These two abstractions, the logical envelope and the logical signature, can be composed so as to synthesize any and all of the controls that we have ever been able to achieve by more traditional means. They can be used for payments, contracts, testaments, and high integrity journals and logs. They provide us with a higher degree of security in an electronic environment than we were ever able to achieve in a paper environment. They provide protection in an open environment that is nearly as high as that which we can achieve in an open one. The Impact of the Great Inventions The impact of these inventions is to provide us with secret codes that are cheap enough to be used by default, and arbitrarily strong. Given assumptions about the quantity of data to be protected, the length of time that it must remain secret, its value to an adversary, and the resources available to the adversary, it is possible to apply modern cryptography in such a way as to be as strong as required. While it is possible to state a problem in such a way as to defy such a solution, it is difficult to identify such a problem in the real world. That is, It is possible to specify so much data to be encrypted under a single key, of such high value and which must remain safe for such a long time that we cannot say with confidence that the mechanism can stand for that time and cost. For example, we cannot say with confidence how to encrypt several hundred gigabytes worth several trillion dollars and keep it safe for a millennium. On the other hand, we are not aware of any real problems that meet such a specification. Put another way, we can always ensure that the cost of obtaining the information by cryptanalysis is higher than the value of the data or the cost of obtaining it by alternative means. While any code can be broken at some cost, modern codes are economically unbreakable, at least in the sense that the cost of doing so can be made to exceed the value of doing it. A very small increase in the cost to the cryptographer can result in astronomical increases in the cost to a potential adversary. Perhaps just as important, these mechanisms are now sufficiently convenient to use, that, within bounds, they can be widely and easily applied. Given that the more data that is encrypted with a single mechanism, the greater the value in breaking it, the more compromising information is available to an adversary, and that the more a mechanism is used the greater the opportunity for a compromising error in its use, we should continue to apply cryptography only to data that can profit from its use. On the other we need never again be inhibited from using it by issues of cost or convenience. Cryptography and Government Policy It should be obvious to a qualified observer that, announcements here to the contrary not withstanding, we are losing the battle for security and privacy in the computerized and networked world. We could have secret codes imbedded in all software of interest for free. This assertion assumes only that all such software is produced by those represented here, who have already paid for licenses and absorbed much of the necessary development cost, and that the cost of a marginal cycle on the desktop approaches zero. That we do not, is the result of ambivalent government policy. While one agency of government has sponsored the use of standard cryptography, another has tried to undermine confidence in those standards. While one agency has asserted that public standards are essential, another has sponsored secret ones, and a third has used public funds to further such secret standards. While one agency has insisted that trusted codes are essential to world prosperity, another has imposed restrictions on their export and undermined confidence in those that are exported. While one agency recognizes that national security depends upon world prosperity, another believes that signals intelligence is more important. Those of you who have seen my comments in Risks, sci.crypt , and the Communications of the ACM, know my position. It is that the prime mover behind all of these initiatives is NSA, that their motive is the preservation of their jobs and power by protecting the efficiency of signals intelligence, that their strategy is to discourage by every means that they can get away with all private and most commercial use of cryptography. That they have infiltrated the departments of State and Commerce and the White House staff, and that they are using the Department of Justice. While they know that they cannot be fully successful, they also know that they do not have to be. Nor is this simply paranoia on my part. It is the only explanation that accounts for all of the government's actions. It also meets the tests proposed by Machiavelli, Willie Sutton and "Deep Throat." While most of the government confesses that cryptography is essential to personal privacy in the modern era, the administration is not prepared to admit that even the current sparse use is consistent with the government's responsibility to preserve public order. Let me stress that the problem is government policy, not public policy and not administration or congressional policy. This policy has been made in secret and has been resistant to public input. It is the policy of the bureaucracy and not of any individuals. I know most of the players in the development of this policy. I know none that are pursuing a personal agenda, like the results, or are proud of their roles in it. They are simply doing the best that they know how in the face of agency momentum, administration consent, and the absence of congressional guidance. However, the momentum behind these policies is such that the good intentions and professionalism of the individuals is not sufficient to resist it. While the administration has aligned itself with the initiatives, it is not their author. While the initiatives have sponsors within the administration, they were here before the administration and they expect to be here when it is gone. They believe that the policy is important and that the administration is not. While some committees of the congress have held hearings on the issues and even decried the arbitrary actions of the bureaucracy, their hearings always conclude with executive sessions with the NSA and no legislative initiatives to curb the excesses. Forgive me a closing political observation not intended to be partisan. This government is too large, over-zealous and under-effective. It is committed to nothing so much as its own survival. It may be too late to influence it, but if it is not influenced, not only will we not enjoy the fruits of modern cryptography, but we may not enjoy those of telecommunications, trade, our labors, or even those of freedom.
Bibliography
Ehrsam, W. F., Matyas, S. M., Meyer, C. H., and Tuchman, W. L., "A Cryptographic Key Management System for Implementing the Data Encryption Standard," IBM Systems Journal Vol. 17(2) pp. 106-125 (1978). Kahn, D., The Codebreakers, Macmillan Co., New York (1967). Matyas, S. M., Meyer, C. H., "Generation, Distribution, and Installation of Cryptographic Keys," IBM Systems Journal Vol. 17(2) pp. 126-137 (1978).
From: WHMurray@DOCKMASTER.NCSC.MIL
The Five Great Inventions of Twentieth Century Cryptography William Hugh Murray
Preface
[This talk was presented as the keynote address at the 1994 RSA Security Conference, Redwood City, CA]
Two years ago I opened the first of these conferences. Jim Bidzos invited me to "kick it off;" nothing so formal as a "keynote." While I wore this same suit, I just sort of got up here to shoot the breeze with a few of my friends and colleagues. No notes, just sort of "off-the-cuff." He did not even tell me how long I could talk. As far as I know there were no reporters present; nothing that I said got me in trouble. After the morning session was over, Jim hosted a lunch for some of the speakers and panelists. Whit Diffie sat beside me, with his notes, and began to quiz me on my sources and authorities for my comments. He even told me that some of my best stories were apocryphal (though he conceded me the points that I made with them). Well, I see the same friends, but there are far more colleagues. The program is more formal, Diffie still has his pad and pencil, the press is here, my remarks are styled as a "keynote," they are sufficiently arguable that I need to choose my words very carefully, and I have a fixed time to end. Prudence suggests that I use notes. Introduction Cryptography, the art of secret communication, is almost as old as writing. Indeed, it has been suggested that, at least for a while, writing itself was a relative secret. Certainly it was esoteric and its use was reserved to an initiated elite. Cryptography and recording and communicating technologies have played leap frog through the pages of history. It is my thesis that both have changed so radically during the nineteenth and twentieth centuries as to constitute a new era. On the recording and communicating side we have photography, telegraphy, telephony, radio, phonography, cinema, television, and telecommunications.hy, telephony, radio, cinema, television, and the computer. Collectively, and even individually, these technologies constitute a dramatic change in our ability to make a mark across time and space. We have seen a similar advance in our ability to conceal those records and messages from all but a chosen few. Modern cryptography has its origins between the two great wars of the twentieth century. .It was driven as much by the use of radio on the battlefield as by any other single influence, but there are an infinite number of important recording and communicating applications that simply cannot be done in clear text. While more sparingly used and less well known, the advances in cryptography have been no less dramatic than those in recording and communications. I propose to consider five inventions of the twentieth century that have defined modern cryptography and that set it apart from ancient or traditional cryptography. The impact of these technologies has been to simplify the use of codes, reduce their cost, and increase by orders of magnitude the cost to a cryptanalyst of recovering information protected by the codes. What constitutes an invention or sets it apart from other inventions is somewhat arbitrary. Some of the inventions that I propose to discuss could be considered as a group of other inventions; the members of the group might or might not be significant by themselves. I have limited myself to a discussion of inventions rather than accomplishments, and to cryptography rather than to cryptanalysis. Many of the accomplishments of the century have been in cryptanalysis and may have been greater than the inventions in cryptography. However, greatness is in the eye of the beholder. Certainly all the inventions have not been limited to cryptography. For example, if cryptanalysts did not invent the modern computer, they certainly gave it a major boost. They have lived to see the advantage that it provides shift, with its scale, from them to the cryptographer. Automated Encoding and Decoding Modern cryptography begins in 1917 with the invention by Gilbert S. Vernam, an employee of the American Telephone & Telegraph Company, of the Vernam System. Vernam used two paper tape readers, one for the message and the other for the key. He added the two (bit-wise and modulo 2) to produce the ciphertext. Moreover, he used the standard information technology of his day to automate the encoding and decoding of information. Modern cryptography is automatic. Translation from plaintext to ciphertext and back again is performed automatically, that is by a machine or automaton. While there may be a separate step, the conversion from one code to the other is done by a machine rather than by a person. Today that conversion can be done by almost any single user computer. With appropriate controls and for some applications it can be done in a multi-user computer. Before computers, this encoding was done in special purpose machines. The Enigma and Purple machines were both early and famous examples of such machines. The requirement to manually convert from natural language to secret codes has always been a limitation. It tended to limit both the amount of traffic encrypted and the complexity of the encoding schemes used. Therefore, encryption machines of any kind increase the complexity and effectiveness of the codes available. At one level, the modern computer can be viewed as a general purpose code conversion machine. That is, it converts information called input into a new representation called output. The relationship between the input and the output can be simple or complex, obvious or obscure, public or secret, and reversible or irreversible. If the conversion is complex, obscure, secret, and reversible, then the computer can be viewed as an encryption machine. But for want of a small amount of readily available software, all of the hundred million general purpose computers in the world are encryption engines of immense power. At some price in performance, the relationship between input and output can be arbitrarily complex and obscure and thus arbitrarily effective in concealing the meaning of the output. The cost of computer performance has been falling steadily and rapidly for fifty years. It has now become so cheap that most capacity is not used for the convenience of having it ready when it is wanted. The result is that the use of secret codes can be viewed as almost free. So cheap is automatic coding and encoding that some applications do it by default and globally, concealing it completely from the user. Since the difference in cost between public codes and secret codes is vanishing and can be paid in a currency, computer cycles, that might otherwise be wasted, secret codes can be used by default. Independent Long Key Variable The major weakness of Vernam's system was that it required so much key material. This was compensated for by Lyman Morehouse who used two key tapes of 1000 and 999 characters, about eight feet each in length, in combination to produce an effective key tape of 999,000 characters, effectively 8000 feet in length. Morehouse had used a long key. Modern cryptography is tailored to a particular use by a key variable, or simply a key. The key is a large integer that tailors the behavior of the standard algorithm and makes it generate a cipher that is specific to that number. The requirement for secrecy is limited to this number. The problem of protecting the data reduces to the simpler one of protecting the key. Access to the cleartext requires access to the combination of the ciphertext, the base mechanism, usually a computer and a program, and the key. Since the rest are readily available, the efficiency of any use depends upon the fact that it is more expensive or difficult to obtain the key than to obtain the protected data by other means. All other things being equal, the longer the key, the more secure the mechanism. Key length is a trade off against the complexity and the secrecy of the algorithm. The longer the key, the simpler and more obvious can be the mechanism or algorithm. If the key is as long as the message, statistically random in appearance, and used only once (one-time pad), then such a simple and obvious mechanism as modulo addition will still provide effective security. For practical reasons, short keys and more complex mechanisms are preferred. Complexity Based Cryptography (The Data Encryption Standard) In May 1973 the US National Bureau of Standards advertised in the Federal Register for a proposal for an encryption mechanism to be employed as a standard mechanism for all of the needs of the civilian sectors of the government. The ad stated that the successful proposal would be for a mechanism that would be secure for at least five years in spite of the fact that the mechanism would be public and published. The resulting Data Encryption Standard was proposed by the IBM Corporation. It was invented by a team led by Walter Tuchman and was based upon a concept originated by Horst Feistel of IBM's Yorktown Research Laboratory. This mechanism, which can be implemented on a chip and completely described in a few 8.5"X11'' pages, changed the nature of cryptography forever. The security of modern encryption mechanisms like the DES is rooted in their complexity rather than in their secrecy. While traditional encryption relied upon the secrecy of the mechanism to conceal the meaning of the message, these modern mechanisms employ standard and public algorithms. These mechanisms are standard in the sense that they are of known strength or have a known cost of attack. However, the trade-off is that their effectiveness can not, must not, depend upon their secrecy. Rather, it relies upon the complexity of the mechanism. The complexity of modern ciphers is such that they can be effective even though most of their mechanism is public. The most well known, trusted, and widely used of all modern ciphers is the Data Encryption Standard. Because of the intended breadth and duration of the use of this cipher, the sponsors specified that it should be assumed to be public. Its effectiveness should rely upon the secrecy only of the key (see the next section). It has been public for more than fifteen years, but its effectiveness is such that trying all possible keys with known plain and cipher text is still the cheapest practical attack. [The DES belongs to a class of ciphers known as Feistel ciphers. These ciphers are also known as block product ciphers. They are called block ciphers because they operate on a fixed length block of bits or characters. They are called product ciphers because they employ both substitution and transposition.] Automatic Key Management The same key must exist at both ends of the communication. Historically, keys were distributed by a separate channel or path than the one by which the encrypted traffic passed. The initial distribution and installation of the keys must be done in such a way as not to disclose them to the adversary. When this is done manually, it represents a significant opportunity for the compromise of the system. Because they were attempting to combine cryptography and computing in a novel manner, Tuchman and his team understood this problem very well. The products that they based upon the DES algorithm addressed it, in part, by automating the generation, distribution, installation, storage, control, and timely changing of the keys. Their elegant system is described in two papers published in the IBM Systems Journal Vol. 17(2) pp. 106-125 (1978) and covered by a number of fundamental patents based upon it. [While NSA had automated some key management operations, and while Rosenblum was awarded a patent for a "key distribution center," these were ad hoc. This work is the first that describes and implements a complete and integrated automatic system.] The impact of this concept on the effectiveness, efficiency, and ease of application of modern cryptography is immense. However, it may also the the least understood and appreciated. For example, much of the analysis of the strength of the DES is made in the context of the primitive DES. However, the DES rarely appears as a primitive. Instead it appears in implementations which use it in such a way as to compensate for its inherent limitations. For example, automatic generation of the keys avoids the use of weak or trivial keys. (the DES has four known weak keys and four semiweak keys.) Since automatic key management systems permit so many keys, they also reduce the exposure to "known plaintext" attacks. History suggests that codes are most often broken because the user fails to apply them with the necessary rigor and discipline, particularly when choosing, distributing, and installing keys. Automating of these steps provides much of the necessary discipline and rigor. Automatic key distribution and installation increases the effectiveness by protecting the keys from disclosure during distribution, and by making the system resistant to the insertion of keys known to attackers. When keys are installed manually they become known to the human agent who installs them. He is in a position to provide a copy of the key to others. To the extent that this agent is vulnerable to coercion or bribery, the system is weakened by this knowledge. Therefore, the system may be strengthened by automatic mechanisms which provide the agent with beneficial use of the key without granting him knowledge of it. For example, systems available from IBM and Motorola provide for the key to be distributed in smartcards and automatically installed in the target machine. The key can be encrypted in the smartcard or destroyed by the installation process. In either case, the agent can use it, but cannot copy it or give it to another. Just as the use of automata for encoding and decoding reduces the cost and inconvenience of using secret codes, the use of automata for key management reduces the cost and inconvenience of changing the keys frequently. By changing the key frequently, e.g., for each, file, session, message, or transaction, the value to an adversary of obtaining a key is reduced, and the effectiveness of the mechanism is improved. One way of looking at automated key management is that it increases the effective length of the key, or makes it approach the length of the data protected. Asymmetric Key Cryptography However, even though most of the key management can be automated, most such systems require some prearrangement. In any-to-any communications in a large open population, this requirement can quickly become overwhelming. For example, in a population of two hundred people, the number of key pairs and secret exchanges would be in the thousands with many opportunities for keys to be compromised. Moreover, with traditional keys, the initial distribution of keys must be done in such a way as to maintain their secrecy, practically impossible in a large population. These problems are addressed, in part, by public key, or asymmetric key, cryptography. This mechanism was proposed by Whitfield Diffee, Martin Hellman, and Ralph Merkle. It may be the single most innovative idea in modern cryptography. The best known and most widely used implementation is the RSA algorithm invented by Ronald Rivest, Adi Shamir, and Leonard Adelman. [In this mechanism the key has two parts, only one of which must be kept secret. The two parts have the special property that what is encrypted with one can only be decrypted with the other. One half of the key-pair, called the private key, is kept secret and is used only by its owner. The other half, called the public key, is published and is used by all parties that want to communicate with the private key owner. It can be published and does not need to be distributed secretly. Since the public key, by definition, is available to anyone, then anyone can send a message to the owner that only he can read.] With a minimum of pre-arrangement, this function provides the logical analog of an envelope that can only be opened by one person. The larger the communicating population, and the more hostile the environment, the greater is its advantage over symmetric key cryptography. This concealment from all but the intended recipient is the traditional use of cryptography. However, asymmetric key cryptography has another use. A message encrypted using the private key can be read by anyone with access to the public key, but it could only have been encrypted by the owner of the corresponding private key. This use is analogous to a digital signature. It provides confidence that the message originates where it appears to have originated. Since if even a bit of the message is changed it will not decrypt properly, this mechanism also provides confidence that the message has not been either maliciously or accidentally altered. In part, this is also true as between the two parties to a message that is sent using symmetric key cryptography. That is, the recipient of the message knows with a high degree of confidence that it originated with the other holder of the key; he knows it, but he cannot prove it to another. However, with asymmetric key cryptography, he can demonstrate it to a third party. If the owner of the key pair has acknowledged the public part of the key to the third party, then he cannot plausibly deny any message that can be decrypted with it. [The concept of the digital signature is such a novel concept as to easily qualify as an invention on its own. However, it is so closely bound in origin and literature to asymmetric key cryptography that I elect to simply treat them as one.] These two abstractions, the logical envelope and the logical signature, can be composed so as to synthesize any and all of the controls that we have ever been able to achieve by more traditional means. They can be used for payments, contracts, testaments, and high integrity journals and logs. They provide us with a higher degree of security in an electronic environment than we were ever able to achieve in a paper environment. They provide protection in an open environment that is nearly as high as that which we can achieve in an open one. The Impact of the Great Inventions The impact of these inventions is to provide us with secret codes that are cheap enough to be used by default, and arbitrarily strong. Given assumptions about the quantity of data to be protected, the length of time that it must remain secret, its value to an adversary, and the resources available to the adversary, it is possible to apply modern cryptography in such a way as to be as strong as required. While it is possible to state a problem in such a way as to defy such a solution, it is difficult to identify such a problem in the real world. That is, It is possible to specify so much data to be encrypted under a single key, of such high value and which must remain safe for such a long time that we cannot say with confidence that the mechanism can stand for that time and cost. For example, we cannot say with confidence how to encrypt several hundred gigabytes worth several trillion dollars and keep it safe for a millennium. On the other hand, we are not aware of any real problems that meet such a specification. Put another way, we can always ensure that the cost of obtaining the information by cryptanalysis is higher than the value of the data or the cost of obtaining it by alternative means. While any code can be broken at some cost, modern codes are economically unbreakable, at least in the sense that the cost of doing so can be made to exceed the value of doing it. A very small increase in the cost to the cryptographer can result in astronomical increases in the cost to a potential adversary. Perhaps just as important, these mechanisms are now sufficiently convenient to use, that, within bounds, they can be widely and easily applied. Given that the more data that is encrypted with a single mechanism, the greater the value in breaking it, the more compromising information is available to an adversary, and that the more a mechanism is used the greater the opportunity for a compromising error in its use, we should continue to apply cryptography only to data that can profit from its use. On the other we need never again be inhibited from using it by issues of cost or convenience. Cryptography and Government Policy It should be obvious to a qualified observer that, announcements here to the contrary not withstanding, we are losing the battle for security and privacy in the computerized and networked world. We could have secret codes imbedded in all software of interest for free. This assertion assumes only that all such software is produced by those represented here, who have already paid for licenses and absorbed much of the necessary development cost, and that the cost of a marginal cycle on the desktop approaches zero. That we do not, is the result of ambivalent government policy. While one agency of government has sponsored the use of standard cryptography, another has tried to undermine confidence in those standards. While one agency has asserted that public standards are essential, another has sponsored secret ones, and a third has used public funds to further such secret standards. While one agency has insisted that trusted codes are essential to world prosperity, another has imposed restrictions on their export and undermined confidence in those that are exported. While one agency recognizes that national security depends upon world prosperity, another believes that signals intelligence is more important. Those of you who have seen my comments in Risks, sci.crypt , and the Communications of the ACM, know my position. It is that the prime mover behind all of these initiatives is NSA, that their motive is the preservation of their jobs and power by protecting the efficiency of signals intelligence, that their strategy is to discourage by every means that they can get away with all private and most commercial use of cryptography. That they have infiltrated the departments of State and Commerce and the White House staff, and that they are using the Department of Justice. While they know that they cannot be fully successful, they also know that they do not have to be. Nor is this simply paranoia on my part. It is the only explanation that accounts for all of the government's actions. It also meets the tests proposed by Machiavelli, Willie Sutton and "Deep Throat." While most of the government confesses that cryptography is essential to personal privacy in the modern era, the administration is not prepared to admit that even the current sparse use is consistent with the government's responsibility to preserve public order. Let me stress that the problem is government policy, not public policy and not administration or congressional policy. This policy has been made in secret and has been resistant to public input. It is the policy of the bureaucracy and not of any individuals. I know most of the players in the development of this policy. I know none that are pursuing a personal agenda, like the results, or are proud of their roles in it. They are simply doing the best that they know how in the face of agency momentum, administration consent, and the absence of congressional guidance. However, the momentum behind these policies is such that the good intentions and professionalism of the individuals is not sufficient to resist it. While the administration has aligned itself with the initiatives, it is not their author. While the initiatives have sponsors within the administration, they were here before the administration and they expect to be here when it is gone. They believe that the policy is important and that the administration is not. While some committees of the congress have held hearings on the issues and even decried the arbitrary actions of the bureaucracy, their hearings always conclude with executive sessions with the NSA and no legislative initiatives to curb the excesses. Forgive me a closing political observation not intended to be partisan. This government is too large, over-zealous and under-effective. It is committed to nothing so much as its own survival. It may be too late to influence it, but if it is not influenced, not only will we not enjoy the fruits of modern cryptography, but we may not enjoy those of telecommunications, trade, our labors, or even those of freedom.
Bibliography
Ehrsam, W. F., Matyas, S. M., Meyer, C. H., and Tuchman, W. L., "A Cryptographic Key Management System for Implementing the Data Encryption Standard," IBM Systems Journal Vol. 17(2) pp. 106-125 (1978). Kahn, D., The Codebreakers, Macmillan Co., New York (1967). Matyas, S. M., Meyer, C. H., "Generation, Distribution, and Installation of Cryptographic Keys," IBM Systems Journal Vol. 17(2) pp. 126-137 (1978).
Comments
Post a Comment