Block cipher

In cryptography, a block cipher is a special kind of mathematical tool used to keep information safe. It works by taking fixed groups of bits, called blocks, and changing them in a way that only someone with the right key can understand. This helps protect secrets when we store or send data.

Block ciphers are like the building pieces for many security systems. Even though a block cipher can only change one block of data at a time, there are many clever ways to use it over and over again safely. These methods, called modes of operation, help make sure that all our information stays private and true.

Because block ciphers are so useful, they are also used in other important security tools, like universal hash functions and pseudorandom number generators. They are a key part of keeping our digital world secure.

Definition

A block cipher uses two paired algorithms: one for encrypting data and the other for decrypting it. Both algorithms need two inputs: a block of data and a secret key. The encryption algorithm changes the data into a coded form, and the decryption algorithm uses the same key to turn the coded data back into its original form.

For example, a block cipher might take a 128-bit block of data and, using a secret key, change it into another 128-bit block of coded data. Each different key picks a unique way to change the data, ensuring that only someone with the correct key can decode it.

History

The modern design of block ciphers started with ideas from Claude Shannon in 1949. He suggested using simple operations like substitutions and permutations in multiple steps to improve security. One common way to do this is called a Feistel network, used in the DES cipher.

A key development was the Atalla Key Block (AKB), created in 1972 by Mohamed M. Atalla. It helped secure communication in the banking industry, especially for ATM networks. The sharing of important secrets like symmetric keys or PINs depends on this format. The DES cipher, published in 1977, helped people understand how block ciphers work and led to new ways to test their security.

Design

Most block ciphers are called "iterated block ciphers." This means they work by taking a piece of data, called plaintext, and turning it into another piece of data, called ciphertext. They do this by repeating a special process many times, called "rounds." Each round uses a secret key to mix up the data further.

There are different ways to build these ciphers. One common way is called a "substitution-permutation network." In this method, the data goes through steps where parts of it are swapped out (substitution) and then rearranged (permutation). Another method is called a "Feistel cipher," where the data is split in half and each half is processed using a special function before being recombined. These designs help keep information safe by making it very hard to read without the right key.

Main article: Substitution–permutation network

Main article: Feistel cipher

Main article: Lai–Massey scheme

Modes of operation

A block cipher can only encrypt one block of data at a time. To encrypt longer messages, the data is split into blocks. In the simplest way, called electronic codebook (ECB) mode, each block is encrypted separately. But this can be insecure because the same blocks of text will look the same after encryption.

To make encryption safer, special methods called block cipher modes of operation have been created. These methods add extra steps to mix the data more thoroughly. For example, in cipher block chaining (CBC) mode, each block is mixed with the next one before encryption. Other methods like cipher feedback (CFB) and output feedback (OFB) also use these extra steps to keep the encrypted message safe. These methods help ensure that even if someone sees the encrypted message, they cannot easily figure out the original text.

Padding

Main article: Padding (cryptography)

Some ways of encrypting data need the information to come in fixed sizes, called blocks. If the last piece of information isn’t big enough, we need to add extra bits, called padding, to make it the right size. Simply adding zeros isn’t safe because it can let someone trick the system. Instead, a safer way is to add one extra bit and then fill the rest with zeros, which helps keep the information safe.

Cryptanalysis

Main article: Cryptanalysis

Cryptanalysis is a way to figure out how to decrypt messages without knowing the secret key used to lock them. There are different types of attacks depending on what information the person trying to break the code has. For example, they might only have the locked-up messages, or they might know some of the original messages too.

There are special methods to break codes, like looking for patterns in how the messages change. These methods help experts test how strong a code is. New codes need to prove they can stand up to these tests to be trusted.

Provable security

When we use a block cipher in a certain way, called a "mode of operation", we want the whole system to be as safe as the block cipher itself. Some ways, like ECB mode, are not safe, but others, like CBC mode, can be shown to be safe if the block cipher is safe too. To say this in a precise way, we need math rules about what "safe" means for a block cipher.

This way of proving that a system is safe by showing it depends on the safety of its parts is called provable security.

Standard model

A block cipher is considered safe in the standard model if an attacker cannot tell it apart from a completely random way of changing data. We can imagine a game where someone flips a coin: if it lands heads, they use the block cipher; if tails, they use a random change. The attacker tries many times to guess which one it is. If the attacker cannot do much better than guessing randomly, the block cipher is very safe, called a pseudo-random permutation.

Ideal cipher model

Main article: Ciphertext indistinguishability

Practical evaluation

Block ciphers can be judged based on several important factors. One key factor is the size of its key and the block it works with, which helps decide how secure the cipher can be. Another important aspect is how well the cipher has held up against attempts to break it over time, which gives us confidence in its design.

We also look at how difficult it is to build the cipher in things like computers or special machines, and how much energy or space it needs. Performance matters too — we want to know how fast it can work and how much memory it uses. Finally, we consider things like cost and flexibility, such as whether the cipher can work with different sizes of keys and data.

Main article: Block cipher modes of operation

Notable block ciphers

Main articles: Lucifer (cipher) and Data Encryption Standard

Lucifer was the first civilian block cipher, created at IBM in the 1970s. A revised version became the U.S. government’s Data Encryption Standard (DES), released in 1976. DES uses 64-bit blocks and a 56-bit key. Although widely used, its short key length became a problem over time. An improvement called Triple DES was developed, which is still considered secure today.

The International Data Encryption Algorithm (IDEA) was designed in 1991 as a replacement for DES. It uses 64-bit blocks and a 128-bit key, combining different operations to enhance security. Another notable cipher is RC5, designed by Ronald Rivest in 1994. RC5 is flexible, allowing different block sizes, key lengths, and rounds.

The Advanced Encryption Standard (AES), based on the Rijndael cipher, was adopted in 2001. AES uses a fixed block size of 128 bits and keys of 128, 192, or 256 bits. Finally, Blowfish, created by Bruce Schneier in 1993, offers a variable key length and was designed to be free of patents and restrictions.

Generalizations

Block ciphers can be adjusted in special ways to work with different types of data. One version, called a "tweakable" block cipher, uses an extra piece of information known as a tweak along with the usual data and key. This tweak helps change how the cipher works, allowing for new ways to protect information, especially in storing data on computers.

Another idea is called format-preserving encryption. Normally, block ciphers work with binary code—strings of zeros and ones. But sometimes, we need to encrypt numbers so they stay as numbers. For example, we might want to keep a credit card number looking like a number even after it’s encrypted. This type of encryption changes the rules so that the encrypted data keeps the same format as the original, like staying a number or a letter code.

Main article: Format-preserving encryption

Relation to other cryptographic primitives

Block ciphers are important tools in making other security methods. They can help create things like stream ciphers, which are used to protect data bit by bit. They can also be used to build special codes called cryptographic hash functions that help check if data has been changed.

Block ciphers can even help make random number generators and secure ways to check messages. All these tools help keep information safe when it is sent or stored.