Block and Stream Ciphers

Cryptography is the science of using codes and ciphers to protect messages. Encryption is encoding messages with the intent of only allowing the intended recipient to understand the meaning of the message. It is a two way function (you need to be able to undo whatever scrambling you’ve done to the message), often used to protect data in transit.

Today, commonly used algorithms for encryption can be broken down into two basic types — symmetric and asymmetric. Symmetric algorithms are also known as ‘secret key’ algorithms, and asymmetric algorithms are known as ‘public key’ algorithms. The key difference between the two is that symmetric algorithms use the same key to encode and decode, while asymmetric algorithms use different keys for encryption and decryption.

For a general overview of cryptography and the difference between symmetric and asymmetric ciphers, check out this article.

What principles are important in developing ciphers?

Kerckhoff's principle states that a cryptographic system should be secure, even if all the details (other than the key) are known publicly. This message was later re-written by Claude Shannon as 'The enemy knows the system.' Essentially, a very well designed system should be able to send secret messages even if an attacker can encrypt and decrypt their own messages using the same algorithm (with a different key). The security of the encrypted message should depend entirely on the key.

Additionally, in order to hinder statistical analysis (attempts to break an encryption algorithm), a good cryptographic system should employ the principles of confusion and diffusion.

Confusion requires that the key does not relate to the ciphertext in a simple manner. Essentially each character of the ciphertext should depend on multiple parts of the key.  The goal is to make it very difficult for an attacker to determine the key from the ciphertext.

Diffusion means that if a single character of the plaintext is changed, then several characters of the ciphertext should change, and if a single character of the ciphertext is changed, then several characters of the plaintext should change. The goal is that the relationship between the ciphertext and the plaintext is hidden. No diffusion is perfect (all will have some patterns), but the best diffusion scatters patterns widely, ideally scrambling several patterns together, making them harder to spot for an attacker, and requiring them to have more data in order to mount a successful attack.

Further Reading: A Mathematical Theory of Cryptography

What are block and stream ciphers?

Both block and stream ciphers are symmetric key ciphers. Block ciphers convert the plaintext to ciphertext block by block while stream ciphers convert one byte at a time. Most modern symmetric algorithms are block ciphers, though the block sizes vary (such as DES (64 bits), AES (128, 192, and 256 bits), etc.).

Why use a stream cipher?

Stream encryption is faster (linear in time) and constant in space. They're also unlikely to propagate errors, as an error in one byte's translation is unlikely to impact the next.

However, there's little diffusion as one plaintext symbol is directly translated to one ciphertext symbol. This also makes the ciphertext susceptible to insertions or modifications. If an attacker is able to break the algorithm, they may be able to insert text which looks authentic.

A stream cipher is typically used when the amount of plaintext is unknown (like audio or video streaming), or when extreme performance is important (ex. very high speed connections, or for devices which need to be very efficient and compact, like smart cards).

A stream cipher works by generating a series of pseudorandom bytes which depend on the key (for any given key, the series of bytes is the same for encryption and decryption). Different keys will produce different strings of bytes. In order to encrypt data the plaintext bytes are XORed with the string of pseudorandom bytes. To decrypt, the ciphertext is XORed with the same string in order to see the plaintext.

Why use a block cipher?

A block cipher has high diffusion (information from one plaintext symbol is spread into several cipher-text symbols). It is also fairly difficult for an attacker to insert symbols without detection, because it can't be easily inserted into the middle of a block.

However, it is slower than a stream cipher (an entire block needs to be transmitted before encryption/decryption can happen) and if an error does occur, it can propagate throughout the block, corrupting the entire section.

Block ciphers are commonly used when the transmission size is known - such as in file transfer. In order to encrypt data which is longer than a single block, there are several 'modes' which have been developed. These describe how to apply the single block principles to longer messages.

What are the commonly used modes of block ciphers?

There are 5 confidentiality modes for block ciphers. Some of these modes require an initialization vector (IV) in order to function.

Initialization Vector (IV): An IV is essentially just another input (in addition to the plaintext and the key) used to create ciphertext. It's a data block, used by several modes of block ciphers to randomize encryption so that different cipher text is created even if the same plain text is repeatedly encrypted. It usually does not need to be secret, though it cannot be re-used. Ideally, it should be random, unpredictable, and single-use. Two of the same message encrypted with the same key, but different IVs will result in different ciphertext, making an attacker's job more difficult.

Electronic Code Book Mode (ECB): There is a fixed mapping between input blocks of plaintext and output blocks of ciphertext (essentially like an actual code book where ciphertext words directly relate to plaintext words). The cipher function is applied independently to each block of plaintext to encrypt it (and the inverse function is applied to each block of ciphertext to decrypt it). This means that multiple blocks can be encrypted and decrypted in parallel (since they don't depend on each other), speeding up the process.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

For this mode to work correctly, either the message length needs to be a multiple of the block size or you need to use padding for the length condition to be met. Padding is essentially extra data added on in order to ensure that the block size is met. With this mode, given the same key, the same plaintext block will always result in the same ciphertext block. This quality makes it relatively easy to attack, meaning that this mode is less commonly used for sensitive information (in fact ECB should not be used).

Cipher Block Chaining Mode (CBC): This mode 'chains' or combines new plaintext blocks with the previous ciphertext block when encrypting them. This requires using an IV with the first plaintext block. It doesn't need to be secret, but it needs to be unpredictable.

The first ciphertext block is created by exclusive or-ing (XORing) the first block of plaintext with the IV. The IV is sent separately as a short message using ECB Mode. Then the encryption algorithm is applied to the block, creating the first block of ciphertext. This block is then XOR-ed with the second plaintext block and the encryption algorithm is applied to produce the second ciphertext block, and so on until the end of the message.

In order to decrypt the message, the reverse is done - the inverse of the encryption algorithm is applied to the first ciphertext block and then the block is XORed with the IV to obtain the first plaintext block. Then the inverse of the encryption algorithm is applied to the second ciphertext block and the block is XORed with the first ciphertext block to obtain the second plaintext block. This process continues until the message is decrypted.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

Because each input block (except the first) relies on the previous block to be encrypted, encryption cannot be done in parallel. However, since the decryption requires XORing with the ciphertext blocks (immediately available), it can be done in parallel. CBC is one of the most commonly used modes.

Similarly to ECB, for this mode to work correctly, either the message length needs to be a multiple of the block size or you need to use padding for the length condition to be met.

Cipher Feedback Mode (CFB): CFB is similar to CBC, but instead of using the entire previous ciphertext block to compute the next block, CFB uses a fraction of the previous block.

  1. It starts with an IV of the same block size as expected by the block cipher, which is encrypted with the encryption algorithm.
  2. s bytes from this output are retained (significant bytes) and XORed with s bytes of plaintext which need to be transmitted.
  3. Then, the IV is shifted s bytes to the left, inserting the ciphertext bytes produced by step 2 as the righthand bytes (IV stays the same length).
  4. Repeat.

To decrypt a message, the IV is the first block and each following block is formed by performing step 3 above and applying the encryption algorithm to form blocks. s bites are then XORed with the corresponding ciphertext to reveal the plaintext.

Within CFB, the encryption system processes s < b plaintext bits at a time, even though the algorithm itself carries out b-bits to b-bits transformation. This means that s can be any number, including 1 byte and CFP can functionally operate as a stream cipher.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

Unfortunately, this means that it can propagate errors downstream - if a byte is received with an error, when it is used to decrypt the first byte, it will produce an erroneous decryption and it will then cause downstream errors when it is fed back into the decryption of the next byte.

Like CBC, when encrypting, the input to each round relies on the result of the previous round, meaning that encryption cannot be done in parallel, though decryption can be performed in parallel if the input blocks are first created from the IV and ciphertext.

Output Feedback (OFB): OFB is similar to CFB, but instead of processing s < b bits into a b-bits to b-bits transformation, it processes s bits directly. Similarly to CFB, OFB can be functionally used as a stream cipher.

OFB requires that the IV be a unique nonce (number used once) for each execution with a given key.

First, the IV is encrypted with the encryption algorithm, producing an output block. This is then XORed with the first plaintext block, producing the first ciphertext block. The first output block is then encrypted with the encryption algorithm to produce the second output block. This is then XORed with the second plaintext block to produce the second ciphertext block. This is then repeated for the length of the message.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

When decrypting, the IV is encrypted with the encryption algorithm, producing an output block. This is then XORed with the first ciphertext block, recovering the first plaintext block. The first output block is then encrypted with the encryption algorithm to produce the second output block. This is then XORed with the second ciphertext block to recover the second plaintext block. This is then repeated for the length of the message.

Because the output blocks for decryption are locally generated, OFB is more resistant to transmission errors than CFB.

Counter (CTR): CTR applies the encryption algorithm to a set of unique input blocks (counters) in order to produce outputs which are XORed with the plaintext to produce ciphertext.

The first counter is encrypted with the encryption algorithm, then the resulting output is XORed with the first plaintext block to produce the first ciphertext block. This is repeated for each block (with a new counter - counters must be unique across all messages encrypted using a single key). If the final block is a partial block of s bytes, the most significant bits, s, of the output block are used for the XOR, while the b - s bytes of the output block are discarded.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

The decryption follows the same pattern - the counter is encrypted with the encryption algorithm, then the resulting output is XORed with the corresponding ciphertext block to produce the plaintext block. If the final block is a partial block of s bytes, the most significant bits, s, of the output block are used for the XOR, while the b - s bytes of the output block are discarded.

CTR has been shown to be at least as secure as the other four modes, while also being able to be executed in parallel (both encryption and decryption), meaning that it is very fast. Each block can be recovered independently if its counter block can be determined and the encryption can be applied to the counters in advance of receiving the plaintext or ciphertext (if memory is no constraint).

Further Reading: NIST Recommendation for Block Cipher Modes of Operation

How do attackers attempt to break ciphers?

There are a number of techniques attackers use, but they broadly fall into the following categories of attack, based on information required to carry it out. These aren't an exclusive list (there are other attacks such side channel attacks), but many of the most common fall into one of these categories.

Known Ciphertext: An attacker has some ciphertext, but does not know what plaintext was used to generate this ciphertext. The attacker does not get to choose which ciphertext they have and they cannot obtain/produce more. This is the easiest type of attack to try, since it's easiest to eavesdrop on an encrypted conversation (since presumably the people having the conversation are using strong encryption and aren't as worried about eavesdroppers), but the hardest to be successful, as long as the people sending messages used appropriately strong encryption.

For example: David finds an encrypted message (ciphertext) in a dead drop, but has no idea what the message means.

Known Plaintext: An attacker has some plaintext and ciphertext pairs which they didn't choose (so the attacker didn't choose the message that was encrypted, but was able to successfully steal a plaintext message and its associated ciphertext). The attacker cannot obtain/produce more pairs.

For example: David finds an enemy spy's hiding place and interrupts him while he is sending an encrypted message. The spy is silly enough to have fled, leaving both the plaintext message and its associated ciphertext written down.

Chosen Plaintext: An attacker can choose any plaintext and obtain the ciphertext in return (but they can't see the key itself).

This is further broken down into batch chosen plaintext (where the attacker can submit a set of plaintexts and receive the ciphertext, but cannot do so again) and adaptive chosen-plaintext (where the attacker can submit plaintext, receive the ciphertext and submit additional plaintext based on the previous ciphertext.)

For example: One nation-state is eavesdropping on another's encrypted communication and knows they use the same key for all of their encryption. They send a sensitive diplomatic communication to the other nation-state, knowing it will be transmitted via the encrypted channel, thus giving them a chosen plaintext - ciphertext pair.

Chosen Ciphertext: This is the opposite of the last attack, where the attacker can choose any ciphertext and obtain the plaintext in return (but they can't see the key itself).

For example:  David knows an enemy spy is going to send an encrypted message tomorrow, so he replaces the text with his own chosen ciphertext, then spies on the recipient, listening as they read out the plaintext of the message.

Sources/Further Reading:

Show Comments
As seen in: