2

Symmetric Encryption Algorithms

After covering an overview of cryptography, it's time now to present the principal algorithms in symmetric encryption and their logic and mathematical principles.

In Chapter 1, Deep Dive into Cryptography, we saw some symmetric cryptosystems such as ROT13 and the Vernam cipher. Before going further into describing modern symmetric algorithms, we need to overview the construction of the classic block ciphers.

If you recall, symmetric encryption is performed through a key that is shared between the sender and receiver, and vice versa. But how do we implement symmetric algorithms that are robust (in the sense of security) and easy to perform (computationally) at the same time? Let's see how we can answer this question by comparing asymmetric with symmetric encryption.

One of the main problems with asymmetric encryption is that it is not easy to perform the operations (especially the decryption), due to the high capacity of computation required to perform such algorithms at the recommended security levels. This problem implies that asymmetric encryption is not suitable for transmitting long messages, but it's better to exchange the key. Hence, by using symmetric encryption/decryption performed with the same shared key, we obtain a smoother scheme to exchange encrypted messages.

In this chapter, we will learn about the following topics:

• The basics of Boolean logic
• The basics of a simplified Data Encryption Standard (DES) where we start to familiarize ourselves with the techniques of S-box, substitution, and transposition of data
• Analyzing DES, Triple DES, and DESX by applying the previously mentioned techniques to these algorithms
• The Advanced Encryption Standard (AES) (Rijndael): the actual standard in symmetric encryption
• Implementing some logical and practical attacks on symmetric algorithms

By the end of the chapter, you will understand how to implement, manage, and attack symmetric algorithms.

Notations and operations in Boolean logic

In order to understand the mechanism of symmetric algorithms, it is necessary to go over some notations in Boolean logic and these operations on a binary system.

As we have already seen in Chapter 1, Deep Dive into Cryptography, the binary system works with a set of bits of {0,1}. So, dealing with Boolean functions means performing logic calculations on a sequence of bits to generate an answer that could be either TRUE or FALSE.

The most frequently used functions are AND (conjunction), OR (disjunction), and XOR (exclusive OR). But there are a few other notations as well that will be explained soon.

A Boolean circuit aims to determine whether a variable, x, combined with another variable, y, satisfies the TRUE or FALSE condition. This problem is called the Boolean satisfiability problem (SAT, or B-SAT) and it is of particular importance in computer science. SAT was the first problem to be shown as NP-complete.

NP-complete refers to the classical NP problem in the theory of complexity. If a group of questions is answerable in a reasonable time, we say P for polynomial time. If the time of answering is NP (for nondeterministic polynomial), then we say that this group of questions is not tractable in a reasonable running machine time. These questions are therefore NP-complete. So, in general, this is a hard problem to solve.

Conversely, I say that this is a hard problem only for a classical computer. An example is the RSA problem of factorization of a semiprime, which can be characterized as an NP problem. We will see that RSA theoretically will not be an issue for a quantum computer applying an appropriate quantum algorithm with a proper number of qubits (Chapter 9, Quantum Cryptography).

The question now is as follows: given a certain function, does an assignment of the TRUE or FALSE values exist such that the expression results in TRUE?

A formula of propositional logic is satisfiable if there exists an assignment that can determine that a proposition is TRUE. If the result is FALSE for all possible variable assignments, then the proposition is said to be unsatisfiable. That is of great importance in algorithm theory, such as for the implementation of search engines, and even in hardware design or electronic circuits.

Let's give an example of propositional logic:

• Premise 1: If the sky is clear, then it is sunny.
• Premise 2: There are no clouds in the sky.
• Conclusion: It's TRUE that it is sunny.

As you can see in Figure 2.1, starting from an input and elaborating on the logic circuit with an algorithm, we obtain a conclusion of TRUE or FALSE.

All these concepts will be particularly useful in further chapters of the book, especially Chapter 5, Zero-Knowledge Protocols, when we talk about zero knowledge, and Chapter 8, Homomorphic Encryption and Crypto Search Engine, where we talk about a search engine that works with encrypted data:

Figure 2.1: A Boolean circuit gives two opposite variables as output

The basic operations performed in Boolean circuits are as follows:

• AND (conjunction): Denoted with the symbol x?y. This condition is satisfied when X together with Y is true. So, we are dealing with propositions such as pear AND apple, for example. If we are searching through some content (let's say a database containing sentences and words), setting the AND operator will select all the elements containing both the words (pear and apple), not just one of them.

Now, let's explore how this operator works in mathematical mode. The AND operator transposed in mathematics is a multiplication of x * y. The following is a representation of the truth table for all the logic combinations of the two elements. As you can see, only when x * y = 1 does it mean that the condition of conjunction x?y is satisfied:

Figure 2.2: Mathematical table for AND

• OR (disjunction): Denoted by the symbol (X?Y). This condition is satisfied when at least one of the elements of X or Y is true. So, we are dealing with a proposition such as pear OR apple. Our example of searching in a database will select all the elements containing at least one of the two words (pear or apple).

In the following table, you can see the OR operator transposed in the mathematical operation x+y. At least one of the variables assumes the value 1, so it satisfies the condition of disjunction x?y, represented by the sum of the two variables:

Figure 2.3: Mathematical table for OR

Idempotence, from idem + potence (same + power), is a property of certain operations in mathematics and computer science that denotes that they can be applied multiple times without changing the result beyond the initial application. Boolean logic has idempotence within both AND and OR gates. A logical AND gate with two inputs of A will also have an output of A (1 AND 1 = 1, 0 AND 0 = 0). An OR gate has idempotence because 0 OR 0 = 0 and 1 OR 1 = 1.

• NOT (negation): Denoted with the symbol ¬x, meaning x excludes y. So, we are dealing with propositions such as pear NOT apple. For example, if we search in a database, we are looking for documents containing only the first word or value (pear) and not for the second (apple). Finally, in the following table, you can see the NOT operator denoted by the symbol of negation, ¬x. It is represented by a unitary operation that gets back the opposite value with respect to its input:

Figure 2.4: Mathematical table for NOT

These basic Boolean operators, AND,...