Chapter 4: Cryptographic Techniques

In this chapter, we introduce and briefly overview some cryptographic techniques that are used in the rest of the book. More specifically , we introduce the topic in Section 4.1; address cryptographic hash functions, secret key cryptography, and public key cryptography in Sections 4.2, 4.3, and 4.4, respectively; address digital envelopes in Section 4.5; and elaborate on some techniques to protect private keys and generate pseudorandom bit sequences in Sections 4.6 and 4.7. Finally, we discuss some legal issues that surround the use of cryptography in Section 4.8, and introduce a notation that can be used to describe cryptographic protocols and applications in Section 4.9.

Note that this chapter is far too short to provide a comprehensive overview about all cryptographic techniques that are relevant for WWW security. For this purpose, you must read one (or several) of the many books on cryptography that are available today. Among these books, I particularly recommend [1 “7].

4.1    Introduction

According to [4], the term cryptography refers to the study of mathematical techniques related to various aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication. It is commonly agreed that cryptography is a major enabling technology for network security, and that cryptographic algorithms and protocols are essential building blocks:

• A cryptographic algorithm is an algorithm defined by a sequence of steps precisely specifying the actions required to calculate a specific function of the input data. Most of the time, cryptographic algorithms are used to achieve specific security objectives.

• A cryptographic protocol is a distributed algorithm defined by a sequence of steps precisely specifying the actions required of two or more entities.

Cryptographic algorithms and protocols are being studied in both theory and practice. The aim is to design and come up with algorithms and protocols that are both secure and practical. Note, however, that there are at least two basic approaches to discussing the security of cryptographic algorithms and protocols:

• Computational security measures the computational effort required to break a specific cryptographic algorithm or protocol. An algorithm or protocol is said to be computationally secure if the best method for breaking it requires at least n operations, where n is some specified, usually very large, number. The problem is that no known practical algorithm or protocol can be proven to be secure under this definition. In practice, an algorithm or protocol is called computationally secure if the best known method of breaking it requires an unreasonably large amount of computational resources (e.g., time or memory). Another approach is to provide evidence of computational security by reducing the security of an algorithm or protocol to some well-studied problem that is thought to be difficult. For example, it may be possible to prove that an algorithm or protocol is secure if a given integer cannot be factored or a discrete logarithm cannot be computed. Algorithms and protocols of this type are sometimes called provably secure, but it must be understood that this approach only provides a proof of security relative to the difficulty of solving another problem, not an absolute proof of security.

• Unconditional security measures the security of a cryptographic algorithm or protocol when there is no upper bound placed on the amount of computational resources an adversary has at hand. Consequently, an algorithm or protocol is called unconditionally secure if it cannot be broken, even with infinite time and memory.

The computational security of a cryptographic algorithm or protocol can be studied from the point of view of computational complexity, whereas the unconditional security cannot be studied from this point of view because computational resources are allowed to be infinite. The appropriate framework in which unconditional security must be studied is probability theory, and the application thereof in communication or information theory [8, 9].

Unconditional security is preferable from a security point of view, because it protects against an infinitely powerful adversary. Unfortunately, unconditional security is generally hard and expensive to achieve in many cases, and sometimes impossible . For example, theory shows that unconditionally secure encryption systems use very long keys, making them unsuitable for most practical applications. Similarly, there is no such thing as an unconditionally secure public key cryptosystem. The best we can achieve is provable security, in the sense that the problem of breaking the public key cryptosystem is arguably at least as difficult as solving a complex mathematical problem. Consequently, one is satisfied with computational security, given some reasonable assumptions about the computational power of a potential adversary. But keep in mind that the security that a computationally secure cryptographic algorithm or protocol may provide is, for the most part, based on the perceived difficulty of a mathematical problem, such as the factorization problem or the discrete logarithm problem in the case of public key cryptography. Confidence in the security of such systems may be high because the problems are public and many minds have attempted to attack them. However, the vulnerability remains that a new insight or computing technology may defeat this type of cryptography. There are at least two recent developments that provide some evidence for this intrinsic vulnerability:

• In 1994, Peter W. Shor proposed randomized polynomial-time algorithms for computing discrete logarithms and factoring integers on a quantum computer, a computational device based on quantum mechanical principles [10, 11]. Note that it is not known how to build a quantum computer of a useful size ; it is not even known to be possible at all.

• Also in 1994, Len M. Adleman ^[1] demonstrated the feasibility of using tools from molecular biology to solve an instance of the directed Hamiltonian path problem, which is known to be hard ^[2] [12]. The problem instance was encoded in molecules of deoxyribonucleic acid (DNA), and the steps of the computation were performed with standard protocols and enzymes. Adleman notes that while the currently available fastest supercomputers can execute approximately 1012 operations per second, it is plausible for DNA computers to execute 1020 or even more operations per second. Moreover, a DNA computer would be far more energy efficient than existing supercomputers. Similar to the quantum computer, it is not clear at present whether it is feasible to actually build a DNA computer with such performance characteristics. Further information on DNA computing can be found in the relevant literature (e.g., [13]).

Should either quantum computers or DNA computers ever become practical, they would have a tremendous impact on modern cryptography. In fact, many cryptographic algorithms and protocols that are computationally secure would be rendered worthless. This is particularly true for algorithms and protocols that make use of public key cryptography.

Cryptographic algorithms and protocols are used to establish secured channels (both in terms of authenticity and integrity, as well as confidentiality). Note the subtle difference between a secure channel and a secured channel. Certain channels are assumed to be secure, including trusted couriers and personal contacts between communicating parties, whereas other channels may be secured by physical or cryptographic techniques. Physical security may be established through physical means, such as dedicated communication links with corresponding access controls put in place, or the use of quantum cryptography. Contrary to conventional cryptography, the security of quantum cryptography does not rely upon any complexity-theoretic or probability- theoretic assumptions, but is based on the Heisenberg uncertainty principle of quantum physics [14]. As such, quantum cryptography is immune to advances in computing power and human cleverness . In the future, quantum cryptography may provide a physical alternative to unconditionally secure cryptographic algorithms and protocols. In the meantime, however, conventional and computationally secure cryptographic algorithms and protocols are much easier to use and deploy. Consequently, we are not going to delve into the details of quantum cryptography in this book. You may refer to any book mentioned above to get information about quantum cryptography.

^[1] Len M. Adleman is a coinventor of the Rivest, Shamir, and Adleman (RSA) cryptosystem.

^[2] According to theoretical computer science, the directed Hamiltonian path problem is NP-complete.