A Cryptography Primer

Cryptography

One of the most central pieces in cryptography is the cipher.

Cipher

A cipher is an algorithm for converting a piece of data, called plaintext, into another piece of data, called ciphertext, which appears as random data and reveals no information about the original data.

We can also define a cipher as a pair of efficient algorithms $(E, D)$ where:

• $E$: $K \times M \to C$ is an encryption function receiving a plaintext (M) and a key (K) as an input and providing a ciphertext (C) as an output.
• $D$: $K \times C \to M$ is a decryption function receiving a ciphertext (C) and a key (K) as an input and providing the original plaintext (M) as an output.

Example

The one-time pad is the simplest example of a secure cipher and it simply uses an $XOR$ operation:

• $E(k, m) = k$ $XOR$ $m$
• $D(k, c) = k$ $XOR$ $c$

$XOR$ is used in this case, because it has a very interesting property:

• if $Y$ is a random variable with an unknown distribution in $\lbrace 0,1\rbrace^N$ and $X$ is an independent variable with a uniform distribution in $\lbrace 0,1\rbrace^N$, then $Z = X$ $XOR$ $Y$ is a variable with a uniform distribution in $\lbrace 0,1\rbrace^N$.

This means that using $XOR$ with a uniformly distributed variable $X$ will remove the underlying patterns in variable $Y$.

This makes the one-time pad a secure cipher under a very strong definition of security, known as semantic security,

Note: In Semantic security, the ciphertext does not reveal any information about the plaintext. However, practically it is not easy , because the key needs to be of the same size as the encrypted message. It is generally proven that perfect secrecy requires a key size equal to or larger than the message size, which makes it quite impractical to have perfectly secure algorithms. For this reason, we can use many different definitions of security depending on the case.

Categories of ciphers

There are two main categories of ciphers: stream ciphers and block ciphers.

Stream cipher

A stream cipher is a cipher that converts plaintext into ciphertext by encrypting one plaintext digit (e.g., bit) at a time with the corresponding digit of a pseudorandom keystream, which is generated based on a random key as shown in the following illustration.

This cipher is useful when the full size of the plaintext is not known in advance.

Stream ciphers are semantically secure, so semantic security is one of the alternative definitions for stream ciphers.

When using a cipher stream, one needs to be careful not to use the same key more than once to preserve its security.

Block ciphers

Contrary to stream ciphers, block ciphers operate on fixed-length groups of bits, called blocks.

Most block ciphers are classified as iterated block ciphers, which means they transform fixed-size blocks of plaintext into identically sized blocks of ciphertext by repeatedly applying an invertible transformation, known as a Round function.

The following illustration shows an example of an iterated block cipher, known as substitution-permutation network, which performs several alternating rounds of substitutions (S-boxes) followed by permutations (P- boxes). In order to be secure, these operations must have specific properties, e.g., the S-boxes should not have any linearities. The key for every round is derived from the original encryption key.

Note: A block cipher by itself allows encryption only of a single data block of the plaintext.

To encrypt multiple blocks (the whole plaintext), each block cipher can be used in different ways, called modes of operation.

An example of a block cipher is the cipher-block chaining mode (CBC), which selects and adds a random initialization vector to an $XOR$. Before getting encrypted, $XOR$ manners to the first plaintext block. Then the resultant ciphertext block is used as the new initialization vector for the next plaintext block, as shown in the following illustration:

The mentioned ciphers provide confidentiality, but not necessarily integrity since a man in the middle could potentially alter the ciphertext in a way that would decrypt into a valid plaintext.

Message Authentication Code (MAC)

A message authentication code (MAC) is a mechanism that can provide integrity but not confidentiality.

It consists of three main functions:

• A key-generating function
• A signing function that can generate a tag for plaintext
• A verifying function that can verify whether a tag is valid for a specific plaintext.

MACs can be constructed from other cryptographic primitives, such as block ciphers algorithms or cryptographic hash functions.

Providing both confidentiality and integrity

When we combine a cipher and a message authentication code, it can provide authenticated encryption, a form of encryption that simultaneously provides confidentiality and integrity.

Out of these techniques, only one combination was proven secure, where the plaintext is first encrypted and then a MAC is produced based on the resulting ciphertext. This technique is also known as encrypt-then-MAC.