I decided to post this in spite of an excess on IP of crypto postings over the past few days (additi

[David Farber <>]

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).