Introduction to Cryptography, Part 2

In the first part of the series, we went over what cryptography is and gave a few examples of historical ciphers. Part two is going to cover stream / block ciphers and their modes of operation, as well as go over the data encryption standard (DES). Let’s start by learning about block ciphers.

Symmetric cryptography is broken down into two different categories – block ciphers and stream ciphers. Block ciphers encrypt blocks of plain text bits with the same key every time. When being encrypted, all plaintext bits that are in the same block depend on each other. Most block ciphers have a block length of 128 bits, or a block length of 64 bits as seen in the data encryption standard and triple DES (3DES). Later on in this article we are going to go over the data encryption standard more in depth. When dealing with encrypted computer communications over the Internet, block ciphers are the ones mostly used.

Unlike block ciphers, stream ciphers encrypt each bit individually. To achieve this, each bit from a key stream is added to a plaintext bit. A key stream is a stream of random or pseudo random characters that are combined with the plaintext to produce the final encrypted message. There are two types of stream ciphers: asynchronous and synchronous. Synchronous stream ciphers depend only on the key, and asynchronous ones depend on both the key and cipher text. Most common stream ciphers are of the synchronous type.

We are now going to take a brief step away from cryptography and learn about modular arithmetic. Even if you do not care about math, learning modular arithmetic is vital to understanding cryptography. Modular arithmetic is just a simple way of performing arithmetic in a finite set of integers. To start, let’s first consider the hours on a clock. When you count hours on a clock, you end up getting something like this: 1h, 2h, 3h,…, 12h, 1h, 2h, 3h, …, 11h, 12h. Even though you add one each time, you never leave the set. Let’s now consider this set of numbers: {0, 1, 2, 3, 4, 5, 6, 7, 8}. As long as the results are less than 9, we can do regular arithmetic (e.x. 4+3=7, 2×3=6). If we have a result that is greater than 9 (e.x. 8+4=12) then we only consider the remainder rather than the result. Because the solution for 8+4=12 and the remainder of 12 / 9 is 3, we would write: 8 + 4 = 3 mod 9.

The exact definition for the modulos operation is as follows:

Let a, r, m ∈ ℤ (where is a set of all integers) and m 0. We write a = r mod m.

If m divides a – r, m is called the modulus and r is called the remainder.

After defining stream ciphers, block ciphers, and modular arithmetic, we are now going to go over how the encryption of each individual bit works in stream ciphers. The encryption and decryption method is simple; all we do is take each bit, xi and add it to the secret key stream bit, si, modulo 2.

Here is the formal definition:

Encryption: y i = e si (xi) = x i + s i mod 2

Decryption: x i = d si (yi) = y i + s i mod 2

Looking at the above formula, we notice that the functions for encryption and decryption are the same. We should have asked ourselves why we can use modulo 2 addition, and what the nature of the key stream bits si is. Before going over why we can use modulo 2 addition, let’s go over why the encryption and decryption functions are the same. To do this, we must prove that the decryption function actually produces the plaintext xi again. Here is the encryption expression in the decryption function:

d si (y i ) = yi + si

This formula states that the expression (2si mod 2) always has the value of zero because 2= 0 mod 2. It can also be stated that if si has either the value 0, then 2si = 2 * 0 = 0 mod 2. If si = 1, we have 2s i = 2 * 1 = 2 = 0 mod 2. Note that Q.E.D. means quod erat demonstandum, which is the Latin translation of a Greek phrase meaning “which had to be proven”. Now that we have gone over why the encryption and decryption function are the same, let’s now go over why modulo 2 addition is a good encryption function.

The main reason modulo 2 addition is a good encryption function is modulo 2 addition is equivalent to the XOR operation (XOR is a binary operation; it stands for “exclusive or”, that is to say that the resulting bit evaluates to one if only exactly one of the bits is set). The XOR operation is extremely useful because it is used to merge a stream cipher and plaintext. Let’s go over an example with the word “hello”. The word “hello” in ASCII is 01101000 01100101 01101100 01101100 01101111. After grouping it in 5 bytes, you can now encrypt this string with a random string of 5 bytes, like a One-Time pad. If the key is never reused, you can never crack the cipher.

XOR also has these advantages in cryptography:

  • It’s very fast to compute
  • Easy to understand
  • Because it is associative, it doesn’t matter how many and in which order you XOR your values

Some ciphers contain what is known as an Initialization Vector (IV). An IV is a random, unpredictable number that makes sure the message is random each time it is encrypted. This IV should be exchanged as part of the ciphertext; a IV does not need to be hidden. To reiterate, it is imperative that a IV is random each time so an adversary cannot guess it before the message is encrypted. There also exists a nonce (number always used once) which is similar to an IV. Much like an IV, it is generally demanded that a nonce is a random, unpredicable number. The random IV’s that are used by block ciphers can be considered nonces. Some crypto authors use the term IV and nonce interchangebly, while others make a distinction between the two. In this series I am going to be making a distinction between the two.

It is now time to introduce the different modes of operation for stream / block ciphers. A mode of operation describes how to repeatedly apply a cipher’s single-block operation to securely transform data larger than a block. There are five main modes of operation: electronic codebook mode (ECB), cipher block chaining mode (CBC, the most popular), output feedback mode (OFB), and cipher feedback mode (CFB), counter mode (CTR). While we are only going to cover the main five modes in this article, there are more links at the end of this article that provide more resources on this topic.

Here is a comparison of the different modes of operation:

  • ECB: ECB is extremely insecure and should never be used. There is a good image of the penguin Tux being shown encrypted with ECB ( Wikipedia link). ECB works by encrypting each block independently. The same plaintext block will result in the same cipher text block.
  • CBC: CBC has an IV and needs to be random every time the message is encrypted. If a part of the message is changed, then transmission errors in one cipher text block will completely destroy the plaintext. To fix this, the plaintext would need to be re-encrypted.
  • CTR: This is a relatively simple mode. It creates a pseudo random stream that is not dependent on the plaintext. This pseudo random stream is created by counting up from different IVs / nonces which are multiplied by a maximum message length so that overlap is prevented. Unlike CBC, transmission errors only affect the wrong bits and not the plaintext.
  • OFB: Like CTR, OFB creates a pseudo random stream that is not dependent on the plaintext.
  • CFB: While CFB uses a pseudo random stream like CTR, CBC, and OFB, CFB’s pseudo random stream depends on the plain text. If a transmission error occurs, it will completely destroy the following block, but only affect the wrong bits in the current block.

The final piece we are going to cover in this article is the data encryption standard (DES). Over the past 30 years, DES has been by far the most popular block cipher. While DES can easily be broken because the key space is too small, it is still used in a lot of legacy applications. Even though this is the case, when you encrypt data three times in a row with DES, it produces a very secure cipher known as 3DES. Because DES is one of the best studied algorithms, learning about DES will help us understand many other symmetric algorithms.

As stated before, DES is a symmetric cipher that encrypts block lengths of 64 bits with a key of size of 56 bits. The internals of DES rely on a structure called a Feistel network. The main advantage of a Feistel network is the encryption and decryption functions are almost the same. When decrypting, it only requires a reversed key schedule. The encryption process uses the Feistel structure that consists of multiple rounds of plaintext, each round consisting of an initial permutation step, key schedule, and final permutation step. The number of rounds used in a Feistel structure depends on the security of the system. While using more rounds makes the system more secure, the tradeoff is slower decryption times. Less rounds means having a quicker decryption time, but overall weaker system.

We have now gone over a brief overview of stream / block ciphers, their modes of operation and DES. In the next part, we are going to go over applying this knowledge by learning the OpenSSL cryptography library. If you have any questions or have seen an error in this article, you can contact [email protected].

References / more links:

Share and Enjoy

  • FacebookFacebook
  • TwitterTwitter
  • DeliciousDelicious
  • LinkedInLinkedIn
  • StumbleUponStumbleUpon
  • Add to favoritesAdd to favorites
  • EmailEmail
  • RSSRSS
mm

TheBitcoinNews.com – leading Bitcoin News source since 2012

Virtual currency is not legal tender, is not backed by the government, and accounts and value balances are not subject to consumer protections. The information does not constitute investment advice or an offer to invest.