Cryptographic abundance and pervasive computing



                        Andrew Odlyzko

                          AT&T Labs
                  Florham Park, NJ 07932, USA

                     amo@research.att.com
               http://www.research.att.com/~amo




Moore's Law and related "laws" describing the steady progress in a variety
of basic technologies are about to usher in a new era of pervasive
computing. We will be surrounded by devices with intelligence built into
them. They will require better security than we have been used to in the PC
era to prevent chaos and disasters. 

These same technological advances will also produce an era of cryptographic
abundance, where the cost of implementing security algorithms will seem to
be trivial. This will lead to a new and welcome freedom in security design,
which has, until now, been hampered by performance limitations. However, the
net gain is likely to seem disappointingly small. Why, then, this paradox,
where a wealth of technologies will seem to yield small fruits? 

The need for information security in civilian applications was realized in
the early 1970s. This led to a surge of unclassified research in
cryptography. The results have been negative in that no rigorous formal
proofs of security have been found for any practical cryptosystems. On the
other hand, they have been positive in that a sense of comfort about the
safety of some types of algorithms has been developed. . 

The time to crack the best symmetric cryptosystems  (where the sender and
recipient share a common key before the start of the session) is an
exponential function of the size of key. ("Exponential" is used here in the
precise mathematical sense of the term, not the colloquial usage denoting
anything that is hard.) This means that small increases in key size have
very large time consequences for the attacker. However, the hardware and
software complexities of implementing and running these algorithms increase
slowly for legitimate users. This means that key sizes and the complexities
of the algorithms do not have to increase much to protect against any
foreseeable advances in conventional hardware, which constitutes a
practical, if not a theoretical, limit to what is possible. (For the time
being, they even seem proof against quantum computers, potentially the most
disruptive technology on the crypto scene.) In particular, the current crop
of algorithms being considered for the next encryption standard all appear
adequate for the next century. This is in marked contrast to the current
standard, DES, which was widely criticized even when it was designed for
being insufficiently strong. The justification for the 56-bit key size in
DES was that anything larger would be too expensive to implement. 

Over the last three decades, we have labored under the constraint that
secure cryptosystems required too much computation to be performed easily.
These constraints are disappearing. Moore's Law is producing general purpose
processors that can handle the necessary crypto functions in a negligible
fraction of their capacity. Tiny special purpose chips can also be produced
inexpensively for fulfilling the crypto demands of special applications.
Thus we are about to be freed from the constraints of the past. (This is
even true for public key schemes. These algorithms, crucial for digital
signatures and key management, do not require the communicating parties to
possess a shared key that only they have.  The computational requirements 
of these methods are still considerably higher than for symmetric ones,
but progress in electronics is overcoming even this barrier.) 

Yet this new freedom is likely to make little difference in practice. Strong
cryptography is required for security. However, strong cryptography alone
does not guarantee security. Almost all security problems that keep
surfacing with monotonous regularity are caused by economic and social
factors, not defects in mathematical cryptography. There are no signs that
this situation is about to change. 

The economic constraint comes from the desire for novelty over usability and
security. Some of it can be blamed on the structure of the industry. It is
software developers that Microsoft caters to, not the final users, and the
developers care more about their convenience than that of users. Further,
the industry has a vested interest in keeping customers on the treadmill of
steady upgrades and bug fixes. Moreover, we have to recognize that users
bear much of the blame. They are the ones who clamor for the latest and
greatest. The computer industry can deliver reliable and user friendly
products, as game consoles show. However, those have limited functionality,
which is not acceptable for most cases. 

The main constraint on security, though, is sociological. People do not fit
easily into the formal structures that any security framework requires. A
key problem with strong information security in an office environment is
that it would stop secretaries from forging their bosses' signatures. A good
assistant exercises judgement and handles routine matters without increasing
the load on the boss. Now, in principle, equivalent functionality could be
built into a secure electronic environment, with electronic delegations,
etc. The prospect of actually doing it in a practicable form are nil. We
have never been able to formalize what jobs require. Indeed, one of the most
powerful weapons labor has in disputes with management is to "work to rule."

In summary, we will have an unprecedented proliferation of devices, the
famed information appliances. They will take advantage of abundant strong
cryptography. However, we are likely to continue operating with the
equivalents of chewing gum and bailing wire, continually running into
security and usability problems and patching them as best we can. The
nirvana of a clean secure environment is not on the horizon.