Cryptography Basics

Cryptography today has evolved into a complex science (some say an art) presenting many great promises and challenges in the field of information security. The basics of cryptography include classes and types of ciphers, various terms and concepts, and the individual components of the cryptosystem.

Classes of ciphers

Ciphers are cryptographic transformations. The two main classes of ciphers are block and stream, which describes how the cipher operates on input data.

 Instant Answer   The two main classes of ciphers are block ciphers and stream ciphers.

Block ciphers

Block ciphers operate on a single fixed block (typically 64 bits) of plaintext to produce the corresponding ciphertext. (To read more about these, jump to the later section “Plaintext and ciphertext.”) Advantages of block ciphers compared with stream ciphers are

• Reusable keys: Key management is much easier.

• Interoperability: Block ciphers are more widely supported.

Block ciphers are typically implemented in software.

Stream ciphers

Stream ciphers operate in real time on a continuous stream of data, typically bit-by-bit. Stream ciphers are generally faster than block ciphers and require less code to implement. However, the keys in a stream cipher are generally used only once (see the later section “A disposable cipher: The one-time pad”) and then discarded. Key management becomes a serious problem. Stream ciphers are typically implemented in hardware.

Types of ciphers

The two basic types of ciphers are substitution and transposition. Both are involved with the process of transforming plaintext into ciphertext.

Substitution ciphers

Substitution ciphers replace bits, characters, or character blocks in plaintext with alternate bits, characters, or character blocks to produce ciphertext. A classic example of a substitution cipher is one that Julius Caesar used: He substituted letters of the message with other letters from the same alphabet. (Read more about this in the sidebar “A brief history of cryptography,” elsewhere in this chapter.) In a simple substitution cipher using the standard English alphabet, a cryptovariable (key) is added modulo 26 to the plaintext message. In modulo 26 addition, the remainder is the final result for any sum equal to or greater than 26. For example, a basic substitution cipher in which the word BOY is encrypted by adding three characters using modulo 26 math produces the following result:

A substitution cipher may be monoalphabetic or polyalphabetic:

• Monoalphabetic: A single alphabet is used to encrypt the entire plaintext message.

• Polyalphabetic: A more complex substitution that uses a different alphabet to encrypt each bit, character, or character block of a plaintext message.

A more modern example of a substitution cipher is the S-boxes (Substitution boxes) employed in the Data Encryption Standard (DES) algorithm. The Sboxes in DES produce a nonlinear substitution (6 bits in, 4 bits out). Note: Do not attempt to sing this to the tune “Shave and a Haircut” to improve the strength of the encryption by hiding any statistical relationship between the plaintext and ciphertext characters.

Transposition (or permutation) ciphers

Transposition ciphers rearrange bits, characters, or character blocks in plaintext to produce ciphertext. In a simple columnar transposition cipher, a message might be read horizontally but written vertically to produce the ciphertext as in the following example:

THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG 

written in 9 columns as

THEQUICKB ROWNFOXJU MPEDOVERT HELAZYDOG

then transposed (encrypted) vertically as

TRMHHOPEEWELQNDAUFOZIOVYCXEDKJROBUTG

The original letters of the plaintext message are the same; only the order has been changed to achieve encryption.

DES performs permutations through the use of P-boxes (Permutation boxes) to spread the influence of a plaintext character over many characters so that they’re not easily traced back to the S-boxes used in the substitution cipher.

Other types of ciphers include

• Codes: Includes words and phrases. For example:

  • Ciphertext = “Colonel Jessup, did you order the Code Red!?”

  • Plaintext = “Did you order the attack!?”

• Running (or book) ciphers: For example, the key is page 137 of The Catcher in the Rye, and text on that page is added modulo 26 to perform encryption/decryption.

• Vernam ciphers: Also known as one-time pads, which are keystreams that can only be used once. We discuss these more in the upcoming section “A disposable cipher: The one-time pad.”

• Concealment ciphers: These include steganography, which we discuss further in the upcoming section “Steganography: A picture is worth a thousand (hidden) words.”

 Instant Answer   Most modern cryptosystems use both substitution and permutation to achieve encryption.

Key clustering

Key clustering (or simply clustering) occurs when identical ciphertext messages are generated from a plaintext message by using the same encryption algorithm but different encryption keys.

 Instant Answer   The science of crypto

Cryptanalysis is the science of deciphering ciphertext without the cryptographic key.

Cryptography is the science of encrypting and decrypting information, such as a private message, to protect its confidentiality, integrity, and/or authenticity.

Cryptology is the science that encompasses both cryptography and cryptanalysis.

Putting it all together: The cryptosystem

A cryptosystem is the hardware or software implementation that transforms plaintext into ciphertext (or encryption) and back into plaintext (or decryption).

An effective cryptosystem must have the following properties:

• The encryption and decryption process is efficient for all possible keys within the cryptosystem’s keyspace.

• The cryptosystem is easy to use.

• The strength of the cryptosystem is dependent on the secrecy of the cryptovariables (or keys) rather than the secrecy of the algorithm. (Most cryptographic algorithms are public anyway.)

Cryptosystems typically comprise two elements:

• Cryptographic algorithm: This algorithm details the step-by-step procedures used to produce

  • Ciphertext (encipher)

  • Plaintext (decipher)

• Cryptovariable: The key to the cryptographic algorithm, the cryptovariable is a secret value applied to the algorithm. The strength and effectiveness of the cryptosystem is largely dependent upon the secrecy and strength of the cryptovariable.

 Instant Answer   A cryptosystem consists of two elements: the cryptographic algorithm and the cryptovariable (key).

 Remember   An analogy of a cryptosystem is a deadbolt lock. A deadbolt lock can be easily identified, and its inner working mechanisms aren’t closely guarded state secrets. What makes a deadbolt lock effective is the individual key that controls a specific lock on a specific door. However, if the key is weak (imagine only one or two notches on a flat key) or not well protected (left under your doormat), the lock won’t protect your belongings. Similarly, if an attacker is able to determine what cryptographic algorithm (lock) was used to encrypt a message, it should still be protected because you’re using a strong key (128 bit) that you have kept secret instead of a 6-character password written on a scrap of paper left under your mousepad.

Encryption and decryption

Encryption (or enciphering) is the process of converting plaintext communications into ciphertext. Decryption (or deciphering) reverses that process, converting ciphertext into plaintext. Traffic on a network can be encrypted by using either end-to-end or link encryption.

End-to-end encryption

With end-to-end encryption, packets are encrypted once at the original encryption source and then decrypted only at the final decryption destination. The advantages of end-to-end encryption are its speed and overall security. However, in order for the packets to be properly routed, only the data is encrypted, not the routing information.

Link encryption

Link encryption requires that each node (for example, a router) has separate key pairs for its upstream and downstream neighbors. Packets are encrypted and decrypted at every node along the network path.

The following example in Lab 8-1 illustrates link encryption:

Lab 8-1 Link Encryption

1. Computer 1 encrypts a message by using Secret Key A and then transmits the message to Router 1.

2. Router 1 decrypts the message by using Secret Key A, re-encrypts the message by using Secret Key B, and then transmits the message to Router 2.

3. Router 2 decrypts the message by using Secret Key B, re-encrypts the message by using Secret Key C, and then transmits the message to Computer 2.

4. Computer 2 decrypts the message by using Secret Key C.

The advantage of using link encryption is that the entire packet (including routing information) is encrypted. However, link encryption has the following two disadvantages:

• Latency: Packets must be encrypted/decrypted at every node.

• Inherent vulnerability: If a node is compromised or a packet’s decrypted contents are cached in a node, the message can be compromised.

He said, she said: The concept of non-repudiation

To repudiate is to deny; non-repudiation means that an action (such as an online transaction, e-mail communication, and so on) or occurrence can’t be easily denied. Non-repudiation is a related function of identification and authentication (I&A) and accountability. For example, it’s difficult for a user to deny sending an e-mail message that was digitally signed with that user’s private key. Likewise, it’s difficult to deny responsibility for an enterprise-wide outage if the accounting logs positively identify you (from username and strong authentication) as the poor soul who inadvertently issued the write-erase command on the core routers two seconds before everything dropped. Gulp.

A disposable cipher: The one-time pad

A one-time pad (key) is a keystream that can only be used once. Considered unbreakable because it’s completely random and is used only once and then destroyed, it consists of a pad of the same length as the message to which it’s applied. Both the sender and receiver have an identical pad, which is used by the sender to encrypt the message and by the receiver to decrypt the message. This type of cipher is very effective for short messages but is impractical for larger (several megabytes) messages. One-time pads are typically implemented as stream ciphers.

 Instant Answer   A one-time pad is an example of a stream cipher.

Plaintext and ciphertext

A plaintext message is a message in its original readable format or a ciphertext message that has been properly decrypted (unscrambled) to produce the original readable plaintext message.

A ciphertext message is a plaintext message that has been transformed (encrypted) into a scrambled message that’s unintelligible. This concept doesn’t apply to messages from your boss that may also happen to be unintelligible!

Work factor: Force x effort = work!

Work factor describes the difficulty - in terms of time, effort, and resources - that are required to break a cryptosystem. Given enough time, effort, and resources, any cryptosystem can be broken. The goal of all cryptosystems, then, is to achieve a work factor that sufficiently protects the encrypted information against a reasonable estimate of available time, effort, and resources. However, reasonable can be difficult to estimate as technology continues to rapidly improve.

Moore’s Law is based on an observation by Gordan Moore, one of the founders of Intel, that processing power seems to double about every 18 months. To compensate for Moore’s Law, some really hard encryption algorithms are used. Today, encrypted information is valuable for perhaps only three months with encryption algorithms that will theoretically take several hundred millennia to break, confident in the knowledge that tomorrow it will be mere child’s play.