Foundations of Security

As mentioned earlier in the chapter, secure systems require several components that work together to provide an environment that is safe. An environment that is safe is made up of elements that are trustworthy, combined with other things that protect us from dangerous objects or that we simply do not know much about. Such systems include policies that establish rules, and mechanisms that are used to implement the functions or services required by the policies.

The set of services that are commonly available to secure systems are

• Identification

• Authentication

• Authorization

• Integrity

• Confidentiality

• Nonrepudiation

• Monitoring/auditing

• Security management

In computer systems, many of the mechanisms used to establish secure systems are built on the foundations of cryptography.

Cryptography

Part of the larger mathematical discipline of cryptology (from the Greek kryptos logos, meaning "hidden word"), cryptography has become more than the science of hiding and recovering information. Cryptography extends to include many more aspects of communication, including most of the services mentioned previously. Ronald Rivest, co-creator of the RSA algorithms and a number of other important security products, said that "Cryptology is about communication in the presence of adversaries." Cryptography is the branch of cryptology that concerns itself with the enforcement of security. Its sibling, cryptanalysis, is dedicated to defeating cryptographic mechanisms.

The most common use of cryptography is for communicating privately or for protecting information by transforming data into a state that is useless without a function or key to return it to a meaningful state. Peer-to-peer systems have many uses for cryptography, such as hiding information exchanged between instant message peers. The process of transforming meaningful data, called plaintext, into useless ciphertext is called encryption. The reverse process is called decryption. Functions that perform encryption and decryption are sometimes known as ciphers.

Note

Interestingly enough, the word cipher has an ancient origin, with an associated meaning of "to be empty" in the case of cryptography, that can be taken to mean "void of meaning."

Early schemes depended on the secrecy of cryptographic functions or their workings (algorithms) to protect information. More useful functions introduced keys, or additional data, into the mixture. These ciphers code and decode information, using one or more keys whose values contribute to the result. Cryptographic keys perform the same function that household keys do for doors having the correct key provides access to the information. Most of us can recall having seen pictures of early padlocks with keys of simple design. These worked well when only a few people owned locks and keys. As more people acquired keys (or became proficient in bypassing the mechanisms of the locks), it became necessary to develop more sophisticated locks and keys. Similarly, cryptography has progressed from simple functions and keys to very sophisticated functions with complex keys.

Cryptosystems

In studying any cryptographic service, there are a number of identifiable elements that constitute a system that provides the service. A cryptosystem consists of the following:

• A set of cryptographic functions

• A set of keys (a keyset)

• The set of all possible plaintexts

• The set of all possible ciphertexts

Secret Key Cryptography

Secret key cryptography is also known as symmetric key cryptography, because the same key is used in both encrypting and decrypting operations. After the plaintext is encoded using the key, anyone who wants to decrypt the ciphertext must know the value of the key used to produce the ciphertext. Symmetric key algorithms use the key to combine with and permute the plaintext. They frequently are designed to work with operations that are performed quickly using hardware, such as the addition and exclusive or operations. Cryptographers design functions that obscure information by doing things such as removing natural patterns while preserving the capability to recover the plaintext. Although it is beyond the scope of this book to get into the details of algorithms, you can be assured that you can find an algorithm resistant enough for your needs from among those that have been developed thus far.

The length of a key is often significant to producing ciphertext that is resistant to cracking, or the attempt to decipher encrypted text without possessing the key. If the algorithm is well designed, a brute-force attack may be required, wherein keys from the keyset are applied to the ciphertext until meaningful plaintext appears. Larger keysets generally make it more difficult to guess what key is the right one. This also makes it possible for more than one key to produce something that might be meaningful, yet different enough from the other results that it casts doubt on all of them.

The numbers of bits in a key determine the number of possible keys. A key that is composed of n bits will produce a keyspace of 2ⁿ possible keys. In practice, such things as using words or phrases that are made up of characters from the western alphabet often reduce keyspaces. On average, you'll try half of the possible keys before finding the correct one. So, if a key has a length of 32 bits, it will take approximately 2 billion attempts to discover a key. Although this is daunting for a human, it's cyber-play for a computer. A current effort at Distributed.net is searching the keyspace for a 64-bit key for the RC5 algorithm at an average rate of 98,609,946 gigakeys/sec; using about 31,000 Internet-linked computers in a single day. The 32-bit key of our example will be found in fewer than one-hundredths of a second. At 5 million keys per second, even a single computer is a formidable challenger. Generally, key lengths of 128 bits or more, resulting in 2¹²⁸ possible keys, are considered to be safe.

Note

"Safe" is a pretty relative term. Because cyber-thieves have to access encrypted data using algorithms and keys, the idea is to make it difficult or costly enough that the value of what is inside is negligible by the time they are able to access it. Most modern symmetric algorithms that use keys of 128 bits or greater are capable of protecting information for more than 40 years, assuming that advances in computing progress at about the same rate it has for the last decade.

DES, Triple-DES, CAST, RC4 and RC5, IDEA, and Blowfish are all examples of common symmetric algorithms. For many years, DES, or the Data Encryption Standard, defined the algorithm (called the Data Encryption Algorithm, or DEA) endorsed by the government for encryption of data, such as the information that accompanies electronic funds transfers. DEA uses a key that is effectively 56 bits in size. Advances in computing technology and cryptanalysis have rendered DEA ineffective for many of the applications it was originally intended for. In October 1999, the "approved symmetric algorithm of choice" became Triple-DES (TDES), and DES has been restricted to use in legacy systems. Triple-DES retains DEA, but requires the algorithm to be exercised with three keys, effectively expanding the available keyspace.

As early as 1997, the National Institute of Science and Technology (NIST) began searching for a successor to DES. The Advanced Encryption Standard (AES) specifies that a new symmetric algorithm, Rijndael (pronounced "Rhine Dale"), has been approved for use. Rijndael can use key lengths of 128, 192 or 256 bits, and has a sufficiently strong algorithm to provide security for another 20 years, or until the Advanced Encryption Standard is replaced.

Tip

Students of cryptography will likely find the other contenders for the "advanced encryption algorithm" and the mechanisms used to select the winner interesting. They are MARS, RC6, Serpent, and Twofish. See the "Additional Resources" section for pointers to where you can obtain additional information.

Secret key cryptography, then, continues to be useful for encryption and will be for many more years. All that one has to worry about is how to provide the secret key to the intended recipient of encoded information, while avoiding giving the key to somebody who shouldn't be "in the know." If a large number of people need to have a key, it is more likely that the key will be compromised. On the other hand, if we used a separate key for each recipient, there might be a lot of keys, and there will certainly be a number of ciphertexts that are all encoded versions of the same plaintext. This might also expose the information to clever cryptanalysts.

Public Key Cryptography

If there were a way that the secret key wasn't so, well, secret then the problem of distributing keys would not be so difficult. Although this sounds strange, it is the basis for public key cryptography.

Public key cryptography makes use of pairs of keys. One of the keys is used with an encryption function and is made publicly available; the other is used with a decryption function and is kept private. With public key cryptosystems, data encoded using a public key can only be decoded with the corresponding private key. It isn't necessary to transfer any secrets to share information securely. Because the private key is never shared with anyone, it is not a "secret" leading to the distinction between secret keys that are used with symmetric algorithms, and private keys that are part of public key cryptosystems.

Using public key cryptography, if Larry wanted to send a private message to Ellen, he would use Ellen's public key to encrypt the message. Larry may have received Ellen's public key directly from her, or from a public repository. Using her private key, Ellen is the only one who can decipher the message. Unlike secret key cryptography, Ellen and Larry do not have to share a key that is only known between them. Of course, if Ellen wanted to securely reply to Larry, she would have to use Larry's public key to encrypt her message to Larry. Because peer-to-peer systems often connect to other systems without prior arrangement, public key cryptography is particularly useful.

Public key cryptography relies on problems that are difficult to solve, or hard problems. With these problems, it may not matter if one understands the problem well or has a grasp of the mechanisms involved.

Most hard problems that are applied to securing information are computationally intensive. One example of a hard problem that is the basis for several cryptosystems is factoring large numbers. From your studies in math, you might recall that integers can be the multiplicative product of two or more integers. Factoring an integer results in identifying the smallest integers whose product is the original number. If the integer we are interested in is very large, and the factors of that number are very large themselves, it's difficult to identify the factors. Doing so requires the ability to determine whether an integer is a factor, and whether it is prime (divisible only by itself and one). Try, for example, to determine the factors of 4,405,829 it's prime, but it will take some manual effort to determine this, although it's relatively trivial to determine whether this small number is prime using a computer. Much larger numbers are significantly more difficult, even for a powerful computer. (Incidentally, 4,405,829 is the patent number awarded to RSA Security, which developed a popular cryptosystem around this particular hard problem.)

It's a lot easier to multiply together two large prime integers to obtain another integer than it is to determine what the original integers were from the result. Functions and their inverses that exhibit these properties are known as one-way functions. Formally, one-way functions are those functions in which it is significantly easier to compute a function in one direction than it is to compute the inverse function. When the ease of computing the inverse function is significantly increased with some additional knowledge, such as one of the original factors, a function is known as a trapdoor one-way function. The trapdoor provides an easy escape from the difficulty of the inverse function.

Public key cryptography makes use of keys that are mathematically related in such a way that knowing the public key does not make it easier to derive the private key the relationship between them is the result of an application of a one-way function. At the same time, the algorithm used to encrypt a plaintext message using a public key is a trapdoor one-way function, in that the private key "unlocks" the trapdoor. Common public key cryptosystems include RSA, Rabin, ElGammal, LUC, and Elliptic Curve Cryptosystems (ECC).

If public key cryptography eliminates the need to distribute secret keys, you may be wondering why secret key cryptography hasn't been replaced. Public key cryptosystems are slower than their secret key counterparts, in part because of their computational complexity, and also because of their affinity with large numbers.

Because public key cryptosystems are more likely to be attacked by using approaches to solving hard problems rather than by brute force, they require keys that are longer than those used by secret key cryptosystems. For example, it's generally agreed that a key length of 1024 bits for RSA is sufficient for the moment.

Public key systems often work together with secret key systems they're ideal for protecting the exchange of a secret key. In fact, public key systems evolved from work performed in connection with the design of secure transmission mechanisms for secret keys. Public key cryptosystems are used to create a digital envelope that encloses a secret key (called a session key) used for future communication. The combination of public key and secret key cryptosystems results in better performance by using the faster secret key cryptosystem to secure the bulk of the information.

Digital Signatures

The usefulness of public key cryptosystems extends beyond their capability to secure information. They can also be used to "sign" data. For example, the functions used in the RSA public key cryptosystem permit it to be used "in reverse." In other words, the encoding function can also be used with the private key to produce ciphertext that is decipherable by the corresponding public key. Although this does not produce a very private message anyone can use the public key to decrypt the content it does produce a "signature" (the ciphertext) that is unique to the application of the private key to the plaintext.

A digital signature "affixed" to a document associates an identity with the document and asserts the content. Only the owner of the private key can sign the document, and if the document is changed, the ciphertext will also change. Once again, there is no need to share a private key. A person can encrypt a message or verify that a document has been signed by using only a public key. For example, if Ellen wanted to ensure the integrity of a message sent to Larry, she would use her private key to produce a signature, which is appended to the document. Using Ellen's public key, Larry can decrypt the signature to produce a copy of the original document. If the copy and the original document match, the document is authentic.

As mentioned earlier, RSA's public key cryptosystem is capable of encryption, decryption, and creating signatures. The ElGammal Signature Scheme (ESS) and its close relative the Digital Signal Algorithm (DSA) are specialists, producing only signatures. DSA is the United States national standard for digital signatures, known as the Digital Signature Standard (DSS).

Hashes

One problem with digital signatures is that they tend to be very large. In the case of RSA's functions, they are at least as large as the plaintext being signed. DSS produces signatures that are twice as large. While incredibly useful, the cryptosystems used to produce signatures are often slow, relying on algorithms that use complicated arithmetic operations.

Special cryptographic functions have been developed for the purpose of validating content. These functions do not require a key, and are not intended to produce ciphertext that can be decrypted to produce the original plaintext. Hash functions are one-way functions that have the following properties:

• They easily produce a fixed length output for input of arbitrary size.

• They produce an output that is unique for every possible input plaintext.

• It is computationally unfeasible to recover the content of the message used to produce the output.

Hash functions take input of any size and produce a message digest of a specific size. In most cases, the digest is at least 160 bits, the minimum size required for DSS. Message digests are used with digital signatures to ensure the integrity of a document. Being smaller, digests are easily signed. Because the digest accurately represents the original message, only the digest needs to be encrypted to insure that the document has not been tampered with. In this case, Larry would decrypt the signature with Ellen's public key to produce the original digest. Using the same digest algorithm that Ellen used, Larry would apply the algorithm to the received document and compare the resulting digest to the one obtained from Ellen's signature. If they match, the document has not been altered.

Examples of systems that produce digests are the Secure Hash Algorithm (SHA-1), produced by NIST and a part of the Secure Hash Specification (SHS), a nationally endorsed standard, and Message Digest Version 5 (MD5) from RSA Security. SHA produces a 160-bit message digest, and MD5 produces a 128-bit digest.

With the background presented in the chapter to this point, we are now ready to look at some of the cryptography services.